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.

Resources

Algorithms

Niching Evolutionary Algorithm 2

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.

Competition Results

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”.

Code

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.

Our Publications

 
Last modified: 2017-02-20 10:50 (external edit)
DokuWikiRSS-Feed