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

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

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

 

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

 

 

 

 

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

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

 

 

 

Ковш Валерия Анатольевна, 
студентка 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

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

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

Решение:

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

Найдем глобальный минимум ,в том случае когда все переменные в интервале (-500.0; 500.0). И будем искать его прямым перебором m значений функции для m значений каждого аргумента на заданных интервалах [3]:

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

Этапы 2,3,...: на каждом этапе область определения уменьшается и строится всё более мелкая сетка. Область определения охватывает лишь точки с минимумами. Каждый этап - это такие же итерации, что и на первом этапе.

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

Используя следующие  начальные параметры (Рисунок 7):

Рисунок 7 

Результаты  полученных расчетов можно увидеть  на рисунке 8, и соответствующий график минимумов представлен на рисунке 9.

Рисунок 8

Рисунок 9

 

2. РЕШЕНИЕ ЗАДАЧИ О РАНЦЕ

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

1929 год. В США великая  депрессия, введен сухой закон.  Страна просто задыхается без  спиртного. В этот сложный момент  группа инициативных граждан  под руководством Аль Капоне решает помочь родной стране. Ими планируется поставка алкогольной продукции из Ливерпуля в Штаты. Благодарные сограждане из 5 крупных городов США готовы платить большие деньги за тонну спиртного: 2000  - 250 долл. в Бостоне, 3000 -300  в Детройте, 2500 -500 в Вашингтоне, 3200 -100 в Нью-Йорке и 1800 -- 600 долл в Чикаго. Все 5 городов находятся на разном расстоянии от порта, куда прибывает груз: Бостон –миль, Детройт –миль, Вашингтон – 500 миль, Нью-Йорк –100 миль и Чикаго –миль. Требуется выбрать города, в которых можно получить максимальную прибыль от продажи спиртного. При этом суммарное расстояние от этих портов до порта с грузом не должно превышать 1000 миль.

2. Решение задачи.

Решим данную задачу о ранце  методом ветвей и границ.

Данная задача является задачей  о ранце вида:

,       (1)

где критерием является функция

,         (2)

которая может быть устремлена и к максимуму, и к минимуму.

Для начала составим следующую  математическую модель:

Пусть – j-тый город, откуда соответственно . При этом, если в j-тый город будет разгружаться алкогольная продукция, то , иначе . Другим ограничением будет являться суммарное расстояние до порта с грузом. Таким образом:

;

Целевой функцией или критерием  будет являться максимальная благодарность  сограждан:

.

Далее отбираем порты по приоритетности, т.е. в порядке убывания отношения  :

(3); (2); (4); (1); (5).

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

, ;

Аналогично рассуждая, далее  получаем:

, ;

, ;

В последнем случае оставшееся после других городов расстояние меньше 500 миль, поэтому  будет дробным: , => .

Таким образом, начальный  опорный план: .

Значение целевой функции: .

Но  обязательно целое. Поэтому чтобы определить, чему все же равен : 0 или 1 вычислим следующие значения:

;– целая часть критерия  при существующем опорном плане. 

;– значение критерия при  целочисленном опорном плане,  т.е.  .

Множество D, которому принадлежит имеет , . Разделим его на 2 подмножества, такие что:

;

- здесь  .

- здесь  .

1) Анализ множества  D₁.

Поскольку целевая функция и ограничения будут иметь вид:

Строим новый опорный  план:

, ;

, ;

, ;

Т.к. , поэтому будет дробным: , => .

Таким образом, новый опорный  план: .

;

, при  .

2) Анализ множества  D₂.

Поскольку целевая функция и ограничения будут иметь вид:

=> .

Строим новый опорный  план:

, ;

, ;

Т.к. , поэтому будет дробным: , => .

Таким образом, новый опорный  план: .

;

, при  .

3) Отсев неперспективного  подмножества.

.

Так как  и больше Rec, то оба подмножества можно считать перспективными, но поскольку , то далее мы будем исследовать подмножество D₂. Разделим его на 2 подмножества, такие что:

;

- здесь  .

- здесь  .

4) Анализ множества  D₃.

Поскольку , целевая функция и ограничения будут иметь вид:

.

Строим новый опорный  план:

, ;

, ;

Т.к. , поэтому будет дробным: , => .

