Классический генетический алгоритм. Часть III. Селекция

Классический генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

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

Рассмотрим четвертый этап: селекция хромосом.

Селекция хромосом заключается в выборе (по рассчитанным на втором этапе значениям функции приспособленности) тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности. Существуют различные методы селекции. Наиболее популярным считается так называемый метод рулетки, который свое название получил по аналогии с известной азартной игрой. Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы. Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки Все колесо рулетки соответствует сумме значений функции приспособленности всех хромосом рассматриваемой популяции. Каждой хромосоме, обозначаемой $ch_{i}$ для $i~=~1,2~...~N$ (где $N$ обозначает численность популяции) соответствует сектор колеса $v(ch_{i})$ , выраженный в процентах согласно формуле:

причем $F(ch_{i})$ – значение функции приспособленности хромосомы $ch_{i}$ , a $p_{s}(ch_{i})$ – вероятность селекции хромосомы $ch_{i}$ . Селекция хромосомы может быть представлена как результат поворота колеса рулетки, поскольку «выигравшая» (т.е. выбранная) хромосома относится к выпавшему сектору этого колеса. Очевидно, что чем больше сектор, тем больше вероятность «победы» соответствующей хромосомы. Поэтому вероятность выбора данной хромосомы оказывается пропорциональной значению ее функции приспособленности. Если всю окружность колеса рулетки представить в виде цифрового интервала $delim{[}{0,100}{]}$ , то выбор хромосомы можно отождествить с выбором числа из интервала $delim{[}{~A,B}{]}$ , где и обозначают соответственно начало и окончание фрагмента окружности, соответствующего этому сектору колеса; очевидно, что . В этом случае выбор с помощью колеса рулетки сводится к выбору числа из интервала $delim{[}{0,100}{]}$ , которое соответствует конкретной точке на окружности колеса. Существуют также другие методы селекции.

В результате процесса селекции создается родительская популяция, также называемая родительским пулом с численностью $N$ , равной численности текущей популяции.