Разновидности генетических алгоритмов

Генетический алгоритм Девиса  включает следующие шаги:

1. Инициализация популяции хромосом.
2. Оценка каждой хромосомы в популяции.
3. Создание новых хромосом посредством изменения и скре­щивания текущих хромосом (применение операторов мутации и кроссинговера).
4. Устранение хромосом из популяции для замены их новыми.
5. Оценка новых хромосом и включение их в популяцию.
6. Проверка условия исчерпания ресурса времени, отведенно­ го на поиск оптимального решения (если время исчерпано, то ра­бота алгоритма завершается и производится возврат к наилучшей хромосоме, в противном случае — переход к шагу 3).

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

1. Стринг (хромосома)выбирается случай­ным образом из текущей популяции.
2. Из множестваслучайным образом вы­бираются два числаи определяются значения и
3. Из хромосомы В формируется новая хромосома путем ин­версии (обратного порядка) сегмента, лежащего справа от пози­ции Xj и слева от позиции х₂ в хромосоме В. После применения оператораинверсии строка В примет вид

Например, для строкипри выбореи  и соответственно х_х=2, х₂=6 результатом инверсии будет 

Операции кроссинговера и мутации, используемые в простом ГА, изменяют структуру хромосом, в том числе разрушают удач­ные фрагменты найденных решений, что уменьшает вероятность нахождения глобального оптимума.

схема (*0000) соответствует двум стрингам {10000 и 00000};

схема (*111*) соответствует четырем строкам НПО,

01111,11111};

схема (0*1**) может соответствовать восьми пятизначным стрингам.

В общем случае хромосома длиной L максимально может иметьсхем (шаблонов), но толькоразличных альтернатив­ных стрингов. Это следует из факта, что схеме (**) в общем случае могут соответствовать 3²=9 стрингов, а именно {**, *1, *0, 1*, 0*, 00,01,10 11}, и только 2²=4 альтернативные строки {00,01,10,11}, т. е. одной и той же строке может соответствовать несколько схем.

Если в результате работы генетического алгоритма удалось найти схемы типа (11*** ) и ( **111), то, применив к ним опера­тор кроссинговера, можно получить хромосому (11111), обладаю­щую наилучшим значением целевой функции.

Схемы небольшой длины называются строительными блока­ми. Размер строительных блоков заметно влияет на качество и скорость нахождения результата. Вид строительного блока выби­рается с учетом специфики решаемой задачи, а их разрыв в гене­тических алгоритмах допускается только в исключительных слу­чаях, определяемых пользователем. Например, в схеме (****1) строительным блоком является элемент 1, а в схеме (10***) — со­ставной элемент 10.

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

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

Процедура удаления лишних хромосом в стационарных и поколенческих генетических алгоритмах основана на эвристичес­ких правилах, примерами которых являются следующие:

• случайное равновероятное удаление хромосом;
• удаление хромосом, имеющих худшие значения целевой функции;
• удаление хромосом на основе обратного значения целевой функции;
• удаление хромосом на основе турнирной стратегии.

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

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

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

Пусть в момент времени / в популяции 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) закрепленных позиций схемы, то для малых величин  вероятность выживания схемы при мутации может быть представлена выражением:

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

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