www.machinelearningmastery.ru

Машинное обучение, нейронные сети, искусственный интеллект
Header decor

Home

Эволюция продавца: полное руководство по генетическому алгоритму для Python

Дата публикации Jul 17, 2018

Черпая вдохновение из естественного отбора, генетические алгоритмы (GA) - это увлекательный подход к решению задач поиска и оптимизации. Пока много написано о ГА (см .:Вота такжеВот), мало что было сделано, чтобы показать пошаговую реализацию GA в Python для более сложных задач. Вот где этот учебник приходит! Следуйте инструкциям, и к концу вы получите полное представление о том, как развернуть GA с нуля.

Введение

Проблема

В этом руководстве мы будем использовать GA, чтобы найти решение проблемы коммивояжера (TSP). TSP описывается следующим образом:

«Учитывая список городов и расстояния между каждой парой городов, каков кратчайший из возможных маршрутов, которые посещают каждый город и возвращаются в исходный город?»

Иллюстрация возможного решения TSP (Автор: Xypron [Public domain], из Wikimedia Commons)

Учитывая это, следует помнить о двух важных правилах:

  1. Каждый город нужно посетить ровно один раз
  2. Мы должны вернуться в стартовый город, поэтому наше общее расстояние должно быть рассчитано соответствующим образом

Подход

Давайте начнем с нескольких определений, перефразированных в контексте TSP:

  • Ген:город (представлен в виде (x, y) координат)
  • Индивидуальный (он же «хромосома»):единый маршрут, удовлетворяющий вышеуказанным условиям
  • Население:набор возможных маршрутов (то есть набор отдельных лиц)
  • Родители:два маршрута, которые объединяются для создания нового маршрута
  • Брачный бассейн:коллекция родителей, которые используются для создания нашего следующего населения (таким образом, создавая маршруты следующего поколения)
  • Фитнес:функция, которая говорит нам, насколько хорош каждый маршрут (в нашем случае, насколько короткое расстояние)
  • Мутация:способ внести изменения в нашу популяцию путем случайного обмена двумя городами на маршруте
  • Элитизм:способ нести лучших людей в следующее поколение

Наша ГА будет действовать в следующих шагах:

1. Создайте население

2. Определить пригодность

3. Выберите брачный пул

4. Порода

5. Мутировать

6.Повторение

Теперь давайте посмотрим на это в действии.

Строим наш генетический алгоритм

Хотя каждая часть нашей GA построена с нуля, мы будем использовать несколько стандартных пакетов, чтобы упростить задачу:

import numpy as np, random, operator, pandas as pd, matplotlib.pyplot as plt

Создайте два класса: Город и Фитнес

Сначала мы создаемCityкласс, который позволит нам создавать и обрабатывать наши города. Это просто наши (x, y) координаты. В классе City мы добавляемdistanceрасчет (с использованием теоремы Пифагора) в строке 6 и более чистый способ вывода городов в виде координат с__repr__в строке 12.

Мы также создадимFitnessучебный класс. В нашем случае мы будем относиться к фитнесу как к обратному расстоянию маршрута. Мы хотим минимизировать расстояние до трассы, поэтому чем больше результат в фитнесе, тем лучше. Исходя из правила № 2, нам нужно начинать и заканчивать в одном и том же месте, поэтому этот дополнительный расчет учитывается в строке 13 расчета расстояния.

Создать население

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

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

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

Определить фитнес

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

Выберите брачный бассейн

Есть несколько вариантов выбора родителей, которые будут использоваться для создания следующего поколения. Наиболее распространенные подходыфитнес пропорциональный выбор(он же «выбор колеса рулетки») илиотбор турниров:

  • Фитнес пропорциональный выбор(версия реализована ниже): пригодность каждого индивида относительно популяции используется для определения вероятности выбора. Думайте об этом как о взвешенной вероятности быть выбранным.
  • Выбор турнира: Определенное количество индивидуумов случайным образом выбирается из популяции, а в группе в качестве первого родителя выбирается человек с наивысшей физической подготовкой. Это повторяется, чтобы выбрать второго родителя.

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

