Том 33. Разум, машины и математика. Искусственный интеллект и его задачи - [14]
Завершающий этап эволюционного цикла — замещение. Его цель — выбрать, какие особи из предыдущего поколения будут замещены новыми, полученными на этапе размножения. Чаще всего заменяются все особи из предыдущего поколения, за исключением лучшей, которой дается возможность «прожить» еще одно поколение. Этот метод, известный как элитизм, несмотря на крайнюю простоту и некоторую неестественность, оказался удивительно эффективным.
Также было предложено множество других стратегий замещения особей. Обратите внимание, что вновь, как и на этапе отбора, можно смоделировать то или иное давление отбора в зависимости от того, как будут выбираться особи для замещения.
Если мы всегда будем выбирать всех особей популяции и замещать их новыми, давление отбора будет отсутствовать. А если мы будем отбирать только неприспособленных особей популяции для замещения, то давление отбора крайне возрастет.
С другой стороны, на этом этапе также эффективны политики видообразования, то есть методы, упрощающие определение различных решений для задач с несколькими оптимумами. Наиболее популярным среди таких методов является метод замещения посредством цитирования (niching). Суть его состоит в том, что для каждой новой полученной особи производится отбор особей предыдущего поколения, сильнее всего схожих с ней. В следующее поколение переходит только лучшая из этой группы схожих особей.
Мы рассказали о некоторых наиболее популярных методах, применяемых на каждом из этапов эволюционных алгоритмов. Следует понимать, что существует и множество других методов.
* * *
ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ ЛАМАРКА
Двойственность теорий Дарвина и теорий Ламарка проявляется и в эволюционных алгоритмах.
Отметим, что обе теории оказались крайне эффективными для решения задач оптимизации. Чаще всего используются дарвиновские эволюционные алгоритмы, описанные в этой главе, а алгоритмы, созданные согласно теориям Ламарка, содержат дополнительный этап между оценкой и отбором. Этот этап заключается в краткой локальной оптимизации, имитирующей обучение или адаптацию особи к окружающей среде перед достижением репродуктивного возраста.
Локальная оптимизация, как правило, представляет собой небольшие мутации, применяемые к каждой особи. После мутации оценивается изменение приспособленности. Если приспособленность повысилась, мутация подтверждается, и цикл «мутация-оценка» повторяется вновь.
Если же мутация привела к снижению приспособленности особи, она отвергается, после чего цикл «мутация-оценка» повторяется начиная с состояния, предшествовавшего мутации. Первые эволюционные алгоритмы, построенные согласно теории Ламарка, получили название эволюционных стратегий. Как мы уже упоминали, они использовались немецкими инженерами во время Второй мировой войны для оптимизации сопл двигателей первых реактивных самолетов.
Как вы уже увидели, используя методы оптимизации, основанные на природных процессах, ученые добились огромных успехов в области искусственного интеллекта. Не так давно эволюционные вычисления при изготовлении лекарств позволили добиться заметных успехов. Напомним, что при создании медикаментов целью исследователей является подбор соединения, для которого энергия связи с определенным белком будет отрицательной и минимально возможной. Искомое соединение должно сформировать внутри нашего организма неразрывную связь с белком-мишенью, чтобы их неодолимо тянуло друг к другу, как сладкоежек тянет к карамели.
Рассмотрим, как действует эволюционный алгоритм при оптимизации молекул во время разработки лекарств. Сначала требуется инициализировать популяцию молекул. На этом этапе молекулы обычно формируются случайным образом. Для простоты будем рассматривать поколения всего из трех молекул, хотя обычно их число в одном поколении достигает нескольких сотен.
Далее произведем оценку молекул, рассчитав энергию взаимодействия каждой из них с белком-мишенью. Для этого используются различные вычислительные методы. Один из них (мы не будем подробно описывать принцип его действия) называется молекулярным докингом — это трехмерное моделирование, в ходе которого оценивается, сможет ли молекула образовать связь при встрече с мишенью и какой будет энергия этой связи. Возникает любопытная ситуация: при использовании эволюционного алгоритма для поиска идеальной молекулы на одном из его этапов мы вновь применяем эволюционный алгоритм, чтобы оценить качество молекулы по сравнению с остальными. Результатом докинга являются оцененные молекулы.
Следующий этап — отбор, который можно организовать, например, путем турнирной селекции. В ходе турнирной селекции случайным образом формируются пары молекул, после чего производится оценка их энергии взаимодействия и принимается решение о том, какие молекулы останутся, а какие — отсеются. Напомним, что энергия взаимодействия должна быть отрицательной и принимать минимально возможное значение.
Следующий этап эволюционного алгоритма — размножение, в ходе которого на основе отобранных молекул создаются новые, сочетающие в себе свойства молекул предыдущего поколения. Так, путем скрещивания двух молекул, отобранных на предыдущем шаге, создаются две новые молекулы.
