Comparative Study of PSO and CMA-ES Algorithms on Black-box Optimization Benchmarks

• Autorzy: Szynkiewicz P.

Identyfikatory

DOI

10.26636/jtit.2018.127418

• Języki publikacji: EN

Abstrakty

EN

Numerous practical engineering applications can be formulated as non-convex, non-smooth, multi-modal and ill-conditioned optimization problems. Classical, deterministic algorithms require an enormous computational effort, which tends to fail as the problem size and its complexity increase, which is often the case. On the other hand, stochastic, biologically-inspired techniques, designed for global optimum calculation, frequently prove successful when applied to real life computational problems. While the area of bio-inspired algorithms (BIAs) is still relatively young, it is undergoing continuous, rapid development. Selection and tuning of the appropriate optimization solver for a particular task can be challenging and requires expert knowledge of the methods to be considered. Comparing the performance of viable candidates against a defined test bed environment can help in solving such dilemmas. This paper presents the benchmark results of two biologically inspired algorithms: covariance matrix adaptation evolution strategy (CMA-ES) and two variants of particle swarm optimization (PSO). COCO (COmparing Continuous Optimizers) – a platform for systematic and sound comparisons of real-parameter global optimization solvers was used to evaluate the performance of CMA-ES and PSO methods. Particular attention was paid to the effciency and scalability of both techniques.

Słowa kluczowe

EN

benchmarking; black-box optimization; CMA-ES; global optimization; PSO; stochastic optimization

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2018
• Tom: nr 4
• Strony: 5--17
• Opis fizyczny: Bibliogr. 31 poz., rys., tab.

Twórcy

autor

Szynkiewicz P.

• Research and Academic Computer Network (NASK), Kolska 12, 01-045 Warsaw, Poland

Bibliografia

