ТСМ-№3 (1088238), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Пример 1.

	*	*	*	*	*		*	*	*	*
A:	2	1	5	3	6	4	8	10	7	9
B:	1*	7*	2*	8*	10*	3*	6*	9*	5*	4*
A`:	7	1	8	3	2	10	5	6	4	9
B`	2	5	4	9	7	8	1	3	10	6

1 – А`:

1-й цикл: (2,1) (1,7) (7,5) (5,2)

2-й цикл: (3,8) (8,6) (6,10) (10,9) (9,4) (4,3)

2 – B`:

1-й цикл: (1,2) (2,5) (5,7) (7,1)

2-й цикл: (8,3) (3,4) (4,9) (9,10) (10,6) (6,8)

Пример 2.

	*	*	*	*	*	*	*	*	*	*
A:	6	9	3	10	5	8	2	7	1	4
B:	4	10	7	1	8	3	9	6	2	5
A`:	2	9	7	5	8	4	6	3	10	1
B`	10	1	8	6	4	7	3	5	2	9

1 – А`:

1-й цикл (6,4) (4,5) (5,8) (8,3) (3,7) (7,6)

2-й цикл (9,10) (10,1) (1,2) (2,9)

2 – B`:

1-й цикл (4,6) (6,7) (7,3) (3,8) (8,5) (5,4)

2-й цикл (10,9) (9,2) (2,1) (1,10)

Универсальный оператор кроссовера

Применяется для решения задач из области теории расписаний.

Особенность – вместо разрезающей точки (точки кроссовера) выбирается двоичная маска, длинна которой совпадает с длинной хромосомы.

1-й потомок получается путем наложения 1-ого родителя с маской на основе следующих правил:

0+0=0

0+1=1

1+0=1

1+1=0

2-й потомок получается аналогично:

A:	0	1	1	0	0	1
B:	0	1	0	1	1	1
Маска:	0	1	1	0	1	0
A`:	0	0	0	0	1	1
B`:	0	0	1	1	0	1

Маска выбирается, как правило, случайным образом (1 или 0 в в основном разряде выпадает с вероятностью 0,5)

Пример 1.

A:	1	1	1	0	0	1	0	0
B:	0	0	1	1	1	0	1	0
Маска:	1	0	1	0	0	1	1	0
A`:	0	1	0	0	0	0	1	0
B`:	1	0	0	1	1	1	0	0

Пример 2.

A:	1	0	0	1	0	1	1	1
B:	1	1	0	0	1	1	0	0
Маска:	0	0	0	1	1	0	0	1
A`:	1	0	0	0	1	1	1	0
B`:	1	1	0	1	0	1	0	1

Жадный оператор Кроссовера

Рассмотрим алгоритм “жадного” оператора кроссовера на примере нахождения на графе пути с минимальной (или максимальной) стоимостью.

Пусть задан граф , где , с весовой матрицей:

Построим популяцию P, из трех родительских хромосом.

Эти матрицы определяют стоимости путей между любыми двумя вершинами графа. Жадный ген в хромосоме кодируется элементом вершины графа.

Алгоритм “жадного” оператора кроссовера

1. выбирается заданное число родительских хромосом, и случайным образом на одной из них определяется точка “жадного” оператора кроссовера.

2. Из выбранной хромосомы для i-ого гена, расположенного справа от точки “жадного” оператора кроссовера, определяется значение частной целевой функции. Например это стоимость пути от выбранного гена к ближайшему, находящемуся с права гену. Аналогичные действия выполняются по определению стоимости пути от i-ого гена во всех остальных хромосомах, выбранных для “жадного” оператора кроссовера.

3. В хромосому-потомок выбираем тот ген, у которого значение стоимости целевой функции ниже, чем минимум значений целевых функций.

4. Процесс продолжается аналогично до построения хромосомы-потомка.

Если в процессе реализации возникает цикл или тупик, то выбираются раннее нерассмотренные гены с наименьшим значением целевой функции.

Для приведенного примера согласно алгоритму выберем точку «жадность» оператора кроссовера между генами b и с в хромосоме P₁:

Теперь выбор (b - c) в P₁ дает целевую функцию = 4

выбор (b - d) в P₂ дает целевую функцию = 3

выбор (b - a) в P₃ дает целевую функцию = 15

Характеристики

Список файлов лекций