4.1.2 Задача о коммивояжере

Задача коммивояжера является классической оптимизационной задачей, которая формулируется следующим образом: дано множество, включающее п городов и матрица расстояний между ними (или стоимостей переезда – в зависимости от интерпретации). Коммивояжеру необходимо объехать все города по кратчайшему пути (или с наименьшими затратами на поездку). Причем в каждом городе он должен побывать один раз и вернуться в исходный город.

Для решения предлагается следующая задача: имеется пять телекоммуникационных станций (ТС), стоимость переезда между которыми представлена матрицей (таблица 4.1):

Таблица 4.1 – Матрица стоимостей проезда

ТС	1	2	3	4	5
1	0	2	3	4	4
2	2	0	1	2	5
3	3	1	0	1	2
4	4	2	1	0	1
5	4	5	2	1	0

Решение представим в виде перестановки чисел от 1 до 5, отображающей последовательность посещения ТС; значение целевой функции будет равно стоимости всей поездки, вычисленной на основе вышеприведенной матрицы. Целью решения алгоритма является поиск минимума целевой функции.

Выберем случайным образом два варианта маршрута M и рассчитаем затраты S(M) по каждому из вариантов:

1. M₁=<1,4,2,5,3>, затраты S(M₁)=4+2+5+2+4=17;

2. M₂=<1,2,3,4,5>, затраты S(M₂)=2+1+1+1+4=9.

Маршрут M₂ более выгоден, однако может не являться оптимальным из всех возможных.

Разработаны различные модификации операции скрещивания для поиска минимума целевой функции, такие как, например, оператор Грефестета [6, стр.165].

Воспользуемся данным оператором для поиска пути с наименьшими затратами (см. рис. 4.4).

Рис. 4.4 – Иллюстрация работы оператора Грефестета

Таким образом, получили путь M=<1,2,3,4,5>.

4.2 Решение задачи о коммивояжере в GeneHunter

Задача о коммивояжере может быть решена с использованием программного средства, например GeneHunter (см. рис. 4.5). Коммивояжер должен совершить замкнутый маршрут через заданное количество городов. Все города связаны между собой дорогами, и каждый город коммивояжер должен посетить только один раз. GeneHunter решает эту задачу, выбирая порядок посещения городов и минимизируя длину маршрута.

Рис. 4.5 – Решение задачи о коммивояжере в GeneHunter

Задаются следующие параметры:

1. параметры популяции (количество индивидуумов);

2. параметры эволюции:

   • вероятность скрещивания p_c (случайный способ объединения хромосом из родительской популяции в пары);

   • вероятность мутации p_m (вероятность изменения значения гена в хромосоме на противоположное);

   • степень обновления (обновление исходной популяции путем создания новых особей и уничтожения «бесперспективных», не удовлетворяющих критерию целевой функции);

   • стратегия элитизма заключается в том, что особи с наибольшей приспособленностью гарантированно переходят в новую популяцию.