theory of swarm intelligence
Social animals as found in fish schools, bird flocks, bee hives, and ant colonies are able to solve highly complex problems in nature. This includes foraging for food, constructing astonishingly complex nests, and evading or defending against predators. Remarkably, these animals in many cases use very simple, decentralized communication mechanisms that do not require a single leader. This makes the animals perform surprisingly well, even in dynamically changing environments. The collective intelligence of such animals is known as swarm intelligence and it has inspired popular and very powerful optimization paradigms, including ant colony optimization (ACO) and particle swarm optimization (PSO). The theory of swarm intelligence has made rapid progress in the last 6 years. Following a very successful line of research in evolutionary computation, results on the computational complexity of swarm intelligence algorithms have appeared. These results shed light on the working principles of swarm intelligence algorithms, help to identify the impact of parameters and other design choices on performance, and contribute to a solid theoretical foundation of swarm intelligence. This tutorial will give a comprehensive overview of recent theoretical results on swarm intelligence algorithms, with an emphasis on their computational complexity. In particular, it will be shown how techniques for the analysis of evolutionary algorithms can be used to analyze swarm intelligence algorithms and how the performance of swarm intelligence algorithms compares to that of evolutionary algorithms. The tutorial will be divided into a first, larger part on ACO and a second, smaller part on PSO. For ACO we will consider simple variants of the MAX-MIN ant system. Investigations of example functions in pseudo-Boolean optimization demonstrate that the choice of the pheromone update strategy and the evaporation rate has a drastic impact on the running time, even for very simple functions like ONEMAX. In terms of combinatorial optimization problems, we will look at the performance of ACO for minimum spanning trees, shortest path problems, and the TSP. For particle swarm optimization, the tutorial will cover results on PSO for pseudo-Boolean optimization as well as a discussion of theoretical results in continuous spaces.
swarm intelligence ant colony optimization particle swarm optimization pseudo-boolean optimization combinatorial optimization runtime analysis