ResearchIn 1953, Metropolis introduced well-defined criteria for the next step of a random walk on vertices of a graph, with vertices represented as 'states'. Since then, new randomized search heuristics continue to evolve with examples of solutions to a wide range of combinatorial optimization problems. Metaphors from physics (simulated annealing heuristic) are increasingly augmented with heuristics that are inspired by metaphors from nature (behaviors of ants, bats, bees, bird flocks, cuckoos, …). The abstract from a 2013 journal article ’Metaheuristics – the Metaphor Exposed’ provides a tongue-in-cheek introduction to the current state-of-the-art:
... a true tsunami of 'novel' metaheuristic methods, most of them based on a metaphor of some natural or man-made process. The behavior of virtually any species of insects, the flow of water, musicians playing together -- it seems that no idea is too far-fetched to serve as inspiration to launch yet another metaheuristic. ...In contrast, my recent research is articulating an antidote which is based on the concept of self-avoiding multiwalk stochastic search.
In my view, experiments that compare runtime performance of algorithms based on
metaphors from nature have led to inconclusive results all too frequently.
My experiments point to two dominating factors that can lead to such results:
(1) problem instances may be "too easy";
(2) statistical tests include too many censored observations.
For the significance of these factors, see the listing
of articles and slides
The common threads are:
(1) problem instances are consistently hard and only get harder as the instance size increases;
(2) statistical tests are based strictly on uncensored mean first-passage-time observations.