Результаты операций репродукции и кроссинговера в простом генетическом алгоритме

Номер хромосомы	Популяция после репродукции	Случайно выбранные	Точка разрыва кроссингоовера	Популяця после кроссинговера	Значение x (десятичный код)	Значение f(x)
	0110I1	1-2
	1100I0	1-2
	11I000	3-4
	10I011	3-4
Суммарное значение целевой функции sum f(x)=1754
Среднее значение целевой функции fср(x) = 439
Максимальное значение целевой функции max f(х) = 729

На шаге 2 с помощью колеса рулетки осуществляется выбор хромосом для кроссинговера. Поля колеса рулетки соответствуют нормированным значениям целевой функции. Указатель рулетки после останова колеса определяет выбранную хромосому. Следует заметить, что случайный механизм не гарантирует выбора лучших хромосом, т.е. иногда результатом выбора могут оказаться хромосомы с низкими значениями целевой функции.

После репродукции выполняется оператор кроссинговера, который может повторяться несколько раз. При этом каждый раз будет осуществляться выбор двух кандидатур из множества хромосом. Затем каждая пара хромосом (стрингов) пересекается. Место пересечения К выбирается случайным образом на интервале (1, L-1), где L— длина хромосомы, определяемая количеством значащих цифр в ее двоичном коде. В нашем случае L = 5. Две новые хромосомы создаются путем взаимного обмена всех значений после точки пересечения, т.е. между позициями (К+ 1) и L. При выборе двух первых хромосом из популяции (см. табл.6. 1) и значения К = 4 до применения оператора кроссинговера имеем описание:

а после применения оператора кроссинговера получаем описание

Аналогично были получены потомки от третьей и четвертой хромосом.

Анализ полученных результатов (см. табл. 6.2) показывает, что после проведения одной генерации улучшились и среднее, и максимальное значение целевой функции по сравнению с начальной популяцией (см. табл. 6.1).

Согласно схеме простого генетического алгоритма на шаге 3 выполняется оператор мутации, который играет существенную роль в естественной генетике я эволюции, но менее значим в генетических алгоритмах. Обычно выбирают одну мутацию на 1000 бит. Оператор мутации относится к унарным операциям и реали­зуется в два этапа.

Этап 1. В хромосоме А = случайным образом определяют две позиции, например, 2 и L-1.

Этап 2. Гены, соответствующие выбранным позициям, меняют местами и формируют новую хромосому

Если длина обрабатываемых последовательностей невелика, то в процессе мутации можно осуществить полный перебор возможных перестановок генов и найти комбинацию с максимальным значением целевой функции. При длине хромосомы L=50 - 200 полный перебор вариантов становится затруднительным, поэтому здесь производится случайно-направленный поиск, который может быть реализован на основе простого генетического алгоритма. Рассмотрим этот механизм на исследуемой задаче.

Выберем третью хромосому из пятого столбца табл. 6.2 со значением целевой функции f(х)=729 и применим операцию мутации к позициям 3 и 4:

У новой хромосомы 3' значение целевой функции равно (29)²=841. Сделаем еще одну перестановку 4 и 5 генов в хромосоме 3':

Значение целевой функции для хромосомы 3" равно 900, чтс соответствует квазиоптимальному решению задачи нахождение максимального значения функции f(x)=x² на интервале [0,31].

В генетических алгоритмах и эволюционном программировании используют два основных механизма воспроизводства хромосом;

• воспроизводство без мутаций, соответствующее митозу, результатом которого являются потомки — копии родителей;

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

В генетических алгоритмах в основном используется механизм (родительского воспроизводства с рекомбинацией и мутацией, в эволюционном программировании - механизм на основе мутации без рекомбинации.

В алгоритмических реализациях механизма воспроизводствa Хромосом следует придерживаться следующих правил.

1 Выбор начальной популяции можно выполнять произвольным образом, например подбрасыванием монеты.

2.Репродукция осуществляется на основе моделирования движения колеса рулетки.

3. Оператор кроссинговера реализуется как взаимный обмен короткими фрагментами двоичных строк гомологичных хромосом.

4. Вероятность оператора кроссинговера принимается равной P(CO)<=1.0

5. Вероятность оператора мутации принимается равной P(МO)>=0,001