Multilocal/Multimodal Optimization

In multilocal optimization, we aim to find a set of (potentially only locally) optimal solutions of a multimodal, single-objective optimization problem. Further details depend on the concrete application, i. e., sometimes the set of all optima is desired, sometimes a small subset may be sufficient. The currently recommended algorithm is NEA2.

• Wikipedia page on evolutionary multimodal optimization
• On 13 September, 2014, there was an International Workshop on Advances in Multimodal Optimization held in conjunction with the 13th International Conference on Parallel Problem Solving from Nature (PPSN 2014) in Ljubljana, Slovenia.
• Tutorial on Multimodal Optimization held on September 14, 2014 at the PPSN 2014 conference (Ljubljana, Slovenia).
• IEEE CIS Task Force on Multimodal Optimization

The Niching Evolutionary Algorithm 2 (NEA2) is the successor of the NBC-CMA (aka NEA1) that had been presented and assessed for the BBOB 2010 GECCO workshop. The main changes consist of a sequential search within the single basins instead of a concurrent search in the whole search space, and an updated clustering mechanism (nearest better clustering with a second rule), these are documented in this paper of 2012: Improved Topological Niching for Real-Valued Global Optimization.

Unfortunately, there is currently no concise treatment of the NEA2, its mechanisms and parameter values in a single paper, therefore we provide some rough description here. The whole algorithm could be considered a sophisticated restart scheme for the CMA-ES, it basically loops over the following steps until the available function evaluations are depleted:

• perform an large initial sample over the whole search space
  
• compute distances and apply the nearest-better clustering in order to recognize the basins
  
• run a CMA-ES for each basin (with much smaller populations), using the clustered points of the last step as initial population (no restarts on this level, stop as soon as any stopping criterion applies)
  

The algorithm, its parameters, and some results are also described in the 2015 book Multimodal Optimization by Means of Evolutionary Algorithms.

NEA2 has won the CEC 2013 niching competition, the competition manual is here: manual.

• A summary of the results of the competition, given by the competition organizers, can be obtained here
  
• The raw data and the computed tables (peak rations/success rates, columns: accuracy from E-1 to E-5, rows: problems 1 to 20) for all 4 algorithms I have submitted are here
  

In the CEC 2015 niching competition, NEA2 did not officially take part but its 2013 results were beaten only by NMMSO, by a small margin. At the GECCO 2016 niching competition, it came in 3rd but performed especially well in the “dynamic case”.

The original NEA2 implementation was coded in Java, however, it is deeply hidden in a large library, so we rather recommend the very concise Python implementation that produces almost identical results on the CEC 2013 benchmark set. The Python code consists of only one file, but in order to enable a comparison based on the CEC 2013 niching benchmark set, it comes together with the problem code (directories cec2013 and data) in a zip file.

Note that you will need to install several Python packages in order to make the code run. The diversipy, optproblems, and evoalgos packages from Simon Wessing can be located on his page. We use a slightly (1D function error supressed) modified version of the recent CMA-ES implementation of Niko Hansen. It is already in the zip file. However, the original package cma is located here.

• Simon Wessing, Mike Preuss. On multiobjective selection for multimodal optimization. Computational Optimization and Applications, Volume 63, Issue 3, pp 875-902, 2016.

• Simon Wessing. Two-stage methods for multimodal optimization. PhD thesis, Technische Universität Dortmund, 2015.

• Mike Preuss. Multimodal Optimization by Means of Evolutionary Algorithms. Springer, 2015

• Simon Wessing, Mike Preuss and Heike Trautmann. Stopping Criteria for Multimodal Optimization. Parallel Problem Solving from Nature – PPSN XIII, LNCS 8672, pp. 141–150, Springer, 2014.

• Mike Preuss, Simon Wessing. Measuring Multimodal Optimization Solution Sets with a View to Multiobjective Techniques. In EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation IV, Advances in Intelligent Systems and Computing, Volume 227, pp. 123–137, Springer, 2013.

• Simon Wessing, Mike Preuss, Günter Rudolph. Niching by Multiobjectivization with Neighbor Information: Trade-offs and Benefits. In IEEE Congress on Evolutionary Computation (CEC), pp. 103–110, 2013.

• Mike Preuss. Improved Topological Niching for Real-Valued Global Optimization. In EvoApplications 2012, pp. 386-395. Springer, 2012

• Catalin Stoean, Mike Preuss, Ruxandra Stoean, Dumitru Dumitrescu Multimodal Optimization by Means of a Topological Species Conservation Algorithm. In IEEE Transactions on Evolutionary Computation, Volume 14, Issue 6, pp. 842-864. 2010