Evolutionary Multi-modal Optimization (EMMO)

by Amit


I have created a Wikipedia article on Evolutionary Multi-modal optimization here. Please help to make it complete.

EMO is already taken: Evolutionary Multi-objective Optimization, so EMMO it is.

Optimization task which involves finding all or most of the multiple solutions  (as opposed to a single best solution) is termed as Multi-modal optimization. Knowledge of multiple solutions to an optimization task is specially 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.

Classical techniques of optimization would need multiple restart p0ints and multiple runs in the hope that a different solution may be discovered every run, with no guarantee however.  Evolutionary alg0rithms (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.

The field of EAs today encompass Genetic Algorithms (GAs), Differential Evolution (DE),  Particle Swarm Optimization (PSO) among others. Attempts have been made to solve multi-modal optimization in all these realms. Since my main area of research involves GAs,  I shall mainly talk about them.

Multi-modal optimization using GAs

Niching is a generic term referred to as the technique of preserving multiple niches, or favorable  parts of the solution space possibly around multiple solutions, so as to prevent convergence to a single solution. Petrwoski’s clearing method,  Goldberg’s sharing function approach,  restricted mating, maintaining multiple subpopulations are some of the popular approaches that have been proposed many years ago. The first two methods are very well studied and respected in the GA community. For a detailed reference to all these and many more papers, please refer the end of this post.

Very recently, we have proposed an approach to obtain multiple solutions by using principles from Multi-objective optimization. You can see some demos showing our approach in action:

Our approach doesn’t implement niching to maintain multiple solutions.  The multi-objective technique helps maintain multiple solutions, due to a property called weak-pareto optimality.

Multi-modal Optimization using DE

For a comprehensive treatment of Multi-modal optimization methods in DE, refer this Ph.D thesis Ronkkonen, J. (2009). Continuous Multimodal Global Optimization with Differential Evolution Based Methods.

Resources to look up:

This post will see further updates.

Advertisements