Параллельный алгоритм для получения равномерного приближения решений множества задач глобальной оптимизации с нелинейными ограничениями

Владислав Валерьевич Соврасов, Константин Александрович Баркалов

Аннотация


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


Ключевые слова


глобальная оптимизация; параллельные вычисления; алгоритмы прямой оптимизации; равномерная сходимость

Полный текст:

PDF

Литература


Barkalov K., 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/s10898-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/s11081-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/s11590-012-0452-1.

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.

To T.B., Korn B. MOBES: A multiobjective evolution strategy for constrained optimization problems. Proceedings of the 3rd international conference on genetic algorithms (Mendel 97). 1997. P. 176–182.

Grishagin V. Operating characteristics of some global search algorithms. Problems of Stochastic Search. 1978. no. 7. P. 198–206. (in Russian)

Norkin V. I. Towards Pijavskyj’s method for solving common global optimization problem. Computational Mathematics and Mathematical Physics. 1992. Vol. 32, no. 7. P. 992–1006. (in Russian)




DOI: http://dx.doi.org/10.14529/cmse200201