Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

 

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

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

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

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

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

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

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

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

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



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


Эта страница нарушает авторские права

allrefrs.ru - 2018 год. Все права принадлежат их авторам!