Сб. Фев 24th, 2024

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

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

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

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

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

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

Для устранения этого недо­статка в генетических алгоритмах используют схемы (схематы или шаблоны), представляющие собой фрагменты решений или хро­мосом, которые желательно сохранить в процессе эволюции. При использовании схем в генетическом алгоритме вводится новый алфавит {0,1,*}, где * интерпретируется как «имеет значение 1 или 0». Например:

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

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

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

Ads Blocker Image Powered by Code Help Pro

Обнаружен блокировщик рекламы! Пожалуйста, обратите внимание на эту информацию.

We\'ve detected that you are using AdBlock or some other adblocking software which is preventing the page from fully loading.

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

Пожалуйста, добавьте tehnar.info к вашему белому списку блокирования объявлений или отключите программное обеспечение, блокирующее рекламу.

Powered By
100% Free SEO Tools - Tool Kits PRO