Реферат: Генетический алгоритм и его сущность

🛑 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Введение…………………………………………………………………..2
Описание Генетического Алгоритма……………………………………3
Результаты тестирования………………………………………………...6
Заключение………………………………………………………………11
Список литературы………………………………………………………13
Приложение………………………………………………………………14
В наше время перед человечеством каждый день возникает огромное множество проблем. И человечество нашло большое количество разных способов их решения. Одним из способов оптимизации, который хорошо себя зарекомендовал, является Эволюционный Алгоритм, и как его частный случай Генетический Алгоритм. Этот алгоритм основан на принципах биологической эволюции. Он способен отыскивать решения практически при полном отсутствии предположений о характере исследуемой функции.На сегодняшний день генетические алгоритмы доказали свою конкурентноспособность при решении многих NP-трудных задач и особенно в практических приложениях, где математические модели имеют сложную структуру и применение стандартных методов динамического или линейного программирования крайне затруднено.
Основной механизм эволюции - это естественный отбор. Его суть состоит в том, что более приспособленные особи имеют больше возможностей для выживания и размножения и, следовательно, приносят больше потомства, чем плохо приспособленные особи. При этом благодаря передаче генетической информации (генетическому наследованию) потомки наследуют от родителей основные их качества. Таким образом, потомки сильных индивидуумов также будут относительно хорошо приспособленными, а их доля в общей массе особей будет возрастать. После смены нескольких десятков или сотен поколений средняя приспособленность особей данного вида заметно возрастает. Именно это и лежит в основе алгоритма.
Меня очень заинтересовали генетические алгоритмы, т.к. ранее я не встречалась с алгоритмами решающими практически любую оптимизационную задачу. Целью моей работы было рассмотреть различные модификации алгоритма на тестовых функциях и проанализировать, при какой модификации алгоритм для всех тестовых функций показывает хорошие результаты.
Генетический алгоритм- это метод поиска решений практически любой оптимизационной задачи, моделирующий процессы природной эволюции.
Генетический алгоритм состоит из нескольких этапов:
Рассмотрим каждый из этих этапов подробно.
На первом этапе ( Инициализация
) случайным образом выбирается первоначальная популяция хромосом (генотипов). Хромосома состоит из генов, которые задаются в бинарном виде, и это является отличительной чертой генетических алгоритмов. Прежде чем проводить Инициализацию, требуется посчитать длину хромосом (количество генов), которые будут использоваться. Длина зависит от количества переменных и области допустимых значений.
Выращивание
- это второй шаг алгоритма, который подразумевает восстановление индивида (фенотипа) по известному генотипу, например - перевод из двоичной системы в десятичную систему исчисления. Выращивание может проводиться, как для целых, так и для вещественных чисел.
Следующий этап это Оценивание
. Он подразумевает вычисление значений функции пригодности индивидов (качества решений-кандидатов).
Селекция
- во время этого шага выбираются особи из текущей популяции и заносятся в популяцию родителей, из которых в свою очередь отбирается пара индивидов, которые, в конце концов, будут скрещиваться (важно заметить, что всё это происходит случайным образом). Для имитации естественной селекции индивиды с более высокой пригодностью должны выбираться с большей вероятностью. Существует большое число различных видов селекции.
Пятый этап называется Скрещивание
. Оно также бывает нескольких видов.
a) При Одноточечном скрещивании
случайным образом выбирается точка разрыва родительской хромосомы, затем в одного из потомков копируется первая часть первого родителя и вторая часть второго, а во второго потомка первая часть второго родителя и вторая часть первого родителя. После чего случайным образом выбирается выживший потомок. Можно сделать и несколько иначе: так же случайным образом находится точка разрыва, после чего случайным образом выбирается, чья часть будет первой и чья соответственно второй, затем выбранные части копируются в потомка.
b) При Двухточечном скрещивании
случайным образом выбираются две точки разрыва, после чего в одного потомка копируются первая и третья части случайным образом выбранного родителя и вторая часть второго родителя. Либо в первого потомка копируются первая и третья части первого родителя и вторая второго, а во второго потомка первая и третья части второго родителя и вторая часть первого, и после этого случайным образом выбирается выживший потомок. Не следует оценивать обоих потомков, до того как выбран выживший, так как их пригодность не влияет на выбор, а её вычисление является наиболее долгим процессом.
c) При Равномерном скрещивании
случайным образом (для каждого гена) выбирается номер (первый, второй) родителя, чей ген и записывается в потомка. В этом случае родителей может быть больше двух, в том числе возможно участие всей популяции родителей в целом.
И последний этап это Мутация
. Мутация состоит из выполнения(обычно небольших) изменений в значениях одного или нескольких генов в хромосоме. В двоичных хромосомах мутация состоит в инвертировании случайным образом выбранного бита генотипа, например 1010101010 --> 1011101010.В генетических алгоритмах мутация рассматривается как метод восстановления потерянного генетического материала (а не как поиск лучшего решения). В генетических алгоритмах мутация применяется к генам с низкой вероятностью. Можно выбирать вероятность в зависимости от длины хромосомы p m

