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

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

Что необходимо, чтобы понять эту статью?

Читатель должен быть знаком с генетическими алгоритмами; принципы соответствия, случайное колесное выделение, скрещивание, мутации и так далее. К статье также требуется некоторое очень базовое понимание 2D-векторной математики (расстояние между двумя точками в двух измерениях).

Что необходимо, чтобы реализовать эту статью?

Если вы хотите компилировать код, который шел с этой статьей, вы должны использовать стандартный совместимый компилятор C++. Код будет насколько возможно как "стандарт", но так как он не может быть проверен на каждом компиляторе, некоторые исправления должны быть сделаны к исходному коду для некоторых компиляторов. Если вы не имеете компилятор C++, но все еще хотели бы проверить код, можете попробовать Gcc или Djgpp.

Чтобы понять, что действительно делает код, вам необходим некоторый опыт в объектно-ориентированном программиировании, тогда как программисты C++ и Java не будут иметь никаких трудностей, читая код. Если кто-то желает портировать код на другой язык, тогда действуйте, и это может помочь другим понять то, что происходит внутри алгоритма.

Реализация

Здесь мы попробуем описать главные функции, используемые алгоритмом, чтобы найти кратчайший закрытый путь через группу двумерных позиций.

Так как эта статья не затрагивает класс программирования, попробуем придерживаться простых действий, оставаясь вдалеке от битовых сдвигов и других сложных методов. По этой причине вы заметите несколько "волшебных" чисел. Почти каждая переменная будет сохранена в одном байте, что означает 8 бит. Раз бит может хранить значения 0 или 1, большинство наших переменных будут иметь значения между 0 и 2⁸-1 (255), что означает, что мы будем иметь 2⁸ (256) различных значений, возможных для переменной.

Область поиска

Наша область поиска будет определена как прямоугольная область 256 x 256 вхождений, в пределах от 0 до 255 в обоих направлениях (x,y). Каждая пара (x,y), возможная в этой области, представляет позицию точки.

Затем мы выбираем 256 из этих пар наугад, чтобы населить нашу группу двумерных позиций. Мы индексируем (или надписываем) эти пары от 0 до 255.

Популяция

Наша популяция будет сформирована из 100 строк по 256 генов. Каждый из наших генов в пределах строки представит уникальный индекс, соответствующий паре, выбранной в предыдущем шаге.

Наличие уникальных генов вынудит нас писать другое наследование генов, функции скрещивания и мутации.

Операторы

Функции наследования и скрещивания будут использовать накопитель свободных индексов, из которого используемые индексы будут удалены, чтобы сохранять уникальность переданных индексов.

Функция рулетки - колесного выделения

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

Функция соответствия

Соответствие строки представит строку "как короткий", соединяющую точки, сформированные парами, индексированными по значениям генов от 0 до 255 и наоборот до 0, которые закроют строку. Чтобы получить более высокие значения при меньших значениях длин строк, мы установим соответствие для

n(i) = Значение из (i по модулю 256) гена строки

-->
Vn(i) = Вектор, представляющий n(i) начальную позицию

                    -->
    255        -->      -->
l = S    | ( Vn(i) - Vn(i+1) ) |
    i=0


соответствие = 1 / l

Функция скрещивания

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

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

В нашей задаче географически ближайшие точки дадут лучшее соответствие. Поскольку скрещивание сокращает строку наполовину, очень маловероятно, что информация циклов (типа длина, вычисленная между парами, индексированными в генах 255 и 0) будет сохранена. Так как мы должны восстановить те строки, даем возможность восстановить их от точки, самой далекой от этих двух генов, до точки скрещивания. Что мы делаем - это добавляем гены в Потомка A из Родителя A, начиная от места скрещивания, пока не достигнем головы строки. Теперь заполняем правую сторону строки, запрашивая индексный накопитель с генами Родителя B; если ген все еще свободен, мы устанавливаем его, иначе пропускаем ген и оставляем его пустым, пока не достигнем хвоста строки. Затем случайно заполняем пустые гены индексами, оставшимися в накопителе. Делаем то же самое с Потомком B, но сначала используем Родителя B, затем заполняем левую часть строки генами Родителя A.

Вот стандартный пример того, как должен работать алгоритм (если вы не понимаете его, пожалуйста, обратитесь к исходному коду). Выбираем две случайные строки, Родитель A и Родитель B.

Родитель A
141, 133, 21, ... , 14, 87, 172

Родитель B
2, 127, 221, ... , 47, 122, 251

Мы показываем только 6 из 256 уникальных условий, чтобы упростить пример. Мы выбираем случайное число от 0 до 253 и добавляем к нему 1, чтобы оно стало нашей точкой скрещивания. Это означает, что точка скрещивания может быть только между двумя генами.

Например, позволяет сказать случайное число до 86 (87 = 86 + 1) . Это значит, что Потомок A должен быть составлен точно из 87 генов от Родителя A и приблизительно 169 генов от Родителя B. В противоположность, Потомок B будет иметь точно 169 генов от Родителя B и приблизительно 87 от Родителя A. Очень важно обратить внимание, что, поскольку гены уникальны, есть шансы, что, например, Потомок A получает сначала ген от Родителя A, который должен также быть передан от Родителя B. В этом случае, как заявлено ранее, мы должны оставить ген пустым, пока передача всех свободных генов не закончена. Следующее важное действие состоит в том, чтобы заполнить эти пустые гены всеми оставшимися парами в накопителе.

Чтобы проиллюстрировать этот метод, вот несколько генов вокруг нашей точки скрещивания от Родителя A и Родителя B.

Родитель A
..., 110, 34, 192 | 74, 1, 65, ...

Родитель B
..., 55, 67, 204 | 34, 147, 104, ...

Отсюда мы будем строить Потомка A. Сначала мы передаем все первые 87 генов Родителя A в Потомка A, затем заполняем его генами от Родителя B. Когда мы доходим до места передачи 88-ого гена от Родителя B, мы замечаем, что Родитель A уже передал значение 34, так что мы оставляем 88-ой ген Потомка A пустым. Продолжаем, пока не достигнем хвоста строки.

Во втором проходе все, что мы должны делать - это заполнять промежутки оставшимися индексами, которые все еще не использовались.

Функция мутации

Здесь функция мутации весьма проста. Единственное важное - это обмен двух генов внутри той же строки.

Главный цикл

До главного цикла мы должны сначала инициализировать нашу популяцию. Как заявлено ранее, мы решили использовать популяцию из 100 строк, так что должны создать 100 строк, составленных из случайного списка индексов от 0 до 255. Тогда каждое повторение нашего главного цикла представляет новое поколение. Каждое поколение создает новую популяцию строк и уничтожает старую. Для каждого поколения мы сначала вычисляем соответствие каждой строки. Используя случайное колесное выделение, выбираем двух родителей. Тогда мы проверяем, случается ли скрещивание (оно должно происходить 70 процентов времени). Если это случается, мы скрещиваем родителей для создания двух новых потомков, иначе просто копируем родителей в их потомков без модификаций. С очень низкой вероятностью (скажем, 1 процент) мы применяем мутацию. Вы можете поиграть с этими вероятностями, чтобы увидеть, что алгоритм развивается от фиксированного алгоритма к более случайному.

Таким образом, глобальное соответствие популяции должно увеличиваться после каждого повторения (к кратчайшему уникальному пути). Так как в начале мы не знаем, каким будет этот самый короткий путь, мы должны выполнить зацикливание, пока не будет достигнуто лучшее соответствие для n повторений.

Заключение

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

Автор: Eric Martel,  Перевод: Анжела Семиряд, 10 июня 2003 года