Генетические алгоритмы. 2 Формальное определение Генетический алгоритм это алгоритм, который позволяет найти удовлетворительное решение к аналитически.

Презентация:



Advertisements
Похожие презентации
Генетические алгоритмы. 2 Формальное определение Генетический алгоритм это алгоритм, который позволяет найти удовлетворительное решение к аналитически.
Advertisements

Генетические алгоритмы Студент гр. 4057/2 Мима Андрей Доклад на семинаре по специальности.
Генетические поисковые алгоритмы, основные положения,особенности Генетические поисковые алгоритмы, основные положения,особенности Ву Суан Выонг ЭМС-49.
Генетические поисковые алгоритмы, основные положения,особенности Генетические поисковые алгоритмы, основные положения,особенности Ву Суан Выонг ЭМС-49.
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ Область применения 1.Нахождение экстремумов функций 2. Решение задач размещения ресурсов 3. Решение задач экономического планирования.
Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. К ВЫБОРУ РАЗМЕРА ПОПУЛЯЦИИ.
Применение генетических алгоритмов для генерации тестов к олимпиадным задачам по программированию Буздалов М.В., СПбГУ ИТМО.
Генетические алгоритмы Егоров Кирилл, гр Чураков Михаил, гр
Анализ метода оптимизации на основе моделирования перемещения бактерий Костин Антон, 4 курс ФУПМ МФТИ.
Лекция по основам теории алгоритмов Генетические алгоритмы Составитель: к.т.н. Варламов А.Д
МЕТОДЫ ОПТИМИЗАЦИИ § 1. Основные понятия. Под оптимизацией понимают процесс выбора наилучшего варианта из всех возможных В процессе решения задачи оптимизации.
Подготовил Андреев Алексей. Задача о назначениях Задача о рюкзаке Задача коммивояжера Задача теории распределений Задача маршрутизации транспорта Задача.
Применение генетического программирования для генерации автомата в задаче об «Умном муравье» Царев Ф.Н., Шалыто А.А. IV Международная научно-практическая.
Большая часть классического численного анализа основывается на приближении многочленами, так как с ними легко работать. Однако для многих целей используются.
Синергетика и компьютерное моделирование. Игра «Жизнь» Один из подходов к моделированию процессов самоорганизации – «клеточные автоматы» – появился благодаря.
Технологии ИИ1 ТЕХНОЛОГИИ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА Лекция 4. Генетические алгоритмы.
Лабораторная работа Изучение приспособленности организмов МОУ «Железнодорожная СОШ 1» Назарова Н.Г.
Применение генетического программирования в задаче поиска усердных бобров Д. О. Соколов, П.В. Федотов, Ф. Н. Царев Научный руководитель – А. А. Шалыто.
Выполнил: Горелов С.С. Под руководством: с.н.с. Афонин С.А., проф. Васенин В.А. Усечение пространства поиска в полуструктурированных данных при помощи.
Анализ вариационных рядов. Анализ вариационных рядов. Основные понятия и определения Генеральная совокупность – множество всех значений, характеризующих.
Транксрипт:

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

2 Формальное определение Генетический алгоритм это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым проблемам через последовательный подбор и комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию.

3 Зачем нужны ГА? Генетические алгоритмы применяются для решения следующих задач: – Оптимизация функций – Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний) – Настройка и обучение искусственной нейронной сети – Составление расписаний – Игровые стратегии – Аппроксимация функций – Искусственная жизнь – Биоинформатика

4 Ключевые работы Родителем современной теории генетических алгоритмов считается Д.Х. Холланд (J. Holland). Однако сначала его интересовала, прежде всего, способность природных систем к адаптации, а его мечтой было создание такой системы, которая могла бы приспосабливаться к любым условиям окружающей среды. В 1975 году Холланд публикует свою самую знаменитую работу «Adaptation in Natural and Artificial Systems».В ней он впервые ввёл термин «генетический алгоритм» и предложил схему классического генетического алгоритма (canonical GA). В дальнейшем понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА. Ученики Холланда - Кеннет Де Йонг (Kenneth De Jong) и Дэвид Голдберг (David E. Goldberg) - внесли огромный вклад в развитие ГА. Наиболее известная работа Голдберга - «Genetic algorithms in search optimization and machine learning» (1989).

5 Принцип работы ГА Популяция – совокупностью всех «особей», представляющих собой строки, кодирующие одно из решений задачи. С помощью функции приспособленности: – наиболее приспособленные (более подходящие решения) получают возможность скрещиваться и давать потомство – наихудшие (плохие решения) удаляются из популяции и не дают потомства Таким образом, приспособленность нового поколения в среднем выше предыдущего. В классическом ГА: – начальная популяция формируется случайным образом – размер популяции (количество особей N) фиксируется и не изменяется в течение работы всего алгоритма – каждая особь генерируется как случайная L-битная строка, где L длина кодировки особи – длина кодировки для всех особей одинакова

6 Схема работы любого ГА Шаг алгоритма состоит из трех стадий: 1.генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения 2.скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения 3.мутация нового поколения

Применение генетических алгоритмов в задачах оптимизации – поиска минимума функции Швефеля

Были разработаны специальные функции для тестирования различных оптимизационных алгоритмов. Такие функции характеризуются множеством локальных минимумов и одним глобальным. Задача состоит в том, чтобы найти этот глобальный минимум и при этом не застрять в одном из локальных минимумов. В качестве такой функции примем функцию Ханс-Пауля Швефеля, предложенную им в своей работе 1977 года. В оригинальной работе она выражена так: Здесь аргументов функции может быть множество – это многокритериальная оптимизация. Для геометрической интерпретации поиска примем эту функцию от двух аргументов, так как большее количество аргументов уже не представимо графически в нашем трёхмерном пространстве. Трёхмерная поверхность этой функции имеет следующий вид:

На плоскости XY под трёхмерным графиком находится контурный график с изображёнными линиями одинакового уровня. Для дальнейшей работы строим плоский график этих уровней, причём раскрашиваем его в серые тона, где более тёмные места означают меньшие значения функции. Затем на этот график накладываются точки особей популяции в количестве 1000 особей. Это начальная популяция – поколение 1. Рядом с этим графиком строится гистограмма распределения значений функции по популяции. Затем для каждой особи популяции вычисляется целевая функция – это значение функции. По величине целевой функции сортируется популяция. Верхние 500 особей с меньшими значениями будут родителями, а 500 нижних не выживут и не перейдут в следующее поколение. Их места займут дети верхних особей. Затем кроссовер между родителями, и родители вместе с детьми составляют поколение 2. После этого к каждой особи нового поколения применяется оператор мутации с вероятностью 3%. Затем также осуществляется отбор и далее аналогично.

По графикам видно, что почти всё поле покрыто точками особей. Гистограмма показывает, что математическое ожидание около 0, так как функция симметрична относительно 0, и значения её простираются примерно от до Переходим к последующим поколениям.