Предыдущая страница реферата | 1  2  3 | Следующая страница реферата

                                       (2)

где n- число анализируемых хромосом.

Число копий хромосомы, переходящее в следующее положение, иногда определяют на основе выражения

 .                                          (3)

Далее, согласно схеме классического ПГА, выполняется оператор мутации. Считают, что мутация - вторичный механизм в ГА.

Понятие "схема" (схемата), согласно Холланду, есть шаблон, описывающий подмножество стрингов, имеющих подобные значения в некоторых позициях стринга [8]. Для этого вводится новый алфавит {0,1,*}, где * - означает: не имеет значения 1 или 0. Для вычисления числа схем или их границы в популяции требуются точные значения о каждом стринге в популяции.

Для количественной оценки схем введены 2 характеристики [1,2]: порядок схемы - О(H);  определенная длина схемы - L(H). Порядок схемы - число закрепленных позиций (в двоичном алфавите - число единиц и нулей), представленных в шаблоне.

Предположим, что заданы шаг (временной) t, m примеров частичных схем H, содержащихся в популяции A(t). Все это записывают как m=m(H,t) - возможное различное число различных схем H в различное время t.

В течение репродукции стринги копируются согласно их ЦФ или более точно: стринг A(i) получает выбор с вероятностью, определяемой выражением (1).

После сбора непересекающихся популяций размера n с перемещением из популяции A(t) мы ожидаем иметь m(H,t+1) представителей схемы H в популяции за время t+1. Это вычисляется уравнением

m(H,t+1)=m(H,t) * n * f(H)/sum[ f(j) ],     (4)

где f(H) – есть средняя ЦФ стрингов, представленных схемой H за время t.

Если обозначить среднюю ЦФ всей популяции как f*=sum[f(j)]/n,  тогда

m(H,t+1)=m(H,t)*f(H)/f* .                           (5)

Правило репродукции Холланда: схема с ЦФ выше средней “живет”, копируется и с ниже средней ЦФ “умирает” [1].

Предположим, что схема H остается с выше средней ЦФ с величиной c?f*, где c-константа. Тогда выражение (5) можно модифицировать так

m(H,t+1)=m(H,t)*(f*+c*f*)/f*=(1+c)*m(H,t)  (6)

Некоторые исследователи считают, что репродукция может привести к экспоненциальному уменьшению или увеличению схем, особенно если выполнять генерации параллельно [3-5].

Отметим, что если мы только копируем старые структуры без обмена, поисковое пространство не увеличивается и процесс затухает. Потому и используется ОК. Он создает новые структуры и увеличивает или уменьшает число схем в популяции.

Очевидно, что нижняя граница вероятности выживания схемы после применения ОК может вычислена для любой схемы. Так как схема выживает, когда точка ОК попадает вне "определенной длины", то вероятность выживания для простого ОК  запишется

P(s)=1-O(H)/(L-1).                                 (7)

Если ОК выполняется посредством случайного выбора, например, с вероятностью P(ОК), то вероятность выживания схемы определится

P(s)?1-P(ОК)*L(H)/(L-1).                           (8)

Допуская независимость репродукции (ОР) и ОК, получим [1]:

 m(H,t+1) ? m(H,t) * f(H)/f* *[1-P(ОК) * 

Рекомендуем скачать другие рефераты по теме: сочинение язык, доклад по биологии.





Предыдущая страница реферата | 1  2  3 | Следующая страница реферата