Введение в эволюционное моделирование. Каширина И.Л. - 26 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

26
1
2
3
4
5
t=1
t=5
t=4
t=3
t=2
Рис.32. Полученный потомок
13542
10
=V
Измененный кроссовер
Работа этого кроссовера может быть описана следующим образом.
Выбирается точка сечения (рис. 33), затем первая часть одного родителя ко-
пируется в первого потомка (рис. 34). Во вторую часть потомка копируются
гены второго родителя (рис. 35). Если такие гены уже встречаются в потом-
ке, то они пропускаются, а оставшуюся часть потомка дополняют
гены пер-
вого родителя. Аналогичный алгоритм и для второго потомка.
421 | 35
543 | 12
2
1
=
=
V
V
Рис.33. Точка сечения кроссовера
_ _ _ 2 1
11
=V
Рис.34. Потомок
11
V
_ _ 4 2 1
11
=
V
Рис.35. Потомок
11
V
3 5 4 2 1
11
=V
Рис.36. Потомок
11
V
Мутация
Мутация работает по следующему принципу. Выбираются случайным обра-
зом два города в хромосоме и меняются местами.
2 4 5 3 1
3 4 5 2 1
1
1
=
′
=
V
V
Рис.37. Мутация хромосомы
1
V
(2 и 5 элемент меняются местами)
“Жадная мутация”
“Жадная мутация” (greedy reconnection) состоит в упорядочивании по-
следовательности городов. Ее применение помогает хорошо искать локаль-
ные оптимумы. Сначала случайным образом выбираются две точки сечения
в хромосоме (рис.38) так, чтобы между ними было по крайне мере 2 города.
Затем последовательность городов между точками сечения упорядочивает-
ся: они переставляются в зависимости
от близости друг к другу. В нашем
случае среди городов 2, 5 и 4 определяется город, ближайший к городу 1.
Пусть, например, это город 5. Он ставится следом за городом 1. Затем среди
городов 2 и 4 определяется ближайший к городу 5. Пусть, например, это го-
                                               26
                                         t=1
                                    1



                                                               t=2

                                                           3
                              t=5
                          2                         t=4
                                               4




                                           5       t=3

                       Рис.32. Полученный потомок V10 = 13542
Измененный кроссовер
      Работа этого кроссовера может быть описана следующим образом.
Выбирается точка сечения (рис. 33), затем первая часть одного родителя ко-
пируется в первого потомка (рис. 34). Во вторую часть потомка копируются
гены второго родителя (рис. 35). Если такие гены уже встречаются в потом-
ке, то они пропускаются, а оставшуюся часть потомка дополняют гены пер-
вого родителя. Аналогичный алгоритм и для второго потомка.
                                        V 1 = 12 | 543
                                        V 2 = 35 | 421
                          Рис.33. Точка сечения кроссовера

  V 11 = 1 2 _ _ _                      V 11 = 1 2 4 _ _               V 11 = 1 2 4 5 3
Рис.34. Потомок V11                 Рис.35. Потомок V11              Рис.36. Потомок V11

                                               Мутация
Мутация работает по следующему принципу. Выбираются случайным обра-
зом два города в хромосоме и меняются местами.
                                        V1 = 1 2 5 4 3
                                        V 1′ = 1 3 5 4 2
            Рис.37. Мутация хромосомы V1 (2 и 5 элемент меняются местами)

“Жадная мутация”
      “Жадная мутация” (greedy reconnection) состоит в упорядочивании по-
следовательности городов. Ее применение помогает хорошо искать локаль-
ные оптимумы. Сначала случайным образом выбираются две точки сечения
в хромосоме (рис.38) так, чтобы между ними было по крайне мере 2 города.
Затем последовательность городов между точками сечения упорядочивает-
ся: они переставляются в зависимости от близости друг к другу. В нашем
случае среди городов 2, 5 и 4 определяется город, ближайший к городу 1.
Пусть, например, это город 5. Он ставится следом за городом 1. Затем среди
городов 2 и 4 определяется ближайший к городу 5. Пусть, например, это го-

Страницы