Решение задачи коммивояжера с помощью генетического алгоритма

На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов, а также алгоритм муравьиной колонии¹.

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

Выясним, что можно считать решением задачи коммивояжера. Очевидно, что каким-либо решением будет любой маршрут между городами, удовлетворяющий следующим условиям: он пересекает все без исключений города и не один не пересекает больше одного раза. Закодировать такой маршрут можно в виде последовательности номеров городов, начиная с самого первого, в конце последовательности номер Алгоритм муравьиной колонии — один из эффективных полиномиальных алгоритмов для нахождения приближенных решений задачи коммивояжера, а также аналогичных задач поиска маршрутов на графах. Суть подхода заключается в анализе и использовании модели поведения муравьев, ищущих пути от колонии к источнику питания и представляет собой мета эвристическую оптимизацию предпоследнего города, так как маршрут замкнут и последним будет город, с которого он начинался. Очевидно, что в этой последовательности не будет повторяющихся значений.

Пусть для простоты примера количество городов N = 8, тогда одной из возможных последовательностей городов будет путь, изображенный на рис. 2.3.1.

Рисунок 2.3.1. — Пример маршрута коммивояжера при обходе 8 городов.

Закодируем города числами от 1 до 8. Тогда тот же самый путь примет вид:

Теперь нам нужно представить решение в виде хромосомы. Выше мы уже закодировали решение в виде последовательности номеров городов, теперь осталось перекодировать ее хромосому. Для определенности будем считать, что мы кодируем в хромосому в виде битового вектора. Очевидно, что длина гена в битах в хромосоме будет равна: а= log_2.

Для нашего примера а= log₂ 8 = 3, то есть для кодирования одного гена понадобиться 3 бита. Кодируем последовательность с помощью двоичного кодирования (табл. 2.3.1):

Таблица 2.3.1 — Кодирование последовательности городов с помощью двоичного кодирования.

Однако представив решение таким образом, мы не учли несколько существенных факторов:

• 1. при случайной генерации начальной популяции может возникнуть хромосома, в которой будут повторяющиеся значения генов:
• 000 000 010 011 100 101 110 010.
• 2. хромосомы с повторяющимися генами может дать кроссинговер или мутация.

Есть несколько способов решения этого недостатка кодирования, но все они ведут к излишнему потреблению вычислительных ресурсов, т.к. надо дополнительно проверять хромосомы. Один из способов — проверять на повторяющиеся значения внутри функции приспособленности, и, встретив такие, заменять их на те значения, которых нет в хромосоме. Второй способ — ничего не проверять, а присвоить таким хромосомам очень низкое значение функции приспособленности, но в этом случае генетический алгоритм начинает крайне неэффективно работать.

Вообще говоря, для генетических алгоритмов очень важен вопрос кодирования решений в последовательность генов. От того, насколько оно удачно, зависит качество работы алгоритма. Самое главное, и обязательное, требование к кодированию — хромосома должна однозначно представлять некоторое решение, чтобы не было возможности трактовать одну и ту же хромосому по-разному. Желательно, чтобы хромосомы занимали как можно меньше бит, были короче. Так же важным условием является простота кодирования. От этого зависит скорость работы.

После кодирования запускается генетический алгоритм с желаемыми параметрами.