Microsoft Word Книга иис мггу 1 Print doc

Скрещивание (crossover) — осуществляет обмен частями хромосом, 
как правило, между двумя хромосомами в популяции.
Скрещивание может 
быть [21]: 
- 
одноточечным, 
- 
многоточечным.
Одноточечное скрещивание
работает следующим образом. Сначала, 
случайным образом выбирается одна из 
l
−1 точек разрыва. Точка разрыва — 
участок 
между 
соседними 
генами. 
Обе 
родительские 
структуры 
разрываются на два сегмента по этой точке. Затем, соответствующие 
сегменты различных родителей склеиваются и получаются два генотипа 
потомков [21]. 

---

186 
При 
двухточечном скрещивании
выбираются две точки разрыва, и 
родительские хромосомы обмениваются сегментом, находящимся между 
этими точками, и равномерное скрещивание, в котором каждый бит первого 
родителя наследуется первым потомком с заданной вероятностью, в 
противном случае этот бит передается второму потомку и наоборот. 
Достаточно часто хорошо работает метод, при котором одинаковый участок 
генов для хромосом остается неизменным (и является некоторым 
шаблоном), и осуществляется обмен генов, не входящих в данный участок 
[21]. 
Мутация — стохастическое изменение части хромосом. В 
хромосоме, которая подвергается мутации, каждый ген с вероятностью 
P
mut
 (обычно очень маленькой) меняется на некоторый другой из заданного 
диапазона значений 
[21]
. 
 
Рисунок 18.2 – Принцип проведения операций в ГА 
 
Работа ГА представляет собой итерационный процесс, который 
продолжается до тех пор, пока поколения не перестанут существенно 
отличаться друг от друга, или не пройдет заданное количество поколений 
или заданное время. Для каждого поколения реализуются отбор, а также 
операции модификации (рис. 18.2):
- 
мутация, 
- 
инверсия, 
- 
кроссовер (скрещивание).

---

187