Evolutionary multimodal optimization: Difference between revisions

Revision as of 11:37, 8 December 2015

Latest revision as of 04:42, 15 April 2025

(38 intermediate revisions by 23 users not shown)

Line 1:

{{Evolutionary algorithms}}

In [[applied mathematics]], '''multimodal optimization''' deals with [[Mathematical optimization|optimization]] tasks that involve finding all or most of the multiple (at least locally optimal) solutions of a problem, as opposed to a single best solution.

In [[applied mathematics]], '''multimodal optimization''' deals with [[Mathematical optimization|optimization]] tasks that involve finding all or most of the multiple (at least locally optimal) solutions of a problem, as opposed to a single best solution. Evolutionary multimodal optimization is a branch of [[Evolutionaryevolutionary computation]], which is closely related to [[Machinemachine learning]]. Wong provides a short survey,<ref>Wong, K. C. (2015), [httphttps://arxiv.org/abs/1508.00457 Evolutionary Multimodal Optimization: A Short Survey] arXiv preprint arXiv:1508.00457</ref> wherein the chapter of Shir<ref>Shir, O.M. (2012), [https://link.springer.com/book/10.1007/978-3-540-92910-9 Niching in Evolutionary Algorithms] {{Webarchive|url=https://web.archive.org/web/20160304110426/http://link.springer.com/book/10.1007/978-3-540-92910-9 |date=2016-03-04 }}</ref> and the book of Preuss<ref>Preuss, Mike (2015), [httphttps://www.springer.com/de/book/9783319074061 Evolutionary Multimodal Optimization by Means of Evolutionary Algorithms]</ref> coverscover the topic in more detail.

== 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 (locally and/or globally optimal) are known, the implementation can be quickly switched to another solution and still obtain the best possible system performance. Multiple solutions could also be analyzed to discover hidden properties (or relationships) of the underlying optimization problem, which makes them important for obtaining [[___domain knowledge]]. 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.<ref>Wong, K. C. et al. (2012), [https://dx.doi.org/10.1016/j.ins.2011.12.016 Evolutionary multimodal optimization using the principle of locality] Information Sciences</ref><ref>{{Cite journal |last1=Jiang |first1=Yi |last2=Zhan |first2=Zhi-Hui |last3=Tan |first3=Kay Chen |last4=Zhang |first4=Jun |date=April 2023 |title=Optimizing Niche Center for Multimodal Optimization Problems |journal=IEEE Transactions on Cybernetics |volume=53 |issue=4 |pages=2544–2557 |doi=10.1109/TCYB.2021.3125362 |issn=2168-2267|doi-access=free |pmid=34919526 }}</ref>

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.<ref>Wong, K. C. et al. (2012), [http://dx.doi.org/10.1016/j.ins.2011.12.016 Evolutionary multimodal optimization using the principle of locality] Information Sciences</ref>

== 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 algorithmsalgorithm]]s (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 EAsclassical optimization techniques, 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), "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.8270&rep=rep1&type=pdf 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[[Evolutionary todayalgorithm]]s encompassencompasses [[genetic algorithm]]s (GAs), [[evolution strategy]] (ES), [[differential evolution]] (DE), [[particle swarm optimization]] (PSO), [[evolution strategy]] (ES)and amongother othersmethods. 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 GAsgenetic algorithms/evolution strategies ==

Petrwoski’sDe clearingJong's crowding method, Goldberg’sGoldberg's sharing function approach, Petrowski's clearing method, restricted mating, maintaining multiple subpopulations are some of the popular approaches that have been proposed by the GA Communitycommunity. The first two methods are veryespecially well studied, andhowever, respectedthey indo thenot GAperform communityexplicit separation into solutions belonging to different basins of attraction.

The application of multimodal optimization within ES was not explicit for many years, and has been explored only recently.

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.

A niching framework utilizing derandomized ES was introduced by Shir,<ref>Shir, O.M. (2008), "[https://openaccess.leidenuniv.nl/handle/1887/12981 Niching in Derandomized Evolution Strategies and its Applications in Quantum Control]"</ref> proposing the [[CMA-ES]] as a niching optimizer for the first time. The underpinning of that framework was the selection of a peak individual per subpopulation in each generation, followed by its sampling to produce the consecutive dispersion of search-points. The ''biological analogy'' of this machinery is an ''alpha-male'' winning all the imposed competitions and dominating thereafter its ''ecological niche'', which then obtains all the sexual resources therein to generate its offspring.

Recently, an evolutionary [[multiobjective optimization]] (EMO) approach was proposed,<ref>Deb, K., Saha, A. (2010) "[https://dl.acm.org/doi/pdf/10.1145/1830483.1830568 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>

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) [httphttps://ieeexplore.ieee.org/xpldocument/freeabs_all.jsp5491155/;jsessionid=F5D1F368440FA8710935CB745020610C?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.)]]

== 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''.<ref>Ronkkonen,J., (2009). [https://oa.doria.fi/bitstream/handle/10024/50498/isbn%209789522148520.pdf Continuous Multimodal Global Optimization with Differential Evolution Based Methods]</ref>

==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.<ref>K. N. Krishnanand and D. Ghose (2005). Detection of multiple source locations using a glowworm metaphor with applications to collective robotics. IEEE Swarm Intelligence Symposium, Pasadena, California, USA, pp. 84–91,</ref><ref>K. N. Krishnanand and D. Ghose. Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions. Swarm Intelligence, Vol. 3, No. 2, pp. 87–124, June 2009.</ref><ref>K. N. Krishnanand and D. Ghose. (2008). Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations. Robotics and Autonomous Systems, 56(7): 549–569.</ref><ref>K. N. Krishnanand and D. Ghose. (2006). Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications. Multi-agent and Grid Systems, 2(3): 209–222.</ref> 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 ==

Line 44 ⟶ 31:

{{refbegin}}

* D. Goldberg and J. Richardson. (1987) "[https://books.google.com/books?id=MYJ_AAAAQBAJ&dq=%22Genetic+algorithms+with+sharing+for+multimodal+function+optimization%22&pg=PA41 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) "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.8027&rep=rep1&type=pdf 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 ([httphttps://books.google.com/books?id=OSTn4GSy2uQC&printsec=frontcover&dqq=multi+objective+optimization&source=bl&ots=tCmpqyNlj0&sig=r00IYlDnjaRVU94DvotX-I5mVCI&hl=en&ei=fHnNS4K5IMuLkAWJ8OgS&sa=X&oi=book_result&ct=result&resnum=8&ved=0CD0Q6AEwBw#v=onepage&q&f=false Google Books)]

* F. Streichert, G. Stein, H. Ulmer, and A. Zell. (2004) "[http://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Niche/streichert03clustering.pdf A clustering based niching EA for multimodal search spaces]". Lecture notesNotes in computerComputer scienceScience, pages 293–304, 2004.

* Singh, G., Deb, K., (2006) "[http://repository.ias.ac.in/81664/1/94-p.pdf 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). [https://web.archive.org/web/20141225150016/https://oa.doria.fi/bitstream/handle/10024/50498/isbn%209789522148520.pdf Continuous Multimodal Global Optimization with Differential Evolution Based Methods]

* Wong, K. C., (2009). [http://portal.acm.org/citation.cfm?id=1570027 An evolutionary algorithm with species-specific explosion for multimodal optimization. GECCO 2009: 923–930]

* J. Barrera and C. A. C. Coello. "[http://delta.cs.cinvestav.mx/~ccoello/EMOO/barrera09a.pdf.gz A Review of Particle Swarm Optimization Methods used for Multimodal Optimization]", pages 9–37. Springer, Berlin, November 2009.

* Wong, K. C., (2010). [httphttps://wwwdoi.springerlinkorg/10.com/content/jn23t10366778017/1007%2F978-3-642-12239-2_50 Effect of Spatial Locality on an Evolutionary Algorithm for Multimodal Optimization. EvoApplications (1) 2010: 481–490]

* Deb, K., Saha, A. (2010) [http://portal.acm.org/citation.cfm?id=1830483.1830568 Finding Multiple Solutions for Multimodal Optimization Problems Using a Multi-Objective Evolutionary Approach. GECCO 2010: 447–454]

* Wong, K. C., (2010). [http://portal.acm.org/citation.cfm?id=1830483.1830513 Protein structure prediction on a lattice model via multimodal optimization techniques. GECCO 2010: 155–162]

* Saha, A., Deb, K. (2010), [httphttps://wwwdoi.springerlinkorg/10.com/content/8676217j87173p60/1007%2F978-3-642-17298-4_10 A Bi-criterion Approach to Multimodal Optimization: Self-adaptive Approach. SEAL 2010: 95–104]

* C. StoeanShir, O.M., PreussEmmerich, RM., StoeanBäck, DT. Dumitrescu (2010), [http://ieeexplorewww.ieeemitpressjournals.org/xpldoi/freeabs_allabs/10.1162/evco.2010.18.1.18104#.jsp?arnumber=5491155VoDu4l6Y7ro MultimodalAdaptive OptimizationNiche byRadii meansand ofNiche aShapes TopologicalApproaches Speciesfor ConservationNiching Algorithm].with Inthe IEEE Transactions onCMA-ES. Evolutionary Computation, Vol. 1418, IssueNo. 61, pagespp.&nbsp; 842–864, 201097-126.]

* C. Stoean, M. Preuss, R. Stoean, D. Dumitrescu (2010) [https://ieeexplore.ieee.org/document/5491155/;jsessionid=B49A922A84DC705DEF017B4E093B0894?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.

* S. Das, S. Maity, B-Y Qu, P. N. Suganthan, "[https://www.sciencedirect.com/science/article/pii/S221065021100023X Real-parameter evolutionary multimodal optimization — A survey of the state-of-the-art]", Vol. 1, No. 2, pp.&nbsp;71–88, Swarm and Evolutionary Computation, June 2011.

{{refend}}

* Shir, O. M.: [http://link.springer.com/referenceworkentry/10.1007%2F978-3-540-92910-9_32 Niching in Evolutionary Algorithms]. In: [http://link.springer.com/book/10.1007/978-3-540-92910-9 Handbook of Natural Computing: Theory, Experiments, and Applications]. Springer-Verlag, Berlin-Heidelberg, Germany (2012) 1035—1069

== External links ==

* [https://web.archive.org/web/20100622065416/http://tracer.uc3m.es/tws/pso/multimodal.html Multi-modal optimization using Particle Swarm Optimization (PSO)]

* [https://web.archive.org/web/20160106231845/http://wwwcs.telhai.princetonac.eduil/~oshirofersh/NichingES/index.htm Niching in Evolution StrategyStrategies (ES)]

* [http://ls11-www.cs.uni-dortmund.de/rudolph/multimodal/start Multimodal optimization page at Chair 11, Computer Science, TU Dortmund University]

* [http://www.epitropakis.co.uk/ieee-mmo/ IEEE CIS Task Force on Multi-modal Optimization]

Line 70 ⟶ 57:

{{Evolutionary computation}}

[[Category:Mathematical optimization]]

[[Category:Cybernetics]]

[[Category:Evolutionary algorithms]]