Evolutionary multimodal optimization

In applied mathematics, multimodal optimization deals with optimization tasks that involve finding all or most of the multiple solutions (as opposed to a single best solution) to a problem.

Motivation

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 (local and global) are known, the implementation can be quickly switched to another solution and still obtain an optimal system performance. Multiple solutions could also be analyzed to discover hidden properties (or relationships), which makes them high-performing. 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.^[1]

Background

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 EAs, 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 ^[2] 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 EAs today encompass genetic algorithms (GAs), differential evolution (DE), particle swarm optimization (PSO), evolution strategy (ES) among others. 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.

Multimodal optimization using GAs

Petrwoski’s clearing method, Goldberg’s sharing function approach, restricted mating, maintaining multiple subpopulations are some of the popular approaches that have been proposed by the GA Community. The first two methods are very well studied and respected in the GA community.

Recently, an evolutionary multiobjective optimization (EMO) approach was proposed,^[3] in which a suitable second objective is added to the originally single objective multimodal optimization problem, so that the multiple solutions form a weak pareto-optimal front. Hence, the multimodal optimization problem can be solved for its multiple solutions using an EMO algorithm. Improving upon their work,^[4] the same authors have made their algorithm self-adaptive, thus eliminating the need for pre-specifying the parameters.

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.^[5]

Finding multiple optima using genetic algorithms in a multi-modal optimization task. (The algorithm demonstrated in this demo is the one proposed by Deb, Saha in the multi-objective approach to multimodal optimization.)

Multimodal optimization using DE

The niching methods used in GAs have also been explored with success in the DE community. DE based local selection and global selection approaches have also been attempted for solving multi-modal problems. DE's coupled with local search algorithms (Memetic DE) have been explored as an approach to solve multi-modal problems.

For a comprehensive treatment of multimodal optimization methods in DE, refer the Ph.D thesis Ronkkonen, J. (2009). Continuous Multimodal Global Optimization with Differential Evolution Based Methods.^[6]

Multimodal optimization using swarm intelligence-based algorithms

Glowworm swarm optimization (GSO) is a swarm intelligence based algorithm, introduced by K.N. Krishnanand and D. Ghose in 2005, for simultaneous computation of multiple optima of multimodal functions.^{[7][8][9][10]} The algorithm shares a few features with some better known algorithms, such as ant colony optimization and particle swarm optimization, but with several significant differences. The agents in GSO are thought of as glowworms that carry a luminescence quantity called luciferin along with them. The glowworms encode the fitness of their current locations, evaluated using the objective function, into a luciferin value that they broadcast to their neighbors. The glowworm identifies its neighbors and computes its movements by exploiting an adaptive neighborhood, which is bounded above by its sensor range. Each glowworm selects, using a probabilistic mechanism, a neighbor that has a luciferin value higher than its own and moves toward it. These movements—based only on local information and selective neighbor interactions—enable the swarm of glowworms to partition into disjoint subgroups that converge on multiple optima of a given multimodal function.

See also

• Glowworm swarm optimization
• Firefly algorithm

References

Bibliography

• Shir, O. M.: Niching in Evolutionary Algorithms. In: Handbook of Natural Computing: Theory, Experiments, and Applications. Springer-Verlag, Berlin-Heidelberg, Germany (2012) 1035—1069

External links

• Multi-modal optimization using Particle Swarm Optimization (PSO)
• Niching in Evolution Strategy (ES)
• Multimodal optimization page at Chair 11, Computer Science, TU Dortmund University

Optimization: Algorithms, methods, and heuristics   Unconstrained nonlinear: Methods calling … … functions Golden section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation … and gradients Convergence Trust region Wolfe conditions Quasi–Newton BFGS and L-BFGS DFP Symmetric rank-one (SR1) Other methods Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient … and Hessians Newton's method   Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming   Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-Exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke   Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch & bound or cut Graph algorithms Minimum spanning tree Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal Network flows Dinic Edmonds–Karp Ford–Fulkerson Push-relabel maximum flow   Metaheuristics Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search Categories Algorithms and methods Heuristics Software