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

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

1. Инициализация популяции хромосом.

2. Оценка каждой хромосомы в популяции.

3. Создание новых хромосом посредством изменения и скрещивания текущих хромосом (применение операторов мутации и кроссинговера).

4. Устранение хромосом из популяции для замены их новыми.

5. Оценка новых хромосом и включение их в популяцию.

6. Проверка условия исчерпания ресурса времени, отведенно¬го на поиск оптимального решения (если время исчерпано, то работа алгоритма завершается и производится возврат к наилучшей хромосоме, в противном случае – переход к шагу 3).

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

1. Стринг (хромосома) В = {b_x, b₂,…, b_L} выбирается случай­ным образом из текущей популяции.

2. Из множества Y{0,1,2, L + 1} случайным образом вы­бираются два числа у₁ и у₂ и определяются значения x₁=min{y₁,y₂} и x₂=max{y₁,y₂}.

3. Из хромосомы В формируется новая хромосома путем ин- -Jверсии (обратного порядка) сегмента, лежащего справа от пози­ции x₁ и слева от позиции х₂ вхромосоме В. После применения оператора инверсиистрока В примет вид В'={b₁,…, b_x1,b_x2-1,b_x2-2,…,b_x1+1,b_x2,…,b_L}.

Например, для строки В={1, 2, 3, 4, 5, 6} при выборе у₁=6 и y₂=2 соответственно x₁ =2, x₂= 6 результатом инверсии будет B^’={1, 2, 5, 4, 3, 6}.

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

- схема (*111*) соответствует четырем строкам {01110, 11110, 01111,11111};

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

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

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

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

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

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

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

- случайное равновероятное удаление хромосом;

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

- удаление хромосом на основе обратного значения целевой функции;

- удаление хромосом на основе турнирной стратегии.

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

Тема 11. Мультиагентные системы