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

Пример одноточечного скрещивания
При 
двухточечном скрещивании
хромосому можно рассматривать как 
кольцо со связанными первым и последним генами. Кольцо 
рассекается на две части и полученные части обмениваются. 
Графическое представление двухточечного скрещивания представлено 
на рисунке 3, пример на рисунке 4. 

---

А.Е. Кононюк Дискретно-непрерывная математика 
377 
Рис. 3. 
Двухточечное скрещивание
Или 
Рис. 4. Пример двухточечного скрещивания 
Равномерное скрещивание
предполагает, что каждый ген потомка 
выбирается случайным образом из соответствующих генов родителей. 
Замечание:
в этом случае родителей может быть больше двух, в том 
числе возможно участие всей популяции родителей в целом (
gene pool 
recombination
) . 
Мутация в ГА 

---

А.Е. Кононюк Дискретно-непрерывная математика 
378 
Мутация состоит из выполнения (обычно небольших) изменений в 
значениях одного или нескольких генов в хромосоме. Мутация 
обеспечивает исследование пространства поиска. 
В двоичных хромосомах мутация состоит в инвертировании 
случайным образом выбранного бита генотипа, например 1010 1000. 
В ГА мутация является методом восстановления потерянной 
генетической информации, а не методом поиска лучшего решения. 
В ГА мутация применяется к генам с очень низкой вероятностью 
p
m 
[0.001, 0.01]. Хорошим эмпирическим правилом считается выбор 
вероятности мутации из соотношения 
p
m
= , где 
H
- число бит в 
хромосоме. На основе этого правила можно произвести 
классификацию мутации таким образом: 
1. Слабая (
p
m
< ), 
2. Средняя (
p
m
=) 
3. Сильная (
p
m
> ) 
Обобщенная пошаговая структура ГА 
1. Сгенерировать случайным образом начальную популяцию. 
2. Оценить полученную популяцию. 
3. Генерировать популяцию потомков. 
Селекция (выбор двух индивидов из текущей популяции).
Рекомбинация (скрещивание выбранных индивидов).
Мутация (генетическое изменение полученного потомка). 

---

А.Е. Кононюк Дискретно-непрерывная математика 
379 
4. Если не все поколения пройдены, то перейти на шаг 2, иначе выдать 
наилучшего найденного индивида и его значение целевой функции в 
качестве решения оптимизации.
Схема генетического алгоритма представлена на рисунке 5. 
Рис. 5.