Контрольная работа: Интеллектуальные информационные технологии и системы: генетические алгоритмы

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

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

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

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

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

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

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

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

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

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

2. из множества Y= (0,1,2,…., L +1) случайным образом выбираются два числа у₁ и у₂ и определяются значения х1=min(у₁ ,у₂ ).

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

Например, для строки В=(1,2,3,4,5,6) при выборе у₁ =6 и у₂ =2 и соответственно х₁ =2, х₂ =6 результатом инверсии будет В= (1,2,3,4,5,6).

Операции кроссинговера и мутации, используемые в простом ГА, изменяют структуру хромосом, в том числе разрушают удачные фрагменты найденных решений, что уменьшает вероятность нахождения глобального оптимума. Для устранения этого недостатка в генетических алгоритмах используют схемы (схематы или шаблоны), представляющие собой фрагменты решений или хромосом, которые желательно сохранить в процессе эволюции. При использовании схем в генетическом алгоритме вводится новый алфавит (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.

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

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

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

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

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

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

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

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