Для ясности, мы создадим пул спаривания в два этапа. Во-первых, мы будем использовать выводrankRoutesопределить, какие маршруты выбрать в нашемselectionфункция. В строках 3–5 мы настраиваем колесо рулетки, вычисляя относительный вес пригодности для каждого человека. В строке 9 мы сравниваем случайное число с этими весами, чтобы выбрать наш пул спаривания. Мы также хотим придерживаться наших лучших маршрутов, поэтому мы вводим элитарность в линию 7. В конечном счете,selectionФункция возвращает список идентификаторов маршрутов, который мы можем использовать для создания пула сопряжения вmatingPoolфункция.

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

разводить

Создав пул спаривания, мы можем создать следующее поколение в процессе под названиемкроссовер(он же «разведение»). Если наши люди были строками 0 и 1, и наши два правила не применялись (например, представьте, что мы решали, включать ли акцию в портфель), мы могли бы просто выбрать точку пересечения и слить две строки вместе, чтобы произвести потомство.

Однако TSP уникален тем, что нам нужно включать все местоположения ровно один раз. Чтобы соблюдать это правило, мы можем использовать специальную функцию разведения под названиемупорядоченный кроссовер, В упорядоченном кроссовере мы случайным образом выбираем подмножество первой родительской строки (см. Строку 12 вbreedниже), а затем заполните оставшуюся часть маршрута генами от второго родителя в том порядке, в котором они появляются, без дублирования каких-либо генов в выбранном подмножестве от первого родителя (см. строку 15 вbreedфункция ниже).

Иллюстрация заказанного кроссовера (кредит:Ли Джейкобсон)

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

Mutate

Мутация выполняет важную функцию в GA, так как она помогает избежать локальной конвергенции путем введения новых маршрутов, которые позволят нам исследовать другие части пространства решений. Как и в случае кроссовера, TSP уделяет особое внимание мутации. Опять же, если бы у нас была хромосома 0 и 1, мутация просто означала бы присвоение низкой вероятности изменения гена от 0 до 1 или наоборот (для продолжения предыдущего примера, акция, которая была включена в портфель потомства, сейчас исключено).

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

Далее мы можем продлитьmutateФункция для запуска через новое население.

Повторение

Мы почти там. Давайте соберем эти кусочки вместе, чтобы создать функцию, которая производит новое поколение. Сначала мы оцениваем маршруты в текущем поколении, используяrankRoutes, Затем мы определяем наших потенциальных родителей, выполняяselectionфункция, которая позволяет нам создавать пул спаривания, используяmatingPoolфункция. Наконец, мы создаем наше новое поколение, используяbreedPopulationфункция, а затем применяя мутацию с помощьюmutatePopulationфункция.

Эволюция в движении

Наконец-то у нас есть все для создания нашей GA! Все, что нам нужно сделать, это создать первоначальную популяцию, и тогда мы сможем пройти через столько поколений, сколько пожелаем. Конечно, мы также хотим увидеть лучший маршрут и насколько мы его улучшили, поэтому мы фиксируем начальное расстояние в строке 3 (помните, что расстояние является обратной величиной от пригодности), конечное расстояние в строке 8 и лучший маршрут в строке 9.

Запуск генетического алгоритма

Со всем на месте решение TSP так же просто, как два шага:

Во-первых, нам нужен список городов для путешествий. Для этой демонстрации мы создадим список из 25 случайных городов (казалось бы, небольшое количество городов, но грубая сила должна была бы протестировать более 300 маршрутов секстиллионов!):

Затем запуск генетического алгоритма представляет собой одну простую строку кода. Здесь искусство встречается с наукой; Вы должны увидеть, какие предположения работают лучше для вас. В этом примере у нас есть 100 особей в каждом поколении, мы сохраняем 20 элитных особей, используем мутацию 1% для данного гена и проходим 500 поколений:

Бонусная функция: сюжет улучшения

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

Запустите GA так же, как и раньше, но теперь, используя только что созданныйgeneticAlgorithmPlotфункция:

Пример вывода из функцииeticAlgorithmPlot

Вывод

Я надеюсь, что это был забавный, практический способ узнать, как построить свой собственный GA. Попробуйте сами и посмотрите, какой короткий путь вы можете получить. Или идите дальше и попробуйте реализовать GA на другом наборе проблем; посмотрим, как бы вы изменилиbreedа такжеmutateфункции для обработки других типов хромосом. Мы просто царапаем поверхность здесь!


Конечные заметки

Вы можете найти сводный блокнотВот,

Ссылки:

Оригинальная статья

Footer decor

© www.machinelearningmastery.ru | Ссылки на оригиналы и авторов сохранены. | map