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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

29
хромосомы будет совпадать с длиной вектора-решения оптимизационной за-
дачи, иначе говоря, каждый ген будет отвечать за одну переменную. Гено-
тип объекта становится идентичным его фенотипу.
Вышесказанное определяет список основных преимуществ непрерыв-
ных алгоритмов.
1. Использование непрерывных генов делает возможным поиск в боль-
ших пространствах (даже в неизвестных), что трудно
делать в случае
двоичных генов, когда увеличение пространства поиска сокращает
точность решения при неизменной длине хромосомы.
2. Одной из важных черт непрерывных ГА является их способность к ло-
кальной настройке решений.
3. Использование непрерывных алгоритмов для представления решений
удобно, поскольку близко к постановке большинства прикладных за-
дач. Кроме того, отсутствие операций
кодирования/декодирования, ко-
торые необходимы в классическом ГА, повышает скорость работы ал-
горитма.
Как известно, появление новых особей в популяции канонического ГА
обеспечивают несколько биологических операторов: отбор, скрещивание и
мутация. В качестве операторов отбора особей в родительскую пару здесь
подходят любые известные : пропорциональный, турнирный, отбор усечени-
ем. Однако операторы скрещивания
и мутации не годятся: в классических
реализациях они работают с битовыми строками. Нужны собственные реа-
лизации, учитывающие специфику непрерывных алгоритмов. Оператор
скрещивания непрерывного ГАпорождает одного или нескольких потомков
от двух хромосом. Собственно говоря, требуется из двух векторов вещест-
венных чисел получить новые векторы по каким-либо законам. Большинство
непрерывных алгоритмов генерируют
новые векторы в окрестности роди-
тельских пар. Для начала рассмотрим простые и популярные кроссоверы.
Пусть C
1
= (c
1
1
,c
2
1
,…,c
n
1
) и C
2
= (c
1
2
,c
2
2
,…,c
n
2
) – две хромосомы, вы-
бранные оператором селекции для скрещивания.
Плоский кроссовер (flat crossover)
Создается потомок H = (h
1
,…,h
k
,…,h
n
), где h
k
, k=1,…, n – случайное
число из интервала [c
k
min
, c
k
max
], c
k
min
= min(c
k
1
,c
k
2
), c
k
max
= max(c
k
1
,c
k
2
).
Простейший кроссовер (simple crossover)
Случайным образом выбирается число k из интервала {1,2,…,n-1} и
генерируются два потомка H1 = (c
1
1
,c
2
1
,…,c
k
1
,c
k+1
2
,…,c
n
2
) и H
2
=
(c
1
2
,c
2
2
,…,c
k
2
,c
k+1
1
,…,c
n
2
).
Арифметический кроссовер (arithmetical crossover) 
                                      29
хромосомы будет совпадать с длиной вектора-решения оптимизационной за-
дачи, иначе говоря, каждый ген будет отвечать за одну переменную. Гено-
тип объекта становится идентичным его фенотипу.
      Вышесказанное определяет список основных преимуществ непрерыв-
ных алгоритмов.
   1. Использование непрерывных генов делает возможным поиск в боль-
      ших пространствах (даже в неизвестных), что трудно делать в случае
      двоичных генов, когда увеличение пространства поиска сокращает
      точность решения при неизменной длине хромосомы.
   2. Одной из важных черт непрерывных ГА является их способность к ло-
      кальной настройке решений.
   3. Использование непрерывных алгоритмов для представления решений
      удобно, поскольку близко к постановке большинства прикладных за-
      дач. Кроме того, отсутствие операций кодирования/декодирования, ко-
      торые необходимы в классическом ГА, повышает скорость работы ал-
      горитма.
      Как известно, появление новых особей в популяции канонического ГА
обеспечивают несколько биологических операторов: отбор, скрещивание и
мутация. В качестве операторов отбора особей в родительскую пару здесь
подходят любые известные : пропорциональный, турнирный, отбор усечени-
ем. Однако операторы скрещивания и мутации не годятся: в классических
реализациях они работают с битовыми строками. Нужны собственные реа-
лизации, учитывающие специфику непрерывных алгоритмов. Оператор
скрещивания непрерывного ГАпорождает одного или нескольких потомков
от двух хромосом. Собственно говоря, требуется из двух векторов вещест-
венных чисел получить новые векторы по каким-либо законам. Большинство
непрерывных алгоритмов генерируют новые векторы в окрестности роди-
тельских пар. Для начала рассмотрим простые и популярные кроссоверы.
      Пусть C1 = (c11,c21, ,cn1) и C2 = (c12,c22, ,cn2) – две хромосомы, вы-
бранные оператором селекции для скрещивания.
Плоский кроссовер (flat crossover)
     Создается потомок H = (h1, ,hk, ,hn), где hk, k=1, , n – случайное
число из интервала [ckmin, ckmax], ckmin = min(ck1,ck2), ck max = max(ck1,ck2).
Простейший кроссовер (simple crossover)
       Случайным образом выбирается число k из интервала {1,2, ,n-1} и
генерируются два потомка H1 = (c11,c21, ,ck1,ck+12, ,cn2) и H2 =
(c12,c22, ,ck2,ck+11, ,cn2).
Арифметический кроссовер (arithmetical crossover)

Страницы