Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

Кроссовер 
Одноточечный кроссовер мы рассмотрели выше. 
При 
двухточечном кроссовере
для родительской пары случайным 
образом выбираются 2 точки раздела, и родители обмениваются 
промежутками между ними. В результате получаются два ребенка. 
Удобно в этом случае представить строки в виде колец:

---

А.Е. Кононюк Дискретно-непрерывная математика 
114 
Определяющая длина в этом случае тоже измеряется в кольце, поэтому 
для такого шаблона, как 1*****1, при одноточечном кроссовере 
определяющая длина равна 6, и точка раздела всегда попадает между 
крайними фиксированными битами, а при двухточечном эта длина 
равна 1.
Следует заметить, что одноточечный кроссовер является частным 
случаем двухточечного, когда одна из точек раздела фиксирована.
Однородный кроссовер
осуществляется следующим образом: один из 
детей наследует каждый бит с вероятностью 
p
0
у первого родителя, а 
иначе у второго. Второй ребенок получает все остальные не 
унаследованные биты. Обычно 
p
0
= 0.5. Для однородного кроссовера не 
важна определяющая длина шаблона, и вообще в большинстве случаев 
шаблон разрушается. Такой агрессивный оператор плохо предназначен 
для отбора гиперплоскостей, однако его применение оправдано при 
малом размере популяции, т. к. он препятствует преждевременному 
схождению, свойственному таким популяциям.
Стратегии отбора 
Как мы уже отмечали выше, для пропорционального отбора 
свойственно уменьшение давления отбора с увеличением средней 
приспособленности популяции. Исправить этот недостаток можно с 
помощью масштабирования (
scaling
): на каждом поколении нулем 
приспособленности можно считать наихудшую особь.
Ранковый отбор
(
rank selection
) отличается от пропорционального тем, 
что для каждой особи ее вероятность попасть в промежуточную 

---

А.Е. Кононюк Дискретно-непрерывная математика 
115 
популяцию пропорциональна ее порядковому номеру в 
отсортированной по возрастанию приспособленности популяции. Такой 
вид отбора не зависит от средней приспособленности популяции.
Турнирный отбор
(
tournament selection
) осуществляется следующим 
образом: из популяции случайным образом выбирается 
t
особей, и 
лучшая из них помещается в промежуточную популяцию. Этот процесс 
повторяется 
N
раз, пока промежуточная популяция не будет заполнена. 
Наиболее распространен вариант при 
t
= 2. Турнирный отбор является 
более агрессивным, чем пропорциональный.
Отбор усечением
(
truncation selection
): популяция сортируется по 
приспособленности, затем берется заданная доля лучших, и из них 
случайным образом 
N
раз выбирается особь для дальнейшего развития.