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

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

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

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

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

Целевая функция (шестигорбый верблюд) F = 4x x / 3 x 6 +xy – 4y 2 + 4y 4

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

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

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

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

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

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

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

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

Тестовая функция Трекани F = x 4 + 4x 3 + 4x 2 + y 2

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

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

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

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

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

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

Результаты экспериментов МетодВремя работы Адаптивное интервальное дробление100 / 100 Случайный интервальный поиск / 350 Случайный интервальный поиск с приоритетом (вариант 1) 67 / 272 Случайный интервальный поиск с приоритетом (вариант 2) 20 / 99 Случайный интервальный поиск с приоритетом (вариант 3) 138 / 73

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

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

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

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

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

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

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

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

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

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

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

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

Результаты работы МетодВремя работы Адаптивное интервальное дробление100 / 100 Генетический алгоритм, постоянные коэффициенты / Генетический алгоритм, случайные коэффициенты / ~120 Генетический алгоритм, случайно-адаптивные коэффициенты ~36 / ~100

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

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

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