Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

FlexTool 
). 
Рис. 1. Схема турнирной селекции для подгрупп, состоящих из двух 
особей. 
При 
ранговой селекции (ranking selection) 
особи популяции 
ранжируются по значениям их функции приспособленности. Это можно 
представить себе как отсортированный список особей, упорядоченных по 
направлению от наиболее приспособленных к наименее приспособленным 
(или наоборот), в котором каждой особи приписывается число, 
определяющее ее место в списке и называемое 
рангом (rank). 
Количество 
копий 
М(k) 
каждой особи, введенных в родительскую популяцию, 
рассчитывается по априорно заданной функции в зависимости от ранга 
особи. Пример такой функции показан на рис. 2. 

---

А.Е. Кононюк Дискретно-непрерывная математика 
149 
Рис. 2. Пример функции, определяющей зависимость количества копий 
особи в родительском пуле от его ранга при ранговой селекции. 
Достоинство рангового метода заключается в возможности его применения 
как для максимизации, так и для минимизации функции. Он также не 
требует 
масштабирования 
из-за 
проблемы 
преждевременной 
сходимости, актуальной для метода рулетки. Существуют различные 
варианты алгоритмов селекции. Представленные ранее методы 
(рулетки, турнирный и ранговый) применяются чаще всего. Другие 
методы представляют собой либо их модификации, либо комбинации - 
например, метода рулетки с турнирным методом, когда пары 
родительских хромосом выбираются случайным образом, после чего из 
каждой пары выбирается хромосома с наибольшим значением функции 
приспособленности. Большинство методов селекции основано на 
формулах (3.3) и (3.16), по которым рассчитывается вероятность 
селекции и количество копий, вводимых в родительский пул. В так 
называемом детерминированном методе каждая особь получает число 
копий, равное целой части от е(ch
i
), после чего популяция 
упорядочивается в соответствии с дробной частью e(ch
i
), а остальные 
хромосомы, необходимые для пополнения новой популяции, 
последовательно выбираются из верхней части сформированного 
таким образом списка. В другом методе (называемом случайным) 
дробные части e(ch
i
) рассматриваются как вероятности успеха по 
Бернулли и, например, хромосома ch
i
, для которой e(ch
i
) 
= 1,5, получает одну копию гарантированно и еще одну - с ве-
роятностью 0,5. В еще одном методе для устранения расхождения 
между расчетным значением e(ch
i
) и количеством копий хромосом ch
i
, 
выбираемым по методу рулетки, производится модификация e(ch
i
) 
путем увеличения или уменьшения его значения для каждой 
хромосомы, выбранной для скрещивания и/или мутации. 

---

А.Е. Кононюк Дискретно-непрерывная математика 
150