1632
правки
Изменения
м
Для того, чтобы объектизировать эту задачуПрименяя к этой задаче мультиобъктивизацию, нам необходимо определить нужно разбить её на подзадачи. TSP – является <math>NP</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>, то взять случайную вершину из числа не просмотренных. Присвоить полученной вершине значение текущей.# При преждевременном образовании циклов выбирается другой кратчайший путь.# Повторяем пункты 2 и 3 пока не будет просмотрен гамильтонов цикл с квазиминимальной суммарной стоимостью рёберменяем их местами.# Конец работы алгоритма
Для тогоПредполагается, чтобы избежать проблемы локального минимума, в алгоритм вводится модификация:# Предпочтение более невыгодного маршрута с точки зрения заданной целевой функции более выгодному отдается с определенной вероятностьючто <math>a</math> и <math>b</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>
== Источники ==
* [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]
