Алгоритм глобальной оптимизации, использующий деревья решений для выявления локальных экстремумов
Автор: Силенко Д.И., Лебедев И.Г.
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая и системная информатика
Статья в выпуске: 2 (59), 2023 года.
Бесплатный доступ
В работе рассматривается решение задач многомерной глобальной оптимизации с применением деревьев решений для выявления областей притяжения локальных минимумов. Предполагается, что целевая функция задачи задана как «черный ящик» и удовлетворяет условию Липшица с априори неизвестной константой. Мы предлагаем способ выделения окрестностей локальных экстремумов целевой функции на основе анализа накопленной поисковой информации средствами машинного обучения. Это позволяет принять решение о запуске локального метода для уточнения значения функции в локальном минимуме, что может ускорить сходимость алгоритма. Выдвинутое предположение подтверждается результатами вычислительных экспериментов, демонстрирующих ускорение при решении серии тестовых задач.
Деревья решений, глобальная оптимизация, многоэкстремальные функции, локальная оптимизация
Короткий адрес: https://sciup.org/143180999
IDR: 143180999 | УДК: 519.853.4 | DOI: 10.24412/2073-0667-2023-2-21-33
Global optimization algorithm that uses decision trees to find local extrema
The paper considers the algorithms for solving the multidimensional global optimization problems using decision tree to reveal the attraction regions of the local minima. We suppose, that the target function is defined as a “black box” and satisfied Lipschitz condition with unknown constant. We propose a method for selecting the local extrema neighborhood of the target function based on analysis of accumulated search information using machine learning methods. This allows us to make a decision to run a local method, which can speed up the convergence of the algorithm. The proposition was confirmed by the results of numerical experiments demonstrating the speedup when solving a series of test problems.
Список литературы Алгоритм глобальной оптимизации, использующий деревья решений для выявления локальных экстремумов
- 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.
- 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.
- Langdon W.B. Graphics processing units and genetic programming: an overview // Soft Computing, 2011. V. 15. N 8, P. 1657-1669.
- Евтушенко Ю.Г., Малкова В. У., Станевичюс А. А. Параллельный поиск глобального экс-тремума функций многих переменных // Ж. вычисл. матем. и матем. физ, 2009. Т. 49. № 2. С. 246-260.
- Не 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.
- 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.
- Стронгин P. Г., Гергель В.П., Гришагин В. А., Баркалов К. А. Параллельные вычисления в задачах глобальной оптимизации. Издательство Московского университета, 2013.
- 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.
- Химмельблау Д. Прикладное нелинейное программирование. МИР, 1975.
- Nelder J., Mead R. A simplex method for function minimization // Computer Journal, 1965. V. 7. N 4. P. 308-313.
- Brahmbhatt S. Practical OpenCV (Technology in Action). New York: Apress, 2013.
- ОpenCV (open source computer vision) documentation, (accessed: 10 July 2022). [El. Res.]: https://docs.opencv.org/4.x/de/dd6/ml\_intro.html.
- 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.
- 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.
- Сергеев Я.Д., Квасов Д. Е. Диагональные методы глобальной оптимизации. Физматлит, 2008.
- 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.