Таким образом, новый опорный  план: .

;

, при  .

5) Анализ множества  D₄.

Поскольку , целевая функция и ограничения будут иметь вид:

=> .

Строим новый опорный  план:

, ;

Т.к. , поэтому будет дробным: , => .

Таким образом, новый опорный  план: .

;

, при  .

6) Отсев неперспективного  подмножества.

.

Так как  и больше Rec, то оба подмножества можно считать перспективными, но поскольку , то далее мы будем исследовать подмножество D₃. Разделим его на 2 подмножества, такие что:

;

- здесь  .

- здесь  .

7) Анализ множества  D₅.

Поскольку , , целевая функция и ограничения будут иметь вид:

.

Строим новый опорный  план, очевидно: . При , ограничение выполняется всегда.

;

, при  .

8) Анализ множества  D₆.

Поскольку , , целевая функция и ограничения будут иметь вид:

.

Ограничение несовместное, поскольку даже при оно не выполняется. Следовательно множество D₆ не существует.

Таким образом, оптимальным  планом данной задачи будет: , то есть алкоголь выгоднее всего поставлять в 3 города: Детройт, Вашингтон и Нью-Йорк. При этом прибыль составит 8700 долл.

 

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

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

Нахождения минимума функции  Швефеля  с применением генетического  алгоритма будем выполнять при  следующих начальных условиях:

// Количество хромосом (неизвестных  в функции Швефеля)

int chromosomesCount = 15;

// Максимальное количество  поколений (итераций)

int maxGeneration = 10000;

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

int maxEqualGeneration = 300;

// Если на очередной  итерации целевая функция изменилась  на значение,

меньшее ил равное minDelta, то считаем, что целевая функция не изменилась.

double minDelta = 1e-8;

// Максимальный размер  популяции

int populationMaxSize = 100;

// Вероятность мутации

double mutationPossibility = 0.1;

// Вероятность скрещивания

double crossPossibility = 0.9;

// Интервал изменений  хромосом

double chromoMinVal = -500;

double chromoMaxVal = 500;

При этом получим следующий  результат (Рисунок 10):

 

Рисунок 10

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

На следующем рисунке (Рисунок 11) приведено решение данной задачи с применением генетического  алгоритма:

Рисунок 11

В данной программе были использованы следующие  начальные  данные :

// число особей в популяции

           public static int populationCount = 200;

 // максимальный вес, который может содержатьcя в рюкзаке

           public static double maxWeightKnapsack = 1000;

// массив из элементов,  положить в рюкзак

          public static Item[] items = new Item[]{

  new Item(250,2000),

  new Item(300,3000),

  new Item(500,2500),

  new Item(100,3200),

            new Item(600,1800) };   

// вероятность (в процентах)  мутации

           public static double mutationLikelihood = 0.9;

// Число лиц, участвующих  в турнире выбора

         public static int tournamentParticipantsCount = 5;    

// Число "поколений".

         public static int maxIterations = 200;

 

ЗАКЛЮЧЕНИЕ

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

Можно выделить следующие  преимущества генетических алгоритмов:

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

2) ГА хорошо применимы  к задачам оптимизации в крупных  масштабах.

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

4) Они достаточно просты в реализации, но при этом могут быть использованы для широкого класса задач.

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

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

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

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

 

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

1. Холланд Дж. , Генетические алгоритмы / Холланд Дж. // В мире науки. –1992. –  № 9-10.
2. Генетический алгоритм [Электронный ресурс]/Википедия .– Моска, 2010.  – Режим доступа:

 http://ru.wikipedia.org/wiki/ Генетический_алгоритм #cite_note-book-0.  – Дата доступа: 30.10.2012

3. Определения глобального минимума целевой функции [Электронный ресурс]/  У чебный сайт КГМТУ – Режим доступа: http://pvn.ho.ua/pvn.org.ua/www/lection/example/example_6/6_8/NonLinerOpt_auto/greedy_2arg_auto.html. – Дата доступа: 28.11.2012
4. Рутковская Д., Нейронные сети, генетические алгоритмы как нечёткие системы/ Рутковская Д., Пилиньский М., Рутковский Я.. – Москва.: Горячая линия – Телеком, 2004  – с..