1632
правки
Изменения
м
Для того, чтобы объектизировать эту задачуПрименяя к этой задаче мультиобъктивизацию, нам необходимо определить нужно разбить её на подзадачи. TSP - – является <math>NP</math>-сложной именно потому, что нет хорошего разложения этой задачи.Тем не менее задачу можно разбить на две или больше подтуров, каждый из которых мы можем минимизировать. Представим подтуры в виде двух городов. Тогда наша задача примет вид:
Разобьём задачу таким образом:
rollbackEdits.php mass rollback
== Введение ==
В данной статье рассматривается многокритериальная оптимизация, её задача. Рассматривается понятие Парето-фронт - множество Парето оптимальных значений. Также рассматривается задача коммивояжера и предлагается алгоритм её мультиобъективизации
== Задача многокритериальной оптимизации ==
=== Постановка задачи ===
:<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> множество Парето оптимальных значений.
пространства, доминируемая данным решением А. Эта область «замкнута»:
элементы на ее границе также доминируемы А
[[Файл: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 - – Парето фронт]]
Множество Парето оптимальных недоминируемых решений называется '''Парето фронтом.'''
=== Hill-Climbers ===
{{Определение
|definition=
'''Hill-Climbers''' – Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены
}}
{|
|''Initialization:''||<math>P \leftarrow \emptyset </math><br/>'''Init_pop'''<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>
:<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) < \pi (b)</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://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]
