Understanding parameter spaces using local optima networks: a case study on particle swarm optimization

Citation

Cleghorn CW & Ochoa G (2021) Understanding parameter spaces using local optima networks: a case study on particle swarm optimization. In: Chicano F (ed.) GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion. GECCO '21: Genetic and Evolutionary Computation Conference, Lille, France, 10.07.2021-14.07.2021. New York: ACM, pp. 1657-1664. https://doi.org/10.1145/3449726.3463145

Abstract
A major challenge with utilizing a metaheuristic is finding optimal or near optimal parameters for a given problem instance. It is well known that the best performing control parameters are often problem dependent, with poorly chosen parameters even leading to algorithm failure. What is not obvious is how strongly the complexity of the parameter landscape itself is coupled with the underlying objective function the metaheuristic is attempting to solve. In this paper local optima networks (LONs) are utilized to visualize and analyze the parameter landscapes of particle swarm optimization (PSO) over an array of objective functions. It was found that the structure of the parameter landscape is affected by the underlying objective function, and in some cases by a considerable degree across multiple metrics. Furthermore, despite PSO's parameter landscape having a relatively simple macro structure, the LONs demonstrate that there is actually a considerable amount of complexity at a micro level; making parameter tuning harder for PSO than would have been initially thought. Apart from the PSO specific findings this paper also provides a formalism of parameter landscapes and demonstrates that LONs can be used as an effective tool in the analysis and visualization of parameter landscapes of metaheuristics.

Keywords
Local Optima Networks; Particle Swarm Optimization; Parameter Tuning; Fitness landscape analysis

People

Professor Gabriela Ochoa

Professor, Computing Science