Group-12_SwarmIntelligence bbghjgjhgjh.ppt

swarm intelligence

1. Swarm IntelligenceSwarm Intelligence
05005028 (sarat chand)
05005029(naresh Kumar)
05005031(veeranjaneyulu)
05010033(kalyan raghu)

2. Swarms

Natural phenomena as inspiration

A flock of birds sweeps across the Sky.

How do ants collectively forage for food?

How does a school of fish swims, turns together?

They are so ordered.

3. 
What made them to be so ordered?

There is no centralized controller

But they exhibit complex global behavior.

Individuals follow simple rules to interact with
neighbors .

Rules followed by birds
collision avoidance
velocity matching
Flock Centering

4. Swarm Intelligence-Definition

“Swarm intelligence (SI) is artificial intelligence
based on the collective behavior of decentralized,
self-organized systems”

5. Characteristics of Swarms

Composed of many individuals

Individuals are homogeneous

Local interaction based on simple rules

Self-organization

6. Overview

Ant colony optimization

TSP

Bees Algorithms

Comparison between bees and ants

Conclusions

7. Ant Colony Optimization

The way ants find their food in shortest path is
interesting.

Ants secrete pheromones to remember their path.

These pheromones evaporate with time.

8. Ant Colony Optimization..

Whenever an ant finds food , it marks its return
journey with pheromones.

Pheromones evaporate faster on longer paths.

Shorter paths serve as the way to food for most of
the other ants.

9. Ant Colony Optimization

The shorter path will be reinforced by the
pheromones further.

Finally , the ants arrive at the shortest path.

10. Optimization using SI

Swarms have the ability to solve problems

Ant Colony Optimization (ACO) , a meta-heuristic

ACO can be used to solve hard problems like TSP,
Quadratic Assignment Problem(QAP)

We discuss ACO meta-heuristic for TSP

11. ACO-TSP

Given a graph with n nodes, should give the
shortest Hamiltonian cycle

m ants traverse the graph

Each ant starts at a random node

12. Transitions

Ants leave pheromone trails when they make a
transition

Trails are used in prioritizing transition

13. Transitions

Suppose ant k is at u.

Nk(u) be the nodes not visited by k

Tuv be the pheromone trail of edge (u,v)

k jumps from u to a node v in Nk(u) with
probability
puv(k) = Tuv ( 1/ d(u,v))

14. Iteration of AOC-STP

m ants are started at random nodes

They traverse the graph prioritized on trails and
edge-weights

An iteration ends when all the ants visit all nodes

After each iteration, pheromone trails are updated.

15. Updating Pheromone trails

New trail should have two components
Old trail left after evaporation and
Trails added by ants traversing the edge during the
iteration

T'uv = (1-p) Tuv + ChangeIn(Tuv)

Solution gets better and better as the number of
iterations increase

16. Performance of TSP with ACO heuristic

Performs better than state-of-the-art TSP
algorithms for small (50-100) of nodes

The main point to appreciate is that Swarms give
us new algorithms for optimization

17. Bee Algorithm

19. Bees Foraging

Recruitment Behaviour :
Waggle Dancing
series of alternating left and right loops
Direction of dancing
Duration of dancing

Navigation Behaviour :
Path vector represents knowledge representation of
path by inspect
Construction of PI.

20. Algorithm

It has two steps :
ManageBeesActivity()
CalculateVectors()

ManageBeesActivity: It handles agents activities
based on their internal state. That is it decides
action it has to take depending on the knowledge it
has.

CalculateVectors : It is used for administrative
purposes and calculates PI vectors for the agents.

21. Uses of Bee Algorithm

Training neural networks for pattern recognition

Forming manufacturing cells.

Scheduling jobs for a production machine.

Data clustering

22. Comparisons

Ants use pheromones for back tracking route to
food source.

Bees instead use Path Integration. Bees are able to
compute their present location from past trajectory
continuously.

So bees can return to home through direct route
instead of back tracking their original route.

Does path emerge faster in this algorithm.

23. Results

Experiments with different test cases on these
algorithms show that.
Bees algorithm is more efficient when finding and
collecting food, that is it takes less number of steps.
Bees algorithm is more scalable it requires less
computation time to complete task.
Bees algorithm is less adaptive than ACO.

24. Applications of SI

In Movies : Graphics in movies like Lord of the
Rings trilogy, Troy.

Unmanned underwater vehicles(UUV):
Groups of UUVs used as security units
Only local maps at each UUV
Joint detection of and attack over enemy vessels by co-
ordinating within the group of UUVs

25. More Applications

Swarmcasting:
For fast downloads in a peer-to-peer file-sharing
network
Fragments of a file are downloaded from different
hosts in the network, parallelly.

AntNet : a routing algorithm developed on the
framework of Ant Colony Optimization


BeeHive : another routing algorithm modelled on
the communicative behaviour of honey bees

26. A Philosophical issue

Individual agents in the group seem to have no
intelligence but the group as a whole displays
some intelligence

In terms of intelligence, whole is not equal to sum
of parts?

Where does the intelligence of the group come
from ?

Answer : Rules followed by individual agents

27. Conclusion

SI provides heuristics to solve difficult
optimization problems.

Has wide variety of applications.

Basic philosophy of Swarm Intelligence : Observe
the behaviour of social animals and try to mimic
those animals on computer systems.

Basic theme of Natural Computing: Observe
nature, mimic nature.

28. Bibliography

A Bee Algorithm for Multi-Agents System-
Lemmens ,Steven . Karl Tuyls, Ann Nowe -2007

Swarm Intelligence – Literature Overview, Yang
Liu , Kevin M. Passino. 2000.

www.wikipedia.org

The ACO metaheuristic: Algorithms,
Applications, and Advances. Marco Dorigo and
Thomas Stutzle-Handbook of metaheuristics,
2002.