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

 

ПОВОЛЖСКИЙ  ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ  УНИВЕРСИТЕТ

 

 

 

 

 

 

 

 

 

«Генетические алгоритмы и их применение»

 

 

 

 

 

 

 

 

Выполнил: Афонин Андрей

ПИб-12

Руководитель: Бородин Андрей

Викторович.

 

 

 

 

 

 

 

 

г. Йошкар-Ола

2012г.

 

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

 

 

 

 

 

 

 

Оглавление:

 

1. Введение 2

1.1 Мягкие вычисления 2

1.2 Эволюционные вычисления 2

2. История 3

2.1 Несколько открытий в биологии 3

2.2 Ключевые работы 3

3. Классический ГА 4

3.1 Постановка задачи и функция приспособленности 4

3.2 Принцип работы ГА 5

3.3 Алгоритм работы 5

3.4 Отбор 6

3.5 Скрещивание 7

3.6 Мутация 7

3.7 Критерии останова 7

4. Теория 8

4.1 Шаблоны 8

4.2 Неявный параллелизм 9

4.3 Теорема шаблонов 9

5. Настройка ГА 10

6. Различные модификации ГА 11

6.1 Кодирование 11

6.2 Стратегии отбора 12

6.3 Кроссовер 12

6.4 Стратегии формирования нового поколения 12

7. Некоторые модели ГА 13

7.1 Genitor (Whitley) 13

7.2 CHC (Eshelman) 13

7.3 Hybrid algorithm (Davis) 13

7.4 Island Models 14

8. Факторы, создающие сложность для ГА 15

9. Выводы 16

10. Ссылки 17

 

1. Введение

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

1.1 Мягкие вычисления

 

Термин "мягкие вычисления" (Soft computing techniques) был введен Лофти Заде (основоположником нечёткой логики) в 1994 году. Это понятие объединяет такие области как:

• нечёткая логика
• нейронные сети
• вероятностные рассуждения
• сети доверия
• эволюционные вычисления

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

1.2 Эволюционные вычисления

 

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

Также в ней выделяют следующие направления:

• Эволюционные стратегии
• Метод оптимизации, основанный на идеях адаптации и эволюции. Степень мутации в данном случае меняется со временем – это приводит к, так называемой, самоадаптации.
• Генетическое программирование
• Применение эволюционного подхода к популяции программ.
• Эволюционное программирование
• Было впервые предложено Л.Дж. Фогелем в 1960 году для моделирования эволюции как процесса обучения с целью создания искусственного интеллекта. Он использовал конечные автоматы, предсказывающие символы в цифровых последовательностях, которые, эволюционируя, становились более приспособленными к решению поставленной задачи.

Генетические  алгоритмы применяются для решения  следующих задач:

• Оптимизация функций
• Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
• Настройка и обучение искусственной нейронной сети
• Задачи компоновки
• Составление расписаний
• Игровые стратегии
• Аппроксимация функций
• Искусственная жизнь
• Биоинформатика

2. История

2.1 Несколько открытий в биологии

 

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

 

Сначала Чарльз Дарвин опубликовал в 1859 году свою знаменитую работу "Происхождение видов", где были провозглашены основные принципы эволюционной теории:

• Наследственность (потомки сохраняют свойства родителей)
• Изменчивость (потомки почти всегда не идентичны)
• Естественный отбор (выживают наиболее приспособленные).

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

 

В 1944 году Эйвери, Маклеод и Маккарти опубликовали результаты своих исследований, доказывавших, что за наследственные процессы ответственна "кислота дезоксирибозного типа". Однако о том, как работает ДНК, стало известно позднее.

 

В 1953 году в  номере журнала "Nature" вышла статья Уотсона и Крика, которые впервые предложили модель двухцепочной спирали ДНК.

 

Таким образом, стали известны все необходимые  компоненты для реализации эволюционной модели.

2.2 Ключевые работы

 

Первые публикация, которые можно отнести к генетическим алгоритмам, принадлежат Баричелли Н.А. Его работы "Symbiogenetic evolution processes realised by artificial methods" (1957), "Numerical testing of evolution theories" (1962) были направлены прежде всего на понимание природного феномена наследственности.

 

В 1966 году Л.Дж. Фогель, А.Дж. Оуэнс, М.Дж. Уолш предложили и исследовали эволюцию простых автоматов, предсказывающих символы в цифровых последовательностях.

 

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

 

В 1975 году Холланд публикует свою самую знаменитую работу «Adaptation in Natural and Artificial Systems». В ней он впервые ввёл термин «генетический алгоритм» и предложил схему классического генетического алгоритма (canonical GA). В дальнейшем понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА.

 

Ученики Холланда – Кеннет Де Йонг и Дэвид Голдберг – внесли огромный вклад в развитие ГА. Наиболее известная работа Голдберга – «Genetic algorithms in search optimization and machine learning» (1989).

3. Классический ГА

3.1 Постановка задачи и функция приспособленности

Пусть перед нами стоит задача оптимизации, например:

• Задача наилучшего приближения
• Если рассматривать систему n линейных уравнений с m неизвестными

Ax = b

