Автоматизированное проектирование. Норенков И.П. - 117 стр.

UptoLike

ВУЗ: 

МГТУ им. Баумана | Москва

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

Рубрика: 

%!#*%!#&F*:,$* $I*:+*
F*)&* :&)#*'! +($*,#)KH (*L*)&M
5@!"! 4
4#%7+ (0#6'='9) — позиция, занимаемая геном в хромосоме;
8$*#&'0 — экземпляр хромосомы, генотип представляет совокупность внутренних параметров
проектируемого с помощью ГА объекта;
8$*#E#*- — множество всех возможных генотипов;
E7*%='9 0#4$6*#+&' (приспособленности) F — целевая функция;
E$*#&'0 — совокупность генотипа и соответствующего значения F, под фенотипом часто пони-
мают совокупность выходных параметров синтезируемого с помощью ГА объекта.
"84,-
42 @.0.-+A.,7+2 :D@
48+-/.
Вычислительный процесс начинается с генерации исходно-
го поколения — множества, включающего N хромосом, N — размер популяции. Генерация выполня-
ется случайным выбором аллелей каждого гена.
Далее организуется циклический процесс смены поколений:
for (k=0; k<G; k++)
{ for (j=0; j<N; j++)
{ D6&)" ")1,.#(/25)7 8$"6 @")%)2)%;
F")22):#";
='.$>,,;
9>#+5$ C'+5>,, 8)(#3+)2., F 8).)%5):;
G#(#5>,4;
}
H$%#+$ .#5'?#*) 8)5)(#+,4 +):6%;
}
Для каждого витка внешнего цикла генетического алгоритма выполняется внутренний цикл, на
котором формируются экземпляры нового (следующего за текущим) поколения. Во внутреннем цик-
ле повторяются операторы выбора родителей, кроссовера родительских хромосом, мутации, оценки
приспособленности потомков, селекции хромосом для включения в очередное поколение.
Рассмотрим алгоритмы выполнения операторов в простом генетическом алгоритме.
I.2#" "#-'&$4$ ;. Этот оператор имитирует естественный отбор, если отбор в родительскую па-
ру хромосом с лучшими значениями функции полезности F более вероятен. Например, пусть F тре-
буется минимизировать. Тогда вероятность S
i
выбора родителя с хромосомой C
i
можно рассчитать по
формуле
N
S
i
= (F
max
-F
i
) /
∑
(F
max
- F
j
) (4.31)
j=W
где F
max
— наихудшее значение целевой функции F среди экземпляров (членов) текущего поколения,
F
i
— значение целевой функции i-го экземпляра.
Правило (4.31) называют 0")('4 #/ %#4$+) "74$&%'. Если в колесе рулетки выделить секторы,
пропорциональные значениям F
max
-F
i
, то вероятности попадания в них суть P
i
, определяемые в соот-
ветствии с (4.31).
+-0B.-. Пусть N=4, значения F
i
и P
i
приведены в табл. 4.2.
iF
i
F
max
-F
i
P
i
1 2 5 0,5
27 0 0
36 1 0,1
4 3 4 0,4
M:BD+=: 4.2
&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*, #&($"!)&*
117
 5@!"! 4                                   %!#*%!#&F*:,$*         $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M

      4#%7+ (0#6'='9) — позиция, занимаемая геном в хромосоме;
      8$*#&'0 — экземпляр хромосомы, генотип представляет совокупность внутренних параметров
проектируемого с помощью ГА объекта;
      8$*#E#*- — множество всех возможных генотипов;
      E7*%='9 0#4$6*#+&' (приспособленности) F — целевая функция;
      E$*#&'0 — совокупность генотипа и соответствующего значения F, под фенотипом часто пони-
мают совокупность выходных параметров синтезируемого с помощью ГА объекта.
      "84,-42 @.0.-+A.,7+2 :D@48+-/. Вычислительный процесс начинается с генерации исходно-
го поколения — множества, включающего N хромосом, N — размер популяции. Генерация выполня-
ется случайным выбором аллелей каждого гена.
      Далее организуется циклический процесс смены поколений:

for (k=0; k,, 8)(#3+)2., F 8).)%5):;
      G#(#5>,4;
   }
   H$%#+$ .#5'?#*) 8)5)(#+,4 +):6%;
}
     Для каждого витка внешнего цикла генетического алгоритма выполняется внутренний цикл, на
котором формируются экземпляры нового (следующего за текущим) поколения. Во внутреннем цик-
ле повторяются операторы выбора родителей, кроссовера родительских хромосом, мутации, оценки
приспособленности потомков, селекции хромосом для включения в очередное поколение.
     Рассмотрим алгоритмы выполнения операторов в простом генетическом алгоритме.
     I.2#" "#-'&$4$;. Этот оператор имитирует естественный отбор, если отбор в родительскую па-
ру хромосом с лучшими значениями функции полезности F более вероятен. Например, пусть F тре-
буется минимизировать. Тогда вероятность Si выбора родителя с хромосомой Ci можно рассчитать по
формуле
                            N
         Si = (Fmax-Fi) / ∑ (Fmax - Fj)                                                                 (4.31)
                           j=W
где Fmax — наихудшее значение целевой функции F среди экземпляров (членов) текущего поколения,
Fi — значение целевой функции i-го экземпляра.
     Правило (4.31) называют 0")('4#/ %#4$+) "74$&%'. Если в колесе рулетки выделить секторы,
пропорциональные значениям Fmax-Fi, то вероятности попадания в них суть Pi, определяемые в соот-
ветствии с (4.31).
     + - 0 B . - . Пусть N=4, значения Fi и Pi приведены в табл. 4.2.
                                                                                          M:BD+=: 4.2

                      i                     Fi                   Fmax-Fi             Pi

                     1                      2                       5               0,5

                     2                      7                       0                0

                     3                      6                       1               0,1

                     4                      3                       4               0,4


 &.+.)$(*),$" . !"#$%!#&'&($"!))$*                  +($*,#&($"!)&*                                         117

Страницы