Ant Colony Optimization (ACO) in Research
Ant Colony Optimization (ACO)
C
om
S
ens
Research Group
Founding Head: Dr.
Nadeem Javaid
Ph.D, University of Paris-Est, France.
Senior Member IEEE,
Associate Professor, Department of Computer Science,
COMSATS Institute of Information
Technology, 44000, Islamabad, Pakistan.
Real Ants
o
Limited individual capabilities
o
Rudimentary sight
o
Limited visual and auditory communication
o
Not capable of achieving complex tasks on there own
o
Capable of impressive group results
o
Nest building and defence
o
Nest temperature regulation
o
Forming bridges
o
Cooperatively carrying large items
o
Sorting brood and food items
o
Foraging for food sources.
1
Basic Concept
o
In the real world, ants(initially) wander randomly.
o
Upon finding food, ants return to their colony while laying
down pheromone trails.
o
If other ants find such a path, they are likely not to keep
travelling at random.
o
Instead they follow the trail laid by earlier ants, returning and
reinforcing it if they eventually find food.
o
Overt time, the pheromone trail starts to evaporate, thus
reducing its attractive strength.
2
Basic Concept
o
In comparison to the long path, a short path gets marched
over faster, and thus the pheromone density remains high.
o
Pheromone Evaporation:
Advantage:
1.
Avoiding the convergence to a locally optimal
solution.
2.
If there were no evaporation at all, the paths chosen
by the first ants would tend to be excessively
attractive to the following ones. In that case, the
exploration of the solution space would be
constrained.
3
Basic Concept
o
Thus, when one ant finds a good (short) path from the colony
to a food source, other ants are more likely to follow that
path.
o
Such positive feedback eventually leaves all ants following a
single path.
o
The idea of the ant colony algorithm is to mimic this
behaviour with “simulated ants” walking around the search
space representing the problem to be solved
o
ACO algorithm have been used to produce near-optimal
solutions to the travelling salesman problem.
o
This is of interest in network routing and urban transportation
systems.
4
Basic Concept
5
ACO Definintion
o
A heuristic optimization method for shortest path
and other optimization problems which borrows
ideas from biological ants.
o
Based on the fact that ants are able to find shortest
route between their nest and source of food
6
Shortest Route
•
Shortest route is found using pheromone trails
which ants deposit whenever they travel, as a
form of indirect communication.
7
Ant foraging- Co-operative Search by
Pheromone Trails
1.
When
ants leave their nest to
search for a food source, they
randomly rotate around on
obstacle.
2.
Initially the pheromone deposit
will be the
same for right and left
directions.
3.
When the ants in the shorter
direction find a food source, they
carry the food and start returning
back, following their pheromone
trails, and still depositing more
pheromone.
8
4.
An ant will most
likely choose the
shortest path when returning
back to the nest with food as this
path will have the most
deposited pheromone.
5.
For
the same reason, new ants
that later starts out from the nest
to find food will also choose the
shortest path.
6.
Overtime, this positive feedback
(autocatalytic)
process prompts
all ants to choose the shorter
path.
Ant foraging- Co-operative Search by
Pheromone Trails
9
ACO-Algorithm
•
Begin
–
Initialize
–
While stopping criterion not satisfied do
•
Position each ant in a starting node
•
Repeat
–
For each
ant
do
»
Choose next node by applying the state
transition rule
»
Apply step by step pheromone update
–
End For
•
Until every ant has built a solution
•
Update best solution
•
Apply pheromone update
–
End While
•
End
10
ACO
•
The main characteristic of this algorithm is that, at each iteration, the
pheromone values are updated by all the m ants that have built a solution
in the iteration itself. The
τ
ij , associated with the edge joining cities i and j,
is updated as follows [1]:
–
Where
ρ
is the evaporation rate, m is the number of agents, and
is the quantity of pheromone laid on edge (i, j) by ant k:
–
Where Q is a constant and L is the length of the tour constructed by
ant k.
11
[1]
Dorigo, Marco. "Ant colony optimization."
Scholarpedia
2, no. 3 (2007): 1461.
ACO
•
At each point, the ants traverse the construction graph and make a
probabilistic decision.
•
Where N is the set of components that do not belong to the partial
solution of ant k,
α
and
β
are parameters that control the relative
importance of the pheromone versus the heuristic information.
•
η
ij=1/dij is the heuristic information, where dij is the length of the
component.
12
How to implement in a program
13
A
simple
Travel Salesman Problem example
A
E
D
C
B
d
AB
=100;d
BC
= 60…;d
DE
=150
14
Iteration 1
A
E
D
C
B
15
How to build next sub-solution?
A
E
D
C
B
16
Iteration 2
A
E
D
C
B
17
Iteration 3
A
E
D
C
B
18
Iteration 4
A
E
D
C
B
19
Iteration 5
A
E
D
C
B
20
Path and Pheromone Evaluation
L
1
=300
L
2
=450
L
3
=260
L
4
=280
L
5
=420
21
Advantages/Disadvantages
Advantages:
Advantages:
Positive Feedback accounts for rapid discovery of good solutions
Distributed computation avoids premature convergence
The greedy heuristic helps find acceptable solution in the early solution in
the early stages of the search process.
The collective interaction of a population of agents.
Disadvantages:
Disadvantages:
Slower convergence than other Heuristics
No centralized processor to guide the AS towards good solutions
22
Any Questions?
23
ACO, founded by Dr. Nadeem Javaid, mimics the behavior of real ants to find optimal solutions for complex tasks. Real ants rely on limited individual capabilities but excel in group tasks like nest building, foraging, and defense. ACO utilizes pheromone trails and positive feedback to guide simulated ants in finding near-optimal solutions, applicable in various optimization problems like the traveling salesman problem. This heuristic method is inspired by ants' ability to find the shortest path between their nest and food sources.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Ant Colony Optimization (ACO) ComSens Research Group Founding Head: Dr. Nadeem Javaid Ph.D, University of Paris-Est, France. Senior Member IEEE, Associate Professor, Department of Computer Science, COMSATS Institute of Information Technology, 44000, Islamabad, Pakistan.
1 Real Ants o Limited individual capabilities o Rudimentary sight o Limited visual and auditory communication o Not capable of achieving complex tasks on there own o Capable of impressive group results o Nest building and defence o Nest temperature regulation o Forming bridges o Cooperatively carrying large items o Sorting brood and food items o Foraging for food sources.
2 Basic Concept o In the real world, ants(initially) wander randomly. o Upon finding food, ants return to their colony while laying down pheromone trails. o If other ants find such a path, they are likely not to keep travelling at random. o Instead they follow the trail laid by earlier ants, returning and reinforcing it if they eventually find food. o Overt time, the pheromone trail starts to evaporate, thus reducing its attractive strength.
3 Basic Concept o In comparison to the long path, a short path gets marched over faster, and thus the pheromone density remains high. o Pheromone Evaporation: Advantage: 1. Avoiding the convergence to a locally optimal solution. 2. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.
4 Basic Concept o Thus, when one ant finds a good (short) path from the colony to a food source, other ants are more likely to follow that path. o Such positive feedback eventually leaves all ants following a single path. o The idea of the ant colony algorithm is to mimic this behaviour with simulatedants walking around the search space representing the problem to be solved o ACO algorithm have been used to produce near-optimal solutions to the travelling salesman problem. o This is of interest in network routing and urban transportation systems.
5 Basic Concept
6 ACO Definintion o A heuristic optimization method for shortest path and other optimization problems which borrows ideas from biological ants. o Based on the fact that ants are able to find shortest route between their nest and source of food
7 Shortest Route Shortest route is found using pheromone trails which ants deposit whenever they travel, as a form of indirect communication.
Ant foraging- Co-operative Search by Pheromone Trails 8 1. When ants leave their nest to search for a food source, they randomly rotate around on obstacle. Initially the pheromone deposit will be the same for right and left directions. When the ants in the shorter direction find a food source, they carry the food and start returning back, following their pheromone trails, and still depositing more pheromone. 2. 3.
Ant foraging- Co-operative Search by Pheromone Trails 9 4. An ant will most likely choose the shortest path when returning back to the nest with food as this path will have the most deposited pheromone. For the same reason, new ants that later starts out from the nest to find food will also choose the shortest path. Overtime, this positive feedback (autocatalytic) process prompts all ants to choose the shorter path. 5. 6.
10 ACO-Algorithm Begin Initialize While stopping criterion not satisfied do Position each ant in a starting node Repeat For each ant do Choose next node by applying the state transition rule Apply step by step pheromone update End For Until every ant has built a solution Update best solution Apply pheromone update End While End
11 ACO The main characteristic of this algorithm is that, at each iteration, the pheromone values are updated by all the m ants that have built a solution in the iteration itself. The ij , associated with the edge joining cities i and j, is updated as follows [1]: ). 1 ( m + = 1 k ij ij ij k Where is the evaporation rate, m is the number of agents, and is the quantity of pheromone laid on edge (i, j) by ant k: = otherwise 0 k ij Q if ant used k edge (i, tour its in j) k i L k , j Where Q is a constant and L is the length of the tour constructed by ant k. [1] Scholarpedia 2, no. 3 (2007): 1461. Dorigo, Marco. "Ant colony optimization."
12 ACO At each point, the ants traverse the construction graph and make a probabilistic decision. )] ( [ = k allowed k [ ] t ij ij if j N [ [ ( )] ] t k ij ( ) p t ik ik 0 otherwise Where N is the set of components that do not belong to the partial solution of ant k, and are parameters that control the relative importance of the pheromone versus the heuristic information. ij=1/dij is the heuristic information, where dij is the length of the component.
13 How to implement in a program Ants Simple computer agents Move ant Pick next component in the const. solution k j , i Pheromone Memory MK or TabuK Use probability to move ant Next move:
14 [] A simple Travel Salesman Problem example 1 [] 2 A B [] 3 [] C 4 [] D 5 E dAB =100;dBC = 60 ;dDE =150
15 Iteration 1 [B] [A] 2 1 A B [C] 3 C [E] [D] D 5 4 E
16 How to build next sub-solution? [A] 1 A B [A] [ t ( )] [ ] 1 [A] ij [ ij [ allowed if j k C t ( )] ] = k ij p t ( ) ik ik k allowed 1 k [A,D] [A] 0 otherwise 1 1 D E
17 Iteration 2 [E,A] [C,B] 5 3 A B [B,C] 2 C [A,D] [D,E] 1 D 4 E
18 Iteration 3 [D,E,A] [E,A,B] 4 5 A B [A,D,C] 1 C [B,C,D] [C,B,E] 2 D 3 E
19 Iteration 4 [B,C,D,A] [D,E,A,B] 2 4 A B [E,A,B,C] 5 C [C,B,E,D] [A,DCE] 3 D 1 E
20 Iteration 5 [A,D,C,E,B] [C,B,E,D,A] 1 3 A B [D,E,A,B,C] 4 C [E,A,B,C,D] [B,C,D,A,E] 5 D E 2
21 Path and Pheromone Evaluation [D,E,A,B,C] [A,D,C,E,B] L4 =280 L1 =300 4 1 [B,C,D,A,E] [E,A,B,C,D] L2 =450 L5 =420 2 5 [C,B,E,D,A] L3 =260 3 total B , A = + + + + 1 B , A 2 3 B , A 4 B , A 5 B , A B , A Q tour ) j , i ( if j , i = k L k 0 otherwise
22 Advantages/Disadvantages Advantages: Positive Feedback accounts for rapid discovery of good solutions Distributed computation avoids premature convergence The greedy heuristic helps find acceptable solution in the early solution in the early stages of the search process. The collective interaction of a population of agents. Disadvantages: Slower convergence than other Heuristics No centralized processor to guide the AS towards good solutions
23 Any Questions?
