Analysis of statistical model-based optimization enhancements in Generalized Self-Adapting Particle Swarm Optimization Framework

• Autorzy: Zaborski Mateusz , Okulewicz Michał , Mańdziuk Jacek

Identyfikatory

DOI

10.2478/fcds-2020-0013

• Języki publikacji: EN

Abstrakty

EN

This paper presents characteristics of model-based optimization methods utilized within the Generalized Self-Adapting Particle Swarm Optimization (GA– PSO) – a hybrid global optimization framework proposed by the authors. GAPSO has been designed as a generalization of a Particle Swarm Optimization (PSO) algorithm on the foundations of a large degree of independence of individual particles. GAPSO serves as a platform for studying optimization algorithms in the context of the following research hypothesis: (1) it is possible to improve the performance of an optimization algorithm through utilization of more function samples than standard PSO sample-based memory, (2) combining specialized sampling methods (i.e. PSO, Differential Evolution, model-based optimization) will result in a better algorithm performance than using each of them separately. The inclusion of model-based enhancements resulted in the necessity of extending the GAPSO framework by means of an external samples memory - this enhanced model is referred to as M-GAPSO in the paper. We investigate the features of two model-based optimizers: one utilizing a quadratic function and the other one utilizing a polynomial function. We analyze the conditions under which those model-based approaches provide an effective sampling strategy. Proposed model-based optimizers are evaluated on the functions from the COCO BBOB benchmark set.

Słowa kluczowe

EN

Particle Swarm Optimization; global optimization; metaheuristic

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2020
• Tom: Vol. 45, No. 3
• Strony: 234--254
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Zaborski Mateusz

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland

autor

Okulewicz Michał

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland

autor

Mańdziuk Jacek

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland

Bibliografia

• [1] Bartz-Beielstein T. and Zaefferer M. Model-based methods for continuous and discrete global optimization. Applied Soft Computing, 55:154-167, 2017.
• [2] Cai X., Qiu H., Gao L., Jiang C., and Shao X. An efficient surrogate-assisted particle swarm optimization algorithm for high-dimensional expensive problems. Knowledge-Based Systems, 184:104901, nov 2019.
• [3] Chugh T., Rahat A., Volz V., and Zaefferer M. Towards Better Integration of Surrogate Models and Optimizers. In High-Performance Simulation-Based Optimization, pages 137-163. 2020.
• [4] Chugh T., Sun C., Wang H., and Jin Y. Surrogate-Assisted Evolutionary Optimization of Large Problems, pages 165-187. Springer International Publishing, Cham, 2020.
• [5] Clerc M. Standard particle swarm optimisation. 2012.
• [6] Das S., Abraham A., and Konar A. Particle swarm optimization and differential evolution algorithms: technical analysis, applications and hybridization perspectives. In Advances of computational intelligence in industrial systems, pages 1-38. Springer, 2008.
• [7] Guttman A. R-trees: A dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD international conference on Management of data, pages 47-57, 1984.
• [8] Hansen N. The CMA Evolution Strategy: A Comparing Review. In Towards a New Evolutionary Computation: Advances in the Estimation of Distribution Algorithms, pages 75-102. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
• [9] Hansen N., Brockhoff D., Mersmann O., Tusar T., Tusar D., ElHara O.A., Sampaio P.R., Atamna A., Varelas K., Batu U., Nguyen D.M., Matzner F., and Auger A. Comparing Continuous Optimizers: numbbo/COCO on Github, 2019.
• [10] Jin Y. A comprehensive survey of fitness approximation in evolutionary computation. Soft computing, 9(1):3-12, 2005.
• [11] Kennedy J. and Eberhart R.C. Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks. IV, pages 1942-1948, 1995.
• [12] Kleijnen J.P.C. Simulation Optimization Through Regression or Kriging Metamodels. In High-Performance Simulation-Based Optimization, pages 115-135, 2020.
• [13] Nepomuceno F.V. and Engelbrecht A.P. A Self-adaptive Heterogeneous PSO Inspired by Ants. In International Conference on Swarm Intelligence, pages 188-195. Springer, 2012.
• [14] Okulewicz M. and Mańdziuk J. Application of Particle Swarm Optimization Algorithm to Dynamic Vehicle Routing Problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7895:547-558, 2013.
• [15] Okulewicz M. and Manńdziuk J. Two-phase multi-swarm PSO and the dynamic vehicle routing problem. In 2014 IEEE Symposium on Computational Intelligence for Human-like Intelligence (CIHLI), pages 1-8, Orlando, Fl, USA, dec 2014. IEEE.
• [16] Okulewicz M., Zaborski M., and Mańdziuk J. Generalized Self-Adapting Particle Swarm Optimization algorithm with archive of samples, 2020. preprint, available at: https://arxiv.org/pdf/2002.12485.
• [17] Pitra Z., Bajer L., and Holena M. Doubly Trained Evolution Control for the Surrogate CMA-ES. In Parallel Problem Solving from Nature - PPSN XIV, pages 59-68. Springer International Publishing, Cham, 2016.
• [18] Poalk P. and Klema V. JADE, an adaptive differential evolution algorithm, benchmarked on the BBOB noiseless testbed. In Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference companion - GECCO Companion ’12, page 197, New York, New York, USA, 2012. ACM Press.
• [19] Poli R. An analysis of publications on particle swarm optimization applications. Technical report, Technical Report CSM-469, Department of Computer Science, University of Essex, 2007.
• [20] Storn R. and Price K. Differential Evolution - A Simple and Efficient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4):341-359, 1997.
• [21] Uliński M., Zychowski A., Okulewicz M., Zaborski M., and Kordulewski H. Generalized Self-adapting Particle Swarm Optimization Algorithm. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 3242, pages 29-40. Springer, Cham, 2018.
• [22] Yamaguchi T. and Akimoto Y. Benchmarking the novel CMA-ES restart strategy using the search history on the BBOB noiseless testbed. In GECCO ’17 Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 1780-1787, 2017.
• [23] Zaborski M., Okulewicz M., and Mańdziuk J. Generalized Self-Adapting Particle Swarm Optimization algorithm with model-based optimization enhancements. In 2nd PP-RAI Conference (PPRAI-19), pages 380-383, Wrocław, Poland, 2019. Wrocław University of Science and Technology.
• [24] Zhang J. and Sanderson A.C. Jade: Adaptive differential evolution with optional external archive. IEEE Transactions on Evolutionary Computation, 13(5):945-958, 2009.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).