Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
9
Добавлен:
02.03.2016
Размер:
117.93 Кб
Скачать

. Генетические операторы

В классическом генетическом алгоритме операция скрещивания представляет собой так называемое точечное скрещивание, рассмотренное в разд. 2.2 и в примерах 2 и 3. Также применяются и другие виды скрещивания: двухточечное, многоточечное и равномерное [7].

Двухточечное скрещивание (two-point crossover), как следует из его названия, отличается от точечного скрещивания тем, что потомки наследуют фрагменты родительских хромосом, определяемые двумя случайно выбранными точками скрещивания. Для пары хромосом из примера 2 скрещивание в точках 4 и 6 показано на рисунке 39. Обратим внимание, что такое скрещивание не приводит к уничтожению схемы 1**********1, которую представляет родитель 2.

Рисунок 39. Пример двухточечного скрещивания

Многоточечное скрещивание (multiple-point crossover) представляет собой обобщение предыдущих операций и характеризуется соответственно большим количеством точек скрещивания. Очевидно, что одноточечное скрещивание может считаться частным случаем многоточечного скрещивания.

Пример двухточечного скрещивания, представленный на рисунке 39, можно проиллюстрировать способом, показанным на рисунке 40.

Многоточечное скрещивание для четырех точек, равных 1, 4, 6, 9 и 4, 6, 9, 11 для той же пары родителей из предыдущих примеров иллюстрируется на рисунке 41.

Рисунок 40. Двухточечное скрещивание с точками скрещивания 4 и 6

Многоточечное скрещивание с большим четным количеством точек скрещивания протекает аналогично показанному на рисунке 41.

Скрещивание с нечетным количеством точек можно представить таким же образом, если добавить еще одну точку скрещивания в позиции, равной 0. Приведенный выше пример для трех точек можно представить так же, как на рисунке 41, с точками скрещивания 0, 4, 6, 9. При четном количестве точек хромосома рассматривается как замкнутое кольцо (см. рисунки 40 и 41), а точки скрещивания выбираются с равной вероятностью по всей его окружности.

Равномерное скрещивание (uniform crossover), иначе называемое монолитным или одностадийным, выполняется в соответствии со случайно выбранным эталоном, который указывает, какие гены должны наследоваться от первого родителя (остальные гены берутся от второго родителя). Допустим, что для пары родителей из примеров на рисунках 39 – 41 выбран эталон 010110111011, в котором 1 означает принятие гена на соответствующей позиции (locus) от родителя 1, а 0 – от родителя 2. Таким образом формируется первый потомок. Для второго потомка эталон необходимо считывать аналогично, причем 1 означает принятие гена на соответствующей позиции от родителя 2, а 0 – от родителя 1. В этом случае равномерное скрещивание протекает так, как показано на рисунок 41.

Рисунок 41. Многоточечное скрещивание с четырьмя точками скрещивания, равными 1, 4, 6, 9 и 4, 6, 9, 11

Оператор инверсии. Холланд предложил три технологии для получения потомков, отличающихся от родительских хромосом [7]. Это уже известные нам операции скрещивания и мутации, а также операция инверсии. Инверсия выполняется на одиночной хромосоме; при ее осуществлении изменяется последовательность аллелей между двумя случайно выбираемыми позициями (locus) в хромосоме. Несмотря на то, что этот оператор был определен по аналогии с биологическим процессом хромосомной инверсии, он не слишком часто применяется в генетических алгоритмах. В качестве примера выполнения инверсии рассмотрим хромосому [001100111010] и допустим, что выбраны позиции 4 и 10. Тогда в результате инверсии получим [001101110010].

Рисунок 42. Пример равномерного скрещивания

Соседние файлы в папке Ответы_ИИС