Выбор родителей

Этот оператор иллюстрирует естественный отбор, если отбор в родительскую пару хромосом с лучшими значениями F более вероятен.

П

(1)

р. Пусть F треб. min-т., тогда Р_i выбора родителя с хромосомой C_i вычисляется:

F_max – наихудшее значения F среди экземпляров текущего поколения.

F_i –значения функции i-ого экземпляра.

(1) называется Правило колеса рулетки.

Если в колесе рулетки выделены секторы пропорциональные (F_max – F_i), то вероятность попадания в них – суть F_i, определяется в соответствии с (1)

Пр. Пусть N = 4

F_i и Р_i в таблице:

i	1	2	3	4
Fi	2	7	6	3
Fmax – Fi	5	0	1	4
Рi	0,5	0	0,1	0,4

Скрещивание

Скрещивание заключается в передаче участков генов от родителей к потомкам. При простом (одноточечном кроссовере) хромосомы родителей разрываются в позиции одинаковой для обоих родителей. Место разрыва равновероятно. Далее рекомбинация, образовавшихся частей родительских хромосом, как в таблице 1, где разрыв подразделяется между 5 и 6 локусами.

Хромоссомы	Гены
А	f	a	c	d	g	k	v	e
В	a	b	c	d	e	f	g	h
С	f	a	c	d	g	f	g	h
D	a	b	c	d	e	k	v	e

Операция мутации выполняется с вероятностью Р( ). Происходит замена аллели значением, выбираемым с равной вероятностью с области определенного гена. Благодаря мутации расширяется область ген. поиска.

Селекция

После каждого акта генерации пара потомков в новое поколение включается лучший экземпляр пары.

Внутренний цикл простого г.а заканчивается, когда число экземпляров нового поколения станет N.

Количество повторений G внешнего цикла, чаще всего определяется автоматически, по выявлению признаков вырождения (стагнации), но с условием не превышения лимита маш. t.

Разновидности ген. Операторов

Кроссовер:

В-первых, допустимы схемы много точечного кроссовера

Во-вторых, отметаем ситуации, когда на состав аллель наложены дополнительные условия.

Например. Пусть задача разбиение графа число вершин в подграфе А₁ и А₂ должно быть N₁ и N₂. Пусть к-тый аллель равен 1. Это означает, что К попадает в А₁, если же к-тый аллель равен 0, то в А₂.

Очевидно, что число 1 в хромосоме должно быть равно N₁, а число 0 N₂.

При рекомбинации левый участок хромосомы берется от одного из родителей без изменений, а в правом участке от другого родителя н. соглас-ть число 1 с N₁.

Один из способов – метод РМХ.

Для иллюстрации метода рассмотрим пример двух точечного кроссовера в задаче, когда в хромосоме должны присутствовать, причем только по одному разу, все значения генов из заданного набора.

Пусть в пр. набор включ-т от 1..9

1	2	3	4	5	6	7	8	9	Родители
3	7	1	9	2	4	8	6	5
1	2	1	9	2	6	7	8	9
1	2	3	9	5	6	7	8	4

В таблице третья строка содержит хромосому первого из потомков, сгенерированного в результате применения первого из кроссовер (после второго и пятого покус.). Полеченные хромосома не относиться к числу допустимых, так как в ней значение генов 1, 2, 9 встречаются второго рода, а значения 3, 2, 5 отсутствуют.

Четвертая строка показывает результат применения метода РМХ. В этом методе выделяются сопряженные пары аллелей в локусе в одной из рекомбинированных частей. В нашем примере это пары 3–1, 4–9, 5–2. Хромосома потомка просматривается слева на право. Если встречаются повторяющиеся значения, то они заменяются сопряженным значением. В пр., повторно встречающиеся аллели заменены значениями 3, 5, 4.