Параллельный алгоритм для получения равномерного приближения решений множества задач глобальной оптимизации с нелинейными ограничениями
Автор: Соврасов Владислав Валерьевич, Баркалов Константин Александрович
Статья в выпуске: 2 т.9, 2020 года.
Бесплатный доступ
В данной работе рассматривается построение параллельной версии алгоритма глобальной оптимизации, решающего одновременно множество задач с нелинейными ограничениями и получающего при этом равномерные оценки решений на этом множестве. Последнее свойство позволяет наиболее оптимально распределять вычислительные ресурсы, т.к. в процессе работы алгоритма погрешности численного решения во всех задачах убывают примерно с одинаковой скоростью. Алгоритм присваивает приоритет каждой задаче и на каждой итерации производит вычисления целевых функций в нескольких задачах параллельно. При окончании работы метода в произвольный момент времени во всех задачах из решаемой серии будут получены решения сходного качества. Серии из нескольких задач возникают, если задача глобальной оптимизации имеет дискретный параметр или, например, при решении задачи многокритериальной оптимизации методом свертки критериев. Рассматриваемый алгоритм использует отображения типа кривой Пеано для редукции многомерных задач оптимизации к одномерным. Эффективность реализованного алгоритма протестирована на наборах искусственно сгенерированных задач глобальной оптимизации, а также при решении серии задач, полученной в результате скаляризации задачи многокритериальной оптимизации. Также экспериментально подтверждена равномерная сходимость метода.
Глобальная оптимизация, параллельные вычисления, алгоритмы прямой оптимизации, равномерная сходимость
Короткий адрес: https://sciup.org/147234272
IDR: 147234272 | УДК: 004.021, | DOI: 10.14529/cmse200201
Parallel global optimization algorithm for obtaining uniform convergence when simultaneously solving a set of global optimization problems
In this work building of a parallel version of a method simultaneously solving a set of constrained global optimization problems is considered. This method converges uniformly to solutions of all the problems. That allows the method to arrange computational resources in an optimal way, since uniform convergence guarantees approximately equal precision of numerical solutions at the whole set of problems at the each iteration of optimization. The algorithm assigns a priority to each problem, and then at the each iteration carries out calculation of objective functions and constraints in several problems in parallel. If the method stops at any arbitrary moment, in all the problems numerical sulutions with the similar accuracy will be obtained. Sets of similar global optimization problems appear for an instance after scalarization of multi-objective problems or when a global optimization problem has a discrete parameter which takes a finite number of possible values. The considered method uses Peano-type curves to transform multidimensional problems into univariate ones. Efficiency of the implemented parallel algorithm is evaluated on several sets of synthetically generated constrained global optimization problems and on a scalarized multi-objective problem. Also the uniform convergence was confirmed numerically by validation quality of intermediate solutions during the optimization process.
Список литературы Параллельный алгоритм для получения равномерного приближения решений множества задач глобальной оптимизации с нелинейными ограничениями
- Barkalov К., Lebedev I. Comparing two approaches for solving constrained global optimization problems // Learning and Intelligent Optimization (Nizhny Novgorod, Russia, June, 19-21, 2017). Springer International Publishing, Cham. 2017. P. 301-306. DOI: 10.1007/978-3-319-69404-7_22.
- Barkalov K., Lebedev I. Parallel algorithm for solving constrained global optimization problems // Parallel Computing Technologies (Nizhni Novgorod, Russia, Sept., 4-8, 2017). Springer International Publishing, Cham. 2017. P. 396-404. DOI: 10.1007/978-3-319-62932-2_38.
- Barkalov K., Strongin R. Solving a set of global optimization problems by the parallel technique with uniform convergence // Journal of Global Optimization. 2018. Vol. 71, no. 1. P. 21-36. DOI: 10.1007/sl0898-017-0555-4.
- Beiranvand V., Hare W., Lucet Y. Best practices for comparing optimization algorithms // Optimization and Engineering. 2017. Vol. 18, no. 4. P. 815-848. DOI: 10.1007/sll081-017-9366-1.
- Ehrgott M. Multicriteria Optimization. Springer-Verlag, Berlin, Heidelberg, 2005. 323 p. DOI: 10.1007/3-540-27659-9.
- Evtushenko Y., Posypkin M. A deterministic approach to global box-constrained optimization // Optimization Letters. 2013. Vol. 7. P. 819-829. DOI: 10.1007/sll590-012-0452-l.
- Gaviano M., Kvasov D.E., Lera D., Sergeev Ya.D. Software for generation of classes of test functions with known local and global minima for global optimization // ACM Transactions on Mathematical Software. 2003. Vol. 29, no. 4. P. 469-480. DOI: 10.1145/962437.962444.
- Gergel V., Barkalov K., Lebedev I., Rachinskaya M., Sysoyev A. A flexible generator of constrained global optimization test problems // AIP Conference Proceedings. 2019. Vol. 2070, no. 1. P. 020009. DOI: 10.1063/1.5089976.
- Jones D.R. The direct global optimization algorithm // The Encyclopedia of Optimization. Springer, Heidelberg, 2009. P. 725-735. DOI: 10.1007/978-0-387-74759-0_128.
- Paulavivcius R., Zilinskas J., Grothey A. Parallel branch and bound for global optimization with combination of Lipschitz bounds // Optimization Methods and Software. 1997. Vol. 26, no. 3. P. 487-498. DOI: 10.1080/10556788.2010.551537.
- Riquelme N., Von Lucken C., Baran B. Performance metrics in multi-objective optimization // 2015 Latin American Computing Conference (Arequipa, Peru, Oct., 19-23, 2015). IEEE. 2015. P. 1-11. DOI: 10.1109/clei.2015.7360024.
- Sergeyev Y., Kvasov D. Deterministic Global Optimization. Springer, New York, 2017. 136 p. DOI: 10.1007/978-1-4939-7199-2.
- Sergeyev Y.D., Strongin R.G., Lera D. Introduction to global optimization exploiting space-filling curves. Springer Briefs in Optimization, Springer, New York, 2013. 125 p. DOI: 10.1007/978-1-4614-8042-6.
- Strongin R.G., Sergeyev Ya.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Kluwer Academic Publishers, Dordrecht, 2000. 704 p. DOI: 10.1007/978-1-4615-4677-1.
- То Т.В., Korn В. MOBES: A multiobjective evolution strategy for constrained optimization problems // Proceedings of the 3rd international conference on genetic algorithms (Mendel 97). 1997. P. 176-182.
- Гришагин В.А. Операционные характеристики некоторых алгоритмов глобального поиска // Проблемы статистической оптимизации. 1978. № 7. С. 198-206.
- Норкин В.И. О методе Пиявского для решения общей задачи глобальной оптимизации // Журнал вычислительной математики и математической физики. 1992. № 32. С. 992-1006.
