Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



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

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.

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

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

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

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

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

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

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

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




Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!