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>P(S)</math> - множество оптимальных по Парето решений.
Целевой вектор является оптимальным по Парето=== Hill-Climbers ==={{Определение |definition='''Hill-Climbers''' – Итеративный алгоритм, если соответствующий ему вектор из области определения также оптимален по Паретокоторый начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены}}
<math>P(Z)</math> - множество оптимальных по Парето целевых векторов.
Множество оптимальных по Парето векторов является подмножеством оптимальных по Парето в слабом смысле векторов. Вектор {||''Initialization:''||<math>P \leftarrow \vec xemptyset </math><br/>'''Init_pop'''<math>(P)</math>|-|''Main Loop:''||<math>x_1 \in Sleftarrow </math>'''Rand_mem'''<math>(P)</math> является слабым оптимумом по Парето тогда, когда не существует вектора <math>x'_2 \vec leftarrow </math>'''Rand_mem'''<math>(P)</math><br/><math>x'_1 \leftarrow </math>'''Mutate'''<math>(P)</math>,<math>x_2 \in Sleftarrow </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>f_i(\vec x_1,x'_2) < f_i/math><br/>'''if''' <math>f(x'_1) > f(x_1)</math><br/>: <math>P \leftarrow P \vec cup x'_1 \setminus x_1</math><br/>'''if''' <math>f(x'_2) > f(x_2)</math> для всех <br/>: <math>i=1, 2, P \leftarrow P \cup x'_2 \dots, ksetminus x_2</math>|-|''Termination:''||'''return Best'''<math>(P)</math>.|}
Множество оптимальных по Парето решений также называют Парето== Задачи ======Hierarchical-фронтомif-and-only-if function===='''H-IIF''' – предназначена для моделирования проблемы с блочной структурой, каждый блок которой строго связан с остальными блоками.
Парето-фронт не может быть вычислен за полиномиальное время
Отношение лексикографического порядка где <math><_{\mathrm{lex}}B</math> между векторами – блок бит <math>\vec a</math> и <math>\vec b</math> выполняется{b_1, если <math>a_q < b_q</math>b_2, где <math>q = min \left\{k : a_k \neq b_k\rightdots,b_n \}</math>. То есть, первая <math>q</math> компонента вектора <math>\vec a</math> меньше компоненты вектора <math>\vec b|B|</math>– размер блока, а компоненты <math>q+1B_L, B_R</math> — уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным– левая и правая часть блока соответственно.
Вектор <math>\vec x \in X</math> является лексикографическим решениемПрименяя к этой задаче мультиобъективизацию, если не существует вектора разобьём задачу <math>\vec x' \in Xf</math>, такого, что на <math>f(\vec x') <_{\mathrm{lex}} f(\vec x)k</math>-задач.
Поскольку отношение лексикографического порядка является линейнымПредставим, можно доказать, что вектор <math>\vec x</math> является лексикографическим решением, если для всех как будет выглядеть <math>\vec x' \in X</math> выполняется:: <math>\vec f(\vec xB) <_{\mathrm{lex}} \vec f(\vec x').</math>:
Функция скаляризации должна удовлетворять следующим условиямгде <math>f_0(x)</math> – первая цель; <math>f_0(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 ) < 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 TSP),</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^0NP</math> является решением по Парето-сложных задач.Формулируется задача следующим образом:
'''Недостатки:''' невозможность охватить все оптимальные по Парето точки из множества ПаретоПрименяя к этой задаче мультиобъктивизацию, нужно разбить её на подзадачи. TSP – является <math>NP</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_ia</math> - вес нормализованного критерия и <math>w_ib</math>– два города, то величина указанных ''априори''. Если <math>p_iw_i\pi (x_aa)=s</math>, где <math>x_0\pi (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_ia</math> - вес нормализованного критерия и <math>w_ib</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 ==
Суть метода мульти-объективизации заключается в разбитии сложной задачи с одной целевой функцией на несколько подзадач, найти для каждой подзадачи решение и выбрать оптимальное решение.
== Критерий оптимальности Алгоритмы ==Перечислим основные критерии оптимальности=== Критерий Парето ===Вектор решения <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>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>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>C=== Метод взвешенных множителей ===\{c_1,c_2,\dots,c_N\} </math> – множество городов и для каждой пары <math>\{c_i,c_j\}</math> задано расстояние. Наша цель – найти цепь из городов, минимизирующую величину:: <math>F_1\sum^{N-1}_{i=1} d(C_{\vec fpi(i)},C_{\vec xpi(i+1)}) = w_1 f_1 +d(C_{\vec xpi(N) + },C_{\dots + w_r f_r pi(\vec x1)}).</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>,
== Источники ==
* [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]
