The importance of implementation details and parameter settings in black-box optimization: a case study on Gaussian estimation-of-distribution algorithms and circles-in-a-square packing problems

• Published in: Soft computing (Berlin, Germany) Germany), 2018-02, Vol.22 (4), p.1209-1223
• Main Authors: Bosman, Peter A. N., Gallagher, Marcus
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial Intelligence; Benchmarks; Black boxes; Computational Intelligence; Control; Covariance matrix; Design; Engineering; Genetic algorithms; Mathematical Logic and Foundations; Mechatronics; Methodologies and Application; Normal distribution; Optimization; Parameters; Performance evaluation; Robotics; Variables
• ISSN: 1432-7643; 1433-7479
• DOI: 10.1007/s00500-016-2408-3

We consider a scalable problem that has strong ties with real-world problems, can be compactly formulated and efficiently evaluated, yet is not trivial to solve and has interesting characteristics that differ from most commonly used benchmark problems: packing n circles in a square (CiaS). Recently, a first study that used basic Gaussian EDAs indicated that typically suggested algorithmic parameter settings do not necessarily transfer well to the CiaS problem. In this article, we consider also AMaLGaM, an enhanced Gaussian EDA, as well as arguably the most powerful real-valued black-box optimization algorithm to date, CMA-ES, which can also be seen as a further enhanced Gaussian EDA. We study whether the well-known performance on typical benchmark problems extends to the CiaS problem. We find that although the enhancements over a basic Gaussian EDA result in superior performance, the further efficiency enhancements in CMA-ES are not highly impactful. Instead, the most impactful features are how constraint handling is performed, how large the population size is, whether a full covariance matrix is used and whether restart techniques are used. We further show that a previously published version of AMaLGaM that does not require the user to set the the population size parameter is capable of solving the problem and we derive the scalability of the required number of function evaluations to solve the problem up to 99.99 % of the known optimal value for up to 30 circles.