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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

23
второй точки кроссовера. Наконец, города, уже представленные в потомках,
удаляются (рис.16), и оставшиеся элементы копируются вместо пустых про-
белов потомка, начиная со второй точки сечения кроссовера (рис. 17).
[2 1 3 5 4]
Рис.15. Список городов во втором родителе
[2 1 3 5 4] => [1 3 4]
Рис.16. Удаление дублируемых городов
1
2
3
4
5
t=4
t=2
t=1
t=3
t=5
Рис.17. Потомок
42513
7
=V
Циклический кроссовер
В циклическом кроссовере каждый город берется от одного из роди-
телей. Первый город потомка берется от первого родителя. Второй город по-
томка берется у второго родителя из последней позиции (рис.19). В данном
случае мы не можем взять его от второго родителя, так как этот город уже
находится в
хромосоме, поэтому мы его берем от первого родителя, и т.д. до
тех пор, пока новая хромосома не будет создана.
3 4 5 2 1
1
=V
1 2 4 5 3
6
=V
1
8
=V
Рис.18. Копирование города из 1-го родителя
3 4 5 2 1
1
=
V
1 2 4 5 3
6
=
V
1
8
=
V
3
Рис.19. Копирование следующего города
1
2
3
4
5
t=1
t=4
t=3
t=2
t=5
Рис. 20. Потомок
15423
8
=V
Кроссовер рекомбинации ребер
Кроссовер рекомбинации ребер делает потомство только с помощью
ребер, представленных в обоих родителях. Сначала из двух родителей 
                                                23
второй точки кроссовера. Наконец, города, уже представленные в потомках,
удаляются (рис.16), и оставшиеся элементы копируются вместо пустых про-
белов потомка, начиная со второй точки сечения кроссовера (рис. 17).

                [2 1 3 5 4]                                       [2 1 3 5 4] => [1 3 4]
 Рис.15. Список городов во втором родителе                 Рис.16. Удаление дублируемых городов
                                          t=4
                                      1



                                                                        t=5

                                                                    3
                                t=2
                            2                        t=1
                                                4




                                            5       t=3

                                  Рис.17. Потомок V7 = 42513
Циклический кроссовер
      В циклическом кроссовере каждый город берется от одного из роди-
телей. Первый город потомка берется от первого родителя. Второй город по-
томка берется у второго родителя из последней позиции (рис.19). В данном
случае мы не можем взять его от второго родителя, так как этот город уже
находится в хромосоме, поэтому мы его берем от первого родителя, и т.д. до
тех пор, пока новая хромосома не будет создана.
              V1 = 1 2 5 4 3                                                V1 = 1 2 5 4 3
              V6 = 3 5 4 2 1                                                V6 = 3 5 4 2 1

              V8 = 1                                                        V8 = 1 3
Рис.18. Копирование города из 1-го родителя                Рис.19. Копирование следующего города
                                          t=1
                                      1



                                                                            t=5

                            t=4                                         3

                        2                            t=3
                                                4




                                            5       t=2

                                  Рис. 20. Потомок V8 = 15423
Кроссовер рекомбинации ребер
      Кроссовер рекомбинации ребер делает потомство только с помощью
ребер, представленных в обоих родителях. Сначала из двух родителей

Страницы