Генетический алгоритм Девиса включает следующие шаги:
- Инициализация популяции хромосом.
- Оценка каждой хромосомы в популяции.
- Создание новых хромосом посредством изменения и скрещивания текущих хромосом (применение операторов мутации и кроссинговера).
- Устранение хромосом из популяции для замены их новыми.
- Оценка новых хромосом и включение их в популяцию.
- Проверка условия исчерпания ресурса времени, отведенно го на поиск оптимального решения (если время исчерпано, то работа алгоритма завершается и производится возврат к наилучшей хромосоме, в противном случае — переход к шагу 3).
Холланд предложил для генетического алгоритма оператор инверсии, который реализуется по схеме:
- Стринг (хромосома)выбирается случайным образом из текущей популяции.
- Из множестваслучайным образом выбираются два числаи определяются значения и
- Из хромосомы В формируется новая хромосома путем инверсии (обратного порядка) сегмента, лежащего справа от позиции Xj и слева от позиции х2 в хромосоме В. После применения оператораинверсии строка В примет вид
Например, для строкипри выбореи и соответственно хх=2, х2=6 результатом инверсии будет
Операции кроссинговера и мутации, используемые в простом ГА, изменяют структуру хромосом, в том числе разрушают удачные фрагменты найденных решений, что уменьшает вероятность нахождения глобального оптимума.
схема (*0000) соответствует двум стрингам {10000 и 00000};
схема (*111*) соответствует четырем строкам НПО,
01111,11111};
схема (0*1**) может соответствовать восьми пятизначным стрингам.
В общем случае хромосома длиной L максимально может иметьсхем (шаблонов), но толькоразличных альтернативных стрингов. Это следует из факта, что схеме (**) в общем случае могут соответствовать 32=9 стрингов, а именно {**, *1, *0, 1*, 0*, 00,01,10 11}, и только 22=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) числа схем.
Лемма. Если на некотором шаге генетического алгоритма Р1 есть вероятность того, что хромосома А порождает потомка, и Р2 есть вероятность, что А уничтожается, то ожидаемое число потомков хромосомы А равно
Вероятность выживания хромосомы А на шаге t после операции репродукции определяется по формуле где t = 1, 2,… , g; g — число шагов (генераций) генетического алгоритма. Значение вероятности выживания хромосомы изменяется после операций кроссинговера и мутации. Использование оператора кроссинговера может вызывать увеличение или уменьшение числа схем в популяции. Если кроссинговер не применяется, то обмен между хромосомами отсутствует, поэтому поисковое пространство не увеличивается, и процесс затухает.
Вероятность выживания схемы после применения оператора кроссинговера определяется по формуле
где О(Н) — порядок схемы; L — длина стринга.
Если оператор кроссинговера выполняется на основе случайного выбора с вероятностью Р(СО), то вероятность выживания схемы определяется по формуле
где L(H) — определенная длина схемы.
Приведенное выражение свидетельствует о том, что вероятность выживания схемы уменьшается при возрастании Р(СО).
Вычислим число схем Н в новой генерации после операций репродукции и кроссинговера, допуская их взаимную независимость:
Из этого выражения следует, что число схемзависит от значений целевой функции для схемы и для всей популяции, а также от длины схемы
Рассмотрим влияние мутации на выживание схем. Известно, что единственная хромосома выживает с вероятностью где Р(МО) — вероятность оператора мутации. Еслиучесть тот факт, что частная схема выживает в случаях, когда выживает каждая из L(H) закрепленных позиций схемы, то для малых величин вероятность выживания схемы при мутации может быть представлена выражением:
С учетом вышесказанного и согласно для частной схемы Н можно определить ожидаемое число копий в следующей генерации после реализации операторов репродукции, кроссинговера и мутации по следующей формуле:
Данная формула отражает фундаментальную теорему генетического алгоритма, которая определяет асимптотическое число схем, выживающих при его реализации на каждой итерации. Наиболее существенное влияние на число выживающих схем оказывают значения целевых функций отдельной схемы и всей популяции, а эффективность реализации генетических алгоритмов зависит от размера строительных блоков.