= , где M
- число бит в хромосоме.
Генетический алгоритм- это итерационный процесс. После мутации алгоритм снова возвращается ко второму шагу (Выращивание). Так повторяется некоторое количество раз. Количество повторов называется количеством поколений, и оно выбирается подходяще для каждой конкретной задачи. Также и сам алгоритм запускается несколько раз (число прогонов алгоритма). Количество поколений и прогонов выбирается таким образом, чтобы алгоритм хорошо искал решение, а так же работал быстро.
Описание: Решение функции находили в целых числах.
Описание: Вокруг глобального минимума находится еще несколько локальных минимумов. Поэтому для улучшения результатов поиска, приходится увеличивать ресурсы (количество поколений).
Описание: Вокруг глобального минимума, находится область, на которой значения функции достаточно близки к значению минимума, но т.к. явных локальных минимумов нет, алгоритм работает достаточно хорошо и при меньших ресурсах.
Описание: функция отличается тем ,что на заданной области в большой ее части функция принимает одно и тоже значение и есть небольшая область, на которой сосредоточено несколько локальных минимумов, среди которых находится и глобальны минимум. Из результатов видно, что при небольшом увеличении ресурсов, алгоритм хорошо работает и с этой функцией, а, например, поиск локального спуска не смог найти бы решение.
Описание: Сложность функции состоит в том, что вокруг глобального минимума, по кругу расположены локальные минимумы, и перепутать их с глобальным достаточно легко. Но при еще большем увеличении ресурсов, алгоритм снова показывает неплохие результаты.
Описание: у этой функции вокруг глобального минимума находится очень много точек локального минимума, и даже при увеличении ресурсов алгоритм с трудом находит решение, но все таки находит, хоть и с малой вероятностью.
Описание: функция так же имеет локальные минимумы рядом с глобальным, но на взятой области их не много, и алгоритм работает хорошо даже при небольших затратах.
Описание: из-за увеличения области, увеличивается и количество локальных минимумов, но увеличив ресурсы, мы снова видим неплохой результат.
Замечание: графики исследуемых функций представлены в приложении.
Я долго подбирала нужное количество ресурсов, при которых алгоритм дает хорошие результаты. Затем я множество раз запускала алгоритм, и в результатах тестирования приведены усредненные результаты. Затем я проводила исследования, какая же модификация алгоритма работает лучше. Для этого я снова составила таблицу. «+» в данной таблице отмечены модификации, в которых был лучший результат (бралось 3 наилучших результата для каждой функции) , «-» худшие результаты.
Из таблицы видно, что наилучшей модификацией является пропорциональная селекция + 2-точечное скрещивание + средняя мутация.
Наихудший результат так однозначно определить сложнее, но плохие результаты показали пропорциональная селекция + 1-точечное скрещивание + низкая мутация, турнирная селекция + 1-точечное скрещивание +высокая мутация, , турнирная селекция + равномерное скрещивание + высокая мутация, пропорциональная селекция + равномерное скрещивание + высокая мутация.

Работать с генетическими алгоритмами очень интересно. В дальнейшем я планирую, разработать свои собственные модификации, которые улучшат работу алгоритма, и затем с помощью генетического алгоритма буду решать интересные мне прикладные задачи.
3. Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995.
4. Батищев Д.И., Гуляева П.А., Исаев С.А. Генетический алгоритм для решения задач невыпуклой оптимизации / Тез.докл. Междунар. конф. "Новые информационные технологии в науке, образовании и бизнесе", Гурзуф, 1997.
6. Исаев С.А.. Генетические алгоритмы - эволюционные методы поиска. URL: http://rv.ryazan.ru/~bug/library/ai/isaev/2/part1.html.
8. Росс К. Генетические алгоритмы: почему они работают? когда их применять? / Компьютерра, 1999, № 11
9. Скурихин А.Н. Генетические алгоритмы / Новости искусственного интеллекта, 1995, №4, с. 6-46.

Название: Генетический алгоритм и его сущность
Раздел: Рефераты по биологии
Тип: реферат
Добавлен 19:52:55 12 июня 2011 Похожие работы
Просмотров: 39
Комментариев: 13
Оценило: 2 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Реферат: Генетический алгоритм и его сущность
Дипломная работа по теме Совершенствование сбытовой деятельности торговой организации
Эссе 5 Абзацев
Эссе На Тему Родной Язык Казахский
Сочинение По Произведению Гоголя Петербургские Повести
Курсовая Работа На Тему Лечебное Питание
Сочинение Про Воробья 6 Класс
Курсовая работа по теме Внешний долг Российской Федерации
Реферат: An Analysis Of In Search Of Respect
Реферат: Екатерина II - великая императрица. Скачать бесплатно и без регистрации
Дипломная работа по теме Макроэкономические основы антикризисного управления предприятием
Реферат: Основные задачи и этапы разработки финансового плана предприятия
Реферат Закаливание Детей Раннего Возраста
Как Писать Эссе Правила
Подготовка К Историческому Сочинению
Курсовая работа: Розробка математичної програми в середовищі С++
Реферат: The Metamorphosis By Kafka Essay Research Paper
Реферат: Взаимодействие человека и организации. Скачать бесплатно и без регистрации
Короткое Сочинение На Тему Праздник
Реферат: Euthanasia Informational Outlo Essay Research Paper Euthanasia
Слова Из Слова Курсовик
Статья: История западноевропейского воспитания: основные этапы развития и их смысл
Реферат: Украина тени коррупции
Сочинение: Мастерство воплощения мимолетных настроений и переживаний в поэзии А. А. Фета