Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

Реальная база готовых
студенческих работ

Узнайте стоимость индивидуальной работы!

Вы нашли то, что искали?

Вы нашли то, что искали?

Да, спасибо!

0%

Нет, пока не нашел

0%

Узнайте стоимость индивидуальной работы

это быстро и бесплатно

Получите скидку

Оформите заказ сейчас и получите скидку 100 руб.!


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

Тип Реферат
Предмет Информатика
Просмотров
534
Размер файла
72 б
Поделиться

Ознакомительный фрагмент работы:

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

Министерство транспорта и связи Украины

Одесская национальная академия связи им.О.С. Попова

Кафедра информатизации и управления

Комплексное задание

на тему:

«ГЕНЕТИЧЕСКИЙ АЛГОРИТМ»

Выполнила:

Ст. группы ПС-3.12

Волощук В.С.

Проверил:

зав.кафедры Адреев А.И.

Одесса 2010

Содержание

1История

2Описание алгоритма

2.1Создание начальной популяции

2.2Размножение (Скрещивание)

2.3Мутации

2.4Отбор

3Применение генетических алгоритмов

4Пример тривиальной реализации на C++

Примечания

Книги

Ссылки

Литература


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

Генети́ческий алгори́тм (англ.genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическуюэволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.


1.История

«Отцом-основателем» генетических алгоритмов считается Джон Холланд (en:John Henry Holland), книга которого «Адаптация в естественных и искусственных системах» (1975)[1] является основополагающим трудом в этой области исследований. Ему же принадлежит Генетические алгоритмы.

Идея генетических алгоритмов заимствована у живой природы и состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. Разработчик генетических алгоритмов выступает в данном случае как "создатель", который должен правильно установить законы эволюции, чтобы достичь желаемой цели как можно быстрее. Впервые эти нестандартные идеи были применены к решению оптимизационных задач в середине 70-х годов . Примерно через десять лет появились первые теоретические обоснования этого подхода . На сегодняшний день генетические алгоритмы доказали свою конкурентноспособность при решении многих NP-трудных задач и особенно в практических приложениях, где математические модели имеют сложную структуру и применение стандартных методов типа ветвей и границ, динамического или линейного программирования крайне затруднено.

Ежегодно в мире проводится несколько конференций по этой тематике, информацию о которых можно найти в Интернет по адресам:

http://www.natural-selection.com/eps/

http://mat.gsia.cmu.edu/Conferences/ .

Общую схему генетических алгоритмов проще всего понять, рассматривая задачи безусловной оптимизации

max{ f (i) | i{0,1}n}.

Примерами служат задачи размещения, стандартизации, выполнимости и другие. Стандартный генетический алгоритм начинает свою работу с формирования начальной популяцииI0 = {i1, i2, …, is} — конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью вероятностных жадных алгоритмов . Как мы увидим ниже, выбор начальной популяции не имеет значения для сходимости процесса в асимптотике, однако формирование "хорошей" начальной популяции (например из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума.

На каждом шаге эволюции с помощью вероятностного оператора селекции выбираются два решения, родители i1, i2. Оператор скрещивания по решениям i1, i2 строит новое решение i' , которое затем подвергается небольшим случайным модификациям, которые принято называть мутациями. Затем решение добавляется в популяцию, а решение с наименьшим значением целевой функции удаляется из популяции.

Доказательство теоремы схем.

1. Выбрать начальную популяцию I0иположить

f* = max{ f (i)| i I0}, k : = 0.

2. Пока не выполнен критерий остановки делать следующее.

2.1. Выбрать родителей i1, i2 из популяции Ik.

2.2. Построить i' по i1, i2.

2.3. Модифицировать i' .

2.4. Если f* < f(i' ), то f*: = f(i' ).

2.5. Обновить популяцию и положить k : = k+1.

Гипотеза 1.

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

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


2. Описание алгоритма

Схема работы генетического алгоритма

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

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

Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.

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

· нахождение глобального, либо субоптимального решения;

· исчерпание числа поколений, отпущенных на эволюцию;

· исчерпание времени, отпущенного на эволюцию.

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

Таким образом, можно выделить следующие этапы генетического алгоритма:

1. Задать целевую функцию (приспособленности) для особей популяции

2. Создать начальную популяцию

· (Начало цикла)

1. Размножение (скрещивание)

2. Мутирование

3. Вычислить значение целевой функции для всех особей

4. Формирование нового поколения (селекция)

5. Если выполняются условия останова, то (конец цикла), иначе (начало цикла).

2.1 Создание начальной популяции

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

2.2 Размножение (Скрещивание)

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

Размножение в разных алгоритмах определяется по-разному — оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.

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

2.3 Мутации

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

2.4 Отбор

На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.


3. Применение генетических алгоритмов

Генетические алгоритмы применяются для решения следующих задач:

1. Оптимизация функций

2. Оптимизация запросов в базах данных

3. Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)

4. Настройка и обучение искусственной нейронной сети

5. Задачи компоновки

6. Составление расписаний

7. Игровые стратегии

8. Теория приближений

9. Искусственная жизнь

10. Биоинформатика (фолдинг белков)

4. Пример тривиальной реализации на C++

Поиск в одномерном пространстве, без скрещивания.

# include <iostream># include <algorithm># include <numeric> int main(){usingnamespace std;srand((unsigned)time(NULL));constint N =1000;int a[N];//заполняемнулямиfill(a, a+N, 0);for(;;){//мутация в случайную сторону каждого элемента:for(int i =0; i < N;++i)if(rand()%2 == 1)a[i]+=1;elsea[i]-=1;//теперь выбираем лучших, отсортировав по возрастанию...sort(a, a+N);//... и тогда лучшие окажутся во второй половине массива.//скопируем лучших в первую половину, куда они оставили потомство, а первые умерли:copy(a+N/2, a+N, a /*куда*/);//теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше.cout<< accumulate(a, a+N, 0)/ N << endl;}}
Книги

· Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М: Физматлит, 2003. — С. 432. — ISBN 5-9221-0337-7

· Курейчик В. М., Лебедев Б. К., Лебедев О. К. Поисковая адаптация: теория и практика. — М: Физматлит, 2006. — С. 272. — ISBN 5-9221-0749-6

· Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. — 2-е изд.. — М: Физматлит, 2006. — С. 320. — ISBN 5-9221-0510-8

· Гладков Л. А., Курейчик В. В, Курейчик В. М. и др. Биоинспирированные методы в оптимизации: монография. — М: Физматлит, 2009. — С. 384. — ISBN 978-5-9221-1101-0

· Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. — 2-е изд.. — М: Горячая линия-Телеком, 2008. — С. 452. — ISBN 5-93517-103-1

Ссылки

-Научные статьи по генетическим алгоритмам

-Реализация генетического алгоритма для .NET Framework 2.0

-Проект CuberGA — расширяемый framework для реализации генетических алгоритмов

· Эволюционные вычисления

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

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

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

· Подборка статей по теме Генетические алгоритмы

· Основные операции генетического алгоритма

· Использование генетических алгоритмов в проблеме автоматического написания программ

· Реализация генетических алгоритмов в среде MATLAB v6.12

· Сергей Николенко. Генетические алгоритмы (слайды) — лекция № 4 из курса «Самообучающиеся системы»

· geneticprogramming.us

· Обзор методов эволюции нейронных сетей

· Генерирование автоматов состояний с помощью ГА

· Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. — Запоріжжя: ЗНТУ, 2009. — 375 с.(укр.)

· A Field Guide to Genetic Programming. — Lulu.com, freely available from the internet, 2008. — ISBN 978-1-4092-0073-4

· Special Interest Group for Genetic and Evolutionary Computation (former ISGEC)(англ.)

· JAGA (Java API for Genetic Algorithms) — Extensible and pluggable open source API for implementing genetic algorithms and genetic programming applications in Java(англ.)

· IlliGAL (Illinois Genetic Algorithms Laboratory) Home Page(англ.)

· Evolutionary Computation Laboratory at George-Mason University(англ.)

· GENITOR Research Group (CS, Colorado)(англ.)

· Evolutionary and Adaptive Systems (EASy) at Sussex(англ.)

· Genetic Algorithms Articles(англ.)

· Evolutionary Algorithms Research Group at University of Dortmund(англ.)

· Evolutionary Digest Archive(англ.)

· GAUL: Genetic Algorithm Utility Library — нетривиальная обобщенная свободная реализация GA(англ.)

· Очень большая подборка статей по использованию генетических алгоритмов в задачах многокритериальной оптимизации(англ.)

· Genetic Algorithms in Ruby(англ.)

· Lakhmi C. Jain; N.M. Martin Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications. - CRC Press, CRC Press LLC, 1998


Литература

1. Александров Д. А. Алгоритм муравьиной колонии для задачи о минимальном покрытии. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т3 (1998), Иркутск, с. 17–20.

2. Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.

3. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер. 2. т6 (1999), № 1, с. 12–32.

4. Горбачевская Л. Е., Кочетов Ю. А. Вероятностная эвристика для двухуровневой задачи размещения. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т1 (1998), Иркутск, с. 249–252.

5. Гэри В., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

6. Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд.физ.-мат.наук. Омск, 2000.

7. Растригин Л.А. Случайный поиск — специфика, этапы истории и предрассудки. Вопросы кибернетики. Вып. 33 (1978), с. 3–16.

8. Aggarwal C. C., Orlin J. B., Tai R. P. Optimized crossover for maximum independent set. Oper. Res. v45 (1997), pp 225–234.

9. Balas E., Niehaus W. Finding large cliques in arbitrary graphs by bipartite matching. Cliques, coloring, and satisfiability. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. v26 (1996), pp 29–49.

10. Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems. J. Heuristics. v4 (1998), N4, pp 107–122.

11. Boese K. D., Kahng A. B., Muddu S. A new adaptive multi–start technique for combinatorial global optimizations. Oper. Res. Lett. v16 (1994), N2, pp 101-114.

12. Bremermann H. J., Roghson J., Salaff S. Global properties of evolution processes. Natural automata and useful simulations. London: Macmillan. 1966. pp 3-42.


Нет нужной работы в каталоге?

Сделайте индивидуальный заказ на нашем сервисе. Там эксперты помогают с учебой без посредников Разместите задание – сайт бесплатно отправит его исполнителя, и они предложат цены.

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

avatar
Математика
Физика
История
icon
136882
рейтинг
icon
5824
работ сдано
icon
2637
отзывов
avatar
Математика
История
Экономика
icon
135700
рейтинг
icon
3028
работ сдано
icon
1325
отзывов
avatar
Химия
Экономика
Биология
icon
90036
рейтинг
icon
1992
работ сдано
icon
1252
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
50 871 оценка star star star star star
среднее 4.9 из 5
СамГМУ
Все сделано быстро, без замечаний Попросил добавить пару деталий, без споров все было сделано
star star star star star
РАНХ и ГС Дзержинский филиал
Работа выполнена досрочно,но не были проставлены ссылки которые дожны быть.Замечания испра...
star star star star star
БАТиП
Всё чудесно, работа выполнена досрочно. Не первый раз обращаюсь и не последний, всё на выс...
star star star star star

Последние размещённые задания

Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

Тема: смертная казнь за и против.

Реферат, Основы Права

Срок сдачи к 10 апр.

только что

«Уголовное право в РФ в отношении несовершеннолетних».

Другое, Обществознание

Срок сдачи к 7 апр.

1 минуту назад

2 Заданий в файле

Другое, Финансовый менеджмент

Срок сдачи к 31 мар.

1 минуту назад

Эффективные коммуникативные техники

Реферат, Деловой русский язык

Срок сдачи к 28 мар.

1 минуту назад
1 минуту назад

Реферат на тему следственный осмотр

Реферат, уголовно-процессуальное право

Срок сдачи к 31 мар.

2 минуты назад

Выполнить лабы по теоретические основы электротехники

Лабораторная, Электротехника

Срок сдачи к 31 мар.

3 минуты назад

Решить 4 задания

Решение задач, Таможенная статистика

Срок сдачи к 30 мар.

3 минуты назад

практическая

Контрольная, метрология

Срок сдачи к 2 апр.

3 минуты назад

Решить

Решение задач, Интегральные Исчисления

Срок сдачи к 30 мар.

3 минуты назад

сделать задания указанные в методичке

Другое, экономика и менеджмент горного дела

Срок сдачи к 31 мар.

4 минуты назад
4 минуты назад

Задача + чертеж

Курсовая, Детали машин и основы конструирования

Срок сдачи к 8 апр.

7 минут назад

Решение задач

Решение задач, Физика

Срок сдачи к 29 мар.

7 минут назад

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

Другое, конституционное право

Срок сдачи к 1 апр.

8 минут назад

Решить задачу

Решение задач, теоретические основы электротехники

Срок сдачи к 28 мар.

9 минут назад

Сделать презентацию

Презентация, Информатика

Срок сдачи к 31 мар.

10 минут назад

Социальное обеспечение медицинских работников

Курсовая, Социальное обеспечение

Срок сдачи к 4 апр.

10 минут назад
planes planes
Закажи индивидуальную работу за 1 минуту!

Размещенные на сайт контрольные, курсовые и иные категории работ (далее — Работы) и их содержимое предназначены исключительно для ознакомления, без целей коммерческого использования. Все права в отношении Работ и их содержимого принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие в связи с использованием Работ и их содержимого.

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно