Transcript An Ant Colony Optimization Approach to the Border Penetration Model

An Overview of Swarm
Intelligence and Ant Colony
Optimization Heuristics
Philipp A. Djang Ph.D.
Army Research Labs
"Go to the ant, thou sluggard; consider her ways, and be wise:
Which having no guide, overseer, or ruler,
Provideth her meat in the summer,
and gathereth her food in the harvest"
(Proverbs vi 6-8)
Overview
 Swarm Intelligence
 Ant Colony Algorithm
 Solving a Traveling Salesperson
Problem
 Other Examples
 References
Swarm Intelligence
 Swarm Intelligence (SI) is the property of a
system whereby the collective behaviors of
(unsophisticated) agents interacting locally
with their environment cause coherent
functional global patterns to emerge.
 SI provides a basis with which it is possible to
explore collective (or distributed) problem
solving without centralized control or the
provision of a global model.
 Leverage the power of complex adaptive
systems to solve difficult non-linear stochastic
problems
Swarm Intelligence
 Characteristics of a swarm:
 Distributed,
no central control or data
source;
 Limited communication
 No (explicit) model of the environment;
 Perception of environment (sensing)
 Ability to react to environment changes.
Swarm Intelligence
 Social interactions (locally shared
knowledge) provides the basis for
unguided problem solving
 The efficiency of the effort is related to
but not dependent upon the degree or
connectedness of the network and the
number of interacting agents
Swarm Intelligence
 Robust exemplars of problem-solving in
Nature
 Survival
in stochastic hostile environment
 Social interaction creates complex
behaviors
 Behaviors modified by dynamic
environment.
 Emergent behavior observed in:
 Bacteria, immune system, ants, birds
 And other social animals
Ants – Swarm Intelligence
Example
 Franks observed Lasius Niger ants,









regulation of 1 degree Celsius range;
forming bridges;
raiding specific areas for food;
building and protecting nest;
sorting brood and food items;
cooperating in carrying large items;
emigration of a colony;
finding shortest route from nest to food source;
preferentially exploiting the richest food source available.
 Without Any Central Leadership or Control
Ant Colony Optimization:
Introduction
 First proposed by M. Dorigo, 1992
 Heuristic optimization method inspired by
biological systems
 Multi-agent approach for solving difficult
combinatorial optimization problems

Traveling Salesman, vehicle routing, sequential
ordering, graph coloring, routing in
communications networks
 Has become new and fruitful research area
Ant Colony Algorithms
 Algorithm was inspired by observation
of real ant colonies.
 Ants are essentially blind, deaf and
dumb.
 Ants are social creatures – behavior
directed to survival of colony
 Q: how can ants find the short path to
food sources?
 Ants deposit pheromones on ground
that form a trail. The trail attracts other
ants.
Ant Colony Algorithms
 Ant behavior is a kind of stochastic
distributed optimization behavior.
 Although one ant is capable of building
a solution, it is the behavior of an
ensemble of ants that exhibits the
shortest path behavior.
 The behavior is induced by indirect
communication (pheromone paths)
without central control.
Ant Colony Algorithms
 Ants do not know the global structure of
the problem - discover the network
 Limited ability to sense local
environment - can only “see” adjacent
nodes of immediate neighborhood.
 Each ant chooses an action based on
variable probability
 random
choice
 pheromone mediated
Ant Colony Algorithms
 Each ant collects information about
local environment; acts concurrently
and independently
 No direct communication: stigmergy
paradigm governs information exchange
 Incremental constructive approach to
building solutions
 High quality solutions emerge via global
cooperation.
Stigmergy
 Indirect communication via interaction
with environment [Gassé, 59, Wilson,
75]
 Sematonic

stigmergy
action of agent directly related to problem
solving and affects behavior of other agents.
 Sign-based

stigmergy
action of agent affects environment not directly
related to problem solving activity.
Pheromone Trails
 Species lay pheromone trails traveling from
nest, to nest or possibly in both directions.
 Pheromones evaporate.
 Pheromones accumulate with multiple ants
using path.
Nest
Food
source
Pheromone Trails Example
E
E
E
T=
1
T=
0
30 ants
30 ants
D
d=1.0
d=0.5
H
C
d=1.0
B
A
d=0.5
15
ants
D
15
ants
C
H
15
ants
10
ants
B
15
ants
30
A ants
D
20
ants
C
H
10
ants
B
20
ants
30
A ants
Ant Colony Algorithms
 Pheromone mediated “following”
behavior induces the emergence of
shortest paths.
 Probability of choosing a branch of a
path at a certain time depends on the
total amount of pheromone on the
branch.
 The choice is proportional to the
number of ants that have used the
branches.
Ant Colony Algorithms
 Let um and lm be the number of ants that
have used the upper and lower
branches.
 The probability Pu(m) with which the
(m+1)th ant chooses the upper branch
is:
(

k
)
u
m
P ( m) 
(u m  k )  (l m  k )
h
u
h
h
Traveling Salesperson Problem
 Famous NP-Hard Optimization Problem
 Given a fully connected, symmetric
G(V,E) with known edge costs, find the
minimum cost tour.
 Artificial ants move from vertex to vertex
to order to find the minimum cost tour
using only pheromone mediated trails.
Traveling Salesperson Problem
 The three main ideas that this ant
