Задача многокритериальной оптимизации. Multiobjectivization — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Критерий оптимальности)
(→‎Получение оптимальных по Парето решений)
Строка 28: Строка 28:
 
}}
 
}}
  
−
== Получение оптимальных по Парето решений ==
 
−
Для получения оптимальных по Парето решений используют методы скаляризации. Целевую функцию задачи многокритериальной оптимизации  превращают в функцию со скалярным значением.
 
−
 
−
Функция скаляризации должна удовлетворять следующим условиям.
 
−
 
−
Пусть <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://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/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]
 
* [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/3/p1213.pdf Friedrich T., Neumann F. Foundations of Evolutionary Multi-Objective Optimization]

Версия 01:48, 19 июня 2012

Определение

Мультикритериальная оптимизация - это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.


Задача многокритериальной оптимизации

Постановка задачи

Определение:
Задача многокритериальной оптимизации:
[math]maximize \{f(x) = (f_1(x),\dots,f_K(x))\}[/math]
[math] x \in X[/math]
где [math] f(x) : X \rightarrow R^K[/math] - целевая вектор-функция, где [math]K \ge 2[/math]

Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество [math]X^* \subseteq X [/math] множество Парето оптимальных значений.

Множество Парето оптимальных значений

Определение:
Множество Парето оптимальных значений:
[math]\forall x^* \in X^* \not\exists x \in X [/math]:[math]x \succ x^*[/math], где [math]x \succ x^* \Leftrightarrow (\forall i \in 1..K, (f_i(x) \ge f_i(x^*))\land (\exists i \in 1..K, f_i(x) \gt f_i(x^*)))[/math]

Выражение [math]x \succ x^*[/math] означает, что [math]x[/math] доминирует над [math]x^*[/math]. Решения в Парето оптимальном множестве также являются эффективными или допустимыми.


Определение:
Для двух решений [math]x[/math] и [math]x'[/math] говорят [math]x \sim x'[/math] тогда и только тогда, когда [math]\exists i \in 1..K \colon f_i(x) \gt f_i(x') \land \exists j \in 1..K, j \ne i \colon f_j(x') \gt f_j(x)[/math] - такую пару решений называют несравнимой


Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_многокритериальной_оптимизации._Multiobjectivization&oldid=25697»