АЛГОРИТМ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ, ИСПОЛЬЗУЮЩИЙ ДЕРЕВЬЯ РЕШЕНИЙ ДЛЯ ВЫЯВЛЕНИЯ ЛОКАЛЬНЫХ ЭКСТРЕМУМОВ

EDN: MLGKOX

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

Список литературы

1.  Ferreiro М. , Garcia J. А. , Lopez-Salas J. G., Vazquez С. An efficient implementation of parallel simulated annealing algorithm in GPUs // Journal of global optimization, 2013. V. 57. N 3. P. 863-890. 2. Garcia-Martinez J.M., Garzon E. M., Ortigosa P. M. A GPU implementation of a hybrid evolutionary algorithm: Gpuego // Journal of super-computing, 2014. V. 70. N 2. P. 684-695. 3. Langdon W.B. Graphics processing units and genetic programming: an overview // Soft Computing, 2011. V. 15. N 8, P. 1657-1669. 4. Евтушенко Ю.Г., Малкова В. У., Станевичюс А. А. Параллельный поиск глобального экс-тремума функций многих переменных // Ж. вычисл. матем. и матем. физ, 2009. Т. 49. № 2. С. 246-260. 5. Не J., Verstak A., Watson L. Т., Sosonkina М. Design and implementation of a massively parallel version of direct // Computational optimization and applications, 2008. V. 40. N 2. P. 217-245. 6. Paulavicius R., Zilinskas J., Grothey A. Parallel branch and bound for global optimization with combination of Lipschitz bounds // Optimization methods and software, 2011. V. 26. N 3. P. 487-498. 7. Стронгин P. Г., Гергель В.П., Гришагин В. А., Баркалов К. А. Параллельные вычисления в задачах глобальной оптимизации. Издательство Московского университета, 2013. 8. Gergel V. Р. A global optimization algorithm for multivariate functions with lipschitzian first derivatives // Journal of Global Optimization, 1997. V. 10. N 3. P. 257-281. 9. Химмельблау Д. Прикладное нелинейное программирование. МИР, 1975. 10. Nelder J., Mead R. A simplex method for function minimization // Computer Journal, 1965. V. 7. N 4. P. 308-313. 11. Brahmbhatt S. Practical OpenCV (Technology in Action). New York: Apress, 2013. 12. ОpenCV (open source computer vision) documentation, (accessed: 10 July 2022). [El. Res.]: https://docs.opencv.org/4.x/de/dd6/ml\_intro.html. 13. Sysoyev, Barkalov K., Sovrasov V., Lebedev L, Gergel V. Globalizer — a parallel software system for solving global optimization problems // Lecture Notes in Computer Science, 2017. V. 10421. N LNCS. P. 492-499. 14. Gaviano M., Lera D., Kvasov D.E., Sergeyev Y. D. Software for generation of classes of test functions with known local and global minima for global optimization // ACM Transactions on Mathematical Software, 2003. V. 29. P. 469-480. 15. Сергеев Я.Д., Квасов Д. Е. Диагональные методы глобальной оптимизации. Физматлит, 2008. 16. Sergeyev Y. D., Kvasov D.E. Global search based on efficient diagonal partitions and a set of Lipschitz constants // SIAM Journal on Optimization, 2006. V. 16. N 3. P. 910-937.