Игнаси Белда - Том 33. Разум, машины и математика. Искусственный интеллект и его задачи

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

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

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

После получения потомства проводится мутация, при которой с очень маленькой вероятностью (как правило, около 5 %) несколько генов в новых хромосомах изменяются случайным образом. В теории и на практике можно показать, что без мутаций генетические алгоритмы не слишком способствуют оптимизации — результатами их работы обычно становятся субоптимумы функции, то есть локальные максимумы. Благодаря мутациям генетические алгоритмы совершают небольшие случайные прыжки в пространстве поиска. Если результаты этих прыжков окажутся не слишком многообещающими, то в ходе эволюции они будут отброшены, в противном случае — закрепятся в наиболее приспособленных особях следующих поколений.

* * *

ГРЕГОР МЕНДЕЛЬ И ГЕНЕТИКА

Австрийский монах Грегор Мендель(1822–1884) открыл и в 1866 году опубликовал первые законы наследования. Эти законы, открытые по результатам скрещивания нескольких видов гороха и известные сегодня как законы Менделя, описывают передачу определенных признаков от родителей к потомкам. С открытием этих законов в генетике и науке вообще появилось важное понятие — доминантные и рецессивные гены.

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

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

Завершающий этап эволюционного цикла — замещение. Его цель — выбрать, какие особи из предыдущего поколения будут замещены новыми, полученными на этапе размножения. Чаще всего заменяются все особи из предыдущего поколения, за исключением лучшей, которой дается возможность «прожить» еще одно поколение. Этот метод, известный как элитизм, несмотря на крайнюю простоту и некоторую неестественность, оказался удивительно эффективным.