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

Zaborski, Mateusz; Okulewicz, Michał; Mańdziuk, Jacek

doi:10.2478/fcds-2020-0013

Abstract

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.

References

[1] Bartz-Beielstein T. and Zaefferer M. Model-based methods for continuous and discrete global optimization. Applied Soft Computing, 55:154–167, 2017.10.1016/j.asoc.2017.01.039
Search in Google Scholar Back to article
[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.10.1016/j.knosys.2019.104901
Search in Google Scholar Back to article
[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.10.1007/978-3-030-18764-4_7
Search in Google Scholar Back to article
[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.10.1007/978-3-030-18764-4_8
Search in Google Scholar Back to article
[5] Clerc M. Standard particle swarm optimisation. 2012.
Search in Google Scholar Back to article
[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.10.1007/978-3-540-78297-1_1
Search in Google Scholar Back to article
[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.10.1145/971697.602266
Search in Google Scholar Back to article
[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.10.1007/3-540-32494-1_4
Search in Google Scholar Back to article
[9] Hansen N., Brockho 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.
Search in Google Scholar Back to article
[10] Jin Y. A comprehensive survey of fitness approximation in evolutionary computation. Soft computing, 9(1):3–12, 2005.10.1007/s00500-003-0328-5
Search in Google Scholar Back to article
[11] Kennedy J. and Eberhart R. C. Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks. IV, pages 1942–1948, 1995.
Search in Google Scholar Back to article
[12] Kleijnen J. P. C. Simulation Optimization Through Regression or Kriging Meta-models. In High-Performance Simulation-Based Optimization, pages 115–135. 2020.10.1007/978-3-030-18764-4_6
Search in Google Scholar Back to article
[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.10.1007/978-3-642-32650-9_17
Search in Google Scholar Back to article
[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.10.1007/978-3-642-38610-7_50
Search in Google Scholar Back to article
[15] Okulewicz M. and Mań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.10.1109/CIHLI.2014.7013391
Search in Google Scholar Back to article
[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.
Search in Google Scholar Back to article
[17] Pitra Z., Bajer L., and Holeňa 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.10.1007/978-3-319-45823-6_6
Search in Google Scholar Back to article
[18] Poaík 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.10.1145/2330784.2330814
Search in Google Scholar Back to article
[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.
Search in Google Scholar Back to article
[20] Storn R. and Price K. Differential Evolution – A Simple and E cient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4):341–359, 1997.10.1023/A:1008202821328
Search in Google Scholar Back to article
[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.10.1007/978-3-319-99253-2_3
Search in Google Scholar Back to article
[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.10.1145/3067695.3084203
Search in Google Scholar Back to article
[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.
Search in Google Scholar Back to article
[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.10.1109/TEVC.2009.2014613
Search in Google Scholar Back to article

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

Abstract

Paradigm

My account