'

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

Понравилась презентация – покажи это...





Слайд 0

Стохастические интервальные подходы в задачах глобальной оптимизации Интервальный генетический алгоритм Н. В. Панов, С. П. Шарый Институт вычислительных технологий СО РАН г. Новосибирск


Слайд 1

Глобальная оптимизация функций Поиск глобального минимума ( или максимума ) вещественнозначной функции на прямоугольном брусе Х со сторонами, параллельными координатным осям. Ищем


Слайд 2

Глобальная оптимизация функций Удачная область для применения интервальных методов В отличии от классических (точечных) методов не требуется знание априорной информации о функции Константа Липшица Производные Интервальное расширение функции, фактически, дает верхнюю и нижнюю оценку оптимума. Границы могут быть избыточными. Результат гарантируется


Слайд 3

Да Выход: Оценка глобального оптимума. Вход: Целевая функция. Область. Допуск на размер бруса. Извлечь из рабочего списка ведущий (наиболее “перспективный”) брус. Достигнут критерий остановки? Нет Раздробить брус. Вычислить интервальные расширения целевой функции по брусам-потомкам и добавить их в рабочий список Блок-схема оптимизационного алгоритма адаптивного интервального дробления


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

Маленький промежуточный итог Интервальный анализ удобен для задач глобальной оптимизации. Существующий алгоритм бывает недостаточно эффективен.


Слайд 12

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


Слайд 13

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


Слайд 14

Пути улучшения Смена алгоритма [ Отказ от детерминизма ] Отказываемся от жесткого детерминизма метода и допускаем некоторые статистические переходы.


Слайд 15

Случайный интервальный поиск Извлечь из рабочего списка случайный брус. Достигнут критерий остановки? Да Выход: Оценка глобального оптимума. Нет Раздробить брус. Вычислить интервальные расширения целевой функции по брусам-потомкам и добавить их в рабочий список. Вход: Целевая функция. Начальная область определения. Критерий остановки.


Слайд 16

Тестовая функция Трекани F = x4 + 4x3 + 4x2 + y2


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

Случайный интервальный поиск с приоритетом Извлечь из рабочего списка брус случайным образом с учетом ширины. Достигнут критерий остановки? Да Выход: Глобальный оптимум. Нет Раздробить брус. Вычислить интервальные расширения целевой функции по брусам-потомкам и добавить их в рабочий список. Вход: Целевая функция. Область. Допуск на размер бруса (критерий остановки).


Слайд 21

Параметры исследования Приоритет по ширине интервала Приоритет по ширине интервальной оценки


Слайд 22

Функция «Розенброк4» (RB4) Общий вид (слева) и поведение вблизи точки глобального минимума (справа).


Слайд 23

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


Слайд 24

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


Слайд 25

Выход: Глобальный оптимум целевой функции. Количество шагов. Использованная память. Вход: Целевая функция. Область ее определения. Допуск на размер бруса. Начальная температура. Случайным образом извлечь брус из рабочего списка. Да Нет Температура < 0 Достигнуто условие выхода? Поделить брус любым способом на подбрусы-потомки. Вычислить интервальные расширения целевой функции по подбрусам. Добавить брусы-потомки в рабочий список. На этом брусе получаем лучшую оценку целевой функции? Да Нет Уменьшить температуру Т. Нет Брус при- нимается с вероятностью exp(-DE / kT). Брус принят? Да


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

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


Слайд 32

Интервальный генетический алгоритм Популяция – список брусов Благоприятные условия: среда обитания – оценка значения функции на брусе способность к воспроизводству – ширина бруса


Слайд 33

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


Слайд 34

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


Слайд 35

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


Слайд 36

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


Слайд 37

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


Слайд 38

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


Слайд 39

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


Слайд 40


Слайд 41


×

HTML:





Ссылка: