Презентация на тему Стохастические интервальные подходы в задачах глобальной оптимизацииИнтервальный генетический алгоритм

Презентация на тему Презентация на тему Стохастические интервальные подходы в задачах глобальной оптимизацииИнтервальный генетический алгоритм, предмет презентации: Разное. Этот материал содержит 42 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

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


Н. В. Панов, С. П. Шарый

Институт вычислительных технологий СО РАН
г. Новосибирск


Слайд 2
Текст слайда:

Глобальная оптимизация функций




Поиск глобального минимума
( или максимума )
вещественнозначной функции

на прямоугольном брусе Х
со сторонами, параллельными
координатным осям.

Ищем


Слайд 3
Текст слайда:

Глобальная оптимизация функций


Удачная область для применения интервальных методов

В отличии от классических (точечных) методов не требуется знание априорной информации о функции

Константа Липшица

Производные

Интервальное расширение функции, фактически, дает верхнюю и нижнюю оценку оптимума.







Границы могут быть избыточными.

Результат гарантируется


Слайд 4
Текст слайда:

Да


Выход:

Оценка
глобального
оптимума.


Вход:
Целевая функция.
Область.
Допуск на размер бруса.

Извлечь из рабочего списка ведущий (наиболее “перспективный”) брус.


Достигнут
критерий остановки?

Нет

Раздробить брус. Вычислить интервальные расширения целевой функции по брусам-потомкам и добавить их в рабочий список

Блок-схема оптимизационного алгоритма адаптивного интервального дробления


Слайд 5
Текст слайда:

Но

Застаивание и избыточность интервальной оценки могут существенно ухудшить производительность метода.


Слайд 6
Текст слайда:

Целевая функция (шестигорбый верблюд) F = 4x2 + 2.1x4 + 1/3x6 +xy – 4y2 + 4y4


Слайд 7
Текст слайда:

Целевая функция (шестигорбый верблюд) F = 4x2 + 2.1x4 + 1/3x6 +xy – 4y2 + 4y4


Слайд 8
Текст слайда:

Целевая функция Растригина (10ая) F = x2 + y2 – cos(18x) – cos(18y)


Слайд 9
Текст слайда:

Целевая функция Растригина (10ая) F = x2 + y2 – cos(18x) – cos(18y)


Слайд 10
Текст слайда:

Застаивание и избыточность интервальной оценки могут существенно ухудшить производительность метода.


Слайд 11
Текст слайда:

Процесс работы алгоритма

[ «неудобная» функция «Шестигорбый верблюд» ]


Слайд 12
Текст слайда:

Маленький промежуточный итог

Интервальный анализ удобен для задач глобальной оптимизации.

Существующий алгоритм бывает недостаточно эффективен.


Слайд 13
Текст слайда:

Причины неуспешности алгоритма

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


Слайд 14
Текст слайда:

Пути улучшения Процедуры отбраковки

Отбраковка по значению
Тест на монотонность
Тест на выпуклость-вогнутость
Метод Ньютона


Слайд 15
Текст слайда:

Пути улучшения Смена алгоритма [ Отказ от детерминизма ]

Отказываемся от жесткого детерминизма метода и допускаем некоторые статистические переходы.


Слайд 16
Текст слайда:

Случайный интервальный поиск


Извлечь из рабочего списка случайный брус.


Достигнут критерий остановки?

Да

Выход:

Оценка
глобального
оптимума.


Нет

Раздробить брус. Вычислить интервальные расширения целевой функции по брусам-потомкам и добавить их в рабочий список.


Вход:
Целевая функция.
Начальная область определения.
Критерий остановки.



Слайд 17
Текст слайда:

Тестовая функция Трекани

F = x4 + 4x3 + 4x2 + y2


Слайд 18
Текст слайда:

Случайный интервальный поиск

Распределение ширины брусов


Слайд 19
Текст слайда:

Случайный интервальный поиск


Слайд 20
Текст слайда:

Повышение эффективности метода

Отбраковка бесперспективных
Локальные оптимизирующие процедуры
И т.д.


Слайд 21
Текст слайда:

Случайный интервальный поиск с приоритетом

Извлечь из рабочего списка брус случайным образом с учетом ширины.


Достигнут критерий остановки?

Да

Выход:

Глобальный
оптимум.


Нет

