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

Пример колеса рулетки
Проблемы с пропорциональной селекцией: 
Преждевременная сходимость
. Эта проблема возникает, когда на 
первых стадиях работы алгоритма в популяции появляется один или 
несколько супериндивидов, у которых достаточно большая 
пригодность, и они доминируют при выборе родителя для создания 
потомка. Вскоре каждая последующая популяция будет состоять из 
этих супериндивидов.
Стагнация
Ранговая селекция 
В этом виде селекции индивиду назначается вероятность быть 
отобранным в зависимости от его места в упорядоченном ряду по 
пригодности индивидов текущей популяции. Таким образом, 
индивиды сортируются (ранжируются) на основе их пригодности 
таким образом, чтобы 
f
i 
f
j
для 
i 
> 
j
. 
Затем каждому индивиду назначается вероятность 
p
i
быть отобранным. 
Используемое распределение вероятностей: 

---

А.Е. Кононюк Дискретно-непрерывная математика 
375 
Линейное: 
p
i
 
= 
ai
+ 
b 
(
a 
< 0). 
Преимущества: 
Нет преждевременной сходимости, т.к. нет индивидов с 
N
i
>> 1. 
Нет стагнации, так как и к концу работы алгоритма 
N
1
N
2 
… . 
Нет необходимости в 
явном вычислении пригодности
, т.к. для 
упорядочения индивидов достаточно иметь возможность их по парного 
сравнения. 
Недостатки
: значительные накладные расходы на 
переупорядочивание и трудность теоретического анализа сходимости. 
Турнирная селекция 
Одна из самых простых в реализации и эффективных в оптимизации 
является турнирная селекция. Для отбора индивида создается группа из 
M
(
M 
2) индивидов, выбранных из текущей популяции случайным 
образом 
Индивид с наибольшей пригодностью в группе отбирается, остальные - 
игнорируются
Преимущества:
Нет преждевременной сходимости 
Нет стагнации 
Не требуется глобальное переупорядочивание 
Не требуется явное вычисление функции пригодности 
Элитарная селекция 

---

А.Е. Кононюк Дискретно-непрерывная математика 
376 
В данной селекции один или несколько лучших индивидов популяции 
всегда проходит в следующее поколение 
Преимущество
: гарантия сходимости, т.е. если глобальный максимум 
будет обнаружен, то ГА сойдется к этому максимуму 
Недостаток:
слабая глобальная сходимость, большой риск найти 
локальный минимумом 
Скрещивание в ГА 
Оператор 
скрещивание
предназначен для поиска новых решений на 
основе отобранных 
селекцией
родителей. 
· 
Одноточечное скрещивание
представляет собой разделение 
родительских хромосом в выбранной случайным образом общей точке 
и обмен правыми частями. (ТС - точка скрещивания). Пример 
одноточечного скрещивания представлена на рисунке 2. 
Рис. 2.