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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Источники)
м (rollbackEdits.php mass rollback)
 
(не показаны 32 промежуточные версии 3 участников)
Строка 1: Строка 1:
−
== Определение ==
+
== Введение ==
 +
В данной статье рассматривается многокритериальная оптимизация, её задача. Рассматривается понятие Парето-фронт - множество Парето оптимальных значений. Также рассматривается задача коммивояжера и предлагается алгоритм её мультиобъективизации
  
−
'''Мультикритериальная оптимизация''' - это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.
+
== Задача многокритериальной оптимизации ==
 +
=== Постановка задачи ===
 +
{{Определение
 +
|definition=
 +
'''Задача многокритериальной оптимизации:'''  
 +
:<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> &ndash; целевая вектор-функция, где <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>.
 +
 
 +
Говорят,  что <math>x</math> ''доминирует над'' <math>x^*</math>. по
 +
Парето, если <math>x</math> не хуже <math>x^*</math> по всем критериям и хотя бы по одному критерию превосходит <math>x^*</math>.
 +
В таком случае в выборе <math>x^*</math> нет  смысла, т.к. <math>x</math> по всем параметрам не уступает, а по каким-то и превосхожит <math>x^*</math>. Если рассматривать всего
 +
два критерия  то на рис. 1  показана область
 +
пространства,  доминируемая данным решением А.  Эта область  «замкнута»:
 +
элементы на ее границе также доминируемы А
 +
[[Файл:Dogmin points.jpg|мини|200px|Рис.1 &ndash; Доминируемые решения ]]
 +
 
 +
{{Определение
 +
|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> &ndash; такую пару решений называют '''недоминируемой'''
 +
}}
 +
На рис. 2 показана граница Парето для
 +
возможных решений в двухкритериальном пространстве
 +
[[Файл:Pareto_front.jpg|мини|200px|Рис.2 &ndash; Парето фронт]]
 +
Множество Парето оптимальных недоминируемых решений называется '''Парето фронтом.'''
 +
 
 +
== Multi-objectivization ==
 +
Суть метода мульти-объективизации заключается в разбитии сложной задачи с одной целевой функцией на несколько подзадач, найти для каждой подзадачи решение и выбрать оптимальное решение.
  
 +
Для выполнения оптимизации многокритериальной задачи мы должны добавить в целевую функцию новые параметры, либо должны добавить новые целевые функции.
  
−
== Задача многокритериальной оптимизации ==
+
Сложность этой процедуры заключается в разложении проблемы на ряд мелких независимых между собой подпроблем.
−
Задача многокритериальной оптимизации формулируется следующим образом:
 
−
: <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>
 
−
где <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>\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> - множество оптимальных по Парето решений.  
+
=== Hill-Climbers ===
 +
{{Определение
 +
|definition=
 +
'''Hill-Climbers''' &ndash; Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены
 +
}}
  
−
Целевой вектор является оптимальным по Парето, если соответствующий ему вектор из области определения также оптимален по Парето.
 
  
−
<math>P(Z)</math> - множество оптимальных по Парето целевых векторов.
+
{|
 +
|''Initialization:''||<math>P \leftarrow \emptyset </math><br/>'''Init_pop'''<math>(P)</math>
 +
|-
 +
|''Main Loop:''||<math>x_1 \leftarrow </math>'''Rand_mem'''<math>(P)</math>,<math>x'_2 \leftarrow </math>'''Rand_mem'''<math>(P)</math><br/>
 +
<math>x'_1 \leftarrow </math>'''Mutate'''<math>(P)</math>,<math>x_2 \leftarrow </math>'''Mutate'''<math>(P)</math><br/>
 +
'''if'''<math>(H(x_1,x'_1)+H(x_2,x'_2) > H(x_1,x'_2)+H(x_2,x'_1))</math><br/>
 +
:'''Swap'''<math>(x_1,x'_2)</math><br/>
 +
'''if''' <math>f(x'_1) > f(x_1)</math><br/>
 +
: <math>P \leftarrow P \cup x'_1 \setminus x_1</math><br/>
 +
'''if''' <math>f(x'_2) > f(x_2)</math><br/>
 +
: <math>P \leftarrow P \cup x'_2 \setminus x_2</math>
 +
|-
 +
|''Termination:''||'''return Best'''<math>(P)</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>.
+
== Задачи ==
 +
====Hierarchical-if-and-only-if function====
 +
'''H-IIF''' &ndash; предназначена для моделирования проблемы с блочной структурой, каждый блок которой строго связан с остальными блоками.
  
−
Множество оптимальных по Парето решений также называют Парето-фронтом.
 
  
−
Парето-фронт не может быть вычислен за полиномиальное время
+
:<math>
 +
f(B)= \begin{cases}1,& \mbox{if } |B| = 1, \mbox{ else}
 +
\\|B|+f(B_L)+f(B_R),& \mbox{if }(\forall i \{b_i=0\} \mbox{ or } \forall i \{b_i = 1 \})
 +
\\f(B_L) + f(B_R), & \mbox{otherwise}
 +
\end{cases}
 +
</math>,
  
−
=== Лексикографический порядок ===
+
где <math>B</math> &ndash; блок бит <math>\{b_1,b_2,\dots,b_n \}, |B|</math> &ndash; размер блока, а <math>B_L, B_R</math> &ndash; левая и правая часть блока соответственно.
−
Если одни целевые функции важнее других, критерий оптимальности можно определить по лексикографическому порядку.
 
  
−
Отношение лексикографического порядка <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>f</math> на <math>k</math>-задач.
  
−
Вектор <math>\vec x \in X</math> является лексикографическим решением, если не существует вектора <math>\vec x' \in X</math>, такого, что <math>f(\vec x') <_{\mathrm{lex}} f(\vec x)</math>.
+
Представим, как будет выглядеть <math>f(B)</math>:
  
−
Поскольку отношение лексикографического порядка является линейным, можно доказать, что вектор <math>\vec x</math> является лексикографическим решением, если для всех <math>\vec x' \in X</math> выполняется:
+
:<math>
−
: <math>\vec f(\vec x) <_{\mathrm{lex}} \vec f(\vec x').</math>
+
f(B)= \begin{cases}
 +
0, & \mbox{if } |B| = 1 \mbox{ and }b_1 \neq k,  \mbox{ else}
 +
\\1,& \mbox{if } |B| = 1 \mbox{ and }b_1 = k,  \mbox{ else}
 +
\\|B|+f_k(B_L)+f_k(B_R),& \mbox{if }(\forall i \{b_i=k\}),
 +
\\f_k(B_L) + f_k(B_R), & \mbox{otherwise}
 +
\end{cases}
 +
</math>
  
−
== Получение оптимальных по Парето решений ==
+
где <math>f_0(x)</math> &ndash; первая цель; <math>f_0(x)</math> &ndash; вторая цель.
−
Для получения оптимальных по Парето решений используют методы скаляризации. Целевую функцию задачи многокритериальной оптимизации  превращают в функцию со скалярным значением.  
 
  
−
Функция скаляризации должна удовлетворять следующим условиям.
+
Данный подход помогает избежать проблему локальных максимумов (минимумов).
  
−
Пусть <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>
+
Задача коммивояжера (TSP)является наиболее известно из всего класса <math>NP</math>-сложных задач.
 +
Формулируется задача следующим образом:  
  
−
тогда решение <math>\vec x^0</math>, что минимизирует <math>F</math> до <math>X</math>, является решением по Парето.
+
Задано <math>C=\{c_1,c_2,\dots,c_N\} </math> &ndash; множество городов и для каждой пары <math>\{c_i,c_j\}</math> задано расстояние. Наша цель &ndash; найти цепь из городов, минимизирующую величину:
−
Если <math>F</math> сохраняет отношение порядка <math><</math> в <math>\vec y</math>, то есть, если для произвольных <math>\vec y^1, \vec y^2 \in \vec f(X)</math> выполняется:
+
:<math>\sum^{N-1}_{i=1} d(C_{\pi(i)},C_{\pi(i+1)})+d(C_{\pi(N)},C_{\pi(1)})</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> является решением по Парето.
 
  
−
=== Метод взвешенных множителей ===
+
Применяя к этой задаче мультиобъктивизацию, нужно разбить её на подзадачи. TSP &ndash; является <math>NP</math>-сложной именно потому, что нет хорошего разложения этой задачи.
−
: <math>F_1(\vec f(\vec x)) = w_1 f_1 (\vec x) + \dots + w_r f_r (\vec x).</math>
+
Тем не менее задачу можно разбить на две или больше подтуров, каждый из которых мы можем минимизировать.
  
−
'''Недостатки:''' невозможность охватить все оптимальные по Парето точки из множества Парето-фронта.
+
Представим подтуры в виде двух городов. Тогда наша задача примет вид:
−
В задачах комбинаторной многокритериальной оптимизации множество целевых значений не является выпуклым, поэтому метод взвешенных сумм не подходит для скаляризации целевых функций для этих задач.
 
  
−
=== Функция скаляризации Чебышева ===
+
:<math>minimize\{f(\pi,a,b) = (f_1(\pi,a,b),f_2(\pi,a,b))\}</math>
−
: <math>F_\infty (\vec f(\vec x)) = \max_{1\leq i \leq r} w_i f_i(\vec x).</math>
+
::'''where'''<math>f_1(\pi,a,b)=\sum^{\pi^{-1}(b)-1}_{i=\pi^{-1}(a)} d(C_{\pi(i)},C_{\pi(i+1)})</math>
−
Взвешенная функция скаляризации Чебышева сохраняет отношения <math><</math> и поэтому минимум <math>F_\infty</math> является слабым по Парето.
+
::'''and'''  <math>f_2(\pi,a,b)=\sum^{N-1}_{i=\pi^{-1}(b)} d(C_{\pi(i)},C_{\pi(i+1)}) + \sum^{\pi^{-1}(a)-1}_{i=1} d(C_{\pi(i)},C_{\pi(i+1)}) </math> <math>+ d(C_{\pi(N)},C_{\pi(1)})</math>,
  
−
=== Метод ограничений ===
+
где <math>a</math> и <math>b</math> &ndash; два города, указанных ''априори''. Если <math>\pi (a) < \pi (b)</math>, меняем их местами.
−
В качестве решения задачи принимают компромиссное решение.
 
  
−
'''Компромиссное решение''' - эффективное решение, которое обеспечивает одинаковые минимальные взвешенные относительные потери по всем критериям одновременно. Если <math>p_i</math> - вес нормализованного критерия <math>w_i</math>, то величина <math>p_iw_i(x_a)=s</math>, где <math>x_0</math> - компромиссное решение, будет постоянна для всех критериев.
+
Предполагается, что <math>a</math> и <math>b</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/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://en.wikipedia.org/wiki/Multiobjective_optimization Wikipedia: Multiobjective optimization]
 +
* [http://en.wikipedia.org/wiki/Hill_climbing Wikipedia: Hill climbing]

Текущая версия на 19:13, 4 сентября 2022

Введение

В данной статье рассматривается многокритериальная оптимизация, её задача. Рассматривается понятие Парето-фронт - множество Парето оптимальных значений. Также рассматривается задача коммивояжера и предлагается алгоритм её мультиобъективизации

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

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

Определение:
Задача многокритериальной оптимизации:
[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[/math] не хуже [math]x^*[/math] по всем критериям и хотя бы по одному критерию превосходит [math]x^*[/math]. В таком случае в выборе [math]x^*[/math] нет смысла, т.к. [math]x[/math] по всем параметрам не уступает, а по каким-то и превосхожит [math]x^*[/math]. Если рассматривать всего два критерия то на рис. 1 показана область пространства, доминируемая данным решением А. Эта область «замкнута»: элементы на ее границе также доминируемы А

Рис.1 – Доминируемые решения


Определение:
Для двух решений [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] – такую пару решений называют недоминируемой

На рис. 2 показана граница Парето для возможных решений в двухкритериальном пространстве

Рис.2 – Парето фронт

Множество Парето оптимальных недоминируемых решений называется Парето фронтом.

Multi-objectivization

Суть метода мульти-объективизации заключается в разбитии сложной задачи с одной целевой функцией на несколько подзадач, найти для каждой подзадачи решение и выбрать оптимальное решение.

Для выполнения оптимизации многокритериальной задачи мы должны добавить в целевую функцию новые параметры, либо должны добавить новые целевые функции.

Сложность этой процедуры заключается в разложении проблемы на ряд мелких независимых между собой подпроблем.

Алгоритмы

Hill-Climbers

Определение:
Hill-Climbers – Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены


Initialization: [math]P \leftarrow \emptyset [/math]
Init_pop[math](P)[/math]
Main Loop: [math]x_1 \leftarrow [/math]Rand_mem[math](P)[/math],[math]x'_2 \leftarrow [/math]Rand_mem[math](P)[/math]

[math]x'_1 \leftarrow [/math]Mutate[math](P)[/math],[math]x_2 \leftarrow [/math]Mutate[math](P)[/math]
if[math](H(x_1,x'_1)+H(x_2,x'_2) \gt H(x_1,x'_2)+H(x_2,x'_1))[/math]

Swap[math](x_1,x'_2)[/math]

if [math]f(x'_1) \gt f(x_1)[/math]

[math]P \leftarrow P \cup x'_1 \setminus x_1[/math]

if [math]f(x'_2) \gt f(x_2)[/math]

[math]P \leftarrow P \cup x'_2 \setminus x_2[/math]
Termination: return Best[math](P)[/math]

Задачи

Hierarchical-if-and-only-if function

H-IIF – предназначена для моделирования проблемы с блочной структурой, каждый блок которой строго связан с остальными блоками.


[math] f(B)= \begin{cases}1,& \mbox{if } |B| = 1, \mbox{ else} \\|B|+f(B_L)+f(B_R),& \mbox{if }(\forall i \{b_i=0\} \mbox{ or } \forall i \{b_i = 1 \}) \\f(B_L) + f(B_R), & \mbox{otherwise} \end{cases} [/math],

где [math]B[/math] – блок бит [math]\{b_1,b_2,\dots,b_n \}, |B|[/math] – размер блока, а [math]B_L, B_R[/math] – левая и правая часть блока соответственно.

Применяя к этой задаче мультиобъективизацию, разобьём задачу [math]f[/math] на [math]k[/math]-задач.

Представим, как будет выглядеть [math]f(B)[/math]:

[math] f(B)= \begin{cases} 0, & \mbox{if } |B| = 1 \mbox{ and }b_1 \neq k, \mbox{ else} \\1,& \mbox{if } |B| = 1 \mbox{ and }b_1 = k, \mbox{ else} \\|B|+f_k(B_L)+f_k(B_R),& \mbox{if }(\forall i \{b_i=k\}), \\f_k(B_L) + f_k(B_R), & \mbox{otherwise} \end{cases} [/math]

где [math]f_0(x)[/math] – первая цель; [math]f_0(x)[/math] – вторая цель.

Данный подход помогает избежать проблему локальных максимумов (минимумов).

Задача коммивояжера

Задача коммивояжера (TSP)является наиболее известно из всего класса [math]NP[/math]-сложных задач. Формулируется задача следующим образом:

Задано [math]C=\{c_1,c_2,\dots,c_N\} [/math] – множество городов и для каждой пары [math]\{c_i,c_j\}[/math] задано расстояние. Наша цель – найти цепь из городов, минимизирующую величину:

[math]\sum^{N-1}_{i=1} d(C_{\pi(i)},C_{\pi(i+1)})+d(C_{\pi(N)},C_{\pi(1)})[/math]

Применяя к этой задаче мультиобъктивизацию, нужно разбить её на подзадачи. TSP – является [math]NP[/math]-сложной именно потому, что нет хорошего разложения этой задачи. Тем не менее задачу можно разбить на две или больше подтуров, каждый из которых мы можем минимизировать.

Представим подтуры в виде двух городов. Тогда наша задача примет вид:

[math]minimize\{f(\pi,a,b) = (f_1(\pi,a,b),f_2(\pi,a,b))\}[/math]
where[math]f_1(\pi,a,b)=\sum^{\pi^{-1}(b)-1}_{i=\pi^{-1}(a)} d(C_{\pi(i)},C_{\pi(i+1)})[/math]
and [math]f_2(\pi,a,b)=\sum^{N-1}_{i=\pi^{-1}(b)} d(C_{\pi(i)},C_{\pi(i+1)}) + \sum^{\pi^{-1}(a)-1}_{i=1} d(C_{\pi(i)},C_{\pi(i+1)}) [/math] [math]+ d(C_{\pi(N)},C_{\pi(1)})[/math],

где [math]a[/math] и [math]b[/math] – два города, указанных априори. Если [math]\pi (a) \lt \pi (b)[/math], меняем их местами.

Предполагается, что [math]a[/math] и [math]b[/math] выбраны произвольно.

Источники

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