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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования 
«Брестский государственный университет имени А. С. Пушкина»

 

Математический факультет 
Прикладной математики технологии программирования

 

 

 

 

Курсовая работа

ПРИМИНЕНИЕ ГЕНЕТИЧЕСКОГО  АЛГОРИТМА ПРИ РЕШЕНИЯ ЗАДАЧ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

 

 

 

Ковш Валерия Анатольевна, 
студентка 4 курса специальности «Прикладная математика»

Крощенко Александр Александрович – преподаватель кафедры прикладной математики технологии программирования

 

 

 

 

Брест 2012 г.

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ 2

ВВЕДЕНИЕ 3

1.1. ИСТОРИЯ 5

1.2 СИМВОЛЬНАЯ  МОДЕЛЬ ПРОСТОГО ГА 6

1.3 ПРИМЕНЕНИЕ  ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 7

ГЛАВА 2  АЛГОРИТМ РАБОТЫ 8

2.1. СХЕМА  РАБОТЫ ГЕНЕТИЧЕСКОГО АЛГОРИТМА 8

2.2 ОТБОР 9

2.3 СКРЕЩИВАНИЕ 10

2.3 МУТАЦИЯ 11

2.4 КРИТЕРИИ  ОСТАНОВА 12

ГЛАВА 3 ЧИСЛЕННЫЙ  ЭКСПЕРИМЕНТ 13

3.1 МИНИМИЗАЦИЯ ФУНКЦИИ ШВЕФЕЛЯ 13

3.2 РЕШЕНИЕ ЗАДАЧИ О РАНЦЕ 16

ГЛАВА 4 РЕЗУЛЬТАТЫ ЧИСЛЕННОГО ЭКСПЕРИМЕНТА 21

4.1 МИНИМИЗАЦИЯ  ФУНКЦИИ ШВЕФЕЛЯ 21

4.2 РЕШЕНИЕ  ЗАДАЧИ О РАНЦЕ 22

ЗАКЛЮЧЕНИЕ 23

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 24

 

  

ВВЕДЕНИЕ

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

На мировоззрение людей сильно повлияла теория эволюции Чарльза Дарвина, представленная в работе "Происхождение  Видов", в 1859 году. Множество областей научного знания многим обязана революции, вызванной теорией эволюции и развития. Дарвин предполагал, что в основе развития лежит естественный отбор, но  не мог не ошибаться. В свою очередь он обнаружил главный механизм развития: отбор в соединении с изменчивостью. Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорные, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемые в природе.

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

Благодаря открытиям последних  ста лет современной науке  известны все основные механизмы  эволюции, связанные с генетическим наследованием. Эти механизмы достаточно просты по своей идее, но остроумны (если к природе применимо это  слово) и эффективны. Удивительно, но простое моделирование эволюционного  процесса на компьютере позволяет получить решения многих практических задач. Такие модели получили название “генетические  алгоритмы” и уже широко применяются  в различных областях.    

Объектом изучения данной курсовой работы являются генетические алгоритмы.

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

Цели моей курсовой работы следующие:

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

 

1.1. ИСТОРИЯ

«Отцом-основателем» генетических алгоритмов считается Джон Холланд, книга которого «Адаптация в естественных и искусственных системах» (1975) [1] является основополагающим трудом в этой области исследований. Ему же принадлежит Генетические алгоритмы.

Идея генетических алгоритмов заимствована у живой природы и состоит  в организации эволюционного  процесса, конечной целью которого является получение оптимального решения  в сложной комбинаторной задаче. Разработчик генетических алгоритмов выступает в данном случае как "создатель", который должен правильно установить законы эволюции, чтобы достичь желаемой цели как можно быстрее. Впервые  эти нестандартные идеи были применены  к решению оптимизационных задач  в середине 70-х годов . Тогда в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Примерно через десять лет появились первые теоретические обоснования этого подхода.

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

 

1.2 СИМВОЛЬНАЯ МОДЕЛЬ ПРОСТОГО ГА

Цель в оптимизации  с помощью ГА состоит в том, чтобы найти лучшее возможное решение или решения задачи по одному или нескольким критериям [2]. Чтобы реализовать генетический алгоритм, нужно сначала выбрать подходящую структуру для представления этих решений. В постановке задачи поиска экземпляр этой структуры данных представляет точку в пространстве поиска всех возможных решений.

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

Каждая хромосома представляет собой конкатенацию ряда подкомпонентов, называемых генами. Гены располагаются  в различных позициях или локусах  хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными строками, ген - бит, локус - его позиция в строке, и аллель - его значение (0 или 1). Биологический  термин "генотип" относится к  полной генетической модели особи и  соответствует структуре в ГА. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров

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

 

1.3 ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

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

1. Оптимизация функций
2. Оптимизация запросов в базах данных
3. Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
4. Настройка и обучение искусственной нейронной сети
5. Задачи компоновки
6. Составление расписаний
7. Игровые стратегии
8. Теория приближений
9. Искусственная жизнь
10. Биоинформатика (фолдинг белков)

 

ГЛАВА 2  АЛГОРИТМ РАБОТЫ

2.1. СХЕМА РАБОТЫ  ГЕНЕТИЧЕСКОГО АЛГОРИТМА

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

Рисунок 1

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

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

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

Рисунок 2

 

 

2.2 ОТБОР

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

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

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

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

Рисунок 3

 

2.3 СКРЕЩИВАНИЕ

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

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

Пример:

011010.01010001101  ->  111100.01010001101

111100.10011101001      011010.10011101001

 

 

2.3 МУТАЦИЯ

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

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

1011001100101101 -> 1011001101101101

Можно выбирать некоторое количество точек в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать  сразу некоторую группу подряд идущих точек [4]. Среди рекомендаций по выбору вероятности мутации нередко можно встретить варианты 1/L или 1/N.

 

2.4 КРИТЕРИИ ОСТАНОВА

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

Схождением называется состояние  популяции, когда все строки популяции  находятся в области некоторого экстремума и почти одинаковы. То есть кроссовер практически никак не изменяет популяции, а мутирующие особи склонны вымирать, так как менее приспособлены. Таким образом, схождение популяции означает, что достигнуто решение близкое к оптимальному (Рисунок 4).

Рисунок 4

Итоговым решением задачи может  служить наиболее приспособленная  особь последнего поколения.

 

ГЛАВА 3 ЧИСЛЕННЫЙ ЭКСПЕРИМЕНТ

1. МИНИМИЗАЦИЯ ФУНКЦИИ ШВЕФЕЛЯ

Этот проект реализует  минимизацию функции Швефеля, формула которой представлена ниже

Эта функция замечательна тем, что она имеет много локальных  минимумов и максимумов, но глобальный минимум у нее только один.

Чтобы иметь представление о том насколько изрезана целевая функция, на рисунках 5, и 6 приведены линии уровня для n = 2.

Рисунок 5

Рисунок 6

Постановка задачи:

Найти глобальный минимум  функции Швефеля

Решение:

Искомый минимум находится  в правом верхнем углу, но при  желании можно искать и максимум, который находится в левом  нижнем углу.