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

Содержание:

 

Введение

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

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

1.2 Представление объектов. Кодирование признаков

1.3 Основные генетические операторы

1.4 Схема функционирования генетического алгоритма

Вывод

Глава 2. Задачи оптимизации

2.1 Задачи, решаемые с помощью генетических алгоритмов

2.2 Математическая постановка задачи оптимизации

2.3 Решение Диофантова уравнения

2.4 Пути решения задач оптимизации

2.5 Задача коммивояжера

Вывод

Глава 3. Программная реализация. Создание пособия по генетическим алгоритмам

3.1 Обоснование выбора программного обеспечения

3.2 Описание программной реализации

Заключение

Библиография

 

 

ВВЕДЕНИЕ

 

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

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

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

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

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

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

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

Методы исследования:

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

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

Задачи:

1. проанализировать возможности генетических алгоритмов;
2. изучить особенности генетических алгоритмов;
3. создание электронного пособия по основам генетических алгоритмов;

 

ГЛАВА 1: ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

 

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

 

“XIX веке Чарльз Дарвин совершил кругосветное плавание, собирая информацию для теории эволюции на основе естественного отбора, при котором выживает сильнейший. Мог ли он предполагать, что сто лет спустя математики будут использовать эту теорию для решения задачи об оптимальном маршруте кругосветного путешествия с остановками на многих маленьких островах?..”

Автор: РОСС КЛЕМЕНТ 

Опубликовано в журнале "Компьютерра" №11 от 16 марта 1999 года

 

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

Основной закон наследования интуитивно понятен каждому - он состоит  в том, что потомки похожи на родителей. В частности, потомки более приспособленных родителей будут, скорее всего, одними из наиболее приспособленных в своем поколении. Чтобы понять, на чем основано это сходство, нужно немного углубиться в построение естественной клетки - в мир генов и хромосом [4].

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

При наследовании возможны мутации из-за радиоактивности или  других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида. Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов [8]. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

 

1.2. Представление объектов. Кодирование признаков

 

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

В наиболее часто встречающейся  разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.

Для кодирования таких  признаков можно использовать самый  простой вариант – битовое  значение этого признака. Тогда нам  будет весьма просто использовать ген  определенной длины, достаточной для  представления всех возможных значений такого признака. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма [9]. Значения кодов Грея рассмотрены в таблице ниже:

 

Двоичное кодирование			Кодирование по коду Грея
десятичное	двоичное	шестнадца- теричное	десятичное	двоичное	шестнадца- теричное
0	000	0h	0	0000	0h
1	0001	1h	1	0001	1h
2	0010	2h	3	0011	3h
3	0011	3h	2	0010	2h
4	0100	4h	6	0110	6h
5	0101	5h	7	0111	7h
6	0110	6h	5	0101	5h
7	0111	7h	4	0100	4h
8	1000	8h	12	1100	Ch
9	1001	9h	13	1101	Dh
10	1010	Ah	15	1111	Fh
11	1011	Bh	14	1110	Eh
12	1100	Ch	10	1010	Ah
13	1101	Dh	11	1011	Bh
14	1110	Eh	9	1001	9h
15	1111	Fh	8	1000	8h

 

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих  объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины [10]. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит

 

0010

1010

1001

0100

1101

теперь мы можем определить значения признаков

Признак	Значение гена		Двоичное значение признака		Десятичное значение признака
Признак 1	0010		0011	3
Признак 2		1010	1100	12
Признак 3	1001		1110	14
Признак 4		0100	0111	7
Признак 5	1101		1001	9

 

 

 

 

 

 

 

 

 

 

1.3 Основные генетические операторы

 

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

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