Применение генетических алгоритмов к задаче о ранце

 

 

 

 

 

 

Применение  генетических алгоритмов к задаче о  ранце

(курсовая работа)

 

 

 

 

 

 

 

 

 

Тольятти 2009

Содержание

1. Введение…………………………………………………………………….3
2. Постановка задачи………………………………………………………….5
3. Принцип работы генетических алгоритмов……………………………...6
4. Проект решения………………………………………………………….....9
5. Литература………………………………………………..……………….11
6. Приложение……………………………………………………………….12

 

Введение

Развитие природных  систем на протяжении многих веков  привлекало внимание ученых. Неоднократно совершались попытки выделить и осмыслить основополагающие принципы и механизмы, лежащие в основе изменений, происходящих в живой природе. Предлагалось множество различных концепций, пока в 1858 году Чарльз Дарвин не опубликовал свою знаменитую работу «Происхождение видов», в которой были провозглашены принципы наследственности, изменчивости и естественного отбора. Однако на протяжении почти 100 последующих лет оставались неясными механизмы, отвечающие за наследственность и изменчивость организмов. В 1944 году Эйвери, Маклеод и Маккарти опубликовали результаты своих исследований, доказывавших, что за наследственные процессы ответственна «кислота дезоксирибозного типа». Это открытие послужило толчком к многочисленным исследованиям во всем мире, и 27 апреля 1953 года в журнале «Nature» вышла статья Уотсона и Крика, где была описана модель двухцепочечной спирали ДНК.

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

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

но и для решения  прикладных задач оптимизации. Множество  алгоритмов и

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

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

Круг задач, решаемых с помощью ГА очень широк. Ниже перечислены

 

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

- задачи численной  оптимизации;

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

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

- составление расписаний;

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

- отбор (фильтрация) данных;

- настройка и обучение искусственной  нейронной сети;

- искусственная жизнь;

- биоинформатика;

- игровые стратегии;

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

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

 

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

Задача данной курсовой работы заключается в изучении генетических алгоритмов и реализации задачи компоновки рюкзака: пусть имеется n предметов, каждый из которых имеет ценность и объем , . Имеется ранец (рюкзак), объем которого есть V , при этом , то есть все предметы в ранец положить невозможно. Необходимо положить в ранец набор предметов с максимальной суммарной ценностью.

 

 

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

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

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

Формирование начальной  популяции.

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

Селекция.

Селекция (отбор) необходима, чтобы выбрать более приспособленных

особей для скрещивания. Существует множество вариантов  селекции, опишем наиболее известные  из них.

Рулеточная  селекция.

В данном варианте селекции вероятность i-й особь принять участие в скрещивании пропорциональна значению ее приспособленности и равна .

Процесс отбора особей для скрещивания  напоминает игру в «рулетку». Рулеточный круг делится на сектора, причем площадь i-го сектора пропорциональна значению . После этого n раз «вращается» рулетка, где n – размер популяции, и по сектору, на котором останавливается рулетка, определяется особь, выбранная для скрещивания.

Селекция усечением.

При отборе усечением  после вычисления значений приспособленности  для скрещивания выбираются ln лучших особей, где l – «порог отсечения», 0 < l < 1, n – размер популяции. Чем меньше значение k, тем сильнее давление селекции, т.е. меньше шансы на выживание у плохо приспособленных особей. Как правило, выбирают l в интервале от 0,3 до 0,7.

Турнирный отбор.

В случае использования  турнирного отбора для скрещивания, как и при рулеточной селекции, отбираются n особей. Для этого из популяции случайно выбираются t особей, и самая приспособленная из них допускается к скрещиванию. Говорят, что формируется турнир из t особей, t размер турнира. Эта операция повторяется n раз. Чем больше значение t, тем больше давление селекции. Вариант турнирного отбора, когда t = 2, называют бинарным турниром. Типичные значения размера турнира t = 2, 3, 4, 5.

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

Отобранные в результате селекции особи (называемые родительскими)

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

Формирование  нового поколения.

В результате скрещивания  создаются потомки, которые формируют популяцию следующего поколения. Отметим, что обновленная таким образом популяция не обязательно должна включать одних только особей-потомков. Если доля обновляемых особей равна Т, то в новое поколение попадает Тп потомков, п – размер популяции, а (1-Т)п особей в новой популяции являются наиболее приспособленными родительскими особями (элитные особи). Параметр Т называют разрыв поколений. Использование элитных особей позволяет увеличить скорость сходимости генетического алгоритма.

Мутация.

Оператор мутации используется для внесения случайных изменений в хромосомы особей. Это позволяет «выбираться» из локальных экстремумов

и, тем самым, эффективнее  исследовать пространство поиска. Так  же, как и

для оператора кроссовера, существует вероятность применения мутации.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Проект решения

Исходные данные представляются с помощью массива структур e[M] ,

где k – это стоимость  предмета, а w – объем  предмета.

Допустимые решения (хромосомы) представляются с помощью класса rukzak. Этот класс содержит матрицу a[M] ={0,1}, где a[i]=0 означает, что предмет не был положен в рюкзак, a[i]=1 – предмет положен в рюкзак. Поле Wn – сумма объемов генов, значение которых равно 1, т.е. сумма объемов предметов, положенных в рюкзак, высчитываемой по формуле: . Kn – значение фитнесс-функции, высчитываемой для хромосомы по формуле: .

Допустимость проверяется  по формуле:

, где V – максимальный объем рюкзака.

В функции rukzak* create() создается первое поколение. Начальная популяция формируется случайным образом.

Формирование  репродуктивного множества

В программе для отбора особей в репродуктивное множество  используется турнирный отбор. Турнирный отбор – произвольно выбираются 2 разные особи, из них выбирается 1 самая сильная особь, которая попадает в репродуктивное множество. Отбор происходит до тех пор, пока в репродуктивном множестве не станет N особей. Репродуктивное множество хранится в массиве объектов класса rukzak.

Скрещивание

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

 

          1010 1010  1010 1111

            +  => 

0000 1111  0000 1010 

 

10 101010  10 001111

            +  => 

00 001111  00 101010 

 

Проверяем потомков на допустимость. Процесс повторяется до тех пор, пока не будет создано N потомков.

Мутация

Мутировать может только один произвольный потомок. Мутирует потомок или нет, определяется произвольно. Также произвольно определяется ген потомка a[i], который подвергнется мутации. Если a[i]=0, то заменяем на a[i]=1. Если a[i]=0, то потомок не меняется. 

1010 1 010  => 1010 0 010

101 0 1010  => 101 1 1010 

Потомка, подверженного мутации проверяются на допустимость.

Новое поколение

В новое поколение попадет  часть  особей из предыдущего поколения с максимальной фитнесс-функцией. А остальная часть - это самые сильные особи  получаемые в результате скрещивания и мутации. Новое поколение записывается в массив объектов класса rukzak.

 

 

Литература

1. Люгер Ф. «Стратегии и методы решения сложных проблем». – М.: Вильямс 2003г
2. Фогель Л., Оуэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969г
3. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное   программирование: модели и вычислительные алгоритмы: Учеб. пособ. – Изд. 2-е, испр. – М.: ФИЗМАЛИТ, 2003. – 240 с.
4. Павловская Т.А. «С/C++. Программирование на языке высокого уровня».М: Питер 2003г