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

Селекция

Скрещивание

Скрещивание заключается в передаче участков генов от родителей к потомкам. При простом (одноточечном кроссовере) хромосомы родителей разрываются в позиции одинаковой для обоих родителей. Место разрыва равновероятно. Далее рекомбинация, образовавшихся частей родительских хромосом, как в таблице 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, 9 встречаются второго рода, а значения 3, 2, 5 отсутствуют.

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

Дата добавления: 2014-01-14