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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

12
2. Модели ГА
1. Canonical GA (J. Holland)
Данная модель алгоритма является классической. Она была предложе-
на Джоном Холландом в его знаменитой работе "Адаптация в природных и
исусственных средах" (1975). Часто можно встретить описание простого ГА
(Simple GA, D. Goldberg), он отличается от канонического тем, что использу-
ет либо рулеточный, либо турнирный отбор. Модель канонического ГА име-
ет следующие характеристики.
• Фиксированный размер популяции.
• Фиксированная разрядность генов.
• Пропорциональный отбор.
• Одноточечный кроссовер и одноточечная мутация.
• Следующее поколение формируется из потомков текущего поколения
без "элитизма".
Алгоритм работы ГА (репродуктивный план Холланда) может иметь в
данном случае следующий вид.
1. Инициализация начальной популяции. Положить номер эпохи t=0. Ини-
циализировать случайным образом m генотипов особей и сформиро-
вать из них случайную популяцию. Вычислить приспособленность
особей популяции F(0)=(f
1
(0), .., f
m
(0)), а затем  среднюю приспо-
собленность по популяции
mff
m
i
icp
/)0()0(
1
∑
=
=
.
2. Выбор родителей для скрещивания. Увеличить номер эпохи на едини-
цу: t = t + 1. Определить случайным образом номер первого родителя
}...1{ ml ∈
, назначив вероятность выпадения любого номера h пропор-
циональной величине
(t)f(t)f
cph
/
. Повторным испытанием определить
номер второго родителя k.
3. Формирование генотипа потомков. С заданной вероятностью p
c
про-
вести над генотипами выбранных родителей одноточечный кроссовер.
Далее к каждому из полученных потомков с вероятностью p
M
приме-
нить оператор мутации.
4. Обновление популяции. Поместить потомков в популяцию, предвари-
тельно удалив из нее родителей. Вычислить приспособленности потом-
ков и обновить значение средней приспособленности популяции
(t)f
cp
.
Если формирование популяции не завершено, перейти к шагу 2.
Замечание. В некоторых модификациях этого алгоритма потомки замещают
в популяции не своих родителей, а две случайно выбранные особи. 
                                       12

                                2. Модели ГА
  1. Canonical GA (J. Holland)
      Данная модель алгоритма является классической. Она была предложе-
на Джоном Холландом в его знаменитой работе "Адаптация в природных и
исусственных средах" (1975). Часто можно встретить описание простого ГА
(Simple GA, D. Goldberg), он отличается от канонического тем, что использу-
ет либо рулеточный, либо турнирный отбор. Модель канонического ГА име-
ет следующие характеристики.
   • Фиксированный размер популяции.
   • Фиксированная разрядность генов.
   • Пропорциональный отбор.
   • Одноточечный кроссовер и одноточечная мутация.
   • Следующее поколение формируется из потомков текущего поколения
      без "элитизма".
   Алгоритм работы ГА (репродуктивный план Холланда) может иметь в
данном случае следующий вид.
  1. Инициализация начальной популяции. Положить номер эпохи t=0. Ини-
     циализировать случайным образом m генотипов особей и сформиро-
     вать из них случайную популяцию. Вычислить приспособленность
     особей популяции F(0)=(f1(0), .., fm(0)), а затем � � среднюю приспо-
                                             m

     собленность по популяции f cp ( 0 ) =   ∑f
                                             i =1
                                                    i   (0) / m .

  2. Выбор родителей для скрещивания. Увеличить номер эпохи на едини-
     цу: t = t + 1. Определить случайным образом номер первого родителя
     l ∈ {1 ... m } , назначив вероятность выпадения любого номера h пропор-

     циональной величине f h (t) / f cp (t) . Повторным испытанием определить
     номер второго родителя k.
  3. Формирование генотипа потомков. С заданной вероятностью pc про-
     вести над генотипами выбранных родителей одноточечный кроссовер.
     Далее к каждому из полученных потомков с вероятностью pM приме-
     нить оператор мутации.
  4. Обновление популяции. Поместить потомков в популяцию, предвари-
     тельно удалив из нее родителей. Вычислить приспособленности потом-
     ков и обновить значение средней приспособленности популяции f cp (t) .
     Если формирование популяции не завершено, перейти к шагу 2.
Замечание. В некоторых модификациях этого алгоритма потомки замещают
в популяции не своих родителей, а две случайно выбранные особи.

Страницы