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

                                          16
n3 таких коротких схем низкого порядка и с высокой приспособленностью.
Он называл это явление неявным параллелизмом. Для решения реальных за-
дач присутствие неявного параллелизма означает, что большая популяция
имеет больше возможностей локализовать решение экспоненциально быст-
рее популяции с меньшим числом особей.
Теорема схем (The schema theorem)
      Теорема схем является одной из основных теорем теории ГА. Она по-
лучена для канонического генетического алгоритма.
      Предположим, что у нас есть популяция двоичных строк длины n. Ве-
роятность проведения кроссовера равна Рс. Тип кроссовера � � одноточеч-
ный. Пусть определяющая длина схемы S равна δ(S), а её приспособлен-
ность f(S). Доля строк, соответствующих схеме S в текущем поколении t,
равна m(H,t). Нас интересует, какая доля строк, соответствующих схеме S
будет присутствовать в популяции в следующем поколении � �        m(S,t+1).
Вычислим, с какой вероятностью кроссовер разрушит уже имеющуюся схе-
му. Очевидно, что если точка разрыва не попадает внутрь уже имеющейся
схемы, то схема не будет разрушена. Т.е. если Рс*δ(S)/(n-1) � �     вероят-
ность того, что точка разрыва попадет внутрь схемы, то 1-Рс*δ(Н)/(L-1) � �
вероятность того, что кроссовер не разрушит схему. Согласно стратегии от-
бора канонического ГА шансы особи принять участие в скрещивании вы-
числяются в соответствии с отношением f/fср, где f � � значение приспо-
собленности данной особи, а fср - средняя приспособленность. Таким обра-
зом, вероятность того, что строка соответствующая схеме Н будет участво-
вать в скрещивании равна m(S,t)*f(S,t)/fср(t). Принимая во внимание вероят-
ность разрушения схемы кроссовером, можно сформулировать первоначаль-
ную теорему схем (Холланд, 1975):
                                            f(S,t) ⎡           ∂(S) ⎤
                     m(S,t + 1 ) ≥ m(S,t)              1 − p           .
                                            f cp (t) ⎢⎣        n − 1⎥⎦
                                                             c


      Одним из недостатков данной теоремы является то, что в ней отсутст-
вует влияние мутации на создание и разрушение схем. Если считать, что ве-
роятность мутации равна Pm, а порядок схемы Н равен о(S), то вероятность
того, что мутация не разрушит схему равна (1-Pm)o(S) . Т.е. если мутирующий
разряд не попадает ни на одну фиксированную позицию внутри схемы, то
она не изменяется. С учетом этого исправленная теорема схем выглядит сле-
дующим образом (Холланд, 1992):
                                          f(S,t) ⎡         ∂(S) ⎤
                    m(S,t +1 ) ≥ m(S,t)            ⎢1 − pc      ⎥( 1 − p m )o(S)
                                          f cp (t) ⎣       n − 1⎦
      В то время как теорема схем предсказывает рост примеров хороших
схем, сама теорема весьма упрощенно описывает поведение ГА. Прежде все-