1632
правки
Изменения
м
== Задача многокритериальной оптимизации ==Задача многокритериальной оптимизации формулируется следующим образом:: <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''' – Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены}}
Целевой вектор является оптимальным по Парето, если соответствующий ему вектор из области определения также оптимален по Парето.
Множество оптимальных по Парето векторов является подмножеством оптимальных по Парето в слабом смысле векторов. Вектор <math>\vec x== Задачи ======Hierarchical-if-and-only-if function===='''H-IIF''\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>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><_{\mathrm{lex}}</math> между векторами <math>\vec a</math> и <math>\vec b</math> выполняетсяПрименяя к этой задаче мультиобъективизацию, если разобьём задачу <math>a_q < b_qf</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 xB)</math>.:
Поскольку отношение лексикографического порядка является линейным, можно доказать, что вектор :<math>f(B)= \vec x</math> является лексикографическим решениемbegin{cases}0, если для всех <math>& \mbox{if } |B| = 1 \mbox{ and }b_1 \vec x' neq k, \in X</math> выполняется:mbox{ else}: <math>\vec f(\vec x) <_1,& \mbox{if } |B| = 1 \mathrmmbox{lexand }b_1 = k, \mbox{ else} \vec f\|B|+f_k(B_L)+f_k(B_R),& \mbox{if }(\vec x'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>FNP</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>C=\vec x^0</math>{c_1,c_2, что минимизирует <math>F</math> до <math>X</math>\dots, является решением по Парето.Если <math>F</math> сохраняет отношение порядка <math><</math> в <math>c_N\vec y} </math>, то есть, если – множество городов и для произвольных каждой пары <math>\vec y^1{c_i, c_j\vec y^2 \in \vec f(X)}</math> выполняетсязадано расстояние. Наша цель – найти цепь из городов, минимизирующую величину:: <math>\vec ysum^{N-1}_{i=1 < } d(C_{\vec y^2 pi(i)},C_{\implies F pi(\vec y^i+1 ) < F })+d(C_{\vec y^2 pi(N)},</math>тогда решение <math>\vec x^0</math>, что минимизирует <math>F</math> до <math>X</math>, является ''слабым по Парето''. Если <math>F</math> непрерывна на <math>C_{\vec y</math> и <math>\vec x^0</math> единственная точка минимума <math>F</math> на <math>X</math>, тогда <math>\vec x^0pi(1)})</math> является решением по Парето.
=== Метод взвешенных множителей ===: Применяя к этой задаче мультиобъктивизацию, нужно разбить её на подзадачи. TSP – является <math>F_1(\vec f(\vec x)) = w_1 f_1 (\vec x) + \dots + w_r f_r (\vec x).NP</math>-сложной именно потому, что нет хорошего разложения этой задачи.Тем не менее задачу можно разбить на две или больше подтуров, каждый из которых мы можем минимизировать.
'''НедостаткиПредставим подтуры в виде двух городов. Тогда наша задача примет вид:''' невозможность охватить все оптимальные по Парето точки из множества Парето-фронта.В задачах комбинаторной многокритериальной оптимизации множество целевых значений не является выпуклым, поэтому метод взвешенных сумм не подходит для скаляризации целевых функций для этих задач.
=== Функция скаляризации Чебышева ===: <math>F_minimize\infty {f(\vec fpi,a,b) = (f_1(\pi,a,b),f_2(\vec xpi,a,b))\}</math>::'''where'''<math>f_1(\pi,a,b) = \max_sum^{\pi^{-1}(b)-1\leq }_{i =\leq rpi^{-1} w_i f_i(a)} d(C_{\pi(i)},C_{\vec xpi(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>F_+ d(C_{\inftypi(N)},C_{\pi(1)})</math> является слабым по Парето.,
=== Метод ограничений ===В качестве решения задачи принимают компромиссное решениегде <math>a</math> и <math>b</math> – два города, указанных ''априори''. Если <math>\pi (a) < \pi (b)</math>, меняем их местами.
'''Компромиссное решение''' - эффективное решениеПредполагается, которое обеспечивает одинаковые минимальные взвешенные относительные потери по всем критериям одновременно. Если что <math>p_ia</math> - вес нормализованного критерия и <math>w_ib</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>;
# Решаем полученную однокритериальную задачу симплекс-методом
rollbackEdits.php mass rollback
== Определение Введение ==В данной статье рассматривается многокритериальная оптимизация, её задача. Рассматривается понятие Парето-фронт - множество Парето оптимальных значений. Также рассматривается задача коммивояжера и предлагается алгоритм её мультиобъективизации
== Задача многокритериальной оптимизации ===== Постановка задачи ==={{Определение |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> – целевая вектор- это процесс одновременной оптимизации двух или более конфликтующих функция, где <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 – Доминируемые решения ]] {{Определение |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> – такую пару решений называют '''недоминируемой'''}}На рис. 2 показана граница Парето длявозможных решений в двухкритериальном пространстве[[Файл:Pareto_front.jpg|мини|200px|Рис.2 – Парето фронт]]Множество Парето оптимальных недоминируемых решений называется '''Парето фронтом.''' == Multi-objectivization ==Суть метода мульти-объективизации заключается в заданной области определенияразбитии сложной задачи с одной целевой функцией на несколько подзадач, найти для каждой подзадачи решение и выбрать оптимальное решение.
Для выполнения оптимизации многокритериальной задачи мы должны добавить в целевую функцию новые параметры, либо должны добавить новые целевые функции.
{||''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(Zx'_2) > f(x_2)</math> <br/>: <math>P \leftarrow P \cup x'_2 \setminus x_2</math>|- множество оптимальных по Парето целевых векторов.|''Termination:''||'''return Best'''<math>(P)</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://rainen.ifmowikipedia.ruorg/~tsarevwiki/teachingMultiobjective_optimization Wikipedia: Multiobjective optimization]* [http:/ea-2012/lecturesen.wikipedia.org/3wiki/p1213.pdf Friedrich T., Neumann F. Foundations of Evolutionary Multi-Objective OptimizationHill_climbing Wikipedia: Hill climbing]