в случае, когда она переопределена (n > m), то иногда оказывается естественной задача о нахождении вектора x, который "удовлетворяет этой системе наилучшим образом", т. е. из всех "не решений" является лучшим.

• Задача о рационе.
• Пусть имеется n различных пищевых продуктов, содержащих m различных питательных веществ. Обозначим через a_ij содержание (долю) j-го питательного вещества в i-ом продукте, через b_j — суточную потребность организма в j-ом питательном веществе, через c_i — стоимость единицы i-го продукта. Требуется составить суточный рацион питания минимальной стоимости, удовлетворяющий потребность во всех питательных веществах
• Транспортная задача.
• Эта задача — классическая задача линейного программирования. К ней сводятся многие оптимизационные задачи. Формулируется она так. На m складах находится груз, который нужно развезти n потребителям. Пусть a_i (i = 1, ..., n) — количество груза на i-ом складе, а b_j (j = 1, ..., m) — потребность в грузе j-го потребителя, c_ij — стоимость перевозки единицы груза с i-го склада j-му потребителю. Требуется минимизировать стоимость перевозок.
• Задачи о распределении ресурсов.
• Общий смысл таких задач — распределить ограниченный ресурс между потребителями оптимальным образом. Рассмотрим простейший пример — задачу о режиме работы энергосистемы. Пусть m электростанций питают одну нагрузку мощности p. Обозначим через x_j активную мощность, генерируемую j-ой электростанцией. Техническими условиями определяются возможный минимум m_j и максимум M_j вырабатываемой j-ой электростанцией мощности. Допустим затраты на генерацию мощности x на j-ой электростанции равны e_j(x). Требуется сгенерировать требуемую мощность p при минимальных затратах.

Переформулируем задачу оптимизации как задачу нахождения максимума некоторой функции f(x₁, x₂, …, x_n), называемой функцией приспособленности (fitness function).  Она должна принимать неотрицательные значения на ограниченной области определения (для того, чтобы мы могли для каждой особи считать её приспособленность, которая не может быть отрицательной), при этом совершенно не требуются непрерывность и дифференцируемость.

Каждый  параметр  функции приспособленности  кодируется строкой битов.

Особью  будет называться строка, являющаяся конкатенацией строк упорядоченного набора параметров:

1010   10110   101    …    10101

|  x1  |    x2    |   x3   |  … |    xn   |

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

3.2 Принцип работы ГА

 

Генетические  алгоритмы оперируют совокупностью  особей (популяцией), которые представляют собой строки, кодирующие одно из решений  задачи. Этим ГА отличается от большинства других алгоритмов оптимизации, которые оперируют лишь с одним решением, улучшая его.

 

С помощью  функции приспособленности среди  всех особей популяции выделяют:

• наиболее приспособленные (более подходящие решения), которые  получают возможность скрещиваться и давать потомство
• наихудшие (плохие решения), которые удаляются из популяции и не дают потомства

Таким образом, приспособленность нового поколения  в среднем выше предыдущего.

 

В классическом ГА:

• начальная популяция формируется случайным образом
• размер популяции (количество особей N) фиксируется и не изменяется в течение работы всего алгоритма
• каждая особь генерируется как случайная L-битная строка, где L — длина кодировки особи
• длина кодировки для всех особей одинакова

3.3 Алгоритм работы

На  рисунке изображена схема работы любого генетического алгоритма:

 

Шаг алгоритма состоит из трех стадий:

1. генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения
2. скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения
3. мутация нового поколения

Первые  две стадии (отбор и скрещивание):

3.4 Отбор

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

В классическом ГА вероятность каждой особи попасть в промежуточную популяцию пропорциональна ее приспособленности, т.е. работает пропорциональный отбор (proportional selection).

Существует  несколько способов реализации данного  отбора:

• stochastic sampling. Пусть особи располагаются на колесе рулетки так, что размер сектора каждой особи пропорционален ее приспособленности. N раз запуская рулетку, выбираем требуемое количество особей для записи в промежуточную популяцию.
• remainder stochastic sampling. Для каждой особи вычисляется отношение ее приспособленности к средней приспособленности популяции. Целая часть этого отношения указывает, сколько раз нужно записать особь в промежуточную популяцию, а дробная показывает её вероятность попасть туда ещё раз. Реализовать такой способ отбора удобно следующим образом: расположим особи на рулетке так же, как было описано. Теперь пусть у рулетки не одна стрелка, а N, причем они отсекают одинаковые сектора. Тогда один запуск рулетки выберет сразу все N особей, которые нужно записать в промежуточную популяцию. Такой способ иллюстрируется следующим рисунком:

3.5 Скрещивание

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

В классическом ГА применяется одноточечный оператор кроссовера (1-point crossover): для родительских строк случайным образом выбирается точка раздела, потомки получаются путём обмена отсечёнными частями.

011010.01010001101  ->  111100.01010001101

111100.10011101001      011010.10011101001

3.6 Мутация

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

Каждый  бит каждой особи популяции с  некоторой вероятностью инвертируется. Эта вероятность обычно очень мала, менее 1%.

1011001100101101 -> 1011001101101101