Формирование нового поколения

После скрещивания и мутации особей необходимо решить проблему: какие из новых особей войдут в следующее поколение, а какие - нет, и что делать с их предками. Есть два наиболее распространенных способа.

1. Новые особи (потомки) занимают места своих родителей. После этого наступает следующий этап, в котором потомки оцениваются, отбираются, дают потомство и уступают место своим "детям".

2. Следующая популяция включает в себя как родителей, так и их потомков.

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

Критерии останова

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

Схождением называется такое состояние популяции, когда все строки популяции почти одинаковы и находятся в области некоторого экстремума (рис. 16).

Рис.16. Схождение генетического алгоритма

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

Виды генетических алгоритмов

Существуют различные модели генетического алгоритма (классический, простой генетический алгоритм, гибридный, CHC генетический алгоритм и др.) Они различаются по стратегиям отбора и формирования нового поколения особей, операторами генетического алгоритма, кодированием ген и т.д.

CHC-алгоритм

CHC (Cross generational elitist selection, Heterogenous recombination, Cataclysmic mutation) был предложен Эсхелманом и характеризуется следующими параметрами:

1. Для нового поколения выбираются N лучших различных особей среди родителей и детей. Дублирование строк не допускается.

2. Для скрещивания выбирается случайная пара, но не допускается, чтобы между родителями было мало Хэммингово расстояние или мало расстояние между крайними различающимися битами.

3. Для скрещивания используется разновидность однородного кроссовера HUX (Half Uniform Crossover): ребенку переходит ровно половина битов каждого родителя.

4. Размер популяции небольшой, около 50 особей. Этим оправдано использование однородного кроссовера.

CHC противопоставляет агрессивный отбор агрессивному кроссоверу, однако все равно малый размер популяции быстро приводит ее к состоянию, когда создаются только более или менее одинаковые строки. В таком случае CHC применяет cataclysmic mutation: все строки, кроме самой приспособленной, подвергаются сильной мутации (изменяется около трети битов). Таким образом, алгоритм перезапускается и далее продолжает работу, применяя только кроссовер.

Genitor

Этот алгоритм был создан Д. Уитли. Genitor-подобные алгоритмы отличаются от классического ГА следующими тремя свойствами:

1. На каждом шаге только одна пара случайных родителей создает только одного ребенка.

2. Этот ребенок заменяет не родителя, а одну из худших особей популяции (в первоначальном Genitor — самую худшую).

3. Отбор особи для замены производится по ее ранку (рейтингу), а не по приспособленности.

В Genitor поиск гиперплоскостей происходит лучше, а сходимость быстрее, чем у классического генетического алгоритма, предложенного Холландом.

Гибридные алгоритмы

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

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