Разум, машины и математика. Искусственный интеллект и его задачи
Шрифт:
Еще одна стратегия отбора, пригодная для решения сложных задач, — это ранговая селекция. При ее использовании отбирается n копий наиболее приспособленной особи, n — 1 — второй по порядку и так далее до n = 0. Эта стратегия исключает вероятность того, что некая «сверхособь» снизит вероятность отбора прочих особей.
(«Сверхособью» называется особь, далекая от оптимальной, но намного превышающая по своим параметрам прочих особей из своего поколения.) Наличие сверхособей приводит к тому, что популяция оказывается скученной возле нее, и улучшить результаты становится невозможно.
Третья стратегия, турнирная селекция, заняла монопольное положение среди стратегий отбора, используемых при решении реальных задач, благодаря выгодным математическим свойствам и высокой
Чтобы лучше понять схему проведения турнира, представьте себе начальные этапы футбольной Лиги чемпионов. Они проводятся по схеме 4:2 — футбольные команды объединяются произвольным образом в группы по четыре, а две лучшие переходят в следующий этап. Конечно, в примере с Лигой чемпионов нельзя говорить о действительно случайном турнире, так как при формировании групп учитываются определенные критерии — так, в одну группу не могут попасть две команды из одной страны. Однако мы тоже можем вводить свои правила при использовании эволюционных алгоритмов, что будет определять тот или иной тип эволюции.
Часто используется правило, согласно которому в одном турнире соперничают максимально похожие особи. Алгоритм способен находить оптимальные значения функции со множеством оптимумов.
Эти роботы-крабы определяют участки с максимальной освещенностью. У одного из этих роботов нет ног, у другого их сразу четыре. Создатель роботов, Джош Бонгард из Вермонтского университета, описал их поведение с помощью эволюционного генетического алгоритма и смог показать, что они действовали лучше, чем классические роботы, созданные с той же целью.
После отбора особей, которые оставят потомство, наступает этап размножения.
Существует несколько систем размножения, которые необязательно являются важнейшими составляющими эволюционных алгоритмов, но на самом деле конкретный эволюционный алгоритм получает свое название в зависимости от того, какая система размножения в нем используется. К примеру, генетические алгоритмы, о которых мы поговорим чуть позже, представляют собой эволюционные алгоритмы, в которых для размножения особей применяется скрещивание с мутациями.
Генетические алгоритмы — самые популярные среди всех эволюционных алгоритмов благодаря тому, что они оптимально сочетают сравнительно невысокую сложность программирования и хорошие результаты. Размножение путем скрещивания с мутациями тесно связано с основными понятиями генетики. В генетическом алгоритме каждая особь представлена хромосомой, а каждая хромосома представляет собой последовательность генов. При скрещивании хромосом двух особей сначала случайным образом определяется точка, которая делит хромосомы на две половины.
Далее эти четыре половины (две для каждой из родительских особей) скрещиваются между собой, и образуется два потомка. Первый потомок содержит первую половину хромосомы первой родительской особи (назовем ее отцом) и вторую половину хромосомы второго родителя (матери). Второй потомок будет содержать первую половину хромосомы матери (до точки пересечения) и вторую половину хромосомы отца.
После
* * *
ГРЕГОР МЕНДЕЛЬ И ГЕНЕТИКА
Австрийский монах Грегор Мендель (1822–1884) открыл и в 1866 году опубликовал первые законы наследования. Эти законы, открытые по результатам скрещивания нескольких видов гороха и известные сегодня как законы Менделя, описывают передачу определенных признаков от родителей к потомкам. С открытием этих законов в генетике и науке вообще появилось важное понятие — доминантные и рецессивные гены.
Мендель в ходе своих экспериментов зафиксировал окрас горошин у различных видов гороха. Первое поколение он получил путем скрещивания растений, приносивших желтые горошины, с растениями, приносившими зеленые горошины. Мендель заметил, что растения, полученные в результате скрещивания, имеют только желтые горошины. Но позднее он обнаружил, что при скрещивании этих растений между собой растения следующего поколения в большинстве своем имеют желтые горошины, однако, к удивлению ученого, у некоторых растений горошины вновь имели зеленый цвет. Соотношение растений с желтыми и зелеными горошинами равнялось 3:1. Проведя аналогичные эксперименты для других признаков, Мендель пришел к выводу: существуют гены, которые доминируют над другими и тем самым подавляют их проявление.
Существование доминантных и рецессивных генов объясняло, почему скрещивание особей с одним и тем же выраженным геном может давать потомство с другим выраженным геном — оба родителя являются носителями рецессивного гена, который подавляется доминантным. Несмотря на то что в свое время труды Менделя не получили широкой известности, в них были заложены основы генетики — науки, которая сыграла определяющую роль в развитии современной медицины.
Завершающий этап эволюционного цикла — замещение. Его цель — выбрать, какие особи из предыдущего поколения будут замещены новыми, полученными на этапе размножения. Чаще всего заменяются все особи из предыдущего поколения, за исключением лучшей, которой дается возможность «прожить» еще одно поколение. Этот метод, известный как элитизм, несмотря на крайнюю простоту и некоторую неестественность, оказался удивительно эффективным.
Также было предложено множество других стратегий замещения особей. Обратите внимание, что вновь, как и на этапе отбора, можно смоделировать то или иное давление отбора в зависимости от того, как будут выбираться особи для замещения.
Если мы всегда будем выбирать всех особей популяции и замещать их новыми, давление отбора будет отсутствовать. А если мы будем отбирать только неприспособленных особей популяции для замещения, то давление отбора крайне возрастет.
С другой стороны, на этом этапе также эффективны политики видообразования, то есть методы, упрощающие определение различных решений для задач с несколькими оптимумами. Наиболее популярным среди таких методов является метод замещения посредством цитирования (niching). Суть его состоит в том, что для каждой новой полученной особи производится отбор особей предыдущего поколения, сильнее всего схожих с ней. В следующее поколение переходит только лучшая из этой группы схожих особей.