Авторы: Вильям Кук
Решение задачи коммивояжера c использованием генетических алгоритмов
Перевод: Поправко А.А.

Source of information: Источник статьи

Я разработал решение задачи коммивояжера (TSP) с помощью генетического алгоритма (ГА). В задаче коммивояжера, цель – найти кратчайшее расстояние между N разными городами. Путь, по которому продавец должен пройти называется туром.

Проверка всех вариантов прохода по N городам будет N!. Для расчета 30 туров по городу придется измерить общее расстояние в 2,65 X 10³² различных туров. Предполагая около триллиона операций в секунду, это займет 252.333.390.232.297 лет. Добавление еще одного города вызовет увеличение количеситва расчетов на 31!. Очевидно, что это решение неприемлимо.

Генетический алгоритм может быть использован, чтобы найти решение за гораздо более короткий срок. Хотя он не может найти лучшее решение, он может стать практически идеальным решением для расчета 100 туров по городу менее чем за минуту. Есть несколько основных шагов в решении задачи коммивояжера помощью ГА.

Во-первых, создать группу из многих случайных туры в так называемой популяции. Этот алгоритм использует жадные вычисления для расчета первоначальной популяции, отдавая предпочтение связи городам, которые находятся близко друг к другу.

Во-вторых, выбрать из 2х  лучше (кратчайших) туров родителей в популяции и скомбинировать их, сделать два новых потомка. Надеясь, что эти потомки будут лучше, чем любой из родителей.

С небольшой вероятностью потомки туров мутируют. Это делается, чтобы предотвратить идентичность всех туров в популяции.

Новые потомки туров ребенка заменяют собой длиннейшие туры в популяции. Численность особей в популяции остается неизменной.

Новые туры детей неоднократно создаются до достижения желаемой цели.

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

2 наиболее сложных вопроса, с использованием генетического алгоритма для решения задачи коммивояжера является вопрос кодирования тура и алгоритм кроссовера, который используется, чтобы объединить два тура родителей, для получения потомков тура.

В стандартном генетическом алгоритме, кроссовер обеспечивается случайным выбором позиции в родительской последовательности и обменом частей родителей. В этом примере, точка пересечения - между 3-м и 4-м пунктом списка.

Родитель 1	FAB | ECGD
Родитель 2	DEA | CGBF
Ребенок 1	FAB | CGBF
Ребенок 2	DEA | ECGD

Трудность задачи коммивояжера состоит в том, что в каждый город может быть использован в туре только один раз. Если буквы в приведенном выше примере представляют города, туры-потомки, созданные этим кроссовером, будут считаться недействительными. 1-й ребенок едет в город F и B два раза, и никогда не выйдет в города D или E.

Кодирование не может быть просто списком городов в порядке, как они были посещены. Для этого созданы другие методы кодирования. Хотя эти методы не будут создавать недействительные туры, они не принимают во внимание тот факт, что тур "ABCDEFG"такой же, как "GFEDCBA". Чтобы решить эту проблему должным образом кроссовер алгоритма должен быть сложнее.

Мое решение хранит ссылки в обоих направлениях для каждого тура. В приведенном выше примере о турах, новый родитель 1 будет сохранен как:

Город	Первая вершина	Вторая вершина
A	F	B
B	A	E
C	E	G
D	G	F
E	B	C
F	D	A
G	C	D

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

В конце концов, ГА сделает так, что все решения будут идентичны. Это не является идеальным решением. Если все особи в ГА станут идентичны, ГА не смодет улучшить решение. Есть два способа обойти это. Первый заключается в использовании очень больших начальных размеров популяции, так, что ГА потребуется много времени, чтобы все особи стали идентичны. Второй метод - мутация, когда случайные потомки мутируют, создавая новый уникальный тур.

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

Есть 6 параметров для управления работой генетического алгоритма:

Численность населения - численность населения первоначального числа случайных туров, которые создаются, когда алгоритм начинает работу. Большая численность особей требует больше времени, чтобы найти результат. Меньшее население увеличивается вероятность того, что каждый тур в известной степени будет замещать другой и быть идентичным. Это увеличивает вероятность того, что лучшее решение не будет найдено.

Квартал / Группа Размер - Каждое поколение, это количество туров, случайно выбранное из популяции. 2 лучшие туры родителей. Худшем 2 туров получить заменены детей. Для группы размер, высокое число возрастет вероятность того, что действительно хорошие экскурсии будет выбран в качестве родителей, но он также вызывает много гастролирует никогда не будет использоваться в качестве родителей. Большой размер группы приведет алгоритм работает быстрее, но он не может найти самое лучшее решение.

Мутация% - процент, что каждый ребенок после кроссовер будет проходить мутации Когда тур мутировал, один из городов случайно переехал из одной точки в тур на другой.

# Близлежащих городов - В рамках жадные исходной популяции, А. предпочитают ссылка города, которые находятся близко друг к другу, чтобы сделать первоначальный туров. При создании исходной популяции это число городов, которые считаются близкими.

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

Максимальная поколений - Сколько кроссоверы выполняются до алгоритм завершается.

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

Случайное начальное - Это семена для генератора случайных чисел. Имея фиксированные, а не случайных зерно, то вы можете повторить предыдущие результаты тех пор, пока все остальные параметры те же. Это очень полезно при поиске ошибок в алгоритме.

Город List - загружаемая версия позволяет импортировать списки из города XML файлов. Опять же, при отладке проблем, полезно иметь возможность запускать алгоритм с той же точных параметров.

Начальные значения параметра:

Параметр	Начальное значение
Размер популяции	10,000
Размер групы	5
Мутации	3 %
Количество соседних вершин	5
Коэффициенты соседних городов	90 %

Примечание: Я написал эту программу в 1995 году в прямом C. Туры в популяции были сохранены в массиве в 32 бит Int, где каждый бит указывает на связь. Ex: Если тур [0] = 00000000000001000000010000000000 в двоичном, а затем город 0 подключен к городской 11 и 19. Эта реализация была гораздо быстрее, чем текущий C# версии. Жадную часть - кроссовер может быть выполнен на практике бинарных и на 2 туров. Хотя этот код работает очень быстро, у него много бинарных операций.