О некоторых способах балансировки локального и глобального поиска в параллельных алгоритмах глобальной оптимизации
Авторы
-
К.А. Баркалов
- В.В. Рябов
- С.В. Сидоров
Ключевые слова:
Аннотация
Данная работа продолжает развитие информационно-статистического подхода к минимизации многоэкстремальных функций при невыпуклых ограничениях, получившего название индексного метода глобальной оптимизации. Решение многомерных задач сводится к решению эквивалентных им одномерных. Редукция основана на использовании кривых Пеано, однозначно отображающих единичный отрезок вещественной оси на гиперкуб. Используется схема построения множества кривых Пеано ("вращаемые развертки"), которую можно эффективно применять при решении задачи на кластере с десятками и сотнями процессоров. Основное внимание уделяется применению смешанной локально-глобальной схемы вычислений для ускорения сходимости параллельного алгоритма, а также применению локального спуска при каждом улучшении оценки глобального оптимума (локальное уточнение рекорда) с последующим продолжением глобального поиска. Работа выполнена при поддержке Совета по грантам Президента Российской Федерации (гранты № МК-1536.2009.9 и № НШ-64729.2010.9). Статья рекомендована к печати программным комитетом международной научной конференции «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи» (http://agora.guru.ru/abrau2010)
Загрузки
Опубликован
Выпуск
Раздел
Библиографические ссылки
- Стронгин Р.Г. Поиск глобального оптимума. М.: Знание, 1990.
- Стронгин Р.Г. Параллельная многоэкстремальная оптимизация с использованием множества разверток // Ж. вычисл. матем. и матем. физ. 1991. 31, № 8. 1173-1185.
- Стронгин Р.Г., Баркалов К.А. О сходимости индексного алгоритма в задачах условной оптимизации с epsilon-резервированными решениями // Математические вопросы кибернетики. М.: Наука, 1999. 273-288.
- Strongin R.G., Sergeyev Ya.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Dordrecht: Kluwer Academic Publishers, 2000.
- Баркалов К.А., Стронгин Р.Г. Метод глобальной оптимизации с адаптивным порядком проверки ограничений // Ж. вычисл. матем. и матем. физ. 2002. 42, № 9. 1338-1350.
- Баркалов К.А. Ускорение сходимости в задачах условной глобальной оптимизации. Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2005.
- Баркалов К.А., Рябов В.В., Сидоров С.В. Использование кривых Пеано в параллельной глобальной оптимизации // Материалы IX Международной конференции-семинара «Высокопроизводительные параллельные вычисления на кластерных системах». Владимир, 2009. 44-47.
- Стронгин Р.Г., Гергель В.П., Баркалов К.А. Параллельные методы решения задач глобальной оптимизации // Известия высших учебных заведений. Приборостроение. 2009. 52, № 10. 25-32.
- Jones D.R., Perttunen C.D., Stuckman B.E. Lipschitzian optimization without the Lipschitz constant // J. of Optimization Theory and Applications. 1993. 79, N 1. 157-181.
- Gablonsky M.J. Modifications of the DIRECT algorithm. Ph.D. thesis, North Carolina State University. Raleigh, 2001.
- Gablonsky M.J., Kelley C.T. A locally-biased form of the DIRECT algorithm // J. of Global Optimization. 2001. 21, N 1. 27-37.
- Gaviano M., Kvasov D.E., Lera D., Sergeyev Ya.D. Software for generation of classes of test functions with known local and global minima for global optimization // ACM TOMS. 2003. 29, N 4. 469-480 // (verb|http://si.deis.unical.it/ yaro/GKLS.html|).
- Lera D., Sergeyev Ya.D. Lipschitz and Hölder global optimization using space-filling curves // Applied Numerical Mathematics. 2010. 60, N 1-2. 115-129.
