Институт вычислительной математики и математической геофизики СОРАН

Тезисы докладов

Статистическое моделирование и методы Монте-Карло

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

Для решения задачи глобальной оптимизации используются различные подходы, как классические, так и все более популярные интервальные, основанные на адаптивном дроблении области определения в сочетании с оцениванием области значений по получающимся подобластям [1, 2]. Такие алгоритмы хорошо работают для функций сложного рельефа, но не слишком большого числа переменных, надежно находя гарантированные двусторонние оценки для глобального оптимума и доставляющих его аргументов.

Ценное свойство современных интервальных методов - доказательность (гарантированность) результатов, но оно же является одной из причин их недостаточной вычислительной эффективности в сравнении с классическими подходами. Возникает вопрос - нельзя ли повысить их эффективность, возможно, отказавшись от доказательности и (или) чисто детерминистского характера интервальных оптимизационных методов в той или иной степени? На наш взгляд, отказ от чистого детерминизма алгоритма и допущение некоторых стохастических переходов в методах интервальной глобальной оптимизации может привести к созданию численных алгоритмов с качественно новыми свойствами, в частности, с улучшенной эффективностью.

Впервые такой подход к решению задач глобальной оптимизации был разработан С.П.~Шарым. В частности, в [3] среди прочих предложена интервальная версия алгоритма "симулированного отжига". Это вероятностный метод, моделирующий одноименный физический процесс. Его имеет смысл применять в тех ситуациях, где определяющим требованием являются простота реализации и желание получить в сложной задаче хоть какие-то результаты за заданное ограниченное время.

В рамках этой работы рассматриваются интервальные версии стохастических алгоритмов в сравнении с некоторыми традиционными интервальными аналогами. Приводятся численные эксперименты по сравнению простейшего классического алгоритма интервальной глобальной оптимизации с интервальными стохастическими алгоритмами, такими как интервальное случайное дробление, метод интервального симулированного отжига и некоторые другие. 1. Hansen E.R., Walster G.W.} Global optimization using interval analysis. - New York: Marcel Dekker, 2004. 2. Kearfott R.B. Rigorous global search: continuous problems. - Dordrecht: Kluwer, 1996. 3. Шарый С.П. Стохастические подходы в интервальной глобальной оптимизации // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения", Иркутск - Северобайкальск, 2-8 июля 2005 года. Том 4 "Интервальный анализ". - Иркутск: ИСЭМ СО РАН, 2005. - C. 85-105.

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:52:06)