Evolutionary multimodal optimization

Knowledge of multiple solutions to an optimization task is especially helpful in engineering, when due to physical (and/or cost) constraints, the best results may not always be realizable. In such a scenario, if multiple solutions (locally and/or globally optimal) are known, the implementation can be quickly switched to another solution and still obtain the best possible system performance. Multiple solutions could also be analyzed to discover hidden properties (or relationships) of the underlying optimization problem, which makes them important for obtaining domain knowledge. In addition, the algorithms for multimodal optimization usually not only locate multiple optima in a single run, but also preserve their population diversity, resulting in their global optimization ability on multimodal functions. Moreover, the techniques for multimodal optimization are usually borrowed as diversity maintenance techniques to other problems.^[4][5]

Classical techniques of optimization would need multiple restart points and multiple runs in the hope that a different solution may be discovered every run, with no guarantee however. Evolutionary algorithms (EAs) due to their population based approach, provide a natural advantage over classical optimization techniques. They maintain a population of possible solutions, which are processed every generation, and if the multiple solutions can be preserved over all these generations, then at termination of the algorithm we will have multiple good solutions, rather than only the best solution. Note that this is against the natural tendency of classical optimization techniques, which will always converge to the best solution, or a sub-optimal solution (in a rugged, “badly behaving” function). Finding and maintenance of multiple solutions is wherein lies the challenge of using EAs for multi-modal optimization. Niching^[6] is a generic term referred to as the technique of finding and preserving multiple stable niches, or favorable parts of the solution space possibly around multiple solutions, so as to prevent convergence to a single solution.

The field of Evolutionary algorithms encompasses genetic algorithms (GAs), evolution strategy (ES), differential evolution (DE), particle swarm optimization (PSO), and other methods. Attempts have been made to solve multi-modal optimization in all these realms and most, if not all the various methods implement niching in some form or the other.

De Jong's crowding method, Goldberg's sharing function approach, Petrowski's clearing method, restricted mating, maintaining multiple subpopulations are some of the popular approaches that have been proposed by the community. The first two methods are especially well studied, however, they do not perform explicit separation into solutions belonging to different basins of attraction.

The application of multimodal optimization within ES was not explicit for many years, and has been explored only recently. A niching framework utilizing derandomized ES was introduced by Shir,^[7] proposing the CMA-ES as a niching optimizer for the first time. The underpinning of that framework was the selection of a peak individual per subpopulation in each generation, followed by its sampling to produce the consecutive dispersion of search-points. The biological analogy of this machinery is an alpha-male winning all the imposed competitions and dominating thereafter its ecological niche, which then obtains all the sexual resources therein to generate its offspring.

Shir, Emmerich and Bäck subsequently proposed adaptive niche radii and niche shapes for niching with CMA-ES, allowing the niche geometry to adapt during the evolutionary search.^[8]

An approach that does not use any radius for separating the population into subpopulations (or species) but employs the space topology instead is proposed in.^[9]

Multimodal multi-objective optimization considers multi-objective problems in which distinct solutions or solution sets in decision space may correspond to similar or identical trade-offs in objective space. Algorithms may therefore need to preserve diversity both along the Pareto front and in decision space. The topic connects multimodal optimization with evolutionary multi-objective optimization.

Early algorithmic work investigated the ability of evolutionary multi-objective methods to preserve multiple equivalent solution sets. Preuss, Naujoks and Rudolph studied evolutionary multi-objective algorithms on problems with multimodal Pareto sets,^[10] and Rudolph et al. subsequently considered the detection and preservation of equivalent Pareto subsets.^[11] Deb and Tiwari's Omni-optimizer similarly incorporated diversity in both decision and objective spaces in a generic evolutionary algorithm for problems with single or multiple optima.^[12]

A related approach reformulates an originally single-objective multimodal problem as a multi-objective problem. Deb and Saha proposed adding a suitable second objective so that multiple solutions form a weak Pareto-optimal front and can be recovered using an evolutionary multi-objective algorithm.^[13] Saha and Deb subsequently proposed a self-adaptive bi-criterion version.^[14]

Landscape analysis provides a complementary perspective. Stadler and Flamm extended concepts such as local optima, basins, saddle points and barriers to partially ordered multi-objective landscapes using barrier trees.^[15] For discrete problems, Verel et al. studied Pareto local optima in multi-objective NK landscapes.^[16] For continuous problems, Kerschke et al. formalized multimodality in multi-objective landscapes and introduced a corresponding test bed and landscape characteristics.^[17] Kerschke and Grimme later studied multimodal multi-objective landscapes and their visualization,^[18] and Schäpermeier, Grimme and Kerschke introduced the PLOT visualization for representing local and global efficient sets and their landscape structure.^[19]