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

Стратегии отбора (selection strategies)
ГА представляет из себя итерационный процесс, в котором особи 
сначала отбираются для скрещивания, потом скрещиваются, затем из 
их потомков формируется новое поколение и все начинается сначала. 
Стратегии отбора являются составной частью ГА и определяют 
"достойных" для скрещивания особей. Ниже рассматриваются 
несколько наиболее распространенных стратегий.
Пропорциональный отбор (Proportional selection)
При данном виде отбора сначала подсчитывается присособленность 
каждой особи f
i
. После этого находят среднюю приспособленность в 
популяции 
f
ср
как 
среднее 
арифметическое 
значений 
приспособленности всех особей. Затем для каждой особи вычисляется 
отношение f
i
/f
ср
. Если это отношение больше 1, то особь считается 
хорошо приспособленной и допускается к скрещиванию, в противном 
случае особь, скорее всего, останется "за бортом". Например, если 
дробь равна 2.36, то данная особь имеет двойной шанс на скрещивание 
и будет иметь вероятность равную 0.36 третьего скрещивания. Если же 
приспособленность равна 0.54, то особь примет участие в 
единственном скрещивании с вероятностью 0.54.

---

А.Е. Кононюк Дискретно-непрерывная математика 
166 
Реализовать это можно, например, следующим образом. Пусть имеется 
массив двоичных строк (популяция) и дополнительный массив для 
особей допущенных к скрещиванию. Определим для каждой особи 
популяции значение описанного выше отношения. Далее, будем 
записывать строки в промежуточный массив согласно следующему 
правилу: возьмем целую часть понятно-какого-отношения и ровно 
столько раз запишем данную строку во вспомогательный массив, после 
этого с помощью случайной величины (СВ) определим, будем ли мы 
записывать данную строку ещё раз: если СВ больше дробной части 
отношения, то "да", если нет, то "нет". В дальнейшем, особи для 
скрещивания выбираются только из промежуточного массива 
случайным образом, так что, если строка присутствует в нем в 
нескольких экземплярах, то у нее больше шансов оставить след в 
истории. Для уже рассмотренных примеров с числами 2.36 и 0.51 
ситуация будет выглядеть следующим образом: первая строка 
запишется в промежуточный массив два раза и с вероятностью 0.36 
запишется в третьй раз. Вторая же строка имеет вероятность равную 
0.51 того, что она вообще будет присутствовать во вспомогательном 
массиве.
Данная стратегия отбора знаменита тем, что именно для неё создана 
классическая теорема схем (вот откуда там дробь).