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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

28
BEDCA)(ABEDCV=(BEDCA)V
≡
≠
13
0100000010001000000110000
.
ГА может создать некоторые хромосомы, не имеющие путевого представ-
ления (невалидные решения). Это может произойти при создании начальной
популяции и при действии стандартных генетических операторов . Напри-
мер, при одноточечном кроссовере может возникнуть следующая ситуация:
000,0000010001 100000100010
100,0010001000 001000001000
2
1
|=V
|=V
0000000010001 001000001000
4
=V
.
Рис.44. Пример скрещивания, в результате которого получилось неверное решение
4
V
Очевидно, что такое решение неправильно, т.к. город C ни разу не посещен.
Таблица неверного решения
1 2 3 4 5
A
10000
B
01000
4
V
=
C
00000
D
00100
E
01000
Также неправильное решение появится в результате скрещивания
1
V
и
3
V
.
В этом случае необходимо проводить восстановление решений (добавлять
единицы в недостающих местах или убирать лишние). Например, восстанов-
ленное решение V4 может иметь вид:
0000100100000100100010000
4
=V
.
Фокс (Fox) и Макмахон (McMahon) рассматривали маршрут как двоичную
матрицу, в которой элемент Х
ij
содержит 1, если город i стоит в маршруте
раньше, чем город j.
Существует также альтернативное матричное представление, при ко-
тором в матрицу в элемент X
ij
записывается 1 только в том случае, если i-й
город непосредственно предшествует j-му(является соседом, стоящим непо-
средственно перед j-м городом).
Для этих представлений также разработаны способы скрещивания и
мутации, но они достаточно сложны, поэтому в алгоритмах чаще использу-
ются рассмотренные ранее способы символьного кодирования хромосом.
5.
Непрерывные генетические алгоритмы
Математический аппарат непрерывных ГА
При работе с оптимизационными задачами в непрерывных простран-
ствах вполне естественно представлять гены напрямую вещественными чис-
лами. В этом случае хромосома есть вектор вещественных чисел. Длина 
                                        28
V3 (BEDCA) = 0000110000000100010001000 ≠ V1 (ABEDC ≡ BEDCA) .
 ГА может создать некоторые хромосомы, не имеющие путевого представ-
ления (невалидные решения). Это может произойти при создании начальной
популяции и при действии стандартных генетических операторов . Напри-
мер, при одноточечном кроссовере может возникнуть следующая ситуация:
                        V1 = 100000100000 | 0010001000100,
                        V2 = 000010001010 | 0000010001000,
                        V4 = 100000100000 0000010001000 .
Рис.44. Пример скрещивания, в результате которого получилось неверное решение V4
Очевидно, что такое решение неправильно, т.к. город C ни разу не посещен.

                            Таблица неверного решения
                                        1 2 3 4 5
                                  A 1 0 0 0 0
                                  B 0 1 0 0 0
                           V4 = C 0 0 0 0 0

                                  D 0 0 1 0 0
                                  E 0 1 0 0 0
Также неправильное решение появится в результате скрещивания V1 и V3 .
В этом случае необходимо проводить восстановление решений (добавлять
единицы в недостающих местах или убирать лишние). Например, восстанов-
ленное решение V4 может иметь вид:
                      V4 = 10000 01000 00010 00100 00001 .
Фокс (Fox) и Макмахон (McMahon) рассматривали маршрут как двоичную
матрицу, в которой элемент Хij содержит 1, если город i стоит в маршруте
раньше, чем город j.
     Существует также альтернативное матричное представление, при ко-
тором в матрицу в элемент Xij записывается 1 только в том случае, если i-й
город непосредственно предшествует j-му(является соседом, стоящим непо-
средственно перед j-м городом).
     Для этих представлений также разработаны способы скрещивания и
мутации, но они достаточно сложны, поэтому в алгоритмах чаще использу-
ются рассмотренные ранее способы символьного кодирования хромосом.
            5. Непрерывные генетические алгоритмы
   Математический аппарат непрерывных ГА
      При работе с оптимизационными задачами в непрерывных простран-
ствах вполне естественно представлять гены напрямую вещественными чис-
лами. В этом случае хромосома есть вектор вещественных чисел. Длина

Страницы