TutORial: Nature-Inspired Heuristics

By Craig Tovey.

Evolutionary Programming, Genetic Algorithms, Simulated Annealing, Ant Colony Optimization, and Particle Swarm Optimization are among the earliest optimization heuristics inspired by animate and inanimate phenomena in the natural world. Some of the more recently invented methods have exotic names such as Roach Infestation, Shuffled Frog-Leaping, Invasive Weed Optimization, and Cuckoo Search. This tutorial is a guide to the bewildering, burgeoning menagerie of such heuristics, which now comprises more than 100 algorithms, and whose accompanying publications number in the hundreds of thousands. Their underlying principles include populations, recombination, exploration, reinforcement, encoding, selection, randomness and perturbation. They have been successful in many implementations, ofttimes winning out against classical OR/CS methods for implementation or a user's acceptance. They have been less successful, sometimes spectacularly so, in many computational test comparisons with classical methods. I speculate as to why these success levels differ so greatly. On the one hand, I critique the insularity and mathematical naiveté of this heuristic research, particularly its limited nature-versus-nature comparisons and self-contradictory stance on algorithm parameter tuning. On the other hand, I critique the OR community's having implicitly ceded important optimization territory to others, and our failure to face what is now there. In an attempt to spur our community to thoroughly engage with nature-inspired heuristics, I conclude by observing a misalignment between individual and community incentives, identifying a few potentially powerful nature-inspired heuristic ideas for optimization, and proposing some specific research questions that may attract operations researchers.