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>.
Задача многокритериальной оптимизации состоит в поиске вектора целевых переменных=== Hill-Climbers ==={{Определение |definition='''Hill-Climbers''' – Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, удовлетворяющего наложенным ограничениям алгоритм сохраняет его и оптимизирующего векторную функциюповторяет и повторяет своё выполнение до тех пор, элементы пока лучшие решения не могут быть найдены}} {||''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>|} == Задачи ======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,\vec xdots,c_N\in S} </math> - оптимальный по Парето, если – множество городов и для каждой пары <math>\not\exists\vec x'{c_i,c_j\in S}</math>задано расстояние. Наша цель – найти цепь из городов, минимизирующую величину::<math>f_i\sum^{N-1}_{i=1} d(C_{\vec xpi(i) },C_{\le f_ipi(i+1)})+d(C_{\vec x'pi(N)</math> для всех <math>i=1}, C_{\dots, k</math> и <math>f_ipi(\vec x1) < f_i(\vec x'})</math> для хотя бы одного <math>i</math>.
Целевой вектор является оптимальным по Парето, если соответствующий ему вектор из области определения также оптимален по ПаретоПредставим подтуры в виде двух городов. Тогда наша задача примет вид:
Множество оптимальных по Парето векторов является подмножеством оптимальных по Парето в слабом смысле векторов. Вектор где <math>\vec x'\in Sa</math> является слабым оптимумом по Парето тогда, когда не существует вектора и <math>\vec x\in Sb</math> такого– два города, что указанных ''априори''. Если <math>f_i\pi (\vec xa) < f_i\pi (\vec x'b)</math> для всех <math>i=1, 2, \dots, k</math>меняем их местами.
Множество оптимальных по Парето решений также называют Парето-фронтомПредполагается, что <math>a</math> и <math>b</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://en.wikipedia.org/wiki/Multiobjective_optimization Wikipedia: Multiobjective optimization]* [http://en.wikipedia.org/wiki/Hill_climbing Wikipedia: Hill climbing]
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 ==Суть метода мульти-объективизации заключается в разбитии сложной задачи с одной целевой функцией на несколько подзадач, найти для каждой подзадачи решение и выбрать оптимальное решение. Для выполнения оптимизации многокритериальной задачи мы должны добавить в целевую функцию новые параметры, либо должны добавить новые целевые функции. Сложность этой процедуры заключается в заданной области определенияразложении проблемы на ряд мелких независимых между собой подпроблем.
== Алгоритмы ==
Применяя к этой задаче мультиобъктивизацию, нужно разбить её на подзадачи. TSP – является <math>P(S)NP</math> - множество оптимальных по Парето решенийсложной именно потому, что нет хорошего разложения этой задачи.Тем не менее задачу можно разбить на две или больше подтуров, каждый из которых мы можем минимизировать.
:<math>Pminimize\{f(Z\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>,