1632
правки
Изменения
м
Для того, чтобы объектизировать эту задачуПрименяя к этой задаче мультиобъктивизацию, нам необходимо определить нужно разбить её на подзадачи. TSP – является <math>NP</math>-сложной именно потому, что нет хорошего разложения этой задачи.Тем не менее задачу можно разбить на две или больше подтуров, каждый из которых мы можем минимизировать. Представим подтуры в виде двух городов. Тогда наша задача примет вид:
Разобьём задачу таким образом:
* Гладков Л.А., Курейчик В.В., Курейчик В.М. "Генетические алгоритмы. Учебное пособие"
rollbackEdits.php mass rollback
== Введение ==
В данной статье рассматривается многокритериальная оптимизация, её задача. Рассматривается понятие Парето-фронт - множество Парето оптимальных значений. Также рассматривается задача коммивояжера и предлагается алгоритм её решение с помощью генетического алгоритма с "жадной" стратегией.мультиобъективизации
== Задача многокритериальной оптимизации ==
== Задачи ==
====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>\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://en.wikipedia.org/wiki/Multiobjective_optimization Wikipedia: Multiobjective optimization]
* [http://en.wikipedia.org/wiki/Hill_climbing Wikipedia: Hill climbing]
