This chapter describes Swarm Algorithms.
Swarm intelligence is the study of computational systems inspired by the 'collective intelligence'. Collective Intelligence emerges through the cooperation of large numbers of homogeneous agents in the environment. Examples include schools of fish, flocks of birds, and colonies of ants. Such intelligence is decentralized, self-organizing and distributed through out an environment. In nature such systems are commonly used to solve problems such as effective foraging for food, prey evading, or colony re-location. The information is typically stored throughout the participating homogeneous agents, or is stored or communicated in the environment itself such as through the use of pheromones in ants, dancing in bees, and proximity in fish and birds.
The paradigm consists of two dominant sub-fields 1) Ant Colony Optimization that investigates probabilistic algorithms inspired by the stigmergy and foraging behavior of ants, and 2) Particle Swarm Optimization that investigates probabilistic algorithms inspired by the flocking, schooling and herding. Like evolutionary computation, swarm intelligence 'algorithms' or 'strategies' are considered adaptive strategies and are typically applied to search and optimization domains.
Seminal books on the field of Swarm Intelligence include "Swarm Intelligence" by Kennedy, Eberhart and Shi [Kennedy2001], and "Swarm Intelligence: From Natural to Artificial Systems" by Bonabeau, Dorigo, and Theraulaz [Bonabeau1999]. Another excellent text book on the area is "Fundamentals of Computational Swarm Intelligence" by Engelbrecht [Engelbrecht2006]. The seminal book reference for the field of Ant Colony Optimization is "Ant Colony Optimization" by Dorigo and Stützle [Dorigo2004].
There are many other algorithms and classes of algorithm that were not described from the field of Swarm Intelligence, not limited to:
- Ant Algorithms: such as Max-Min Ant Systems [Stutzle2000] Rank-Based Ant Systems [Bullnheimer1999], Elitist Ant Systems [Dorigo1996], Hyper Cube Ant Colony Optimization [Blum2001] Approximate Nondeterministic Tree-Search (ANTS) [Maniezzo1999] and Multiple Ant Colony System [Gambardella1999].
- Bee Algorithms: such as Bee System and Bee Colony Optimization [Lucic2001], the Honey Bee Algorithm [Tovey2004], and Artificial Bee Colony Optimization [Karaboga2005] [Basturk2006].
- Other Social Insects: algorithms inspired by other social insects besides ants and bees, such as the Fireﬂy Algorithm [Yang2008] and the Wasp Swarm Algorithm [Pinto2007].
- Extensions to Particle Swarm: such as Repulsive Particle Swarm Optimization [Urfalioglu2004].
- Bacteria Algorithms: such as the Bacteria Chemotaxis Algorithm [Muller2002].
||B. Basturk and D. Karaboga, "An Artificial Bee Colony (ABC) Algorithm for Numeric function Optimization", in IEEE Swarm Intelligence Symposium, 2006.
||C. Blum and A. Roli and M. Dorigo, "HC–ACO: The hyper-cube framework for Ant Colony Optimization", in Proceedings of the Fourth Metaheuristics International Conference, 2001.
||E. Bonabeau and M. Dorigo and G. Theraulaz, "Swarm Intelligence: From Natural to Artificial Systems", Oxford University Press US, 1999.
||B. Bullnheimer and R. F. Hartl and C. Strauss, "A New Rank Based Version of the Ant System: A Computational Study", Central European Journal for Operations Research and Economics, 1999.
||M. Dorigo, "The Ant System: Optimization by a colony of cooperating agents", IEEE Transactions on Systems, Man, and Cybernetics–Part B, 1996.
||M. Dorigo and T. Stützle, "Ant Colony Optimization", MIT Press, 2004.
||A. P. Engelbrecht, "Fundamentals of Computational Swarm Intelligence", Wiley & Sons, 2006.
||L. M. Gambardella and E. Taillard and G. Agazzi, "MACS–VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows", in New Ideas in Optimization, pages 63–76, McGraw-Hill, 1999.
||D. Karaboga, "An idea based on honey bee swarm for numerical optimization", Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.
||J. Kennedy and R. C. Eberhart and Y. Shi, "Swarm Intelligence", Morgan Kaufmann, 2001.
||P. Lučić and D. Teodorović, "Bee system: modeling combinatorial optimization transportation engineering problems by swarm intelligence", in Preprints of the TRISTAN IV Triennial Symposium on Transportation Analysis, 2001.
||V. Maniezzo, "Approximate nondeterministic tree-search procedures for the quadratic assignment problem", INFORMS Journal on Computing, 1999.
||S. D. Müller and J. Marchetto and S. Airaghi and P. Koumoutsakos, "Optimization Based on Bacterial Chemotaxis", IEEE Transactions on Evolutionary Computation, 2002.
||P. C. Pinto and T. A. Runkler and J. M. Sousa, "Wasp Swarm Algorithm for Dynamic MAX-SAT Problems", in Proceedings of the 8th international conference on Adaptive and Natural Computing Algorithms, Part I, 2007.
||T. Stützle and H. H. Hoos, "MAX–MIN Ant System, Future Generation Computer Systems", Future Generation Computer Systems, 2000.
||C. Tovey, "The Honey Bee Algorithm: A Biological Inspired Approach to Internet Server Optimization", Engineering Enterprise, the Alumni Magazine for ISyE at Georgia Institute of Technology, 2004.
||O Urfalioglu, "Robust Estimation of Camera Rotation, Translation and Focal Length at High Outlier Rates", in Proceedings of the 1st Canadian Conference on Computer and Robot Vision, 2004.
||X. S. Yang, "Nature-Inspired Metaheuristic Algorithms", Luniver Press, 2008.
Get one algorithm per week...
- ...delivered to your inbox
- ...described in detail
- ...to read at your own pace
Own A Copy
This 438-page ebook has...
- ...45 algorithm descriptions
- ...best practice usage
- ...pseudo code
- ...Ruby code
- ...primary sources