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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

27
род 4. Ставим его за городом 5. На последнее место ставим оставшийся го-
род 2. В результате имеем модифицированную хромосому (рис. 41).
3_ _ _ 1
3|4 5 2| 1
1
1
=V
=V
'
Рис.38. Шаг 1
_3 _ 5 1
1
=V
'
Рис.39. Шаг 2
3 _ 4 5 1
1
=V
'
Рис.40. Шаг 3
3 2 4 5 1
1
=
′
V
Рис.41. Потомок, полученный при мутации
1
V
4. Матричное представление
Для кодирования хромосомы также может служить бинарная матрица
V
, где
1
=V
ct
, если город
c
посещен в момент времени
t
(находится в мар-
шруте в позиции t), в противном случае
=V
ct
0.
Например, пути ABEDC и CEDBA могут быть представлены в виде сле-
дующих матриц (строки-города, столбцы-время):
Таблица пути ABEDC
1 2 3 4 5
A
1 0 0 0 0
B
0 1 0 0 0
V
1
=
C
0 0 0 0 1
D
0 0 0 1 0
E
0 0 1 0 0
Таблица пути CEDBA
1 2 3 4 5
A
00001
B
00010
V
2
=
C
10000
D
00100
E
01000
A
B
C
D
E
t=1
t=2
t=4
t=3
t=5
Рис.42. Путь ABEDC
A
B
C
D
E
t=5
t=4
t=3
t=2
t=1
Рис.43. Путь CEDBA
Матрицы могут быть представлены в виде следующих хромосом:
0100010000001000000100010
0010000001000101000001000
2
1
=V
=V
Необходимо отметить, что города в одинаковой последовательности, но с
разными стартовыми точками или с противоположным направлением коди-
руются разными матрицами, т.е. разными хромосомами. Например: 
                                                           27
род 4. Ставим его за городом 5. На последнее место ставим оставшийся го-
род 2. В результате имеем модифицированную хромосому (рис. 41).
              V1 = 1 | 2 5 4 | 3                                                V1' = 1 5 _ _3
              V1' = 1 _ _ _ 3                                                   Рис.39. Шаг 2
              Рис.38. Шаг 1
                  V1' = 1 5 4 _ 3                                    V 1′ = 1 5 4 2 3
                  Рис.40. Шаг 3                        Рис.41. Потомок, полученный при мутации V1

                                      4. Матричное представление
      Для кодирования хромосомы также может служить бинарная матрица
V , где Vct = 1 , если город c посещен в момент времени t (находится в мар-
шруте в позиции t), в противном случае Vct = 0.
Например, пути ABEDC и CEDBA могут быть представлены в виде сле-
дующих матриц (строки-города, столбцы-время):
              Таблица пути ABEDC                                      Таблица пути CEDBA
                       1   2         3   4   5                              1    2   3   4         5
                   A   1   0         0   0   0                         A    0    0   0   0         1
                   B   0   1         0   0   0                         B    0    0   0   1         0
       V 1=        C   0   0         0   0   1             V 2=        C    1    0   0   0         0
                   D   0   0         0   1   0                         D    0    0   1   0         0
                   E   0   0         1   0   0                         E    0    1   0   0         0

                    t=1                                                           t=5
              A                                                             A



                                                     t=5                                                   t=1

                                                 C                                                     C
       t=2                                                            t=4
   B                            t=4                               B                           t=3
                           D                                                             D




                       E       t=3                                                   E       t=2

              Рис.42. Путь ABEDC                                            Рис.43. Путь CEDBA

Матрицы могут быть представлены в виде следующих хромосом:
                                         V1 = 1000001000000010001000100
                                         V2 = 0000100010100000010001000
Необходимо отметить, что города в одинаковой последовательности, но с
разными стартовыми точками или с противоположным направлением коди-
руются разными матрицами, т.е. разными хромосомами. Например:

Страницы