Вывод 4.5

Вывод 4.4 (влияние мутации)

Вывод 4.2 (влияние скрещивания)

Для некоторой хромосомы из M(k) n S вероятность того, что она будет отобрана для скрещивания и ни один из ее потомков не бу­дет принадлежать к схеме S. ограничена сверху величиной

Эта величина называется вероятностью уничтожения схемы S. Вывод 4.3

Для некоторой хромосомы из М(к) п S вероятность того, что она не будет отобрана для скрещивания либо, что хотя бы один из ее потомков после скрещивания будет принадлежать к схеме S, ограни­чена снизу величиной

d(S)

Рс £_-|

Эта величина называется вероятностью выживания схемы S.

Легко показать, что если данная хромосома принадлежит к схе­ме S и отбирается для скрещивания, а вторая родительская хромосо­ма также принадлежит к схеме S, то оба их потомка тоже будут при­надлежать к схеме S. Выводы 4.2 и 4.3 подтверждают значимость по­казателя охвата схемы d(S) для оценки вероятности уничтожения или выживания схемы.

Рассмотрим теперь влияние мутации на родительский пул М(к). Оператор мутации с вероятностью р_т случайным образом изменяет значение в конкретной позиции с 0 на 1 и обратно. Очевидно, что схе­ма переживет мутацию только в том случае, когда все ее постоянные позиции, останутся после выполнения этой операции неизменными

Хромосома из родительского пула, принадлежащая к схеме S (т.е. хромосома из множества М(к) п S) останется в этой схеме тог­да и только тогда, когда ни один символ этой хромосомы, соответст­вующий постоянным символам схемы S, не изменится в процессе му­тации. Вероятность такого события равна (1 - pm)°^^s\ Этот результат можно представить в форме следующего вывода:

Вероятность того, что некоторая хромосома из М(к) n S будет принадлежать к схеме S после операции мутации, определяется вы­ражением

(1-Pm)^0(s>

Эта величина называется вероятностью выживания схемы S после мутации.

Глава 4. Генетические алгоритмы

Если вероятность мутации р_т мала (р_т «1), то можно считать, что вероятность выживания схемы S после мутации, определенная в выводе 4.4, приближенно равна

1-p_mo(S).

Эффект совместного воздействия селекции, скрещивания и му­тации (выводы 4.1 - 4.4) с учетом факта, что если хромосома из мно­жества M(k) n S дает потомка, соответствующего схеме S, то он будет принадлежать к Р(к + 1) n S, ведет к построению следующей схемы репродукции [7]:

. (4.10)

E[c(S,/c +

Зависимость (4.10) показывает, как изменяется от популяции к популяции количество хромосом, соответствующих данной схеме. Это изменение вызывается тремя факторами, представленными в правой части выражения (4.10), в частности: F(S,k) I F (к) отражает роль среднего значения функции приспособленности, 1 -p_cd(S)/(L- 1) показывает влияние скрещивания и (1 - p_m)^0(S) - влияние мутации. Чем больше значение каждого из этих факторов, тем большим оказы­вается ожидаемое количество соответствий схеме S в следующей по­пуляции. Вывод 4.5 позволяет представить зависимость (4.10) в виде

S)). (4.11)

Для больших популяций зависимость (4.11) можно аппроксими­ровать выражением

c(S,/c ₊ 1)>c(S,/c)^^lfi-Pc-^-Pm0(S)l (4.12)
F(k) V ^L~ ■ '

Из формул (4.11) и (4.12) следует, что ожидаемое количество хромосом, соответствующих схеме S в следующем поколении, можно считать функцией от фактического количества хромосом, принадле­жащих этой схеме, относительной приспособленности схемы, а также порядка и охвата схемы. Заметно, что схемы с приспособленностью выше средней и с малым порядком и охватом характеризуются возра­станием количества своих представителей в последующих популяци­ях. Подобный рост имеет показательный характер, что следует из вы­ражения (4.9). Для больших популяций эту формулу можно заменить рекуррентной зависимостью вида [33]

S^ (4.13)

c(S,/c + 1) c(S,/c)S^. F(k)

Если допустить, что схема S имеет приспособленность на е % выше средней, т.е.

4.7. Основная теорема о генетических алгоритмах 151

F(S,k)=F(k) + eF{k), (4.14)

то при подстановке выражения (4.12) в неравенство (4.11) в предпо­ложении, что е не изменяется во времени, при старте от к - 0 получа-

e = (F(S,k)-F(k))IF(k), (4.15)

т.е. е > 0 для схемы с приспособленностью выше средней и е < 0 -в противном случае.

Равенство (4.15) описывает геометрическую прогрессию Из этого следует, что в процессе репродукции схемы, оказавшиеся луч­ше (хуже) средних, выбираются на очередных итерациях генетическо­го алгоритма в показательно возрастающих (убывающих) количест­вах. Обратим внимание, что зависимости (4.9) - (4.13) основаны на предположении, что функция приспособленности F принимает только положительные значения. При использовании генетических алгорит­мов для решения оптимизационных задач, в которых целевая функ­ция может принимать и отрицательные значения, необходимы некото­рые дополнительные соотношения между оптимизируемой функцией и функцией приспособленности. Конечный результат, получаемый из выражений (4.10) - (4.12), можно сформулировать в форме теоремы Это основная теорема генетических алгоритмов, иначе называемая теоремой о схемах [21].

Дата добавления: 2015-06-04