Генетические алгоритмы

 

Содержание                                                                                                 

Генетический  алгоритм                                                                                           3

Простой генетический алгоритм                                                                            6

Области применения генетических алгоритмов                                                   7

Выводы                                                                                                                     7

Список   литературы                                                                                                8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Генетический  алгоритм

Генетический алгоритм это одна из разновидностей случайного поиска. Она похожа на  естественный отбор и размножение.

Генетический алгоритм начинает свою работу с популяцией. Популяция представляет собой некоторый случайный набор исходных решений. Элементы популяции называются  хромосомой  и представляют собой решение проблемы в первом приближении. Она состоит из генов. Хромосома эта строка символов некоторой природы.

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

Генетический  алгоритм имеет  несколько этапов:

1. Инициализация
2. Выращивание
3. Оценивание
4. Селекция
5. Скрещивание
6. Мутация

Первый этап - это инициализация. Инициализация это формирование исходной популяции. Каждая особь популяции представляет собой решение задачи, которая является кандидатом на решение. Формирование исходной популяции происходит с использованием какого-нибудь случайного закона. В ряде случаев исходная популяция может быть и результатом работы другого алгоритма.

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

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

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

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

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

В каждом алгоритме скрещивание  зависит от представления данных. Одна из важнейших требований к размножению — это чтобы потомок или потомки унаследовали черты обоих родителей, «смешав» их каким-либо способом.

И последний  этап это Мутация. Она состоит из выполнения небольших изменений в значениях одного или нескольких генов в хромосоме. В генетических алгоритмах мутация это метод восстановления потерянного генетического материала. Здесь мутация применяется к генам с низкой вероятностью. Вероятность выбирается в зависимости от длины хромосомы и вычисляется по формуле  p_m = ,  где M  это число бит в хромосоме.

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

      Вот одна из таких схем работы генетический алгоритм                                                           

 

Вот еще одна из схем работы генетического алгоритма

                                      Простой генетический алгоритм 

                                                                                                                                                                                            Как видно из  репродуктивного плана Холланда генетические схемы поиска оптимальных решений включают такие шаги процесса эволюции:

а. разрабатывается начальная популяция. Сначала вводится начальная точка отсчёта поколений t = 0. И вычисляются адаптированность хромосом популяции и средняя адаптированность всей популяции.

    б. фиксируется значение t= t+1. Отбираются две хромосомы (родители) для кроссинговера. И этот выбор совершается случайным образом пропорционально жизнеспособности хромосом, которая определяется значениями целевой функции.

         в. далее формируется генотип потомка. С этой целью с заданной вероятностью над генотипами выбранных хромосом совершаются операция кроссинговера. Случайным образом отбирается один из потомков А(t). И этот потомок сохраняется как член новой популяции. Потом к потомку А(t)                     пошагово с заданными вероятностями применяются операторы инверсии и мутации. И в итоге полученный генотип потомка сохраняется как А(t).

        г. восстановление текущей популяции путём обновления случайно выбранной хромосомы на А(t)/

       д. определение адаптированности А(t) и пересчёт средней адаптированности популяции.

   е. если t=t, где t – это заданное число шагов, то нужен переход к этапу ж, иначе - переход к этапу б.

ж. и конец алгоритма.

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

Области применения генетических алгоритмов

Генетические алгоритмы применяются в очень многих областях. И приведенный список не является единственным:

1. экстремальные задачи (нахождение точек минимума и минимума);

2. задачи о кратчайшем пути;

3. задачи компоновки;

4. написание расписаний;

5. аппроксимация функций;

6. отбор входных данных;

7. настройка искусственной нейронной сети;

8. моделирование искусственной жизни;

9. биоинформатика (свертывание белков и РНК);

10. игровые стратегии;

11. нелинейная фильтрация;

12. развивающиеся агенты/машины.

Выводы

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

У генетических алгоритмов множество модификаций. Они сильно зависят от параметров. И даже небольшое изменение одного из них может повлиять на изменение результата.

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

 

 

Список  литературы

1. Батищев Д. И., Неймарк Е. А., Старостин Н. В. Применение генетических алгоритмов к решению задач дискретной оптимизации / Д. И. Батищев, Е. А. Неймарк, Н. В. Старостин. – Н. Новгород: 2007.

2. Генетические алгоритмы [Электронный ресурс] // Генетические алгоритмы и не только. – Электрон. дан. – [б.м.], 2003-2007. - URL: http://qai.narod.ru/GA/ (Дата обращения: 01.06.2010).

3.Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, Л. Рутковский; пер. с польск. И. Д. Рудинского. – М: Горячая линия, 2006.

4. Исаев С.А. Популярно о генетических алгоритмах

5. Исаев С.А.. Генетические алгоритмы - эволюционные методы поиска. URL: http://rv.ryazan.ru/~bug/library/ai/isaev/2/part1.html

6. Редько В. Прикладное эволюционное моделирование. Генетический алгоритм. Оценка эффективности генетического алгоритма. URL:http://www.keldysh.ru/BioCyber/Lecture10.html