Раздробить брус. Вычислить интервальные расширения целевой функции по брусам-потомкам и добавить их в рабочий список.


Вход:
Целевая функция.
Область.
Допуск на размер бруса (критерий остановки).



Слайд 22
Текст слайда:

Параметры исследования

Приоритет по ширине интервала
Приоритет по ширине интервальной оценки


Слайд 23
Текст слайда:

Функция «Розенброк4» (RB4)

Общий вид (слева) и поведение вблизи точки глобального минимума (справа).


Слайд 24
Текст слайда:

Результаты экспериментов


Слайд 25
Текст слайда:

Интервальный симулированный отжиг

Алгоритм Метрополиса
Метод M(RT)2
Алгоритм «Отпуска»
Симулированный отжиг.


Слайд 26
Текст слайда:

Выход:

Глобальный
оптимум целевой
функции.
Количество шагов.
Использованная
память.


Вход:
Целевая функция. Область ее определения. Допуск на размер бруса. Начальная температура.

Случайным образом извлечь брус из рабочего списка.



Да

Нет

Температура < 0
Достигнуто условие выхода?

Поделить брус любым способом на подбрусы-потомки. Вычислить интервальные расширения целевой функции по подбрусам. Добавить брусы-потомки в рабочий список.


На этом брусе
получаем лучшую оценку целевой функции?

Да

Нет

Уменьшить температуру Т.

Нет


Брус при-
нимается с вероятностью
exp(-ΔE / kT). Брус
принят?

Да


Слайд 27
Текст слайда:

Сравнение адаптивного интервального дробления (бисекции) и интервального симулированного отжига на «шестигорбом верблюде»


Слайд 28
Текст слайда:

Целевая функция Растригина (10ая) F = x2 + y2 – cos(18x) – cos(18y)


Слайд 29
Текст слайда:

Сравнение адаптивного интервального дробления (бисекции) и интервального симулированного отжига на функции F = x2 + y2 – cos(18x) – cos(18y)

Сравнение адаптивного интервального дробления (бисекции) и интервального симулированного отжига на функции F = x2 + y2 – cos(18x) – cos(18y)


Слайд 30
Текст слайда:

Алгоритм интервального адаптивного дробления


Слайд 31
Текст слайда:

Интервальный алгоритм симулированного отжига

[ неоптимальные настройки ]


Слайд 32
Текст слайда:

Интервальный генетический алгоритм


Слайд 33
Текст слайда:

Интервальный генетический алгоритм

Популяция

– список брусов

Благоприятные условия:

среда обитания

– оценка значения функции на брусе

способность к воспроизводству

– ширина бруса


Слайд 34
Текст слайда:

Интервальный генетический алгоритм

Вариативность:
Максимальное количество потомков
Минимальное количество потомков
Сколько объектов, начиная с самого приспособленного, могут оставить потомство.
Брусы бьются на равные части, либо же в некой пропорции, «разновесные» дети.

Приспособленность:
Нижняя оценка функции на брусе.
Ширина интервальной оценки на брусе.
Размер бруса.


Слайд 35
Текст слайда:

Интервальный генетический алгоритм

Объединенная функция приспособленности:

f(b) – интервальная оценка целевой функции f на брусе b
f(b) – нижняя граница интервальной оценки (оценка минимума снизу)
wid(f(b)) – ширина (точность) интервальной оценки.


Слайд 36
Текст слайда:

0. Создать начальную популяцию (произвести несколько дроблений).
1. Вычислить функцию приспособленности по новым подбрусам.
2. N из наиболее приспособленных брусов с вероятностью Pn оставляют от Ln до Un потомков.
3. M из неприспособленных брусов с вероятностью Pm оставят от Lm до Um потомков.
4.* Подбрусы проверяются на жизнеспособность (применяются критерии отбраковки)
5.* Если критерий отбраковки был улучшен, случается Эпидемия (улучшенные критерии применяются ко всему списку брусов)

Интервальный генетический алгоритм
глобальной оптимизации


Слайд 37
Текст слайда:

Результаты работы


Слайд 38
Текст слайда:

Вывод

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

2) Применение стохастических подходов
в интервальных методах
глобальной оптимизации оправдано.


Слайд 39
Текст слайда:

Дополнительная информация



Слайд 40
Текст слайда:

Точность интервальных оценок


Слайд 41
Текст слайда:




Слайд 42
Текст слайда:




Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика