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

Загрузка...

главная страница Рефераты Курсовые работы текст файлы добавьте реферат (спасибо :)Продать работу

поиск рефератов

Курсовая на тему Генетические алгоритмы

скачать
похожие рефераты • Точное совпадение: 2 реферата
подобные качественные рефераты

Размер: 127.03 кб.
Язык: русский
Разместил (а): Ольга
12.11.2010
1 2 3    
Содержание:
Введение
Глава 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 году. Множество областей научного знания многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим современникам, предполагающим, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Однако Дарвин обнаружил главный механизм развития: отбор в соединении с изменчивостью. Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорные, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемые в Природе.  Поэтому не удивительно, что ученые, занимающиеся компьютерными исследованиями, в поисках вдохновения обратились к теории эволюции. Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в естественных системах, была очень привлекательной. Эта надежда является причиной появления ряда вычислительных систем, построенных на принципах естественного отбора.
Итак, в природе постоянно происходит процесс решения задач оптимизации. Задачи оптимизации — наиболее распространенный и важный для практики класс задач. Их приходится решать каждому из нас либо в быту, распределяя свое время между различными делами, либо на работе, добиваясь максимальной скорости работы программы или максимальной доходности компании — в зависимости от должности.    
Благодаря открытиям последних ста лет современной науке известны все основные механизмы эволюции, связанные с генетическим наследованием. Эти механизмы достаточно просты по своей идее, но остроумны (если к природе применимо это слово) и эффективны. Удивительно, но простое моделирование эволюционного процесса на компьютере позволяет получить решения многих практических задач. Такие модели получили название “генетические алгоритмы” и уже широко применяются в различных областях.    
В процессе изучения различных подходов к решению задач оптимизации нами выдвигается гипотеза что,  решение задач оптимизации возможно с помощью генетических алгоритмов.
Объектом изучения данной курсовой работы являются генетические алгоритмы.
Предмет изучения – применение генетических алгоритмов для нахождения решения оптимизационной задачи.
Методы исследования:
o сбор и анализ литературных источников по данной теме;
o изучение особенностей создания и использования генетических алгоритмов;
o моделирование работы генетического алгоритма на компьютере применимо к нахождению решения задачи оптимизации.
Целью данной курсовой работы является разработка электронного пособия,  в котором поэтапно описывается решение задачи о нахождении кратчайшего маршрута в существующей системе дорог.
Задачи:
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 Основные генетические операторы
Как известно в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется скрещивание (его также называют кроссовер или кроссинговер). Этот оператор определяет передачу признаков родителей потомкам. Действует он следующим образом:
o из популяции выбираются две особи, которые будут родителями;
o определяется (обычно случайным образом) точка разрыва;
o потомок определяется как конкатенация части первого и второго родителя.
Рассмотрим функционирование этого оператора
Хромосома_1:
0000000000
Хромосома_2:
1111111111
Допустим, разрыв происходит после 3-го бита хромосомы, тогда получаем.
Хромосома_1:
0000000000
>>
000
1111111
Результирующая хромосома 1
Хромосома_2:
1111111111
>>
111
0000000
Результирующая хромосома 2
Итак, рассмотрим все же операторы по порядку:
1) кроссинговер - создание структуры, основанной на двух структурах - заменой одной части первой структуры на ту же область во второй.
Пример: из (A, B, C, D, E) и (a, b, c, d, e) получится (A, B, c, d, E).
Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.
Следующий генетический оператор предназначен для того, чтобы поддерживать разнообразие особей с популяции. Он называется оператором мутации. При использовании данного оператора каждый бит в хромосоме с определенной вероятностью инвертируется. Кроме того, используется еще и так называемый оператор инверсии, который заключается в том, что хромосома делится на две части, и затем они меняются местами. Схематически это можно представить следующим образом:
000
1111111
>>
1111111
000
2) инверсия - перестановка в структуре некоторой ее части наоборот
Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 0, 1, 0, 1, 0).
 3) мутация - замена в структуре одного из значений случайно выбранной компоненты
Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 1, 1, 0, 1, 0).
В принципе для функционирования генетического алгоритма достаточно этих двух генетических операторов, но на практике применяют еще и некоторые дополнительные операторы или модификации этих двух операторов. Например, кроссовер может быть не одноточечный (как было описано выше), а многоточечный, когда формируется несколько точек разрыва (чаще всего две). Кроме того, в некоторых реализациях алгоритма оператор мутации представляет собой инверсию только одного случайно выбранного бита хромосомы.
1.4. Схема функционирования генетического алгоритма
Теперь, зная как интерпретировать значения генов, перейдем к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.
Инициировать начальный момент времени t=0 . Случайным образом сформировать начальную популяцию, состоящую из k особей. 
Вычислить приспособленность каждой особи и популяции в целом (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
1.         Выбрать особь  из популяции. 
2.         С определенной вероятностью (вероятностью кроссовера ) выбрать вторую особь из популяции и произвести оператор кроссовера.
3.         С определенной вероятностью (вероятностью мутации) выполнить оператор мутации.
4.         С определенной вероятностью (вероятностью инверсии ) выполнить оператор инверсии.
5.         Поместить полученную хромосому в новую популяцию
6.         Выполнить операции, начиная с пункта 3, k раз.
7.         Увеличить номер текущей эпохи t=t+1.
8.         Если выполнилось условие остановки, то завершить работу, иначе переход на шаг 2 [13].
Распишем более подробно следующие этапы:
1. Выбор родительской пары .
Первый подход самый простой - это случайный выбор родительской пары ("панмиксия"), когда обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции, причем любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции.
    продолжение
1 2 3    

Добавить курсовую работу в свой блог или сайт
Удобная ссылка:

Скачать курсовую работу бесплатно
подобрать список литературы


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


Постоянный url этой страницы:
Курсовая Генетические алгоритмы


Разместите кнопку на своём сайте:
Рефераты
вверх страницы


© coolreferat.com | написать письмо | правообладателям | читателям
При копировании материалов укажите ссылку.