This is a chronologically ordered list of metaphor-based metaheuristics and swarm intelligence algorithms, sorted by decade of proposal.
Algorithms
1980s-1990s
Simulated annealing (Kirkpatrick et al., 1983)
Simulated annealing is a probabilistic algorithm inspired by annealing, a heat treatment method in metallurgy. It is often used when the search space is discrete (e.g., all tours that visit a given set of cities). For problems where finding the precise global optimum is less important than finding an acceptable local optimum in a fixed amount of time, simulated annealing may be preferable to alternatives such as gradient descent.
The analogue of the slow cooling of annealing is a slow decrease in the probability of simulated annealing accepting worse solutions as it explores the solution space. Accepting worse solutions is a fundamental property of metaheuristics because it allows for a more extensive search for the optimal solution.
Ant colony optimization (ACO) (Dorigo, 1992)
The ant colony optimization algorithm is a probabilistic technique for solving computational problems that can be reduced to finding good paths through graphs. Initially proposed by Marco Dorigo in 1992 in his PhD thesis, the first algorithm aimed to search for an optimal path in a graph based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants. From a broader perspective, ACO performs a model-based search and shares some similarities with the estimation of distribution algorithms.
Particle swarm optimization (PSO) (Kennedy & Eberhart, 1995)
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. It solves a problem by having a population of candidate solutions, dubbed particles, and moving these particles around in the search space according to simple mathematical formulae over the particle's position and velocity. Each particle's movement is influenced by its local best known position but is also guided toward the best-known positions in the search space, which are updated as better positions are found by other particles. This is expected to move the swarm toward the best solutions.
PSO is originally attributed to Kennedy, Eberhart and Shi and was first intended for simulating social behaviour as a stylized representation of the movement of organisms in a bird flock or fish school. The algorithm was simplified, and it was observed to be performing optimization. The book by Kennedy and Eberhart describes many philosophical aspects of PSO and swarm intelligence. An extensive survey of PSO applications is made by Poli. A comprehensive review of theoretical and experimental works on PSO has been published by Bonyadi and Michalewicz.
2000s
Harmony search (HS) (Geem, Kim & Loganathan, 2001) Harmony search is a phenomenon-mimicking metaheuristic introduced in 2001 by Zong Woo Geem, Joong Hoon Kim, and G. V. Loganathan and is inspired by the improvization process of jazz musicians. In the HS algorithm, a set of possible solutions is randomly generated (called Harmony memory). A new solution is generated by using all the solutions in the Harmony memory (rather than just two as used in GA) and if this new solution is better than the worst solution in Harmony memory, the worst solution gets replaced by this new solution. The effectiveness and advantages of HS have been demonstrated in various applications like design of municipal water distribution networks, structural design, load dispatch problem in electrical engineering, multi-objective optimization, rostering problems, clustering, and classification and feature selection. A detailed survey on applications of HS can be found. and applications of HS in data mining can be found in.
Dennis (2015) claimed that harmony search is a special case of the evolution strategies algorithm. However, Saka et al. (2016) argues that the structure of evolution strategies is different from that of harmony search.
Artificial bee colony algorithm (Karaboga, 2005)