Evolutionary multi-modal optimization
Encyclopedia
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.
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.
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. Improving upon their work , 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 .
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.
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
, multimodal optimization deals with Optimization (mathematics)
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
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
Differential evolution
In computer science, differential evolution is a method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Such methods are commonly known as metaheuristics as they make few or no assumptions about the problem being optimized...
(DE), Particle Swarm Optimization
Particle swarm optimization
In computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
(PSO), Evolution strategy
Evolution strategy
In computer science, evolution strategy is an optimization technique based on ideas of adaptation and evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.-History:...
(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
Multiobjective optimization
Multi-objective optimization , also known as multi-criteria or multi-attribute optimization, is the process of simultaneously optimizing two or more conflicting objectives subject to certain constraints....
(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. Improving upon their work , 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 .
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.