Реферат: Генетические алгоритмы

Для количественной оценки схем введены 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(ОК) *

L(H)/(l-L)]. (9)

Из выражения (9) следует, что схемы с выше средней ЦФ и короткой L(H) имеют возможность экспоненциального роста в новой популяции.

Рассмотрим влияние мутации на возможности выживания. ОМ есть случайная альтернативная перестановка элементов в стринге с вероятностью Р(ОМ). Для того, чтобы схема H выжила, все специфические позиции должны выжить. Следовательно, единственная хромосома выживает с вероятностью (1-P(ОМ)) и частная схема выживает, когда каждая из l(H) закрепленных позиций схемы выживает.

1-L(H)*Р(ОМ). (10)

Тогда мы ожидаем, что частная схема H получает ожидаемое число копий в следующей генерации после ОР,ОК ОМ

m(H,t+1)>m(H,t)*f(H)/f**[1-Р(ОК)*l(H)/(l-1)-

l(H)*P(ОМ)]. (11)

Это выражение называется "схема теорем" или фундаментальная теорема ГА [1].

Ответа на вопрос, почему необходимо давать выживание схемам с лучшей ЦФ, нет или он расплывчатый, или каждый раз зависит от конкретной задачи.

Основная теорема ГА, приведенная Холландом, показывает ассимптотическое число схем "выживающих” при реализации ПГА на каждой итерации. Очевидно,что это число, конечно приблизительное и меняется в зависимости от вероятности применения ГА. Особенно сильное влияние на число "выживающих" и "умирающих" схем при реализации ПГА оказывает значение целевой функции отдельной хромосомы и всей популяции.