colony algorithm has adopted from real
ant colonies are:
 The
ants have a probabilistic preference
for paths with high pheromone value
 Shorter paths tend to have a higher rate of
growth in pheromone value
 It uses an indirect communication system
through pheromone in edges
Traveling Salesperson Problem
 Ants select the next vertex based on a
weighted probability function based on two
factors:


The number of edges and the associated cost
The trail (pheromone) left behind by other ant
agents.
 Each agent modifies the environment in two
different ways :


Local trail updating: As the ant moves between
cities it updates the amount of pheromone on the
edge
Global trail updating: When all ants have
completed a tour the ant that found the shortest
route updates the edges in its path
Traveling Salesperson Problem
 Local Updating is used to avoid very
strong pheromone edges and hence
increase exploration (and hopefully
avoid locally optimal solutions).
 The Global Updating function gives the
shortest path higher reinforcement by
increasing the amount of pheromone on
the edges of the shortest path.
Empirical Results
 Compared Ant Colony Algorithm to
standard algorithms and meta-heuristic
algorithms on Oliver 30 – a 30 city TSP
 Standard: 2-Opt, Lin-Kernighan,
 Meta-Heuristics: Tabu Search and
Simulated Annealing
 Conducted 10 replications of each
algorithm and provided averaged results
Comparison to Standard
Algorithms
 Examined Solution
Quality – not speed;
in general, standard
algorithms were
significantly faster.
 Best ACO solution 420
2-Opt L-K
Near
Neighbor
437
421
Far Insert
421
420
Near Insert
492
420
Space Fill
431
421
Sweep
426
421
Random
663
421
Comparison to Meta-Heuristic
Algorithms
 Meta-Heuristics are algorithms that can be
applied to a variety of problems with a minimum
of customization.
 Comparing ACO to other Meta-heuristics
provides a “fair market” comparison (vice TSP
specific algorithms).
Best
Mean
Std Dev
ACO
420
420.4
1.3
Tabu
420
420.6
1.5
SA
422
459.8
25.1
Other Application Areas
 Scheduling : Scheduling is a
widespread problem of practical
importance.
 Paul Forsyth & Anthony Wren,
University of Leeds Computer Science
department developed a bus driver
scheduling application using ant colony
concepts.
Other Application Areas
 Telecommunication Networks : Network
routing refers to the activity of creating,
maintaining and using routing tables (one for
each node in the network) to determine
where to direct an incoming data stream so
that it can continue its travel through the
network.
 In telecommunications, this is an extremely
difficult problem because of the constant
changes in network traffic load. The Ant
Colony algorithm provides adaptive
advantages that can adjust to traffic load.
Other Application Areas
 Vehicle Routing Problem: The VRP is
similar to the TSP, but is complicated by
multiple vehicles, vehicle capacity, pickup and drop off points (which can
dictate vehicle packing and scheduling).
 Bernd Mullenheimer, Richard Hartl and
Christine Strauss developed an Ant
Colony algorithm for solving the VRP
Ant Colony Algorithms: Summary
 Ant Colony Algorithms mimic Real Ants
 Colony
of cooperating individuals
 Simulated Pheromone Trail and Stigmergy
 Shortest path searching with local moves
 Stochastic and myopic state transition
policy
 Artificial ants:
 Discrete
state transitions
 Pheromones based on solution quality
 Pheromone laying is problem dependent
Interesting Reading
 Alexandrov D., Kochetov Y. Behavior of the Ant Colony





Algorithm for the Set Covering Problem, Proc. of Symposium.
on Operations. Research., Springer Verlag, 2000
On the MAX/MIN Ant system, Thomas Stützle, 2001.
Hybrid Ant System for the Sequential Ordering Problems, Luca
Gambardella, 2002.
Parallelization Strategies for Ant Colony Optimization by
Thomas Stützle. In Proceedings of PPSN-V, Amsterdam,
Springer Verlag, LNCS 1998
Improvements on the Ant System: Introducing the MAX-MIN Ant
System by Thomas Stützle. Proceedings of Artificial Neural Nets
and Genetic Algorithms 1997
The Ant System Applied to the Quadratic Assignment Problem
by Maniezzo, Colorni and Dorigo. Tech. Rep. IRIDIA/94-28,
Université Libre de Bruxelles 1994
Interesting Reading
 Dorigo, M., Maniezzo, V., Colorni, A., The Ant
System: Optimization by a Colony of Cooperating
Agents, IEEE Transactions on Systems, Man and
Cybernetics-Part B, v26,n1, 1996
 Rafael S. Parpinelli and Heitor S. Lopes and Alex A.
Freitas, An Ant Colony Based System for Data
Mining: Applications to Medical Data, Proceedings of
the Genetic and Evolutionary Computation
Conference ({GECCO}-2001)
 Nicolas Monmarché, Mohamed Slimane, Gilles
Venturini, AntClass: discovery of clusters in numeric
data by an hybridization of an ant colony with the
kmeans algorithm, 1999
On-Line Resources
 http://www.swarm.org/
 http://www.swarm-bots.org/
 http://dsp.jpl.nasa.gov/members/payman/swarm/
 http://www.engr.iupui.edu/~shi/pso.html
 http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
 http://www.cs.technion.ac.il/~wagner/
 http://ants.gsfc.nasa.gov/