Фундаментальная теорема генетического алгоритма

Пусть в момент времени / в популяции S(t) содержится мно­жество хромосом а схема Я строится на основе ал­фавита V= {0,1,*}. Тогда схема может быть определена на двоич­ной хромосоме длины _. Очевидно, что для алфавита мощности М существует схем и схем, содержащихся в популя­ции размера п, поскольку стринг представляется двумя схемами.

Для количественной оценки схем введем две характеристики: порядок схемы 0{Н) и определенная длина схемы Порядок

схемы определяет число закрепленных позиций (в двоичном ал­фавите - число единиц и нулей), представленных в шаблоне. Оп­ределенная длина схемы — это расстояние между первой и по­следней числовой позицией стринга.

Предположим, что заданы шаг по времени t и т примеров схем Я, содержащихся в популяции S(t), которые определяют возмож­ное число различных схем Я при заданном t, т.е. т = т(Н, t).

В процессе репродукции вероятность попадания хромосомы

в репродуцированное множество равна т.е. зави-

сит от значения целевой функции. За время t + 1 в популяции S(t) ожидается получить т(Н, t+1) представителей схемы Я, которое вычисляется по формуле

гдеДЯ) - среднее значение целевой функции хромосом, представленных схемой Я за время /.

Так как среднее значение целевой функции для всей популя­ции равно

Из этой формулы можно сделать вывод о том, что увеличение количества частных схем определяется отношением среднего значения целевой функции схемы к среднему значению целевой функции популяции. Поэтому схема, для которой значение целе­вой функцииДЯ) выше имеет большую вероятность копи­рования.

Правило Холланда: Схема со значением целевой функции вы­ше среднего живет и копируется, а схема со значением ниже среднего умирает.

Если предположить, что схема Я является жизнеспособной, то Тогда значение целевой функции для схемы Я

можно выразить через среднее значение для всей популяции, например, следующим образом: где с — константа.

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

Если принять значение с постоянным во времени, то за пери­од можно вычислить количество представителей схемы Я по формуле из которой следует, что ре­продукция может приводить к экспоненциальному увеличению (с > 0) или уменьшению (с < 0) числа схем.

Лемма. Если на некотором шаге генетического алгоритма Р₁ есть вероятность того, что хромосома А порождает потомка, и Р₂ есть вероятность, что А уничтожается, то ожидаемое число по­томков хромосомы А равно

Вероятность выживания хромосомы А на шаге t после опера­ции репродукции определяется по формуле где t = 1, 2,... , g; g - число шагов (генераций) генетического ал­горитма. Значение вероятности выживания хромосомы изменя­ется после операций кроссинговера и мутации. Использование оператора кроссинговера может вызывать увеличение или умень­шение числа схем в популяции. Если кроссинговер не применя­ется, то обмен между хромосомами отсутствует, поэтому поиско­вое пространство не увеличивается, и процесс затухает.

Вероятность выживания схемы после применения оператора кроссинговера определяется по формуле

где О(Н) — порядок схемы; L - длина стринга.

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

где L(H) — определенная длина схемы.

Приведенное выражение свидетельствует о том, что вероят­ность выживания схемы уменьшается при возрастании Р(СО).

Вычислим число схем Н в новой генерации после операций репродукции и кроссинговера, допуская их взаимную независи­мость:

Из этого выражения следует, что число схем зависит

от значений целевой функции для схемы и для всей популяции, а также от длины схемы

Рассмотрим влияние мутации на выживание схем. Известно, что единственная хромосома выживает с вероятностью где Р(МО) — вероятность оператора мутации. Если учесть тот факт, что частная схема выживает в случаях, когда выживает каж­дая из L(H) закрепленных позиций схемы, то для малых величин вероятность выживания схемы при мутации может быть представлена выражением [23]:

С учетом вышесказанного и согласно [26] для частной схемы Н можно определить ожидаемое число копий в следующей гене­рации после реализации операторов репродукции, кроссингове­ра и мутации по следующей формуле:

Данная формула отражает фундаментальную теорему генети­ческого алгоритма, которая определяет асимптотическое число схем, выживающих при его реализации на каждой итерации. На­иболее существенное влияние на число выживающих схем ока­зывают значения целевых функций отдельной схемы и всей по­пуляции, а эффективность реализации генетических алгоритмов зависит от размера строительных блоков.