Скрещивание и формирование нового поколения

Отобранные в результате селекции особи (называемые родительскими) скрещиваются и дают потомство. Хромосомы потомков формируются в процессе обмена генетической информацией (с применением оператора кроссинговера) между родительскими особями. Созданные таким образом потомки составляют популяцию следующего поколения. Ниже будут описаны основные операторы кроссинговера для целочисленного и вещественного кодирования. Будем рассматривать случай, когда из множества родительских особей случайным образом выбираются 2 особи и скрещиваются с вероятностью P_C , в результате чего создаются 2 потомка. Этот процесс повторяется до тех пор, пока не будет создано n потомков. Вероятность скрещивания P_C является одним из ключевых параметров генетического алгоритма и в большинстве случаев ее значение находится в диапазоне от 0,6 до 1. Процесс скрещивания на псевдоязыке выглядит следующим образом (предполагается, что размер подпопуляции родительских особей равен размеру популяции, RANDOM – случайное число из диапазона [0; 1]):

k = 0;

ПОКА (k < РАЗМЕР_ПОПУЛЯЦИИ) {

i = RANDOM * РАЗМЕР_ПОПУЛЯЦИИ;

j = RANDOM * РАЗМЕР_ПОПУЛЯЦИИ;

ЕСЛИ (P_C > RANDOM) {

СКРЕЩИВАНИЕ (РОДИТЕЛЬ[i], РОДИТЕЛЬ[j],

ПОТОМОК[k], ПОТОМОК[k+1]);

k = k+2;

}

}

Целочисленное кодирование.Для целочисленного кодирования часто используются 1-точечный, 2-точечный и однородный операторы кроссинговера.

1-точечный кроссинговер работает аналогично операции перекреста для хромосом при скрещивании биологических организмов. Для этого выбирается произвольная точка разрыва и для создания потомков производится обмен частями родительских хромосом. Иллюстративный пример работы 1-точечного кроссинговера представлен на рис. 5.4а.

Для оператора 2-точечного кроссинговера выбираются 2 случайные точки разрыва, после чего для создания потомков родительские хромосомы обмениваются участками, лежащими между точками разрыва (рис. 5.4б). Отметим, что для 2-точечного оператора кроссинговера, начало и конец хромосомы считаются «склеенными» в результате чего одна из точек разрыва может попасть в начало/конец хромосом и в таком случае результат работы 2-точечного кроссинговера будет совпадать с результатом работы 1-точечного кроссинговера [De Jong, 75]. На рис. 5.4б точка разрыва в месте склеивания хромосом показана пунктирными стрелками.

При использовании однородного оператора кроссинговера разряды родительских хромосом наследуются независимо друг от друга. Для этого определяют вероятность p₀, что i-й разряд хромосомы 1-го родителя попадет к первому потомку, а 2-го родителя – ко второму потомку. Вероятность противоположного события равна (1 – p₀). Каждый разряд родительских хромосом «разыгрывается» в соответствии со значением p₀ между хромосомами потомков. В большинстве случаев вероятность обоих событий одинакова, т.е. p₀ = 0,5.

Рис. 5.4. Примеры работы: а) 1-точечного оператора кроссинговера; б) 2-точечного оператора кроссинговера.

Вещественное кодирование. Для вещественного кодирования рассмотрим 2-точечный, арифметический и BLX-a операторы кроссинговера.

2-точечный кроссинговер для вещественного кодирования в целом аналогичен 2-точечному кроссинговеру для целочисленного кодирования. Различие заключается в том, что точка разрыва не может быть выбрана «внутри» гена, а должна попасть между генами (рис. 5.5).

При использовании арифметического и BLX-a операторов кроссинговера обмен информацией между родительскими особями и потомками производится с учетом значений генов родителей.

Обозначим и – k-е гены родительских особей, 1 £ k £ N, N – количество генов в хромосоме. Пусть также и – k-е гены потомков. Тогда для арифметического кроссинговера:

,

,

где 0 £ l £ 1.

Если используется BLX-a кроссинговер, то значение k-го гена потомка выбирается случайным образом (равномерное распределение) из интервала [c_min – aD_k, c_max + aD_k], где a – константа,

,

,

.

Рис. 5.5. Пример работы 2-точечного кроссинговера

для вещественного кодирования

Изображение интервала, используемого для BLX-a кроссинговера, показано на рис. 5.6.

Рис. 5.6. Интервал для BLX-a кроссинговера

Разрушающая способность кроссинговера. Операторы кроссинговера характеризуются способностью к разрушению (dispurtion) родительских хромосом. Кроссинговер для целочисленного кодирования считается более разрушительным, если в результате его применения расстояние по Хэммингу между получившимися хромосомами потомков и хромосомами родителей велико. Другими словами, способность целочисленного кроссинговера к разрушению зависит от того, насколько сильно он «перемешивает» (рекомбинирует) содержимое родительских хромосом. Так, 1-точечный кроссинговер считается слаборазрушающим, а однородный кроссинговер в большинстве случаев является сильно разрушающим оператором. Соответственно, 2-точечный кроссинговер по разрушающей способности занимает промежуточную позицию по отношению к 1-точечному и однородному операторам кроссинговера.

В случае кроссинговера для вещественного кодирования способность к разрушению определяется тем, насколько велико расстояние в пространстве поиска между точками, соответствующими хромосомам родителей и потомков. Таким образом, разрушающий эффект 2-точечного кроссинговера зависит от содержимого родительских хромосом. Разрушающая способность арифметического кроссинговера зависит от значения параметра l, например, при l ® 1 и l ® 0, способность к разрушению будет низкой. Для BLX-a кроссинговера разрушающая способность зависит как от значения a, так и от разности значений соответствующих генов родительских особей.

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

Формирование нового поколения. Как уже упоминалось выше, в результате скрещивания создаются потомки, которые формируют популяцию следующего поколения.

Отметим, что обновленная таким образом популяция не обязательно должна включать одних только особей-потомков. Пусть доля обновляемых особей равна T, 0 < T < 1, тогда в новое поколение попадает Tn потомков, n – размер популяции, а (1 – T)n особей в новой популяции являются наиболее приспособленными родительскими особями (так называемые элитные особи). Параметр T называют разрыв поколений (generation gap) [32]. Использование элитных особей позволяет увеличить скорость сходимости генетического алгоритма.