Панов Н.
Комбинирование точечных и интервальных методов поиска глобального оптимума
Задача, решению которой посвящена настоящая работа может быть сформулирована следующим образом. Найти глобальный оптимум вещественнозначной целевой функции прямоугольном брусе со сторонами, параллельными координатным осям, который является подмножеством области определения данной функции.
Дифференцируемость целевой функции желательна, но не обязательна. Фактически, единственным важным ограничением, накладываемым на целевую функцию, является то, что она должна задаваться в явном виде: в виде математического выражения или подпрограммы, состоящей из комбинации переменных, арифметических операций и математических функций. Это необходимо для вычисления интервальной оценки [1].
Задачи оптимизации, особенно глобальной, особенно в такой, весьма широкой постановке, часто возникают, например, в конструкторских или экономических задачах. К настоящему моменту разработано множество алгоритмов поиска глобального оптимума [2, 3, 4]. Значительная часть из них применима лишь к определённым подклассам функций. Многие из них разрабатывалась для конкретных типов целевых функций и не эффективны на других, или же требуют тонкой настройки на конкретный класс функций, или же наличие какой-либо априорной информации о целевой функции. Другая существующая крайность это чрезвычайно универсальные алгоритмы, пригодные для решения очень широкого круга задач, но часто не эффективные на большинстве из них. Для решения этой проблемы (чрезвычайно узкой специализации или чрезмерной неэффективности на широком классе задач) был разработан гибридный алгоритм, сочетающий в себе и динамически комбинирующий следующие методы: метод градиентного спуска, точечный и интервальный методы имитации отжига[5] и несколько генетических алгоритмов[6].
Схематично шаги алгоритма можно записать в следующем виде:
- Запускается интервальная процедура распространения ограничений на интервальной оболочке не отбракованной области поиска;
- Над не отбракованной областью поиска запускается интервальный алгоритм адаптивного дробления;
-
Для брусов, признанными перспективными после предыдущего шага, запускается точечный стохастический алгоритм, его результаты используются для отбраковки заведомо бесперспективных областей поиска.
Использование интервальных алгоритмов позволяет гарантировать, что локализованное значение действительно является глобальным оптимумом, а применение классических точечных алгоритмов для направления интервального поиска позволяет значительно повысить их вычислительную эффективность.
[1] Шарый С.П. Конечномерный интервальный анализ. Электронная книга, доступная на http://www-sbras.nsc.ru/interval
[2] Diwekar U. Introduction to Applied Optimization. - Springer, 2008.
[3] Moore R.E., Kearfott R., Cloud M.J. Introduction to Interval Analysis - SIAM, 2009.
[4] Zhigljavsky A., Zilinskas, A. Stochastic Global Optimization - Springer, 2008.
[5] Панов Н.В. Объединение стохастических и интервальных подходов для решения задач глобальной оптимизации функций // Вычислительные технологии. - 2009. - Т.14, #5. - С.49-65.
[6] Панов Н.В. Адаптивный мета-алгоритм глобальной оптимизации // Естественные и технические науки (ISSN 1684-2626). - 2009. #1 (39). - М.: Спутник+, C.315-318.
| Тезисы доклада: | abstracts_84789_ru.pdf |
К списку докладов
