Изменения

Перейти к: навигация, поиск
Получение оптимальных по Парето решений
}}
== Получение оптимальных по Парето решений ==
Для получения оптимальных по Парето решений используют методы скаляризации. Целевую функцию задачи многокритериальной оптимизации превращают в функцию со скалярным значением.
 
Функция скаляризации должна удовлетворять следующим условиям.
 
Пусть <math>F</math> - функция скаляризации. Если для <math> \forall \vec y^1, \vec y^2 \in \vec f(X)</math> выполняется:
: <math>\vec y^1 \le \vec y^2 \implies F (\vec y^1 ) < F (\vec y^2),</math>
 
тогда решение <math>\vec x^0</math>, что минимизирует <math>F</math> до <math>X</math>, является решением по Парето.
Если <math>F</math> сохраняет отношение порядка <math><</math> в <math>\vec y</math>, то есть, если для произвольных <math>\vec y^1, \vec y^2 \in \vec f(X)</math> выполняется:
: <math>\vec y^1 < \vec y^2 \implies F (\vec y^1 ) < F (\vec y^2 ),</math>
тогда решение <math>\vec x^0</math>, что минимизирует <math>F</math> до <math>X</math>, является ''слабым по Парето''. Если <math>F</math> непрерывна на <math>\vec y</math> и <math>\vec x^0</math> единственная точка минимума <math>F</math> на <math>X</math>, тогда <math>\vec x^0</math> является решением по Парето.
 
=== Метод взвешенных множителей ===
: <math>F_1(\vec f(\vec x)) = w_1 f_1 (\vec x) + \dots + w_r f_r (\vec x).</math>
 
'''Недостатки:''' невозможность охватить все оптимальные по Парето точки из множества Парето-фронта.
В задачах комбинаторной многокритериальной оптимизации множество целевых значений не является выпуклым, поэтому метод взвешенных сумм не подходит для скаляризации целевых функций для этих задач.
 
=== Функция скаляризации Чебышева ===
: <math>F_\infty (\vec f(\vec x)) = \max_{1\leq i \leq r} w_i f_i(\vec x).</math>
Взвешенная функция скаляризации Чебышева сохраняет отношения <math><</math> и поэтому минимум <math>F_\infty</math> является слабым по Парето.
 
=== Метод ограничений ===
В качестве решения задачи принимают компромиссное решение.
 
'''Компромиссное решение''' - эффективное решение, которое обеспечивает одинаковые минимальные взвешенные относительные потери по всем критериям одновременно. Если <math>p_i</math> - вес нормализованного критерия <math>w_i</math>, то величина <math>p_iw_i(x_a)=s</math>, где <math>x_0</math> - компромиссное решение, будет постоянна для всех критериев.
 
====Описание алгоритма====
# Задаем вектор предпочтений <math>p=(p_1,p_2,\dots,p_k)</math>;
# Заменяем все критерии одним <math>s \rightarrow min</math>;
# К системе ограничений добавляем неравенства <math>p_iw_i(x)\leq s</math> для каждого из критериев, где <math>p_i</math> - вес нормализованного критерия <math>w_i</math>;
# Решаем полученную однокритериальную задачу симплекс-методом
== Источники ==
* [http://ru.wikipedia.org/wiki/Многокритериальная_оптимизация Википедия: Многокритериальная оптимизация]
* [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/3/multiobjectivization.pdf Knowles J., Watson R., Corne D. Reducing Local Optima in Single-Objective Problems by Multi-objectivization]
* [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/3/p1213.pdf Friedrich T., Neumann F. Foundations of Evolutionary Multi-Objective Optimization]
18
правок

Навигация