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