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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Источники)
(→‎Задача многокритериальной оптимизации)
Строка 5: Строка 5:
  
 
== Задача многокритериальной оптимизации ==
 
== Задача многокритериальной оптимизации ==
−
Задача многокритериальной оптимизации формулируется следующим образом:
+
=== Постановка задачи ===
−
: <math>\min\limits_{\vec{x}}\{f_1(\vec{x}), f_2(\vec x), \dots, f_k(\vec x)\},</math>
+
{{Определение
−
: <math>\vec x \in S</math>
+
|definition=
−
где <math>f_i: R^n \to R</math> это <math>k</math> (<math>k\ge 2</math>) ''целевых функций''. Векторы решений <math>\vec x = (x_1, x_2, \dots, x_n)^T</math> Относятся к области определения <math>S</math>.
+
'''Задача многокритериальной оптимизации:'''
 +
:<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> множество Парето оптимальных значений.
 +
=== Множество Парето оптимальных значений ===
 +
{{Определение
 +
|definition=
 +
''' Множество Парето оптимальных значений: '''
 +
:<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) > f_i(x^*)))</math>
 +
}}
 +
Выражение <math>x \succ x^*</math> означает, что <math>x</math> ''доминирует над'' <math>x^*</math>.
 +
Решения в Парето оптимальном множестве также являются эффективными или допустимыми.
  
−
Задача многокритериальной оптимизации состоит в поиске вектора целевых переменных, удовлетворяющего наложенным ограничениям и оптимизирующего векторную функцию, элементы которой соответствуют целевым функциям.
+
{{Определение
 +
|definition=
 +
Для двух решений <math>x</math> и <math>x'</math> говорят <math>x \sim x'</math> тогда и только тогда, когда <math>\exists i \in 1..K \colon f_i(x) > f_i(x') \land \exists j \in 1..K, j \ne i \colon f_j(x') > f_j(x)</math> - такую пару решений называют '''несравнимой'''
 +
}}
  
 
== Критерий оптимальности ==
 
== Критерий оптимальности ==

Версия 01:47, 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] - такую пару решений называют несравнимой


Критерий оптимальности

Перечислим основные критерии оптимальности

Критерий Парето

Вектор решения [math]\vec x\in S[/math] - оптимальный по Парето, если [math]\not\exists\vec x'\in S[/math]:[math]f_i(\vec x) \le f_i(\vec x')[/math] для всех [math]i=1, \dots, k[/math] и [math]f_i(\vec x) \lt f_i(\vec x')[/math] для хотя бы одного [math]i[/math].

[math]P(S)[/math] - множество оптимальных по Парето решений.

Целевой вектор является оптимальным по Парето, если соответствующий ему вектор из области определения также оптимален по Парето.

[math]P(Z)[/math] - множество оптимальных по Парето целевых векторов.

Множество оптимальных по Парето векторов является подмножеством оптимальных по Парето в слабом смысле векторов. Вектор [math]\vec x'\in S[/math] является слабым оптимумом по Парето тогда, когда не существует вектора [math]\vec x\in S[/math] такого, что [math]f_i(\vec x) \lt f_i(\vec x')[/math] для всех [math]i=1, 2, \dots, k[/math].

Множество оптимальных по Парето решений также называют Парето-фронтом.

Парето-фронт не может быть вычислен за полиномиальное время

Лексикографический порядок

Если одни целевые функции важнее других, критерий оптимальности можно определить по лексикографическому порядку.

Отношение лексикографического порядка [math]\lt _{\mathrm{lex}}[/math] между векторами [math]\vec a[/math] и [math]\vec b[/math] выполняется, если [math]a_q \lt b_q[/math], где [math]q = min \left\{k : a_k \neq b_k\right\}[/math]. То есть, первая [math]q[/math] компонента вектора [math]\vec a[/math] меньше компоненты вектора [math]\vec b[/math], а компоненты [math]q+1[/math] — уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.

Вектор [math]\vec x \in X[/math] является лексикографическим решением, если не существует вектора [math]\vec x' \in X[/math], такого, что [math]f(\vec x') \lt _{\mathrm{lex}} f(\vec x)[/math].

Поскольку отношение лексикографического порядка является линейным, можно доказать, что вектор [math]\vec x[/math] является лексикографическим решением, если для всех [math]\vec x' \in X[/math] выполняется:

[math]\vec f(\vec x) \lt _{\mathrm{lex}} \vec f(\vec x').[/math]

Получение оптимальных по Парето решений

Для получения оптимальных по Парето решений используют методы скаляризации. Целевую функцию задачи многокритериальной оптимизации превращают в функцию со скалярным значением.

Функция скаляризации должна удовлетворять следующим условиям.

Пусть [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 ) \lt F (\vec y^2),[/math]

тогда решение [math]\vec x^0[/math], что минимизирует [math]F[/math] до [math]X[/math], является решением по Парето. Если [math]F[/math] сохраняет отношение порядка [math]\lt [/math] в [math]\vec y[/math], то есть, если для произвольных [math]\vec y^1, \vec y^2 \in \vec f(X)[/math] выполняется:

[math]\vec y^1 \lt \vec y^2 \implies F (\vec y^1 ) \lt 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]\lt [/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] - компромиссное решение, будет постоянна для всех критериев.

Описание алгоритма

  1. Задаем вектор предпочтений [math]p=(p_1,p_2,\dots,p_k)[/math];
  2. Заменяем все критерии одним [math]s \rightarrow min[/math];
  3. К системе ограничений добавляем неравенства [math]p_iw_i(x)\leq s[/math] для каждого из критериев, где [math]p_i[/math] - вес нормализованного критерия [math]w_i[/math];
  4. Решаем полученную однокритериальную задачу симплекс-методом

Источники

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