Немного о генетических алгоритмах

Roman

Geneticist
Staff member
#1
Сегодня я хотел бы немного отойти в сторону от нашей основной темы и сделать этакое лирическое отступление в область генетики, математики и информатики. Так что прослушайте небольшой доклад про генетические алгоритмы. Генетические алгоритмы — это один из методов оптимизации, который позволяет найти глобальный экстремум функции в многофакторном пространстве тогда, когда входные данные можно выразить в виде «хромосомы». Впрочем, алгоритм не гарантирует точности и остановки в обозримое время. Зато он подсмотрен у природы. И потому сегодня генетические алгоритмы очень тщательно изучаются в рамках технологий Искусственного Интеллекта, особенно при рассмотрении многоагентных систем и гибридного ИИ. Так что приступим...

Генетический алгоритм состоит из следующих шагов:
  1. Генерация начальной популяции. Это значит, что необходимо подготовить некоторое количество «начальных» значений в пространстве поиска, с которых алгоритм начнёт свою работу. Начать можно с произвольных значений, но если такие значения будут как можно более близки к целевому, то алгоритм отработает намного быстрее.
  2. Запуск цикличного процесса рождения новых поколений и отбора. Фактически, это и есть сам генетический алгоритм, который раз за разом запускает процесс порождения новых поколений, изучения новых особей и отбора наиболее интересных. Этот процесс состоит из следующих шагов и операций:
    • Скрещивание (или перекрёст, англ. crossingover) — это операция, при которой берутся две особи текущего поколения, и их генотип перемешивается друг с другом. Чаще всего два генотипа разрезаются в одинаковом случайном месте, и после этого вторые части переставляются друг с другом. Так получаются два новых потомка. Фактически, скрещивание делается каждой особи с каждой, да ещё и по нескольку раз, чтобы разрезание генотипа происходило в разных местах. Так получается набор особей следующего поколения.
    • Мутация — это операция по внесению случайных изменений в генотип потомства. С установленной частотой в каждый новый генотип после скрещивания вносятся случайные изменения. Если частота мутаций высокая, то наблюдается «подвижность» поиска, если же частота мутаций слишком низкая, то часто это приводит к «залипанию» алгоритма в локальном экстремуме, из которого он не может выбраться и, соответственно, остановиться. Величину частоты мутаций часто подбирают при помощи экспериментов для каждой конкретной задачи.
    • Отбор — это операция по выбору наиболее приспособленных особей. Обычно выбирается какая-то доля (например, 10 %) тех особей нового поколения, для которых фитнесс-функция возвращает наилучшие результаты. Иногда в отобранное множество особей нового поколения добавляются наименее приспособленные особи, для которых фитнесс-функция возвращает наихудшие результаты. Это делается для получения генетического разнообразия и является инструментов борьбы с залипанием в локальных экстремумах. Также иногда в состав нового поколения включаются некоторые представители предыдущего поколения, которые в данном случае называются «элитой». Вообще, операция отбора также подбирается на основе экспериментов для каждой конкретной задачи.
  3. Возвращение результатов, которые привели к остановке цикла. Завершение алгоритма происходит тогда, когда фитнесс-функция для какой-либо особи находится в окрестности целевого значения с заданной точностью. Собственно, предикат проверки условия для остановки алгоритма проверяет для каждой особи значение фитнесс-функции, и если абсолютное значение разницы между ним и целевым значением меньше заданной точности, то предикат возвращает истину, и алгоритм останавливается. Необходимая точность является входным параметром алгоритма.
Схематически генетический алгоритм может быть изображён при помощи следующей диаграммы:

2018-03-27_12-22-47.png

Задавайте ваши вопросы. Готов отвечать.
 

Delectat

Active member
#2
Получилось немного сложно, но "новые особи" на схеме выглядят убедительно. Опасаюсь мутаций.
 

Delectat

Active member
#4
Самый главный вопрос — какое это отношение имеет к нашей игре?
Я решил, что будет невежливым задавать такой вопрос.
Хотя мне почему-то кажется, что самое прямое. Возможно, это даже такое своеобразное техзадание. :)
 

Roman

Geneticist
Staff member
#5
ТЗ?.. Нет, ТЗ было в духе принятого процесса разработки — переведено на программистский язык и выдано нашим ребятам для непосредственной реализации. Но модель.. Генетическая модель имеет своё предназначение. Таинственное предназначение. Этим сообщением про генетические алгоритмы я лишь попытался приоткрыть чуть-чуть завесу, самый краешек.

И мы до конца сами не понимаем, что там происходит... Цели того, кто инициировал всё, неясны. Иногда мне кажется, что я был всего лишь инструментом (тешу своё тщеславие тем, что высокоуровневым инструментом) в достижении какой-то непостижимой цели.