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

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

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

В первую очередь интересен последний пункт. Многие, думаю, подметили, что технологии нередко черпают вдохновление у природы. Самолеты - это гигантские металические птицы. Водолазы используют ласты, подобные плавникам морских жителей. И этому есть вполне логическое объяснение: люди на Земле существуют порядка 150 тыс. лет, в то время, как эволюция идет уверенной поступью в будущее уже четвертый миллиард лет.

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

Что же такое генетический алгоритм и какое он вообще имеет отношение к играм?

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

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

Поколение - выборка экземпляров, которые существуют одновременно, и соревнуются друг с другом за виживание путем решения поставленной задачи (ну или попыток решения).

Характеристика - один из параметров, которыми обладает образец. Если есть некоторая функция, которая выполняется для достижения цели, то характеристики являются переменными, которые приходят в эту функцию (извините за программирование).

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

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

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

Что это все за слова и как они связаны друг с другом?

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

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

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

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

Довольно круто этот алгоритм задействован здесь. Неплохая иллюстрация алгоритма в игре.

Итак, я прочитал все это, но для меня не было ничего нового.

Техническую часть алгоритма можно подробнее изучить вот тут.

Намного подробнее и с разноцветными картинками об алгоритме здесь.

Дублирую ссылку о прохождении игр алгоритмом, которая где-то была в статье.

Очень интересный цикл видосов, где автор объясняет принцип действия алгоритма, делая игру на основе него.

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

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