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

Механизм эволюции основан на трёх повторяющихся процессах: отборе, амплификации (процесс производства потомков) и мутации. Он используется в качестве механизма случайно направленного комбинаторного перебора при решении задач оптимизации и слабоструктурированных проблем принятия решений.

Генетический алгоритм – это поисковый алгоритм, основанный на природных механизмах селекции и генетики. Э

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

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

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

· Абстрактное и формальное объяснение процессов адаптации в естественных системах;

· Проектирование искусственных программных систем, воспроизводящих механизмы функционирования естественных систем.

Основные отличия ГА от других алгоритмов оптимизации:

· Используются не параметры, а закодированная множества параметров;

· Поиск осуществляется не из единственной точки, а из популяции точек;

· В процессе поиска используются значения целевой функции, а не её приращения;

· Применяются вероятные, а не детерминированные правила поиска и генерации решений;

· Выполняется одновременный анализ различных областей пространства решений, в связи с чем возможно нахождение новых областей с лучшими значениями целевой функции за счёт объединения квазиоптимальных решений из разных популяций.

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).

 Скачать реферат