Пример решения задачи коммивояжера

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

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

0 4 6 2 9

4 0 3 2 9

6 3 0 5 9

2 2 5 0 8

9 9 9 8 0

Для решения задачи применим следующий генетический алгоритм. Ре­шение представим в виде перестановки чисел от 1 до 5,отображающей последовательность посещения городов. Значение целевой функции бу­дет равно стоимости всей поездки, вычисленной в соответствии с вышеприведенной матрицей. Сразу заметим, что одним из оптимальных реше­ний задачи является последовательность 514235 стоимостью 25.

В качестве оператора отбора будем использовать традиционный опе­ратор, описанный выше. При этом заметим, что чем меньше значение целевой функции, тем лучше, т. е. целью в данном случае является поиск минимума целевой функции.

В качестве оператора скрещивания выберем процеду­ру, похожую на двухточечный оператор скрещивания. Поясним его работу на примере. Пусть есть две родительские перестановки (12345) и (34521). Случайно и равновероятно выбираются две точки разрыва. Для примера возьмем ситуацию, когда первая точка разрыва находится между первым и вторым элементами перестановки, а вторая точка – между четвертым и пя­тым: (1|234|5), (3|452|1). На первом этапе перестановки обмениваются фрагментами, заключенными между точками разрыва: (* | 4 52 | *), (* | 234 | *). На втором этапе вместо звездочек вставляются соответствую­щие числа из исходной родительской перестановки, начиная со второго числа выделенного фрагмента и пропуская уже имеющиеся в новой перестановке числа. В данном случае в первой перестановке (1|234|5) таким начальным числом является 3, за ним идет 4, которое есть в новой перестановке, и мы его пропускаем, также пропускаем число 5, переходим на начало перестановки и выбираем число 1. В итоге вместо (* | 452 | *)получаем (34521) , аналогич­но из (3|452|1) и (* | 234 | *) получаем (52341).

Оператор мутации будет представлять собой случайную перестановку двух чисел в хромосоме, также выбранных случайно по равномерному за­кону. Вероятность мутации 0,01. Размер популяции выберем равным 4.

Исходная популяция представлена в таблице 9.1.

Пусть для скрещивания были выбраны следующие пары: (1, 3) и (2, 4). В результате были получены потомки, представленные в таблице 9.2.

Таблица 9.1

Таблица 9.2

Пусть для потомка (12354) сработал оператор мутации, и обменялись местами числа 2 и 3. В данном случае строка (12354) изменилась и приняла значение (13254). Популяция первого поколения после отсечения худших особей в результате работы оператора редукции приняла вид, представ­ленный в таблице 9.3.

Таблица 9.3

Пусть для получения второго поколения были выбраны следующие пары строк: (1,4) и (2, 3). И в результате были получены потомки, показан­ные в таблице 9.4.

Таблица 9.4

Популяция второго поколения после отсечения худших особей приня­ла вид, показанный в таблице 9.5.

Таблица 9.5

Таким образом, после двух итераций значение целевой функции для лучшего решения изменилось с 29 на 28, среднее значение изменилось с 30,5 до 28,75,а общее качество с 122 до 115. Таким образом, имеем незначи­тельное, но улучшение популяции.