Подробное руководство по реализации генетических алгоритмов в вашем коде
Иногда решение проблемы может зависеть от стольких различных и независимых факторов, что написать алгоритм, учитывающий их все, практически невозможно.
Понимание того, когда следует изменить один параметр вместо другого, может потребовать много времени и усилий для исследования.
Вместо этого генетические алгоритмы дают вам возможность найти лучшее решение проблемы «естественным образом», не беспокоясь о параметрах и о том, как они взаимодействуют друг с другом.
Это звучит немного похоже на волшебство, но на самом деле довольно интересно, как они работают, поэтому давайте посмотрим, что представляют собой эти типы алгоритмов и как они могут помочь вам найти решения ваших проблем.
Что такое генетические алгоритмы?
Таким образом, генетические алгоритмы — это способ решения проблем путем имитации (в некоторой степени) того, как размножаются клеточные организмы.
Видите ли, когда чувак и чувак нравятся друг другу до такой степени, что готовы завести ребенка, они, по сути, «смешивают свою ДНК», половина ДНК чувака смешивается с половиной ДНК чувака. Их гены смешиваются, создавая новые, потенциально никогда ранее не встречавшиеся комбинации (по крайней мере, новые в пределах их генеалогического древа), и время от времени некоторые из этих генов мутируют и создают новые комбинации (вот откуда берутся силы мутантов!).
Как перевести все это в алгоритм решения проблем?
"Легкий!" (обратите внимание на кавычки)
Потенциально мы хотим добиться следующего:
- Для данной задачи мы должны закодировать решение в виде потока ДНК, где каждый ген является одним из параметров решения.
- Затем создайте «популяцию» случайных решений.
- Оцените эти случайные решения и присвойте им баллы (назовем это значение «пригодностью»). Чем ближе они к получению желаемого результата, тем лучше будет их пригодность (ваша логика определит, означает ли это, что значение будет выше или ниже).
- Отсортируйте их по пунктам и отбросьте нижнюю половину, они нам не нужны, они «слишком неправильные».
- Теперь возьмите верхнюю половину оставшейся популяции и смешайте ее с другой половиной. Чтобы смешать их, вы берете половину генов одного потенциального решения и смешиваете их с другой половиной другого решения. Это дало бы совершенно новое потенциальное решение (мы будем называть их «потомками»).
- Теперь вернитесь к шагу 3, где у вас будут новые потомки для оценки и сортировки.
Кроме того, если на шаге 5 вы добавите некоторую случайность и «мутируете» некоторые значения перед смешиванием обоих решений, вы можете обнаружить новый появляющийся паттерн, которого изначально не было даже в вашей случайной популяции.
Этот процесс, в идеале, превратит популяцию в набор решений, очень близких к желаемому результату, с надеждой, что одно или несколько потомков обеспечат правильную комбинацию параметров. Такова «теория» того, как это делается, давайте взглянем на некоторые практические сценарии.
Использование генетических алгоритмов
Существует множество различных сценариев, в которых могут пригодиться генетические алгоритмы.
Ключ в том, чтобы найти проблему, для правильного решения которой потребовалось бы множество итераций, если бы вы следовали какому-то другому «традиционному» методу.
Одним из классических примеров здесь является так называемая «задача коммивояжера». Представьте себе, что вы коммивояжер, который ежедневно посещает несколько домов. Все они разбросаны по всему городу, поэтому вам нужно проложить маршрут, который позволит вам посетить их все в кратчайшие сроки.
Вы можете использовать подход обратного отслеживания и попробовать каждый потенциальный маршрут, убивая маршруты, которые в какой-то момент уже показывают, что они не лучше текущего лучшего решения. Но для этого потребовалось бы много логики и (потенциально) рекурсии, в чем, как мы все знаем, JavaScript не силен.
Вы также можете сгенерировать каждый отдельный маршрут, а затем рассчитать время, необходимое для прохождения каждого из них. Это будет так называемый метод «грубой силы». Это эффективно, но потенциально может занять ДОЛГОЕ время, если количество домов достаточно велико.
Вместо этого мы можем использовать метод грубой силы и улучшить его с помощью генетического алгоритма. Давайте сгенерируем несколько случайных решений и пройдем описанный выше процесс. Мы можем позволить природе найти лучший подход.
Внедрение решения
Предположим, мы имеем дело со сценарием, в котором есть 10 городов, и мы, конечно, можем перейти от любого из них к следующему.
Мы будем использовать расстояние между ними, чтобы понять, насколько хорошим является решение, ведь чем меньше общее пройденное расстояние, тем оно будет лучше для нас.
Вот наш установочный код, включая общее количество итераций, которые мы будем выполнять (в конце концов, проблемы такого типа на самом деле не закончатся, если вы не скажете им, когда закончить), размер нашей популяции (т. е. сколько различных решений мы будем иметь дело), а также вероятности кроссинговера и мутации генов.
Обратите внимание на матрицу расстояний: 0 — это расстояние между этим конкретным городом и самим собой.
Давайте теперь создадим нашу начальную случайную совокупность потенциальных решений:
Здесь нет ничего интересного, мы просто создаем список чисел от 0 до NUM_CITIES, а затем перемешиваем порядок. Мы делаем это POPULATION_SIZE раза.
Затем мы запустим генетический алгоритм MAX_ITERATIONS раза, изменив популяцию, а затем отсортируем ее по приспособленности (то есть общему пройденному расстоянию) и сохраним первую.
Эта логика переводится в этот код:
Нам, конечно, не хватает некоторых деталей. Давайте посмотрим, как выглядит функция evolve:
Эта функция выбирает решения для следующего поколения на основе вероятности (вместо метода сортировки-уничтожения, который я описал ранее). Затем он будет генерировать новую популяцию на основе случайности. Если захочется, мы смешаем два раствора вместе и сохраним их потомство.
А затем мы вызовем функцию mutation, которая «мутирует» гены нашего решения, если это позволят случайные боги (мы рассмотрим эту функцию через минуту).
Как только следующее поколение будет готово, мы вернем его.
Давайте посмотрим на следующую самую сложную функцию, функцию selection:
Это длинная функция, но позвольте мне разбить ее для вас:
- Сначала мы вычисляем приспособленность всей популяции. Как вы вскоре увидите, пригодность решения — это общее пройденное расстояние. Это означает, что более низкая пригодность лучше подходит для нашего варианта использования.
- Затем мы нормализуем значения пригодности, вычисляя общую сумму приспособленностей вместе, а затем вычисляя процент, покрываемый каждым решением от этой суммы.
- Затем мы переходим к просмотру нашей совокупности решений и на основе
Math.randomи вероятностей, рассчитанных на предыдущем шаге, выбираем двух потенциальных индивидуумов. Это, в свою очередь, сохранит наиболее приспособленных из обоих вариантов. Поскольку мы делаем этоPOPULATION_SIZEраз, мы вернем массив потенциально повторяющихся значений, но это не проблема, потому что случай также поможет нам скрестить их вместе, чтобы найти новые.
Что приводит меня к функции crossover. Эта функция примет два родительских решения и создаст потомок, выбрав случайную точку пересечения и смешав значения:
Как видите, есть некоторые соображения, которые необходимо учитывать, если смесь обоих путей не является новым полным путем. Нам нужно будет заполнить недостающие города, чтобы создать полное решение.
Наконец, возвращаясь к функции evolve, после разведения наших решений мы также вызываем функцию mutation, которая имеет очень низкую вероятность добавления мутации, что в нашем случае означает замену городов в решении:
Есть две причины, по которым вы захотите добавить мутацию в свой алгоритм:
- Чтобы добавить потенциальные решения, которые никогда не были охвачены как часть начальной случайной популяции или в процессе размножения
- Чтобы сломать потенциальные точки застоя. Без мутации алгоритм потенциально может достичь точки, когда он не сможет найти лучшие решения, а с помощью мутации мы добавляем шум. Этот шум может помочь найти новые решения, которые раньше были невозможны.
Обычно вы хотите поддерживать низкий уровень мутаций, потому что в противном случае случайные боги возьмут верх над вашим алгоритмом, и результаты никогда не будут хорошими. Однако игра с этим числом может помочь вам быстрее добиться лучших результатов, в зависимости от того, чего вы пытаетесь достичь.
Понравилось ли вам то, что вы прочитали? Подпишитесь на мой БЕСПЛАТНЫЙ информационный бюллетень, где я делюсь со всеми своим 20-летним опытом работы в ИТ-индустрии. Присоединяйтесь к Бродяге старого разработчика!
Тестирование алгоритма
Как только у нас будет готов весь наш код и начальные значения настройки, как показано выше, мы должны запустить код.
Результат должен прийти почти мгновенно, потому что на самом деле мы не делаем много вычислений.
В моем случае результат, который я получаю, следующий:
Это означает, что кратчайший маршрут, который он мог найти, был от 0 -> 1 -> 3 -> 4 -> 2 -> 7 -> 6 -> 9 -> 8 -> 5.
Что также можно представить, используя нашу исходную матрицу, вот так:
Если вы сложите все показанные там расстояния, вы получите 100, что является пригодностью этого решения.
Ваши результаты могут отличаться, одна из характеристик этих алгоритмов заключается в том, что они не всегда приходят к одному и тому же выводу, особенно если вы не даете им достаточно времени, чтобы прийти к нему.
Это подводит меня к последнему замечанию о начальных значениях настройки: это примерные значения. Если вы испытываете этот код, не стесняйтесь изменять его, добавлять больше итераций или уменьшать популяцию, экспериментировать и смотреть, какие результаты вы получите.
Генетические алгоритмы — очень интересный способ решения очень сложных проблем, позволяя решению развиваться самостоятельно. К сожалению, они подходят не для всех проблем, но если вы знаете, как реализовать свои собственные, вы в конечном итоге столкнетесь с проблемой, которая поможет им.
Например, я реализовал генератор тем, используя генетические алгоритмы, чтобы разработать лучшую тему на основе предпочтений пользователя. Вы можете ознакомиться с полным руководством здесь.
Кстати, полный исходный код, используемый для этого примера, можно найти в этом репозитории Github, так что не стесняйтесь использовать его для всего, что вам нужно.
Вы использовали генетические алгоритмы в прошлом? Для чего вы их использовали?
Создавайте приложения с повторно используемыми компонентами, как Lego
Инструмент с открытым исходным кодом Bit помогает более чем 250 000 разработчиков создавать приложения с компонентами.
Превратите любой пользовательский интерфейс, функцию или страницу в компонент многократного использования — и поделитесь им со своими приложениями. Легче сотрудничать и строить быстрее.
Разделите приложения на компоненты, чтобы упростить разработку приложений, и наслаждайтесь наилучшими возможностями для рабочих процессов, которые вы хотите:
