Разум, машины и математика

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

Размножение

После отбора особей, которые оставят потомство, наступает этап размножения.

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

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

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

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

* * *