On using the decision trees to identify the local extrema in parallel global optimization algorithm
Автор: Barkalov K.A., Lebedev I.G., Silenko D.I.
Статья в выпуске: 3 т.12, 2023 года.
Бесплатный доступ
In the present work, the solving of the multidimensional global optimization problems using decision tree to reveal the attractor regions of the local minima is considered. The objective function of the problem is defined as a “black box”, may be non-differentiable, multi-extremal and computational costly. We assume that the function satisfies the Lipschitz condition with a priory unknown constant. Global search algorithm is applied for the search of global minimum in the problems of such type. It is well known that the solution complexity essentially depends on the presence of multiple local extrema. Within the framework of the global search algorithm, we propose a method for selecting the vicinity of local extrema of the objective function based on analysis of accumulated search information. Conducting such an analysis using machine learning techniques allows making a decision to run a local method, which can speed up the convergence of the algorithm. This suggestion was confirmed by the results of numerical experiments demonstrating the speedup when solving a series of test problems.
Global optimization, multiextremal functions, parallel computing, machine learning, decision tree
Короткий адрес: https://sciup.org/147241761
IDR: 147241761 | УДК: 519.853.4 | DOI: 10.14529/cmse230301
Об использовании деревьев решений для выявления областей притяжения локальных минимумов в параллельном алгоритме глобальной оптимизации
В работе рассматривается решение многомерных задач многоэкстремальной оптимизации с использованием деревьев решений для выявления областей притяжения локальных минимумов. Целевая функцияпредставлена как «черный ящик», она может быть недифференцируемой, многоэкстремальной и вычислительно трудоемкой. Для функции предполагается, что она удовлетворяет условию Липшица с априоринеизвестной константой. Для решения поставленной задачи многоэкстремальной оптимизации применятсяалгоритм глобального поиска. Хорошо известно, что сложность решения существенно зависит от наличия нескольких локальных экстремумов. В данной работе предложена модификация алгоритма, в которойопределяются окрестности локальных минимумов целевой функции на основе анализа накопленной поисковой информации. Проведение такого анализа с использованием методов машинного обучения позволяетпринять решение о запуске локального метода, что может ускорить сходимость алгоритма. Данный подход был подтвержден результатами численных экспериментов, демонстрирующих ускорение при решениинабора тестовых задач.
Список литературы On using the decision trees to identify the local extrema in parallel global optimization algorithm
- Ferreiro A., Garcia J., Lopez-Salas J., Vazquez C. An efficient implementation of parallel simulated annealing algorithm in GPUs. J. Glob. Optim. 2013. Vol. 57, no. 3. P. 863–890. DOI: 10.1007/s10898-012-9979-z.
- Garcia-Martinez J., Garzon E., Ortigosa P. A GPU implementation of a hybrid evolutionary algorithm: GPuEGO. J. Supercomput. 2014. Vol. 70, no. 2. P. 684–695. DOI: 10.1007/s11227-014-1136-7.
- Langdon W. Graphics processing units and genetic programming: an overview. Soft Computing. 2011. Vol. 15, no. 8. P. 1657–1669. DOI: 10.1007/s00500-011-0695-2.
- Evtushenko Y., Malkova V., Stanevichyus A.A. Parallel global optimization of functions of several variables. Comput. Math. Math. Phys. 2009. Vol. 49, no. 2. P. 246–260. DOI: 10.1134/S0965542509020055.
- He J., Verstak A., Watson L., Sosonkina M. Design and implementation of a massively parallel version of DIRECT. Comput. Optim. Appl. 2008. Vol. 40, no. 2. P. 217–245. DOI: 10.1007/s10589-007-9092-2.
- Paulavicius R., Žilinskas J., Grothey A. Parallel branch and bound for global optimization with combination of Lipschitz bounds. Optim. Method. Softw. 2011. Vol. 26, no. 3. P. 487–498. DOI: 10.1080/10556788.2010.551537.
- Strongin R.G., Sergeyev Y.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Dordrecht: Kluwer Academic Publishers, 2000. DOI: 10.1007/978-1-4615-4677-1.
- Hooke R., Jeeves T. “Direct Search” Solution of Numerical and Statistical Problems. J. ACM. 1961. Vol. 8, no. 2. P. 212–229. DOI: 10.1145/321062.321069.
- Nocedal J., Wright S. Numerical Optimization. New York: Springer, 2006. DOI: 10.1007/b98874.
- Kelley C.T. Iterative Methods for Optimization. Philadelphia: SIAM, 1999. DOI: 10.1137/1.9781611970920.
- Barkalov K., Lebedev I. Solving multidimensional global optimization problems using graphics accelerators. Communications in Computer and Information Science. 2016. Vol. 687. P. 224–235. DOI: 10.1007/978-3-319-55669-7_18.
- Barkalov K., Strongin R. A global optimization technique with an adaptive order of checking for constraints. Computational Mathematics and Mathematical Physics. 2002. Vol. 42, no. 9. P. 1289–1300.
- Gergel V.P. A global optimization algorithm for multivariate functions with Lipschitzian first derivatives. Journal of Global Optimization. 1997. Vol. 10, no. 3. P. 257–281. DOI: 10.1023/A:1008290629896.
- Himmelblau D. Applied Nonlinear Programming. New York: McGraw-Hill, 1972. 498 p.
- Brahmbhatt S. Practical OpenCV (Technology in Action). New York: Apress, 2013. DOI: 10.1007/978-1-4302-6080-6_1.
- Sergeyev Y., Kvasov D. Global Search Based on Efficient Diagonal Partitions and a Set of Lipschitz Constants. SIAM J. Optim. 2006. Vol. 16, no. 3. P. 910–937. DOI: 10.1137/040621132.
- Barkalov K., Lebedev I., Kocheganova M., Gergel V. Combining local and global search in a parallel nested optimization scheme. Communications in Computer and Information Science. 2020. Vol. 1263. P. 100–112. DOI: 10.1007/978-3-030-55326-5_8.
