3.1 Операторы выбора родителей

Существует несколько подходов к выбору родительской пары.

Панмиксия - самый простой оператор отбора. В соответствии с ним каждому члену популяции сопоставляется случайное целое число на отрезке [1;n], где n - количество особей в популяции. Будем рассматривать эти числа как номера особей, которые примут участие в скрещивании. При таком выборе какие-то из членов популяции не будут участвовать в процессе размножения, так как образуют пару сами с собой. Какие-то члены популяции примут участие в процессе воспроизводства неоднократно с различными особями популяции. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции.

Инбридинг представляет собой такой метод, когда первый родитель выбирается случайным образом, а вторым родителем является член популяции ближайший к первому. Здесь «ближайший» может пониматься, например, в смысле минимального расстояния Хемминга (для бинарных строк) или евклидова расстояния между двумя вещественными векторами. Расстояние Хемминга равно числу различающихся локусов (разрядов) в бинарной строке. Пример определения родства бинарных хромосом при выборе родительской пары для хромосомы 1010001 показан в табл. 5.

При аутбридинге также используют понятие схожести особей. Однако теперь брачные пары формируют из максимально далеких особей.

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

Таблица 5

Хеммингово расстояние между хромосомами популяции и хромосомой 1010001

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

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

При турнирном отборе (tournament selection) из популяции, содержащей N особей, выбираются случайным образом t особей, и лучшая из них особь записывается в промежуточный массив (рис. 4). Эта операция повторяется N раз. Особи в полученном промежуточном массиве затем используются для скрещивания (также случайным образом). Размер группы строк, отбираемых для турнира, часто равен 2. В этом случае говорят о двоичном (парном) турнире. Вообще же t называют численностью турнира. Преимуществом данного способа является то, что он не требует дополнительных вычислений.

Рис. 4. Турнирный отбор

В методе рулетки (roulette-wheel selection) особи отбираются с помощью N «запусков» рулетки, где N - размер популяции. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-го сектора пропорционален вероятности попадания в новую популяцию P(i), вычисляемой по формуле:

где f(i) - пригодность i-й особи. Ожидаемое число копий i-ой хромосомы после оператора рулетки определяются по формуле Ni = P(i)N.

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

Таблица 6

Метод рулетки. Суммарная пригодность = 200, суммарная вероятность = 1

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