SWARM INTELLIGENCE

From Natural to Artificial Systems

OVERVIEW
y y y y y y y y y

Introduction History Algorithms Taxonomy Characteristics Applications Scope Limitations Recap

INTRODUCTION
y

Swarm intelligence (SI) describes the collective behaviour of decentralized, selforganized systems, natural or artificial. The concept is employed in work on artificial intelligence.

SI - DEFINITION
any attempt to design algorithms or distributed problem-solving devices inspired by the collective behaviour of social insect colonies and other animal societies [Bonabeau, Dorigo, Theraulaz: Swarm Intelligence]

BRIEF HISTORY OF SI
y

One of the first researchers in this field was French biologist Grass. In 1970s ARPA financed research projects on the first multi-agent systems with the Hearsay-II blackboard project.

HISTORY CONTD.
y

In this decade the Actor Model was invented by Carl Hewitt, Peter Bishop and Richard Steiger. The Multi-Agent Systems Lab at Amherst held the first workshop on distributed artificial intelligence in 1980.

SWARMING EXAMPLE
y

Bird Flocking. Boids model was proposed by Reynolds

Boids = Bird-oids (bird like)

Only three simple rules .

COLLISION AVOIDANCE

FLOCK CENTERING

VELOCITY MATCHING

Collision Avoidance
y

Rule 1: Avoid Collision with neighbouring birds .

Flock Centering
y

Rule 2: Stay near neighbouring birds.

Velocity Matching
y

Rule 3: Match the velocity of neighbouring birds.

EXAMPLE ALGORITHMS
1. 2. 3. 4.

Ant Colony Optimization. Particle Swarm Optimization. Stochastic Diffusion Search. Gravitational Search Algorithm.

1. Ant Colony Optimization Biological Inspiration

Inspired by foraging behaviour of ants. y Ants find shortest path to food source from nest. y Ants deposit pheromone along travelled path. y Has adaptability,robustness and redundancy.
y

Foraging behavior of Ants

2 ants start with equal probability of going on either path.

Foraging behavior of Ants

The ant on shorter path has a shorter toand-fro time from its nest to the food.

Foraging behavior of Ants

The density of pheromone on the shorter path is higher because of 2 passes by the ant (as compared to 1 by the other).

Foraging behavior of Ants

The next ant takes the shorter route.

Foraging behavior of Ants

Over many iterations, more ants begin using the path with higher pheromone, thereby further reinforcing it.

Foraging behavior of Ants

After some time, the shorter path is almost exclusively used.

Ant Colony Metaheuristic

2. Particle Swarm Optimization

Bird flocking is one of the best example of PSO in nature. One motive of the development of PSO was to model human social behavior.

Particle Swarm Optimization

y

In particle swarm optimization (PSO), a set of software agents called particle search for good solutions. Each particle uses its own experience and the experience of neighbour particles to choose how to move in the search space.

3.Stochastic diffusion search

This type of swarm intelligence is based on the tendem-calling mechanism used by a variety of ants. y Individual agents update their own preferences while randomly testing new hypotheses. y This process culminates in a collective or sub-collective choice of the optimal solution.
y

4. Gravitational Search Algorithm

GSA is constructed based on the law of Gravity and the notion of mass interactions. The GSA algorithm uses the theory of Newtonian physics and its searcher agents are the collection of masses.

TAXONOMY OF SI
y Natural

vs. Artificial. Engineering.

y Scientific vs.

SWARMING CHARACTERISTICS
y Simple y No

rules for each individual.

central control.

Decentralized and hence robust.

y Emergent.

Performs complex functions.

APPLICATIONS OF SI
y Crowd simulation. y Ant-based routing. y Swarm Robotics. y creation of

the video sequence.

SCOPE OF SI
y

The U.S. military is investigating swarm techniques for controlling unmanned vehicles. The European Space Agency is thinking about an orbital swarm for self assembly and interferometry.

SCOPE CONTD.
y

A 1992 paper by M. Anthony Lewis and George A. Bekey discusses the possibility of using swarm intelligence to control nanobots within the body for the purpose of killing cancer tumors. NASA is investigating the use of swarm technology for planetary mapping.

SI - LIMITATIONS
y

Theoretical analysis is difficult, due to sequences of probabilistic choices. Most of the researches are experimental. Though convergence is guaranteed, time to convergence is uncertain.

RECAP
y

y y

Swarm intelligence is the discipline that deals with natural and artificial systems composed of many individuals that coordinate using decentralized control and self-organization. Provide heuristic to solve difficult problems . Has been applied to wide variety of applications.

REFERENCES
y

Reynolds, C. W. (1987) Flocks, Herds, and Schools: A Distributed Behavioral Model, in Computer Graphics, 21(4) (SIGGRAPH '87 Conference Proceedings) pages 25-34. James Kennedy, Russell Eberhart. Particle Swarm Optimization, IEEE Conf. on Neural networks 1995 www.adaptiveview.com/articles/ ipsop1 M.Dorigo, M.Birattari, T.Stutzle, Ant colony optimization Artificial Ants as a computational intelligence technique, IEEE Computational Intelligence Magazine 2006

y y

Dumb parts, properly connected into a swarm yield smart .results

THANK YOU