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

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

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

min = 3 => выбираем путь (b — d).

Переходим к точке d на всей популяции.

Далее выбираем P₂:(d — e) — целевая функция = 9 (два раза )

P₃: (d - c ) - целевая функция = 1

min = 1 => выбираем (d — c)

Переходим к точке с (на всей популяции).

Далее выбираем:

P₁ (с — d) — цикл

P₂ (c — a) - целевая функция = 6

P₃ (c - e ) - целевая функция = 10

min = 6 => выбор (с — а)

Переходим к точке а:

Далее выбор:

P₁ (с —b) — цикл

P₂ (c — b) - цикл

P₃ (c - d ) - цикл

Поэтому выбираем ранее не рассматриваемый ген е.

Схематически процесс реализации оператора «жадного» кроссовера изображена на рисунке:

Т.е. хромосома-потомок имеет вид:

P₁: b d c a e

Суммарное значение целевой функции для р'₁:

3 + 1 + 6 + 8 = 18!!!

Для

P₁: φ = 15 + 4 +1 + 9 = 29

P₂: φ = 3 + 9 + 10 + 6 = 28

P₃: φ = 2 + 15 +7 +1 = 25

Построим хромосому — потомок P'₂

Рассмотрим точку кроссовера на р₂:

Выбираем

P₂: (d — e) → частичная целевая функция = 9

P₁: (d — e) → = 9

P₃: (d — c) → = 1

min = 1 — выбираем путь (d — c)

Далее выбираем:

P₁: (с — d) → цикл

P₂: (c — a) → частичная целевая функция = 6

P₃: (c — e) → = 10

min = 6 — выбираем путь (с — а)

Далее выбираем

P₁: (а — b) → частичная целевая функция = 15

P₂: (a — b) → частичная целевая функция = 15

P₃: (a — d) → цикл

min = 15 → выбираем путь (a — b)

Далее выбираем:

P₁: (b — c) → цикл

P₂: (b — d) → цикл

P₃: (b — a) → цикл

Тогда выбираем ранее не рассматриваемый ген: е.

Получим: P'₂ = d c a b e

целевая функция: 1 + 6 + 15 + 2 =24

Построим хромосому — потомок P'₃:

Рассмотрим точку кроссовера на P₃:

Выбираем:

P₃: (b — a) → частичная целевая функция = 15

P₁: (b — c) → частичная целевая функция = 4

P₂: (b — d) → частичная целевая функция = 3

min = 3 → выбираем путь (b — d)

Далее выбираем:

P₁: (d — e) → частичная целевая функция = 9

P₂: (d — e) → частичная целевая функция = 9

P₃: (d — c) → частичная целевая функция = 1

min = 1 → выбираем путь (d — c)

Далее выбираем:

Далее выбираем:

Поэтому выбираем тот член, который ранее не встречался – .

Таким образом, получили (совпадает с ).

Ц.ф. .

Таким образом, получим следующее поколение хромосом:

Построим следующее поколение потомков:

1. Выбираем:

1. Переходим к точке a:

1. Переходим к точке e:

1. Переходим к точке b:

Выбираем путь (и так как он ещё не встречался).

Получили хромосому-потомок

Ц.ф.= .

Построим хромосому-потомок

Выберем точку кроссовера на

Переходим в точку e.

Переходим к точке b.

Выбираем путь (так как ген c ещё не встречался).

Таким образом,

Ц.ф.= .

Построим хромосому-потомок

Выбираем точку кроссовера на

Переходим к точке a:

Переходим к точке e:

Переходим к точке b.

Выбираем (т.к. ген d еще не встречался)

Ц.ф.= .

Получим новое поколение хромосом:

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

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