|
3.9.2.
Особые процедуры репродукции
В качестве особых процедур репродукции можно рассматривать так
называемую
элитарную стратегию
и
генетический алгоритм с
частичной заменой популяции.
Элитарная стратегия (elitist strategy)
заключается в защите
наилучших хромосом на последующих итерациях. В классическом ге-
нетическом алгоритме самые приспособленные особи не всегда пе-
реходят в следующее поколение. Это означает, что новая популяция
Р(k
+1) не всегда содержит хромосому с наибольшим значением
функции приспособленности из популяции
Р(k).
Элитарная стратегия
применяется для предотвращения потери такой особи. Эта особь га-
рантированно включается в новую популяцию.
Генетический алгоритм с частичной заменой популяции,
иначе
называемый
генетическим
алгоритмом
с
зафиксированным
состоянием (steady-state),
характеризуется тем, что часть популяции
переходит в следующее поколение без каких-либо изменений. Это
означает, что входящие в эту часть хромосомы не подвергаются опе-
рациям скрещивания и мутации. Часто в конкретных реализациях ал-
горитма данного типа на каждой итерации заменяются только одна или
две особи вместо скрещивания и мутации в масштабе всей популяции.
Именно такой подход принят, например, в программе
Evolver
. В
других программах, в частности, во
FlexTool
, пользователь может сам
установить - какая часть популяции (в соответствии со значениями
функции приспособленности) должна передаваться без изменений в
следующее поколение. Это подмножество хромосом не подвергается
регулярной селекции и без изменений включается в новую популяцию.
3.9
.3. Генетические операторы
В классическом генетическом алгоритме операция скрещивания
представляет собой так называемое точечное скрещивание. Также
применяются
и
другие
виды
скрещивания:
двухточечное,
многоточечное и равномерное.
Двухточечное скрещивание (two-point crossover),
как следует из его
названия, отличается от точечного скрещивания тем, что потомки
наследуют фрагменты родительских хромосом, определяемые двумя
случайно выбранными точками скрещивания. Для пары хромосом из
примера 1 скрещивание в точках 4 и 6 показано на рис.1. Обратим
А.Е. Кононюк Дискретно-непрерывная математика
151
внимание, что такое скрещивание не приводит к уничтожению схемы
1**********1, которую представляет родитель 2.
Рис.1. Пример двухточечного скрещивания.
Многоточечное скрещивание (multiple-point crossover)
представляет
собой обобщение предыдущих операций и характеризуется
соответственно большим количеством точек скрещивания. Например,
для трех точек скрещивания, равных 4, 6 и 9, и такого же количества
родителей, как на рис.1, результаты скрещивания показаны на рис.2.
Рис.2. Пример трехточечного скрещивания.
Аналогично производится скрещивание для пяти или большего
нечетного количества точек. Очевидно, что одноточечное скрещивание
может считаться частным случаем многоточечного скрещивания.
Пример двухточечного скрещивания, представленный на рис.1, можно
проиллюстрировать способом, показанным на рис. 3.
Рис. 3. Двухточечное скрещивание с точками скрещивания 4 и 6.
А.Е. Кононюк Дискретно-непрерывная математика
152
Многоточечное скрещивание для четырех точек, равных 1,4,6, 9 и 4, 6,
9, 11 для той же пары родителей из предыдущих примеров
иллюстрируется на рис.4.
Рис.4. Многоточечное скрещивание с четырьмя точками скрещивания,
равными 1, 4, 6, 9 и 4, 6, 9, 11.
Многоточечное скрещивание с большим четным количеством точек
скрещивания протекает аналогично показанному на рис.4.
Скрещивание с нечетным количеством точек можно представить таким
же образом, если добавить еще одну точку скрещивания в позиции,
равной 0. Приведенный выше пример для трех точек можно
представить также, как на рис.4, с точками скрещивания 0, 4, 6, 9. При
четном количестве точек хромосома рассматривается как замкнутое
кольцо (см. рис. 3 и 4), а точки скрещивания выбираются с равной
вероятностью по всей его окружности.
Равномерное скрещивание (uniform crossover),
иначе называемое
монолитным
или
одностадийным,
выполняется в соответствии со
случайно выбранным эталоном, который указывает, какие гены
должны наследоваться от первого родителя (остальные гены берутся от
А.Е. Кононюк Дискретно-непрерывная математика
153
второго родителя). Допустим, что для пары родителей из примеров на
рис. 1- 4 выбран эталон 010110111011, в котором 1 означает принятие
гена на соответствующей позиции
(locus)
от родителя 1, а 0 - от
родителя 2. Таким образом формируется первый потомок. Для второго
потомка эталон необходимо считывать аналогично, причем 1 означает
принятие гена на соответствующей позиции от родителя 2, а 0 - от
родителя 1. В этом случае равномерное скрещивание протекает так, как
показано на рис.5.
Рис.5. Пример равномерного скрещивания.
Оператор инверсии.
Холланд предложил три технологии для
получения потомков, отличающихся от родительских хромосом. Это
уже известные нам операции скрещивания и мутации, а также
операция инверсии. Инверсия выполняется на одиночной хромосоме;
при ее осуществлении изменяется последовательность аллелей между
двумя случайно выбираемыми позициями
(locus)
в хромосоме. Не-
смотря на то, что этот оператор был определен по аналогии с биоло-
гическим процессом хромосомной инверсии, он не слишком часто
применяется в генетических алгоритмах. В качестве примера выпол-
нения инверсии рассмотрим хромосому [001100111010] и допустим,
что выбраны позиции 4 и 10. Тогда в результате инверсии получим
[001101110010].
Do'stlaringiz bilan baham: |
