|
|
| Строка 27: |
Строка 27: |
| | Для двух решений <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> - такую пару решений называют '''несравнимой''' | | Для двух решений <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> - такую пару решений называют '''несравнимой''' |
| | }} | | }} |
| − |
| |
| − | == Критерий оптимальности ==
| |
| − | Перечислим основные критерии оптимальности
| |
| − | === Критерий Парето ===
| |
| − | Вектор решения <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) < 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) < f_i(\vec x')</math> для всех <math>i=1, 2, \dots, k</math>.
| |
| − |
| |
| − | Множество оптимальных по Парето решений также называют Парето-фронтом.
| |
| − |
| |
| − | Парето-фронт не может быть вычислен за полиномиальное время
| |
| − |
| |
| − | === Лексикографический порядок ===
| |
| − | Если одни целевые функции важнее других, критерий оптимальности можно определить по лексикографическому порядку.
| |
| − |
| |
| − | Отношение лексикографического порядка <math><_{\mathrm{lex}}</math> между векторами <math>\vec a</math> и <math>\vec b</math> выполняется, если <math>a_q < 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') <_{\mathrm{lex}} f(\vec x)</math>.
| |
| − |
| |
| − | Поскольку отношение лексикографического порядка является линейным, можно доказать, что вектор <math>\vec x</math> является лексикографическим решением, если для всех <math>\vec x' \in X</math> выполняется:
| |
| − | : <math>\vec f(\vec x) <_{\mathrm{lex}} \vec f(\vec x').</math>
| |
| | | | |
| | == Получение оптимальных по Парето решений == | | == Получение оптимальных по Парето решений == |
Версия 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] - такую пару решений называют несравнимой |
Получение оптимальных по Парето решений
Для получения оптимальных по Парето решений используют методы скаляризации. Целевую функцию задачи многокритериальной оптимизации превращают в функцию со скалярным значением.
Функция скаляризации должна удовлетворять следующим условиям.
Пусть [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] - компромиссное решение, будет постоянна для всех критериев.
Описание алгоритма
- Задаем вектор предпочтений [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];
- Решаем полученную однокритериальную задачу симплекс-методом
Источники
