Evolutionary multimodal optimization

In applied mathematics, multimodal optimization deals with Optimization (mathematics) tasks that involve finding all or most of the multiple solutions (as opposed to a single best solution). 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 a optimal system performance. Multiple solutions could also be analyzed to discover hidden properties (or relationships), which makes them high-performing.

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 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, a Evolutionary Multiobjective optimization (EMO) approach was proposed , 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 a EMO algorithm.

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.

See also

• Glowworm swarm optimization
• Firefly algorithm

Bibliography

• D. Goldberg and J. Richardson. (1987) "Genetic algorithms with sharing for multimodal function optimization". In Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application table of contents, pages 41–49. L.Erlbaum Associates Inc. Hillsdale, NJ, USA, 1987.
• A. Petrowski. (1996) "A clearing procedure as a niching method for genetic algorithms". In Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, pages 798–803. Citeseer, 1996.
• Deb,K., (2001) "Multi-objective Optimization using Evolutionary Algorithms", Wiley (Google Books)
• F. Streichert, G. Stein, H. Ulmer, and A. Zell. (2004) "A clustering based niching EA for multimodal search spaces". Lecture notes in computer science, pages 293–304, 2004.
• Singh, G., Deb, K., (2006) "Comparison of multi-modal optimization algorithms based on evolutionary algorithms". In Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 8–12. ACM, 2006.
• Ronkkonen,J., (2009). Continuous Multimodal Global Optimization with Diferential Evolution Based Methods
• Wong,K.C., (2009). An evolutionary algorithm with species-specific explosion for multimodal optimization. GECCO 2009: 923-930
• J. Barrera and C. A. C. Coello. "A Review of Particle Swarm Optimization Methods used for Multimodal Optimization", pages 9–37. Springer, Berlin, November 2009.
• Wong,K.C., (2010). Effect of Spatial Locality on an Evolutionary Algorithm for Multimodal Optimization. EvoApplications (1) 2010: 481-490
• Deb,K., Saha,A. (2010) Finding Multiple Solutions for Multimodal Optimization Problems Using a Multi-Objective Evolutionary Approach. GECCO 2010: 447-454
• Wong,K.C., (2010). Protein structure prediction on a lattice model via multimodal optimization techniques. GECCO 2010: 155-162

External links

• Multi-modal optimization using Particle Swarm Optimization (PSO)
• Niching in Evolution Strategy (ES)