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

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

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

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

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

на тему:

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

Выполнила:

Ст. группы ПС-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}ⁿ }.

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

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

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

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

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

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

2.1. Выбрать родителей i ₁ , i ₂ из популяции I_k .

2.2. Построить i' по i ₁ , i ₂ .

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

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

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

Литература

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

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

3. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостади

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать