Transcript now

Swarm Intelligence
Quantitative analysis: How to make a
decision?
Thank you for all referred pictures and information.
Agenda

Introduction

Nature of Swarm

Swarm Intelligence: Applying

Existing Algorithms and Applications
2
Introduction

A group of simple or complexindividuals can
exhibit very complex emergent behavior

collective behavior

applies to many processes in nature, creating a useful
concept in many contexts

collectively migrating bacteria

insects or birds, or phenomena where groups of
organisms or non-living objects synchronize their signals
or motion
3
Introduction

A collective behavior shows a seeming
intelligence that far transcends the abilities of
the members, named “swarm intelligence”

Decentralized system


requires multiple agents to make their own independent
decisions
Self-organized system

it is not directed or controlled by any agent or subsystem
inside or outside of the system
4
Decentralized System

There is no single centralized authority that
makes decisions on behalf of all the agents.

Agent makes local autonomous decisions towards
its individual goals which may possibly conflict
with those of other agents.

Agents directly interact with each other and share
information or provide service to other agents.
http://www.isr.uci.edu/projects/pace/decentralization.html
5
Self-organized System

“In biological systems self-organization is a
process in which pattern at the global level of
a system emerges solely from numerous
interactions
among
the
lower-level
components of the system. Moreover, the
rules specifying interactions among the
system's components are executed using
only local information, without reference to
the global pattern”
Camazine, Deneubourg, Franks, Sneyd, Theraulaz, Bonabeau, SelfOrganization in Biological Systems, Princeton University Press, 2003.
6
Self-organized System

Examples



Coordination of human movement
Flocking behaviour
Creation of structures by social animals
7
Nature of Swarm

The word swarm conjures up images of large
groups of small insects in which each member
performs a simple role, but the action produces
complex behavior as a whole.




Termites swarm to build colonies
Ants swarm to find food sources
Bees swarm to reproduce
Bird swarms


each bird tries to find another to fly with
flies slightly higher to one side to reduce drag, with the birds
eventually forming a flock.
8
Categorizing Collective Behaviors
http://science.howstuffworks.com/environmental/lif
e/zoology/insects-arachnids/termite3.htm

Coordination

Interactions between individuals generate synchronized
and oriented movements of the individuals toward a
specific goal.

Coordination is at work in most of the building activities in
insect colonies.

Nest building in certain species of social insects
9
Categorizing Collective Behaviors
http://deepintoscripture.com/2012/05/01/in-whichthere-are-ants-and-a-news-reporter-and-tournamentresults/

Cooperation


Occurs when individuals achieve together a task that could
not be done by a single one.
The individuals must combine their efforts in order to
successfully solve a problem that goes beyond their
individual abilities.
 Bringking food back to the nest
10
Categorizing Collective Behaviors

Deliberation
http://www.responsiblepestcontrolmesa.co
m/argentine-ant-pest-control-exterminating/

Deliberation refers to mechanisms that occur when a colony
faces several opportunities.

These mechanisms result in a collective choice for at least one of
the opportunities.


Ants have discovered several food sources with different qualities or
richness, or several paths that lead to a food source, they generally
select only one of the different opportunities.
In this case, the deliberation is driven by the competition between the
chemical trails leading to each opportunity
11
Example Nature of Deliberation

For two food sources: Ant Colony

A rich food source far from the nest and an inferior food
source close to the nest, some ants went to the inferior
food source because it was near the nest, but some other
ants wandered, and then they found the rich food source.

They emitted pheromone along the path from the nest to
the rich food source until the trail to the rich food source
was stronger than the original one.

Finally, the most of ants shift to the richer source.
Therefore, the randomness of some ants’ behavior makes
it possible to explore multiple food sources in parallel
12
Categorizing Collective Behaviors

Collaboration

Collaboration means that different activities are
performed simultaneously by groups of
specialized individuals

foraging for prey or tending brood inside the nest
13
Why do animals swarm?



To forage better
To migrate
As a defense against predators
Social Insects have survived for millions of
years.
14
Swarm Intelligence: Applying

“Swarm” refers to a large group of simple components working
together to achieve a goal and produce significant results.

Swarm intelligence techniques are population-based stochastic
methods used in combinatorial optimization problems in which
the collective behavior of relatively simple individuals arises from
their local interactions with their environment to produce
functional global patterns.

Swarm intelligence has become a hot research topic in both
biology and engineering, exhibiting some important features such
as decentralization, flexibility, robustness, self-organization and
emergence
15
Swarm Intelligence: Applying

Intelligent swarm technology is based on
aggregates of individual swarm members that also
exhibit independent intelligence.

Members of the intelligent swarm can be
heterogeneous or homogeneous.

Due to their differing environments, members can
become a heterogeneous swarm as they learn
different tasks and develop different goals, even if
they begin as homogeneous.
16
Swarm Intelligence: Applying

The individuals in a group are called agents.

Swarm Intelligence based techniques can be
applied to solve complicated problems

Data analysis problems, e.g., data clustering, to group the
data with some features into the same clusters by using
similarity measures

An ant with random motion picks up or drops data with a
probability.

Further to cluster the data, measuring the similarity and
dissimilarity between data are utilised.

This clustering algorithm is very efficient for few data sources,
but not applicable to numerous data.
17
Swarm Intelligence: Applying

Network Routing Problems: utilize mobile software
agents for network management

Agents are autonomous entities, both proactive and
reactive, and have the capability to adapt, cooperate
and move intelligently from one location to the other in
the communication network

Swarm intelligence, uses stigmergy for agent interaction

Swarm intelligence exhibits emergent behavior wherein
simple interactions of autonomous agents, with simple
primitives, give rise to a complex behavior that has not
been specified explicitly
18
Swarm Intelligence: Applying

Swarm Robotics



Swarm robotics refers to the application of swarm
intelligence techniques to the analysis of activities in
which the agents are physical robotic devices that can
effect changes in their environments based on intelligent
decision-making from various input.
The robots can walk, move on wheels, or operate under
water or on other planets.
Job Scheduling Problems

Investigating the flexible way in which honeybees assign
tasks could lead to a more efficient method for
scheduling jobs in a factory
19
Existing Algorithms and Applications

Existing Algorithms


Particle swarm optimization (PSO)
Ant colony optimization (ACO)
Slocum Glider.
Credit: Teledyne Webb Research via Ocean
Observatories Initiative

Existing Applications


Unmanned underwater vehicles (UUV)
Swarmcasting
20
Introduction to Particle swarm optimization (PSO)

PSO simulates the behaviors of bird flocking.

A group of birds are randomly searching food in an area.

There is only one piece of food in the area being searched.

All the birds do not know where the food is.
 But they know how far the food is in each iteration.


What's the best strategy to find the food?
The effective one is to follow the bird which is nearest to the food.
21
Introduction to Particle swarm optimization (PSO)

In PSO, each single solution is a "bird" in the search
space, called "particle".

All of particles have fitness values which are
evaluated by the fitness function to be optimized,
and have velocities which direct the flying of the
particles.

The particles fly through the problem space by
following the current optimum particles.
22
Introduction to Particle swarm optimization (PSO)

PSO is a global optimization algorithm for dealing
with problems in which a point or surface in an n
dimensional space best represents a solution.

Potential solutions are plotted in this space and
seeded with an initial velocity.

Particles move through the solution space, and
certain fitness criteria evaluate them.

Over time, particles accelerate toward those with
better fitness values.
23
Introduction to Ant colony optimization (ACO)

Artificial ants travel through a problem graph
depositing artificial or digital pheromones to enable
other ants to determine more optimal solutions.

Ant colony optimization has solved the traveling
salesman problem, which investigates the shortest
route to several cities and the subsequent return to
a starting point, as well as network and Internet
optimizations.
24
Introduction to Ant colony optimization (ACO)

Ant Colony Optimization Algorithms
http://www.funpecrp.com.br/gmr/year2005/vol3-4/wob09_full_text.htm
25
Introduction to Unmanned underwater vehicles
(UUV)

Each UUV relies on the same template information
containing plans, subplans, and its own local
situation map to make independent decisions.

The UUVs cooperate in the network

for example, group pursuit strategy experiments in a
shallow water pool.

They can identify vessels of interest and pursue them in
environments in which a larger underwater vessel would be
destroyed.
26
Introduction to Swarmcast

A technique that exploits the acceleration of distributed downloading
to provide high-resolution video, audio, and peer-to-peer data
streams, swarmcasting also significantly reduces needed
bandwidth.

It applies the swarm analogy to break down video files into small
pieces so that the system can download components from several
machines simultaneously.


The user can start watching the video before the download
completes.
Swarmcast (www.swarmcast.com), a commercial company,
supports delivery of large amounts of data over networks using
similar concepts and strives to be a significant contributor to the next
generation of Internet TV.
27
PSO: Details


PSO is initialized with a group of random particles (solutions) and
then searches for optima by updating generations.
In every iteration, each particle is updated by following two "best"
values.

The first one is the best solution (fitness) it has achieved so far. (The
fitness value is also stored.)


This value is called pbest.
Another "best" value that is tracked by the particle swarm optimizer is
the best value, obtained so far by any particle in the population.


This best value is a global best and called gbest.
When a particle takes part of the population as its topological neighbors,
the best value is a local best and is called lbest.
28
PSO: Details

After finding the two best values, the particle
updates its velocity and positions with following
equations
Velocity
v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[])
Position
present[] = persent[] + v[] (b)
v[] is the particle velocity, persent[] is the current particle (solution).
pbest[] and gbest[] are defined as stated before.
rand () is a random number between (0,1). c1, c2 are learning factors, c1 = c2
29
PSO: Details

For each particle
Initialize particle
END
Do
For each particle
Calculate fitness value
If the fitness value is better than the best fitness value (pBest) in history
set current value as the new pBest
End
Choose the particle with the best fitness value of all the particles as the gBest
For each particle
Calculate particle velocity according equation (Velocity)
Update particle position according equation (Position)
End
While maximum iterations or minimum error criteria is not attained
30
PSO: Details

Particle Swarm
Optimization Algorithms
(PSO)
http://www.sciencedirect.com/science/article/pii/S09
60148109001232
31
Comparisons between Genetic Algorithm and
PSO





Most of evolutionary techniques have the following procedure:
1. Random generation of an initial population
2. Calculate fitness value for each subject.
It will directly depend on the distance to the optimum.
3. Reproduction of the population based on fitness values.
4. If requirements are met, then stop. Otherwise go back to 2.
PSO shares many common points with GA.
Both algorithms start with a group of a randomly generated
population
Both algorithms have fitness values to evaluate the population.
Both algorithms update the population and search for the optimium
with random techniques.
Both systems do not guarantee success.
32
Comparisons between Genetic Algorithm and
PSO




PSO does not have genetic operators like crossover and
mutation.
Particles update themselves with the internal velocity.
They also have memory, which is important to the algorithm.
The information sharing mechanism in PSO is significantly
different from GAs.
 In GAs, chromosomes share information with each other.


The whole population moves like a one group towards an optimal
area.
In PSO, only gBest (or lBest) gives out the information to others.



It is a one -way information sharing mechanism.
The evolution only looks for the best solution.
All the particles tend to converge to the best solution quickly even in
the local version in most cases.
33
ACO: Details

Ant Colony Optimization Algorithms

the Traveling Salesman Problem: An iterative algorithm

At each iteration, a number of artificial ants are considered.

Each of them builds a solution by walking from node to node on the graph with the
constraint of not visiting any node that she has already visited in her walk.

An ant selects the following node to be visited according to a stochastic
mechanism that is biased by the pheromone: when in node i, the following node is
selected stochastically among the previously unvisited ones

if j has not been previously visited, it can be selected with a probability that is
proportional to the pheromone associated with edge (i, j).

the pheromone values are modified in order to bias ants in future iterations to
construct solutions similar to the best ones previously constructed.
34
ACO: Details

Ant Colony Optimization Algorithms
35
ACO: Details

Ant Colony Optimization Algorithms

ConstructAntSolutions:


ApplyLocalSearch:


A set of m artificial ants constructs solutions from elements of a finite set of
available solution components.
Once solutions have been constructed, and before updating the pheromone, it is
common to improve the solutions obtained by the ants through a local search.
UpdatePheromones:


The aim of the pheromone update is to increase the pheromone values associated
with good or promising solutions, and to decrease those that are associated with
bad ones.
Usually, this is achieved


by decreasing all the pheromone values through pheromone evaporation
by increasing the pheromone levels associated with a chosen set of good solutions.
36
Example: TSP Solving by ACO

Matlab files: Ant_Tsp (Example)
37
Swarm Intelligence

Application of Swarm Principles: Swarm of
Robotics
http://www.domesro.com/2008/08/swarm-robotics-for-domestic-use.html

http://www.youtube.com/watch?feature=playe
r_embedded&v=rYIkgG1nX4E#!
38
References








P. Meesad, S. Sodsee, Z. Li and W.A. Halang, “A Distributed Data
Clustering based on Multiple Colonies Swarm-like Agent,” Proc. Intl. Conf.
Electrical Engineering/Electronics, Computer, Telecommunications and
Information Technology, pp. 618-621, 2009 .
Hinchey, M.G., Sterritt, R., Rouff, C., “Swarms and Swarm Intelligence”,
Computer, Vol.40, Iss.4, pp.111-113, 2007.
Simon Garnier,Jacques Gautrais,Guy Theraulaz, “The biological principles
of swarm intelligence,” Swarm Intelligence, Vol.1, Iss.1, pp.3-31, 2007.
Peter Miller, “Smart Swarm: Using Animal Behaviour to Organise Our
World,” Collins, 2011.
Swarm Intelligence, From Natural to Artificial Systems, Ukradnuté kde sa
dalo, a adaptované.
http://www.swarmintelligence.org/
http://www.isr.uci.edu/projects/pace/decentralization.html
Camazine, Deneubourg, Franks, Sneyd, Theraulaz, Bonabeau, “SelfOrganization in Biological Systems,” Princeton University Press, 2003.
39