Автор работы: Пользователь скрыл имя, 02 Июня 2015 в 20:23, курсовая работа
В последние годы при решении задач функциональной оптимизации стали широко применяться адаптивные методы поиска, среди которых особую популярность завоевали эволюционные и, в том числе, генетические алгоритмы (ГА).
Генетический алгоритм – это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде.
1.Техническое задание…………………………………………………………3
2.Введение………………………………………………………………………4
3.Анализ технического задания……………………………………………….6
4.Генетические алгоритмы…………………………………………………….7
5.Естественная эволюция………………………………………………………8
6.Понятие оптимизации………………………………………………………10
7.Целевая функция и кодирование…………………………………………..11
8.Общая структура генетического алгоритма………………………………12
9.Описание простого генетического алгоритма…………………………….15
Результаты работы программы………………………………………………19
Выводы………………………………………………………………………..20
Список литературы……………………………………………………………21
Факультет дистанционного обучения
Томский Государственный Университет Систем Управления и Радиоэлектроники (ТУСУР)
Курсовая работа
по дисциплине «Информатика»
Вариант 8
Тема «Генетические алгоритмы»
Выполнил:
Раков А.Ю.
г. Нижневартовск
2015
Содержание
1.Техническое задание………………………
2.Введение……………………………………………………
9.Описание простого генетическ
1.Техническое задание
Рассмотреть равномерное скрещивание и инверсионную мутацию.
Каждая переменная кодируется 30 битами.
Провести расчеты для 30 и 100 поколений.
Сравнить получающиеся решения при размерах популяции 10, 20, 30 особей.
2.Введение
В последние годы при решении задач функциональной оптимизации стали широко применяться адаптивные методы поиска, среди которых особую популярность завоевали эволюционные и, в том числе, генетические алгоритмы (ГА).
Генетический алгоритм – это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде.
Генетический алгоритм состоит:
1) Хромосома. Решение рассматриваемой проблемы. Состоит из генов;
2) Начальная популяция хромосом;
3) Набор операторов для
4) Целевая функция для оценки приспособленности решений.
Генетические алгоритмы работают с совокупностью ”особей” – популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее ”приспособленности” согласно к тому, насколько ”хорошо” соответствующее ей решение задачи.
Работа генетического алгоритма начинается с генерирования некоторой популяции хромосом, каждой из которой соответствует точка в пространстве поиска. Затем происходит оценка этих структур и распределение между ними репродуктивных возможностей таким образом, чтобы хромосомы, представляющие лучшее решение исходной проблемы, получили больше шансов для ”воспроизводства” чем хромосомы, соответствующие худшим решениям.
Генетический алгоритм - это не просто еще один вариант случайного поиска, т. к. при отборе новых точек с ожидаемыми более хорошими характеристиками, они эффективно использует предыдущую информацию.
Важной особенностью генетического алгоритма является то, что они обеспечивают сходимость к глобальному оптимуму (это очень важно для задач, где целевая функция имеет несколько локальных экстремумов). Также генетический алгоритм позволяют находить оптимум даже в случае разрывной целевой функции.
Генетические алгоритмы рассматриваются обычно как функциональные оптимизаторы, но область проблем, в которой они могут быть применены, весьма широка.
Для решения данной задачи необходимо знать, что же такое генетический алгоритм и вообще алгоритм в целом.
Алгоритм – это набор инструкций, который описывает, как некоторое задание может быть выполнено.
Генетический алгоритм (ГА) – это стохастический, эвристический оптимизационный метод, основанный на идее эволюции с помощью естественного отбора, выдвинутой Дарвином.
Как известно, у Природы есть свой метод создания лучших организмов. Дарвин назвал его Эволюцией вследствие Естественного отбора.
При сексуальном размножении потомку передается информация о строении родителей путем передачи ДНК. При этом для построения ДНК потомка, родительские ДНК меняются своими участками. Этот процесс называется скрещиванием.
При этом новый ген представляет собой комбинацию информации из родительских ДНК. При размножении может произойти мутация, т.е. случайное изменение небольшой ее части.
Генетические алгоритмы работают с совокупностью «особей» - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее «приспособленности» согласно тому, на сколько «хорошо» соответствующее ей решение задачи.
Для компьютерных алгоритмов решения (поиска), использующих вычислительные модели механизмов естественной эволюции в качестве ключевых структурных элементов, используется обобщенное название - эволюционные алгоритмы.
В генетическом алгоритме (ГА) каждый индивид кодируется сходным с ДНК методом - в виде строки из символов одного типа. Длина строки (ДНК) постоянна. Популяция из индивидов подвергается процессу эволюции с интенсивным использованием скрещивания и мутаций.
Процесс эволюции останавливается, когда популяция отвечает определенному критерию - критерию завершения.
Принципиальная схема работы ГА состоит из следующих основных фаз:
Шаг эволюции можно разделить на следующие этапы:
Основной механизм эволюции – это естественный отбор. Его суть состоит в том, что более приспособленные особи имеют больше возможностей для выживания и размножения и, следовательно, приносят больше потомства, чем плохо приспособленные особи. При этом благодаря передаче генетической информации (генетическому наследованию) потомки наследуют от родителей основные их качества. Таким образом, потомки сильных индивидуумов также будут относительно хорошо приспособленными, а их доля в общей массе особей будет возрастать. После смены нескольких десятков или сотен поколений средняя приспособленность особей данного вида заметно возрастет.
Чтобы сделать понятными принципы работы ГА, поясним также, как устроены механизмы генетического наследования в природе. В каждой клетке любого животного содержится вся генетическая информация этой особи. Она записана в виде набора очень длинных молекул ДНК Каждая молекула ДНК – это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых А, Т, С,G. Собственно, информацию несет порядок следования нуклеотидов в ДНК. Таким образом, генетический код индивидуума – это просто очень длинная строка символов, где используются всего четыре буквы. В живой клетке каждая молекула окружена оболочкой – это образование называется хромосомой.
Каждое врожденное качество особи кодируется определенной частью хромосомы, которая называется геном этого свойства.
При размножении животных происходит слияние двух родительских половых клеток и их ДНК взаимодействия, образуя ДНК потомка. Основной способ взаимодействия – скрещивание. При скрещивании ДНК предков делятся на две части, а затем обмениваются своими половинками.
При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут изменится некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде – при этом произойдет скачкообразное повышение приспособленности вида.
Как уже были отмечено выше, эволюция - это процесс постоянной оптимизации биологических видов. Естественный отбор гарантирует, что наиболее приспособленные особи дадут большое количество потомков, а благодаря генетическому наследованию, часть потомков не только сохранит высокую приспособленность родителей, но будет иметь и новые свойства. Если эти новые свойства оказываются полезными, то с большой вероятностью они перейдут и в следующее поколение. Таким образом, происходит накопление полезных качеств и постепенное повышение приспособленности биологического вида в целом. Зная, как решается задача оптимизации видов в природе, применим похожий метод для решения разных реальных задач. Задачи оптимизации - наиболее распространенный и важный для практики класс задач. Их приходится решать любому из нас или в быту, распределяя свое время между разными делами, или на работе, добиваясь максимальной скорости работы программы или максимальной прибыльности компании - в зависимости от должности. Среди этих задач есть решаемые простым путем, но есть и такие, точное решение которых найти практически невозможно.
Среди компонентов, образующих генетический алгоритм, в большинстве случаев только два непосредственно определяются конкретной задачей - это кодировка задачи (отображение пространства поиска на пространство битовых строк) и целевая функция. Рассматривая задачу параметрической оптимизации, заключающуюся в определении набора переменных, миниимизирующих некоторую величину (цель). Или иначе задача состоит в поиске минимума некоторой функции F(X1, X2, …, XM).
На первом этапе обычно делается предположение, что переменные, представляющие параметры, могут быть представлены битовыми строками. Это означает, что переменные предварительно дискретизируются некоторым образом и что область дискретных значений соответствует некоторой степени 2. Например, с 10 битами на параметр мы получаем область из 210 = 1024 дискретных значений.
Битовую строку длины N можно рассматривать как целое двоичное число I, которому соответствует некоторое вещественное значение r из заданного диапазона . Это соответствие устанавливается формулой: .
За исключением проблемы кодирования, целевая функция обычно дается как часть постановки задачи. С другой стороны, разработка целевой функции иногда может непосредственно входить в разработку алгоритма оптимизации или поиска решения. В других случаях значение целевой функции может зависеть от реализации и давать только приближенный или частный результат.
В природе особи в популяции конкурируют друг с другом за различные ресурсы. Те особи, которые наиболее приспособлены к окружающим условиям, будут иметь относительно больше шансов на воспроизводство потомков. Слабо приспособленные особи либо совсем не произведут потомства, либо их потомство будет очень немногочисленным. Это означает, что гены от высоко адаптированных или приспособленных особей будут распространяться в увеличивающемся количестве потомков на каждом последующем поколении. Таким образом, вид развивается, все лучше приспосабливаясь к среде обитания.
Генетические алгоритмы используют прямую аналогию с таким механизмом. Они работают с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. В конечном итоге популяция будет сходиться к оптимальному решению задачи.