Evolutionary multimodal optimization: Difference between revisions

Revision as of 14:23, 28 December 2014

Revision as of 05:59, 16 January 2015

Line 7:

== 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''' <ref>Mahfoud, S. W. (1995), "Niching methods for genetic algorithms"</ref> 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 algorithm]]s (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.

Line 13:

== 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,<ref>Deb, K., Saha, A. (2010) "Finding Multiple Solutions for Multimodal Optimization Problems Using a Multi-Objective Evolutionary Approach" (GECCO 2010, In press)</ref> 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,<ref>Saha, A., Deb, K. (2010) "A Bi-criterion Approach to Multimodal Optimization: Self-adaptive Approach " (Lecture Notes in Computer Science, 2010, Volume 6457/2010, 95–104)</ref> 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.<ref>C. Stoean, M. Preuss, R. Stoean, D. Dumitrescu (2010) [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5491155 Multimodal Optimization by means of a Topological Species Conservation Algorithm]. In IEEE Transactions on Evolutionary Computation, Vol. 14, Issue 6, pages 842–864, 2010.</ref>

[[File:GA-Multi-modal.ogv|thumbtime=1 |thumb |350px |alt= Finding multiple optima using Genetic Algorithms in a Multi-modal optimization task| 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.)]]

Line 72:

[[Category:Evolutionary algorithms]]

[[Category:Machine learning algorithms]]

[[Category:Articles containing video clips]]