· Проектирование искусственных программных систем, воспроизводящих механизмы функционирования естественных систем.
Основные отличия ГА от других алгоритмов оптимизации:
· Используются не параметры, а закодированная множества параметров;
· Поиск осуществляется не из единственной точки, а из популяции точек;
· В процессе поиска используются значения целевой функции, а не её приращения;
· Применяются вероятные, а не детерминированные правила поиска и генерации решений;
· Выполняется одновременный анализ различных областей пространства решений, в связи с чем возможно нахождение новых областей с лучшими значениями целевой функции за счёт объединения квазиоптимальных решений из разных популяций.
2.Простой генетический алгоритм
Согласно репродуктивному плану Холланда генетические схемы поиска оптимальных решений включают следующие этапы процесса эволюции:
1. конструируется начальная популяция. Вводится начальная точка отсчёта поколений t = 0. вычисляются приспособленность хромосом популяции (целевая функция) и средняя приспособленность всей популяции.
2. устанавливается значение t = t+1. выбираются два родителя (хромосомы) для кроссинговера. Выбор осуществляется случайным образом пропорционально жизнеспособности хромосом, которая характеризуется значениями целевой функции.
3. формируется генотип потомка. Для этого с заданной вероятностью над генотипами выбранных хромосом производится операция кроссинговера. Случайным образом выбирается один из потомков А(t), который сохраняется как член новой популяции. Далее к потомку А(t) последовательно с заданными вероятностями применяются операторы инверсии и мутации. Полученный в результате генотип потомка сохраняется как А(t).
4. обновление текущей популяции путём замены случайно выбранной хромосомы на А(t)/
5. определение приспособленности А (t) и пересчёт средней приспособленности популяции.
6. если t=t, где t – заданное число шагов, то переход к этапу 7, в противном случае – переход к этапу 2.
7. конец работы.
Основная идея эволюции, заложенная в различные конструкции генетических алгоритмов, проявляется в способности "лучших" хромосом оказывать большее влияние на состав новой популяции за счёт длительного выживания и более многочисленного потомства.
Простой генетический алгоритм включает операцию случайной генерации начальной популяции хромосом и ряд операторов, обеспечивающих генерацию новых популяций на основе начальной. Этими операторами являются репродукция, кроссинговер и мутация.
Репродукцией называется процесс копирования хромосом с учётом значений целевой функции, т.е. хромосомы с "лучшими" значениями целевой функции имеют большую вероятность попадания в следующую популяцию. Этот процесс является аналогией митозного деления клеток выбор клеток (хромосом) для репродукции проводится в соответствии принципом "выживания сильнейшего". Простейшим способом представления операции репродукции в алгоритмической форме является колесо рулетки, в котором каждая хромосома имеет поле, пропорциональное значению целевой функции.
3.Разновидности генетических алгоритмов
Генетический алгоритм Девиса (25) включает следующие шаги:
1. инициализация популяции хромосом.
2. оценка каждой хромосомы в популяции.
3. создание новых хромосом посредством изменения и скрещивания текущих хромосом (применение операторов мутации и кроссинговера).
4. устранение хромосом из популяции для замены их новыми.
5. оценка новых хромосом и включение их в популяцию.
6. проверка условия исчерпания ресурса времени, отведённого на поиск оптимального решения (если время исчерпано, то работа алгоритма завершается и производится возврат к наилучшей хромосоме, в противном случае – переход к шагу 3).
Холланд (14,26) предложил для генетического алгоритма оператор инверсии, который реализуется по схеме:
1. стринг (хромосома) В=(b1,b2,…..,b1) выбирается случайным образом из текущей популяции.
2. из множества Y= (0,1,2,…., L +1) случайным образом выбираются два числа у1 и у2 и определяются значения х1=min(у1,у2).
3. из хромосомы В формируется новая хромосома путём инверсии (обратного порядка) сегмента, лежащего справа от позиции х2 в хромосоме В. После применения оператора инверсии строка В примет вид В = (b1, ….,bx1, bx2=1, bx2-2, …,bx1+1, bx2, …, bL).
Например, для строки В=(1,2,3,4,5,6) при выборе у1=6 и у2=2 и соответственно х1=2, х2=6 результатом инверсии будет В= (1,2,3,4,5,6).
Операции кроссинговера и мутации, используемые в простом ГА, изменяют структуру хромосом, в том числе разрушают удачные фрагменты найденных решений, что уменьшает вероятность нахождения глобального оптимума. Для устранения этого недостатка в генетических алгоритмах используют схемы (схематы или шаблоны), представляющие собой фрагменты решений или хромосом, которые желательно сохранить в процессе эволюции. При использовании схем в генетическом алгоритме вводится новый алфавит (0,1,), где интерпретируется как "имеет значение 1 или 0". Например:
Схема(*0000) соответствует двум стрингам (10000 и 00000);
Схема (*111*) соответствует четырём строкам (01110, 11110, 01111, 11111);
Схема (0*1**) может соответствовать восьми пятизначным стрингам.
В общем случая хромосома длиной L максимально может иметь 3L(шаблонов), но только 2L различных альтернативных стрингов. Это следует из факта , что схеме (**) в общем случае могут соответствовать 32=9 стрингов, а именно (**, *1, *0,1*, 0*, 00, 01, 10 11), и только 22=4 альтернативные строки (00, 01, 10, 11), т.е. одной и той же строке может соответствовать несколько схем.
Если в результате работы генетического алгоритма удалось найти схемы типа (11***) и (**111), то, применив к ним, оператор кроссинговера, можно получить хромосому (11111), обладающую наилучшим значением целевой функции.
Схемы небольшой длины называются строительными блоками. Размер строительных блоков заметно влияет на качество и скорость нахождения результата. Вид строительного блока выбирается с учётом специфики решаемой задачи, а их разрыв в генетических алгоритмах допускается только в исключительных случаях, определяемых пользователем. Например, в схеме (****1) строительным блоком является элемент1, а в схеме (10***) – составной элемент10.
При использовании большого числа строительных блоков генетические алгоритмы, основанные на случайной генерации популяций и хромосом, переходят в разряд беспорядочных.
Стационарные генетические алгоритмы отличаются от поколенческих тем, что у первых размер популяции является заданным постоянным параметром, который определяется пользователем, а у вторых размер популяции в последующих генерациях может увеличиваться или уменьшаться.
Процедура удаления лишних хромосом в стационарных и поколенческих генетических алгоритмах основана на эвристических правилах, примерами которых являются следующие
· случайное равновероятное удаление хромосо;
· удаление хромосом, имеющих худшие значения целевой функции;
· удаление хромосом на основе обратного значения целевой функции;
· удаление хромосом на основе турнирной стратегии.
Следует иметь в виду, что использование в генетических алгоритмах тех или иных эвристик удаления хромосом может повлечь за собой негативные последствия. Например, удаление худших хромосом приводит к повреждённый утрате разнообразия и, как следствие, к попаданию целевой функции в локальный оптимум, а при наличии большого числа хромосом с плохими значениями целевой функции утрачивается направленность поиска, и он превращается в "слепой" поиск.