Editing Metaheuristic (section)

== Classification ==
[[Image:Metaheuristics classification.svg|thumb|[[Euler diagram]] of the different classifications of metaheuristics<ref name=nojhan07>[http://metah.nojhan.net/post/2007/10/12/Classification-of-metaheuristics Classification of metaheuristics]</ref>]]

There are a wide variety of metaheuristics<ref name=Bianchi2009 /><ref name="glover03handbook" /> and a number of properties with respect to which to classify them.<ref name=blum03metaheuristics /><ref>{{Citation |last=Raidl |first=Günther R. |title=A Unified View on Hybrid Metaheuristics |date=2006 |work=Hybrid Metaheuristics |series=Lecture Notes in Computer Science |volume=4030 |pages=1–12 |editor-last=Almeida |editor-first=Francisco |url=http://link.springer.com/10.1007/11890584_1 |access-date=2024-08-24 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/11890584_1 |isbn=978-3-540-46384-9 |editor2-last=Blesa Aguilera |editor2-first=María J. |editor3-last=Blum |editor3-first=Christian |editor4-last=Moreno Vega |editor4-first=José Marcos}}</ref><ref name=":4">{{Cite journal |last1=Glover |first1=Fred |last2=Sörensen |first2=Kenneth |date=2015 |title=Metaheuristics |journal=Scholarpedia |language=en |volume=10 |issue=4 |pages=6532 |doi=10.4249/scholarpedia.6532 |doi-access=free |issn=1941-6016}}</ref><ref>{{Cite web |last1=Birattari |first1=Mauro |last2=Paquete |first2=Luis |last3=Stützle |first3=Thomas |last4=Varrentrapp |first4=Klaus |date=2001 |title=Classification of Metaheuristics and Design of Experiments for the Analysis of Components. |s2cid=18347906 |url=https://api.semanticscholar.org/CorpusID:18347906}}</ref> The following list is therefore to be understood as an example.

=== Local search vs. global search ===
One approach is to characterize the type of search strategy.<ref name="blum03metaheuristics" /> One type of search strategy is an improvement on simple local search algorithms. A well known local search algorithm is the [[hill climbing]] method which is used to find local optimums. However, hill climbing does not guarantee finding global optimum solutions.

Many metaheuristic ideas were proposed to improve local search heuristic in order to find better solutions. Such metaheuristics include [[simulated annealing]], [[tabu search]], [[iterated local search]], [[Variable Neighborhood Search|variable neighborhood search]], and [[Greedy randomized adaptive search procedure|GRASP]].<ref name="blum03metaheuristics" /> These metaheuristics can both be classified as local search-based or global search metaheuristics.

Other global search metaheuristic that are not local search-based are usually [[Population model (evolutionary algorithm)|population-based]] metaheuristics. Such metaheuristics include [[ant colony optimization]], [[evolutionary computation]] such as [[genetic algorithm]] or [[Evolution strategy|evolution strategies]], [[particle swarm optimization]], [[rider optimization algorithm]]<ref>{{cite journal |last1=D |first1=Binu |title=RideNN: A New Rider Optimization Algorithm-Based Neural Network for Fault Diagnosis in Analog Circuits |journal=IEEE Transactions on Instrumentation and Measurement |year=2019 |volume=68 |issue=1 |pages=2–26 |doi=10.1109/TIM.2018.2836058 |bibcode=2019ITIM...68....2B |s2cid=54459927 |url=https://ieeexplore.ieee.org/document/8370147}}</ref> and bacterial foraging algorithm.<ref name=":0">{{Cite journal |last1=Pang |first1=Shinsiong |last2=Chen |first2=Mu-Chen |date=2023-06-01 |title=Optimize railway crew scheduling by using modified bacterial foraging algorithm |url=https://www.sciencedirect.com/science/article/pii/S0360835223002425 |journal=Computers & Industrial Engineering |language=en |volume=180 |pages=109218 |doi=10.1016/j.cie.2023.109218 |s2cid=257990456 |issn=0360-8352}}</ref>

=== Single-solution vs. population-based ===
Another classification dimension is single solution vs [[Population model (evolutionary algorithm)|population-based]] searches.<ref name="blum03metaheuristics" /><ref name="talbi09metaheuristics" /> Single solution approaches focus on modifying and improving a single candidate solution; single solution metaheuristics include [[simulated annealing]], [[iterated local search]], [[Variable Neighborhood Search|variable neighborhood search]], and [[Guided Local Search|guided local search]].<ref name="talbi09metaheuristics" /> Population-based approaches maintain and improve multiple candidate solutions, often using population characteristics to guide the search; population based metaheuristics include [[evolutionary computation]] and [[particle swarm optimization]].<ref name="talbi09metaheuristics" /> Another category of metaheuristics  is [[Swarm intelligence]] which is a collective behavior of decentralized, self-organized agents in a population or swarm. [[Ant colony optimization]],<ref name="M. Dorigo, Optimization, Learning and Natural Algorithms">M. Dorigo, ''Optimization, Learning and Natural Algorithms'', PhD thesis, Politecnico di Milano, Italie, 1992.</ref> [[particle swarm optimization]],<ref name="talbi09metaheuristics" /> [[social cognitive optimization]] and bacterial foraging algorithm<ref name=":0" /> are examples of this category.

=== Hybridization and memetic algorithms ===
A hybrid metaheuristic is one that combines a metaheuristic with other optimization approaches, such as algorithms from [[mathematical programming]], [[constraint programming]], and [[machine learning]]. Both components of a hybrid metaheuristic may run concurrently and exchange information to guide the search.

On the other hand, [[Memetic algorithm]]s<ref name="moscato89evolution" /> represent the synergy of evolutionary or any population-based approach with separate individual learning or local improvement procedures for problem search. An example of memetic algorithm is the use of a local search algorithm instead of or in addition to a basic [[Mutation (genetic algorithm)|mutation operator]] in evolutionary algorithms.

=== Parallel metaheuristics ===
A [[parallel metaheuristic]] is one that uses the techniques of [[parallel programming]] to run multiple metaheuristic searches in parallel; these may range from simple [[distributed computing|distributed]] schemes to concurrent search runs that interact to improve the overall solution. 

With population-based metaheuristics, the population itself can be parallelized by either processing each individual or group with a separate thread or the metaheuristic itself runs on one computer and the offspring are evaluated in a distributed manner per iteration.<ref>{{Cite book |last=Cantú-Paz |first=Erick |url=http://link.springer.com/10.1007/978-1-4615-4369-5 |title=Efficient and Accurate Parallel Genetic Algorithms |date=2001 |publisher=Springer US |isbn=978-1-4613-6964-6 |series=Genetic Algorithms and Evolutionary Computation |volume=1 |location=Boston, MA |doi=10.1007/978-1-4615-4369-5}}</ref> The latter is particularly useful if the computational effort for the evaluation is considerably greater than that for the generation of descendants. This is the case in many practical applications, especially in simulation-based calculations of solution quality.<ref name=":6">{{Citation |last=Sudholt |first=Dirk |title=Parallel Evolutionary Algorithms |date=2015 |work=Springer Handbook of Computational Intelligence |pages=929–959 |editor-last=Kacprzyk |editor-first=Janusz |url=http://link.springer.com/10.1007/978-3-662-43505-2_46 |access-date=2024-09-04 |place=Berlin, Heidelberg |publisher=Springer |language=en |doi=10.1007/978-3-662-43505-2_46 |isbn=978-3-662-43504-5 |editor2-last=Pedrycz |editor2-first=Witold}}</ref><ref name=":7">{{Citation |last1=Khalloof |first1=Hatem |last2=Mohammad |first2=Mohammad |last3=Shahoud |first3=Shadi |last4=Duepmeier |first4=Clemens |last5=Hagenmeyer |first5=Veit |date=2020-11-02 |title=A Generic Flexible and Scalable Framework for Hierarchical Parallelization of Population-Based Metaheuristics |work=Proc. of the 12th Int. Conf. on Management of Digital EcoSystems (MEDES'20) |url=https://dl.acm.org/doi/10.1145/3415958.3433041 |language=en |publisher=ACM |pages=124–131 |doi=10.1145/3415958.3433041 |isbn=978-1-4503-8115-4}}</ref>

=== Nature-inspired and metaphor-based metaheuristics ===
{{main|Swarm intelligence|List of metaphor-inspired metaheuristics}}
A very active area of research is the design of nature-inspired metaheuristics. Many recent metaheuristics, especially evolutionary computation-based algorithms, are inspired by natural systems. Nature acts as a source of concepts, mechanisms and principles for designing of artificial computing systems to deal with complex computational problems. Such metaheuristics include [[simulated annealing]], [[evolutionary algorithms]], [[ant colony optimization]] and [[particle swarm optimization]]. 

A large number of more recent metaphor-inspired metaheuristics have started to [[List of metaphor-inspired metaheuristics#Criticism|attract criticism in the research community]] for hiding their lack of novelty behind an elaborate metaphor.<ref name="Sörensen2013" /><ref name=":3" /><ref name=":4" /><ref>{{Citation |last=Lones |first=Michael A. |title=Metaheuristics in nature-inspired algorithms |date=2014 |work=Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO'14) |publisher=ACM |isbn=978-1-4503-2881-4 |editor-last=Igel |editor-first=Christian |series=ACM Conferences |location=New York, NY |pages=1419–1422 |language=en |doi=10.1145/2598394.2609841}}</ref> As a result, a number of renowned scientists of the field have proposed a research agenda for the standardization of metaheuristics in order to make them more comparable, among other things.<ref>{{cite web |last1=Swan |first1=Jerry |last2=Adriaensen |first2=Steven |last3=Bishr |first3=Mohamed |last4=Burke |first4=Edmund K. |last5=Clark |first5=John A. |last6=De Causmaecke |first6=Patrick |last7=Durillo |first7=Juan José |last8=Hammond |first8=Kevin |last9=Hart |first9=Emma |last10=Johnson |first10=Colin G. |last11=Kocsis |first11=Zoltan A. |last12=Kovitz |first12=Ben |last13=Krawiec |first13=Krzysztof |last14=Martin |first14=Simon |last15=Merelo |first15=Juan J. |date=2015 |title=A Research Agenda for Metaheuristic Standardization |url=http://www.cs.nott.ac.uk/~exo/docs/publications/research-agenda-metaheuristic.pdf |access-date=2024-08-30 |website=Semantic Scholar |first16=Leandro L. |last16=Minku |first17=Ender |last17=Özcan |first18=Gisele Lobo |last18=Pappa |first19=Erwin |last19=Pesch |first20=Pablo |last20=García-Sánchez |first21=Andrea |last21=Schaerf |first22=Kevin |last22=Sim |first23=Jim |last23=Smith |first24=Thomas |last24=Stützle |first25=Stefan |last25=Wagner |s2cid=63728283}}</ref> Another consequence is that the publication guidelines of a number of scientific journals have been adapted accordingly.<ref>{{Cite web |title=Journal of Heuristic Policies on Heuristic Search Research |url=https://link.springer.com/journal/10732/submission-guidelines |archive-url=https://web.archive.org/web/20170709034524/https://www.springer.com/cda/content/document/cda_downloaddocument/Journal+of+Heuristic+Policies+on+Heuristic+Search.pdf?SGWID=0-0-45-1483502-p35487524 |archive-date=2017-07-09 |access-date=2024-09-01 |website=Journal of Heuristics - Submission guidelines}}</ref><ref>{{Cite web |title=Aims and scope |url=https://link.springer.com/journal/10288/aims-and-scope |access-date=2024-09-01 |website=4OR}}</ref><ref>{{Cite web |title=Aims and scope |url=https://link.springer.com/journal/12293/aims-and-scope |access-date=2024-09-01 |website=Memetic Computing}}</ref>