49 Генетический алгоритм. Методы скрещивания, применяемые в генетических алгоритмах и их эффективность.

РЕКОМБИHАЦИЯ - скрещивание

Рекомбенация практически всегда ассоциируется с кроссинговером (кроссовером). Она заключается в генерации новых решений на основании отобранных родительских решений. Классическая схема заключается в создании одного или нескольких решений на основании родительской пары (2 родительские особи) посредством различного рода комбинаций их ген. Хотя многие операторы репродукции допускают создание более чем одного потомка, зачастую используется создание только одного, т.к. затраты на рассмотрение более чем одного потомка часто превышают получаемый при этом эффект. Кроме того, многие операторы репродукции при создании более чем одного потомка генерируют "генетически близких" потомков, что приводит к более тщательному изучению некоторого небольшого участка поверхности ответа, а не к изучению новых участков (при больших популяциях это приводит к пустой трате ресурсов).

Hаиболее распространены реализации ГА со статической длиной хромосом особей, т.к. при этом операторы рекомбинации много проще в реализации. Однако, иногда рассматриваются и варианты с переменной длиной хромосом.

Классический (одноточечный) кроссинговер.

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

Двуточечный кроссинговер.

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

линейное представление: хххххххххххх

------------>

циклическое представление:+>хххххххххххх-+

+--------------+

Проще (и понятнее) будет сказать что многоточечный кроссинговер

эквивалентен последовательному применению одноточечного кроссинговера несколько раз. Тоесть, имея n точек скрещивания: x_i, i=1..n, и хромосомы c1_0, c2_0, строим c1_i и c2_i путём скрещивания c1_(i-1) с c2_(i-1) в точке x_i. Повторять для i от 1 до n. c1_n, c2_n и будет результатом скрещивания c1_0, c2_0 в точках x_i, i=1..n.

Унифицированный (однородный) кроссинговер.

Унифицированный кроссинговер принципиально отличается от одноточечного кроссинговера. Каждый ген в потомстве создается посредством копирования соответствующего гена от одного или другого родителя, выбранного согласно случайно сгенерированной маске кроссинговера. Если в маске кроссинговера стоит 1, то ген копируется от первого родителя, если в маске стоит 0, то ген копируется от второго родителя. Процесс повторяется с обмененными родителями для создания второго потомства. Hовая маска кроссинговера случайно генерируется для каждой пары родителей.