• [1] M. J. Asher, B. F. W. Croke, A. J. Jakeman, and L. J. M. Peeter, “A review of surrogate models and their application to groundwater modeling”, Water Resources Res., vol. 51, no. 8, pp. 5957–5973, 2013 (doi: 10.1002/2015WR016967).
• [2] T. Bartz-Beielstein, “A survey of model-based methods for global optimization”, in Proc. of 7th Int. Conf. on Bioinspired Optimiz. Methods and their Applications BIOMA 2016, Bled, Slovenia, 2016, pp. 3–20, 2016.
• [3] A. T. Nguyen et al., “A review on simulation-based optimization methods applied to building performance analysis”, Applied Energy, vol. 113, pp. 1043–1058, 2014 (doi: 10.1016/j.apenergy.2013.08.061).
• [4] E. Niewiadomska-Szynkiewicz and J. Błaszczyk, “Simulation-based optimization methods applied to large scale water systems control”, in Proc. of 16th IEEE Int. Conf. on Scalable Comput. and Commun. ScalCom2016, Toulouse, France, 2016, pp. 649–656 (doi: 10.1109/UIC-ATC-ScalCom-CBDCom-IoP-SmartWorld. 2016.0108).
• [5] J. C. Spall, Introduction to Stochastic Search and Optimization. Wiley, 2003 (doi: 10.1002/0471722138, ISBN 9780471330523).
• [6] S. Gil, A. Kott, and A. L. Barab´asi, “A genetic epidemiology approach to cybersecurity”, Scientific Rep., vol. 4, pp. 1–7, 2014 (doi: 10.1038/srep05659).
• [7] G. Kumar, K. Kumar, and M. Sachdeva, “The use of artificial intelligence-based techniques for intrusion detection: a review”, Artif. Intell. Rev., vol. 34, no. 4, pp. 369–387, 2010 (doi: 10.1007/s10462-010-9179-5).
• [8] E. Niewiadomska-Szynkiewicz, A. Sikora, and J. Kołodziej, “Modeling mobility in cooperative ad hoc networks”, Mobile Netw. and Appl., vol. 18, no. 5, pp. 610–621, 2013 (doi: 10.1007/s11036-013-0450-2).
• [9] P. Szynkiewicz, “A novel GPU-enabled simulator for large scale spiking neural networks”, J. of Telecommun. and Inform. Technology, no. 2, pp. 34–42, 2016.
• [10] M. Marks, E. Niewiadomska-Szynkiewicz, and J. Kołodziej, “High performance wireless sensor network localisation system”, Int. J. of Ad Hoc and Ubiquitous Comput., vol. 17, no. 2–3, pp. 122–133, 2014 (doi: 10.1504/IJAHUC.2014.065776).
• [11] P. Szynkiewicz and A. Kozakiewicz, “Design and evaluation of a system for network threat signatures generation”, J. of Comput. Sci., vol. 22, pp. 187–197, 2017 (doi: 10.1016/j.jocs.2017.05.006).
• [12] N. Hansen, “The CMA evolution strategy: A tutorial”, Tech. Rep., INRIA, 2016, arXiv: 1604.00772.
• [13] J. A. Lozano, P. Larranaga, I. Inza, and E. Bengoetxea, Eds., Towards a New Evolutionary Computation. Advances on Estimation of Distribution Algorithms. Berlin: Springer, 2006 (ISBN 9783540324942).
• [14] R. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory”, in Proc. of the 6th Int. Symp. on Micro Machine and Human Sci. MHS’95, Nagoya, Japan, 1995, pp. 39–43 (doi: 10.1109/MHS.1995.494215).
• [15] N. Hansen, S. Finck, R. Ros, and A. Auger, “Real-parameter blackbox optimization benchmarking 2009: Noiseless functions definitions”, Tech. Rep. RR-6829, INRIA, 2009 [Online]. Available: https://hal.inria.fr/inria-00362633/document
• [16] S. Amaran, N. V. Sahinidis, B. Sharda, and S. J. Bury, “Simulation optimization: a review of algorithms and applications”, Annals of Operations Res., vol. 240, no. 1, pp. 351–380, 2016 (doi: 10.1007/s10479-015-2019-x).
• [17] J. April, F. Glover, J. P. Kelley, and M. Laguna, “Practical introduction to simulation optimization”, in Proc. of the 2003 Conf. on Winter Simul. WSC 2003, New Orleans, LA, USA, 2003, pp. 71–78 (doi: 10.1109/WSC.2003.1261410).
• [18] L. M. Rios and N. V. Sahinidis, “Derivative-free optimization: a review of algorithms and comparison of software implementations”, J. of Global Optimiz., vol. 56, no. 3, pp. 1247–1293, 2013 (doi: 10.1007/s10898-012-9951-y).
• [19] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C. The Art of Scientific Computing. Cambridge University Press, Cambridge, 1992 (ISBN 9780521431088).
• [20] M. M. Ali, A. T¨ orn, and S. Vittanen, “A numerical comparison of some modified controlled random search algorithms”, J. of Global Optimiz., vol. 11, no. 4, pp. 377–385, 1997 (doi: 10.1023/A:1008236920512).
• [21] A. Dekkers and E. Aarts, “Global optimization and simulated annealing”, Mathem. Programming, vol. 50, no 3, pp. 367–393, 1999 (doi: 10.1007/BF01594945).
• [22] J. Kołodziej, Evolutionary Hierarchical Multi-Criteria Metaheuristics for Scheduling in Large-Scale Grid Systems. Studies in Computational Intelligence, vol. 419. Springer, 2012 (ISBN 9783642289705).
• [23] Z. Michalewicz and D. B. Fogel, How to Solve It: Modern Heuristics. Berlin Heidelberg: Springer, 2002 (ISBN 3540660615).
• [24] N. Hansen, A. Auger, O. Mersmann, T. Tuˇsar, and D. Brockhoff, “COCO: A platform for comparing continuous optimizers in a blackbox setting”, ArXiv e-prints, 2016, arXiv: 1603.08785.
• [25] N. Hansen, A. Auger, D. Brockhoff, D. Tuˇsar, and T. Tuˇsar, “COCO: Performance assessment”, ArXiv e-prints, 2016, arXiv: 1605.03560.
• [26] N. Hansen, T. Tuˇsar, O. Mersmann, A. Auger, and D. Brockhoff. “COCO: The experimental procedure”, ArXiv e-prints, 2016, arXiv: 1603.08776.
• [27] N. Hansen, “Python implementation of CMA-ES”, 2016 [Online]. Available: https://github.com/CMA-ES/pycma
• [28] L. J. V. Miranda, “PySwarms: a research toolkit for particle swarm optimization in Python”, The J. of Open Source Softw., vol. 3, no. 21, pp. 1–2, 2018 (doi: 10.21105/joss.00433).
• [29] A. W. van der Vaart, Asymptotic Statistics. Cambridge University Press, 2000 (doi: 10.1017/CBO9780511802256, ISBN 9780511802256).
• [30] S. Finck, N. Hansen, R. Ros, and A. Auger, “Real-parameter blackbox optimization benchmarking 2009: Presentation of the noiseless functions”, Tech. Rep. 20, Research Center PPE, 2009.
• [31] H. Beyer and B. Sendhoff, “Simplify your covariance matrix adaptation evolution strategy”, IEEE Trans. on Evolut. Comput., vol. 21, no. 5, pp. 746–759, 2017 (doi: 10.1109/TEVC.2017.2680320).

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).