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

Министерство общего и профессионального образования

Российской Федерации

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н.Г.ЧЕРНЫШЕВСКОГО

Кафедра

Математической кибернетики и компьютерных наук

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

КУРСОВАЯ РАБОТА

студента 3 курса

факультета Компьютерных Наук и Информационных Технологий

Морозова Владимира Александровича

Научный руководитель

заместитель заведующего кафедрой,

старший преподаватель О.В.Емельянова

Зав. Кафедрой

член-корреспондент АТНУ,

доктор технических наук,

профессор Д.В.Сперанский

Содержание

Введение 3

Основная часть 4

Теоретическая часть 4

Общие сведения 4

Модели генетических алгоритмов 5

Практическая часть 10

Принцип работы программы 10

Листинг программы 11

Заключение 18

Список использованных источников 19

Введение

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

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

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

Основная часть

Теоретическая часть

Общие сведения

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

Вначале генерируется начальная популяция особей (индивидуумов), т.е. некоторый набор решений задачи. Как правило, это делается случайным образом. Затем необходимо смоделировать размножение внутри этой популяции. Для этого случайно отбираются несколько пар индивидуумов, производится скрещивание между хромосомами в каждой паре, а полученные новые хромосомы помещаются в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора — чем приспособленнее индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет участвовать в скрещивании. Теперь моделируются мутации — в нескольких случайно выбранных особях нового поколения изменяются некоторые гены. Затем старая популяция частично или полностью уничтожается и мы переходим к рассмотрению следующего поколения. Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько начальная, но в силу отбора приспособленность в ней в среднем выше. Теперь описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т. д.

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

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

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

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

1. Canonical GA (J. Holland)

Данная модель алгоритма является классической. Она была предложена Джоном Холландом в его знаменитой работе "Адаптация в природных и исусственных средах" (1975). Часто можно встретить описание простого ГА (Simple GA, D. Goldberg), он отличается от канонического тем, что использует либо рулеточный, либо турнирный отбор. Модель канонического ГА имеет следующие характеристики:

 Фиксированный размер популяции.

 Фиксированная разрядность генов.

 Пропорциональный отбор.

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

 Одноточечный кроссовер и одноточечная мутация.

 Следующее поколение формируется из потомков текущего поколения без "элитизма". Потомки занимают места своих родителей.

2. Genitor (D. Whitley)

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

 Фиксированный размер популяции.

 Фиксированная разрядность генов.

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

 Ограничений на тип кроссовера и мутации нет.

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

3. Hybrid algorithm (L. "Dave" Davis)

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

 Фиксированный размер популяции.

 Фиксированная разрядность генов.

 Любые комбинации стратегий отбора и формирования следующего поколения

 Ограничений на тип кроссовера и мутации нет.

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

4. Island Model GA

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

 Наличие нескольких популяций, как правило, одинакового фиксированного размера.

 Фиксированная разрядность генов.

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

 Ограничений на тип кроссовера и мутации нет.

 Случайный обмен особями между "островами". Если миграция будет слишком активной, то особенности островной модели будут сглажены, и она будет не очень сильно отличаться от моделей ГА без параллелизма.

5. CHC (Eshelman)

CHC расшифровывается как Cross-population selection, Heterogenous recombination and Cataclysmic mutation. Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций, используются популяции небольшого размера, и отбор особей в следующее поколение ведется и между родительскими особями, и между их потомками. В силу этого после нахождения некоторого решения алгоритм перезапускается,