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

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

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

Математический факультет 
Кафедра информатики и прикладной математики

 

 

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

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

 

 

Гелис Илья Александрович 
студент 3 курса специальности  «Математика. Информатика»

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Брест 2012 

Оглавление

Оглавление 2

Введение 3

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

Актуальность 3

Обьект исследования 4

Предмет исследования 4

Цель работы 4

Задачи работы 5

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

1. История  эволюционных вычислений 5

2. Естественный отбор в природе 5

Cредства Windows 71333. Основные понятия генетических алгоритмов 6

4. Общий вид генетического алгоритма 8

5. Пример 14

заключение 18

CПиСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 19

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

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

 

Актуальность

 

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

 

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

 

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

 

Цель работы – это обзор темы «Генетические алгоритмы».

 

 

Задачи работы:

• Познакомиться с основными понятиями генетических алгоритмов
• Рассмотреть общий вид генетического алгоритма
• Рассмотреть генетические операторы
• Рассмотреть применение генетического алгоритма на примере задачи нахождения максимума функции

 

 ОСНОВНАЯ ЧАСТЬ

1. История эволюционных вычислений

История эволюционных вычислений началась с разработки ряда различных  независимых моделей. Основными  стали генетические алгоритмы и  классификационные системы Холланда, опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги "Адаптация в естественных и искусственных системах", ставшей классикой в этой области. В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел и Уолш. Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере. [3]

2. Естественный отбор в природе

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

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

Чтобы сделать понятными  принципы работы генетических алгоритмов, поясним также, как устроены механизмы генетического наследования в природе. В каждой клетке любого животного содержится вся генетическая информация этой особи. Эта информация записана в виде набора очень длинных молекул ДНК (Дезоксирибонуклеиновая Кислота). Каждая молекула ДНК - это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых А, T, C и G. Собственно, информацию несет порядок следования нуклеотидов в ДНК. Таким образом, генетический код индивидуума - это просто очень длинная строка символов, где используются всего 4 буквы. В животной клетке каждая молекула ДНК окружена оболочкой - такое образование называется хромосомой.

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

При размножении животных происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия - кроссовер (cross-over, скрещивание). При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками.

При наследовании возможны мутации из-за радиоактивности или  других влияний, в результате которых  могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида. [4]

3. Основные понятия генетических алгоритмов.

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

Популяция - это конечное множество особей.

Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированным в них множествами параметров задачи, т.е. решений, которые иначе называются точками в пространстве поиска (search points). В некоторых работах особи называются организмами.

Хромосомы (другие названия - цепочки или кодовые последовательности) - это упорядоченные последовательности генов.

Ген (также называемый свойством, знаком или детектором) - это атомарный элемент генотипа, в частности, хромосомы.

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

Фенотип - это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска).

Аллель - это значение конкретного гена, также определяемое как значение свойства или вариант свойства.

Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов - это локи.

Очень важным понятием в  генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функционирование генетических алгоритмов и должна иметь точное и корректное определение. В задачах оптимизации функция приспособленности, как правило, оптимизируется (точнее говоря, максимизируется) и называется целевой функцией. В задачах минимизации целевая функция преобразуется, и проблема сводится к максимизации. В теории управления функция приспособленности может принимать вид функции погрешности, а в теории игр - стоимостной функции. На каждой итерации генетического алгоритма приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, составляющих множество потенциальных решений проблемы, например, задачи оптимизации.

Очередная популяция в  генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин “новое поколение” или “поколение потомков”. [7]

 

4. Общий вид генетического алгоритма

Основной (классический) генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

1) Инициализация, или выбор  исходной популяции хромосом;

2) Оценка приспособленности  хромосом в популяции;

3) Проверка условия остановки  алгоритма;

4) Селекция хромосом;

5) Применение генетических  операторов;

6) Формирование новой  популяции;

7) Выбор “наилучшей”  хромосомы.

Блок-схема основного  генетического алгоритма изображена на следующем рисунке.

Рис. 1. - Блок-схема генетического алгоритма.

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

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

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