CS计算机代考程序代写 ant flex algorithm ANT COLONY OPTIMISATION

ANT COLONY OPTIMISATION
DR H.K. LAM
Department of Engineering
King’s College London
Office S2.14, Strand Building, Strand Campus
Email: hak-keung.lam@kcl.ac.uk
https://nms.kcl.ac.uk/hk.lam
Nature-Inspired Learning Algorithms (7CCSMBIM)
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 1/53

Outline
1 Introduction
2 The Binary Bridge Experiments
3 Stigmergy and Artificial Pheromone
4 Simple Ant Colony Optimisation (SACO)
5 Ant System (AS)
6 Examples
7 Ant Colony System (ACS)
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 2/53

Learning Objectives
To know the kind of problems that can be solved by Ant Colony Optimisation algorithms.
To know how Ant Colony Optimisation algorithms work and their limitations.
To apply Ant Colony Optimisation algorithms to shortest-path finding problems.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 3/53

Introduction
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 4/53

Introduction
Swarm Intelligence
“Swarm intelligence is the property of a system whereby the collective behaviours of (unsophisticated) agents interacting locally with their environment cause coherent functional global patterns to emerge.”
“Swarm intelligence provides a basis with which it is possible to explore collective (or distributed) problem solving without centralised control or the provision of a global model.”
Example:
A group of fishes swim in the same direction.
Ants work together to find food and haul back to the nest.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 5/53

Introduction
Characteristics of Social Colonies
Flexible: The colony can respond to internal perturbations and
external challenges.
Robust: Tasks are completed even if some individuals fail.
Decentralised: There is no central control in the colony.
Self-organised: Paths to solutions are emergent rather than predefined.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 6/53

Introduction
Self-organisation
A set of dynamical mechanisms whereby structures appear at the global level of a system from interactions of its lower-level components. Four basic ingredients:
Positive feedback (amplification): To show the right of direction to the food source (optimal solution); to reinforce those portions of good solutions that contribute to the quality of these solutions.
Negative feedback: to introduce a time scale into the algorithm through pheromone evaporation, to prevent premature convergence (stagnation), for counter-balance and stabilisation
Amplification of fluctuation: Randomness or errors, e.g., lost ant foragers can find new food sources. An element moves more randomly to search for a solution and then amplified by a positive feedback loop. Multiple interactions: Direct or indirect communication (e.g.,
modification of the environment).
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 7/53

Introduction
Ants
Ants appeared on earth some 100 million years ago. Estimated total population: 1016 individuals.
Social insects live in colonies of 30 to millions of individuals.
Collective behaviours: foraging behaviour, division of labour, cooperative support, cemetery organisation, brood care, construction of nests, etc.
Stimulus-response agents.
Individual performs simple and basic action based on information of local information.
Simple actions appear to have a large random component.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 8/53

Introduction
Ant Optimisation Algorithm
To search for an optimal path in a graph.
Find the shortest path between their nest and food source, without any visible, central, active coordination mechanisms.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 9/53

Notation
xk(t): the solution of ant k, which is a set of nodes visited by ant k.
x ̃(t): the current best path (the best solution among xk(t)) at generation/iteration t, which is a set of nodes visited by the best ant.
xˆ(t): the global best path found from the first iteration to current iteration of the algorithm.
x+(t): the best solution(s) giving the shortest path(s) (the iteration-best or global best ant(s)).
t: generation/iteration number.
ρ: evaporation rate.
nk: number of ants.
ne: number of elite ants.
(i, j): an edge from node i to node j.
τij(t): pheromone concentration associated with edge (i,j) at generation/iteration t.
∆τk(t): the change of pheromone concentration associated with edge (i,j) at generation/iteration t. ij
∆τe(t): the change of pheromone concentration associated with edge (i,j) visited by the elite ants at generation/iteration t. ij
f (xk (t)): the quality of the solution of ant k.
f (x ̃(t)): the quality of the solution of the x ̃(t) (the best ant).
f (x+ (t)): the cost(s) of the best solution(s) for x+ (t) (the iteration-best or global best ant(s)). Lk(t): length of the path (from the source to the destination) constructed by ant k.
dij(t): cos between edge (i,j). When t is dropped, dij is independent of generation/iteration t. pkij (t): transition probability of selecting the next node j ∈ Ni k (t) by ant k and node i.
Ni k (t): the set of feasible nodes connected to node i, with respect to ant k.
Q > 0: a non-zero positive constant.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 10/53

The Binary Bridge Experiments
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 11/53

The Binary Bridge Experiments
A simple and elegant experiment to study of foraging behaviour of ants.
Ants deposit chemical pheromone while walking.
Ants have larger probability to follow path with higher pheromone trial. Probability of the next ant to choose path A:
(c+nA(t))α
PA(t+1)= (c+nA(t))α +(c+nB(t))α =1−PB(t+1)
nA(t) and nB(t): Number of ants on paths A and B, respectively. c: degree of attraction of an unexplored branch.
α: the bias to using pheromone deposits in the decision process
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 12/53

The Binary Bridge Experiments
Artificial Ant Decision Process
Generate a random number r ∈ [0, 1]; Choose values of c and α;
for each potential path A do
CalculateP (t+1)= if r ≤ PA then;
(c+nA (t))α
A (c+nA (t))α +(c+nB )α
Follow path A;
Break;
end end
Table 1: Pseudo Code of Artificial Ant Decision Process.
DrH.K.Lam (KCL)
AntColonyOptimisation
NILAs2020-21
13/53

The Binary Bridge Experiments
Shortest path selection by forager ants
Shortest path is selected. Ants return to the nest earlier.
The pheromone on the shortest path is reinforced sooner (positive
feedback)
362
àà Ant Algorithms
Nest
Nest
Food (a)
Food (b)
Dr H.K. Lam (KCL)
Figure àà2 ShortestAPntatChoSloenleyctOiopntimbyisFaotiroanger Ants
NILAs 2020-21
14 / 53

The Binary Bridge Experiments
Shortest path selection by forager ants
(a)
Ant Colony Optimization: Part 1
Foraging behavior o(fbA) nts
(d)
(c)
 Over many iterations, more ants begin using the path with higher pheromone, thereby further reinforcing it.
DrH.K.Lam (KCL)
AntColonyOptimisation
NILAs2020-21
15/53

Stigmergy and Artificial Pheromone
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 16/53

Stigmergy and Artificial Pheromone
Stigmergy is a class of mechanisms that mediate animal-to-animal interactions.
A form of indirect communication mediated by modifications of the environment.
Some signs observed by individual trigger a specific response or action, which may reinforce or modify signals (positive or negative feedback) to influence actions of others
Two forms of stigmergy: sematectonic and sign-based. Sematectonic stigmergy: communication via changes in the physical
characteristics of the environment.
Sign-based stigmergy: communication via a signalling mechanism, e.g., implemented via chemical compounds deposited by ants.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 17/53

Stigmergy and Artificial Pheromone
Artificial stigmergy: “indirect communication mediated by numeric modifications of environmental states which are only locally accessible by the communicating agent”. (Dorigo and Di Caro)
Artificial pheromone plays the role of stigmergic variable, which encapsulate the information used by artificial ants to communicate indirectly.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 18/53

Simple Ant Colony Optimisation (SACO)
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 19/53

Simple Ant Colony Optimisation (SACO)
(i, j): An edge from node i to node j.
τij(t): Pheromone concentration associated with edge (i,j) at generation/iteration t.
τij(0) is assigned a small random value. Why?
Lk(t): Length of the path (from the source to the destination)
constructed by ant k.
àà Ant Colony Optimization Meta-Heuristic
365
23
Source
114 5
4 45
67
Figure àà3 Graph for Shortest Path Problems AntColonyOptimisation
Destination
DrH.K.Lam (KCL)
NILAs2020-21
20/53

Simple Ant Colony Optimisation (SACO)
ple terms how a generic ACO algorithm known traveling salesman problem, and more formal description of ACO.
A. ACO for the Traveling Salesman Pro
In the traveling salesman problem, a and the distance between each of the is to find the shortest tour that allows e
is applied to the well- Section II-B gives a
blem
set of cities is given is known. The goal ach city to be visited
Transition probability of selecting the next node j ∈ N k( )
i ant ksitting at node i (roulette wheel selection method):
a
num
ber
of
ar
tifi
cial ants moving on a graph that
τα(t)
ij if j ∈ N k(t)
k 
pij(t) = u∈N k(t) ,k = 1,··· ,nk
where N k(t) is the set of feasible nodes connected to n
i
i
respect to the ant k; α > 0 is a constant.
F
h
30 IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | NOVEMBER 2006 If N k(t) = 0, the predecessor to node i is included in N k(t).
ii
This may cause loops.
Loops are removed when the destination has been reached.
Example: Found path with a loop: 1–4–2–3–4–5 Path after removing a loop: 1–4–5
once and only once. In more formal terms, the goal is to find a Hamiltonian tour of minimal length on a fully con- nected graph.
In ant colony optimization, the problem is tackled by simu-
latin
o
,
IGU
g
e
d
t
b
RE 2
e
w
y
t
h
τα(t) i ∑ iu
i
0 otherwise
i
t
t in
mechanism: if j has not been previously visited, it can be selected with a probability that is proportional to the pheromone associated with
e d g e ( i , j ).
An a
oses the next city to visit via a stochastic
n
city i
ch
o
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 21/53
g
j
ik
m

Simple Ant Colony Optimisation (SACO)
Example
C. Blum / Physics of Life Reviews 2 (2005) 353–373
Node 1: N k(t) = {2,3,4} 1
τα (t) k 1,2
p1,2(t)=τα (t)+τα (t)+τα (t) 1,2 1,3 1,4
k
p1,3(t)=τα (t)+τα (t)+τα (t)
τα (t) 1,3
1,2 1,3 1,4 τα (t)
. Examplekof the solution constructio1n,4for a TSP problem p (t)= α α α
n constru1c,ti4on starts byτrand(omt)l+y cτhoos(itn)g+aτstart(nto)de f 1,2 1,3 1,4
tively the second, construction step. Note that in both cases the current node (i.e., location) of the ant is marked by dark gray color, and the
y visited nodes are marked by light gray color (respectively yellow color, in the online version of this article). The choices of the ant (i.e.,
gessNheomtaey:traτverse()tar)em=arkτedby(dta)shedlines.Theprobabilitiesforthedifferentchoices(accordingtoEq.(4))aregivenunderneaththe i,j j,i
ics. Note that after the second construction step, in which we exemplary assume the ant to have selected node 4, the ant can only move to , and then back to node 1 in order to close the tour.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 22/53
Node 2: N k(t) = {3,4} 2
Node 4: N k(t) = {3} 4
τα (t) k 2,3
p2,3(t)=τα (t)+τα (t) 2,3 2,4
k
p2,4(t)=τα (t)+τα (t)
consisting of 4 cities (modelled by a graph with or the ant; in this case node 1. Figures (a) and (
τα (t) 2,4
2,3 2,4
τα (t) k 4,3
p4,3(t)=τα (t)=1 4,3
4 nodes; see Definition 1). The b) show the choices of the first,
o c
3
ion, i.e., a feasible tour. In other words, the notion of task of an ant changes from “choosing a path from the

Simple Ant Colony Optimisation (SACO)
Example: Transition probability Table (as in the Binary Genetic Algorithm) For node 1:
Next node j
Transition Probability pk1,j(t)
Accumulated Transition Probability
2
τα (t) 1,2
τα (t)+τα (t)+τα (t) 1,2 1,3 1,4
τα (t) 1,2
τα (t)+τα (t)+τα (t) 1,2 1,3 1,4
3
τα (t) 1,3
τα (t)+τα (t)+τα (t) 1,2 1,3 1,4
τα (t)+τα (t) 1,2 1,3
τα (t)+τα (t)+τα (t) 1,2 1,3 1,4
4
τα (t) 1,4
τα (t)+τα (t)+τα (t) 1,2 1,3 1,4
τα (t)+τα (t)+τα (t) 1,2 1,3 1,4
τα (t)+τα (t)+τα (t) = 1 1,2 1,3 1,4
Assume that α = 1, τ1,2 = 0.5, τ1,3 = 0.3 and τ1,4 = 0.2.
Next node j
Transition Probability pk1,j(t)
Accumulated Transition Probability
2
0.5 = 0.5 0.5+0.3+0.2
0.5
3
0.3 = 0.3 0.5+0.3+0.2
0.5 + 0.3 = 0.8
4
0.3 = 0.2 0.5+0.3+0.2
0.5 + 0.3 + 0.2 = 1
Generate a random number, say, r = 0.6. Node 3 is chosen as 0.6 is lying in between 0.5 and 0.8.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 23/53

Simple Ant Colony Optimisation (SACO)
Evaporation of Pheromone Intensity (negative feedback) Pheromone intensity will evaporate.
To force ants to explore more.
To prevent premature convergence.
For each edge (i,j), pheromone intensity is reduced according to τij(t) ← (1−ρ)τij(t)
where ρ ∈ (0, 1) (0 and 1 are not inclusive) is the evaporation rate.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 24/53

Simple Ant Colony Optimisation (SACO)
Update of Pheromone Intensity (positive feedback)
After all ants have constructed their paths from the source to the destination, and all loops are removed, the pheromone intensity on edge (i, j) is adjusted:
nk
ij ij∑ij
τ (t+1)=τ (t)+
where  Q if edge (i,j) occurs in path xk(t)
k=1
∆τk(t)
∆τk(t)= f(xk(t))
ij
0 otherwise xk(t) is the solution of ant k,
f (xk (t)) is the quality of the solution,
Q > 0 is a constant,
nk is the number of ants.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 25/53

Simple Ant Colony Optimisation (SACO)
Example: Source node: 1; Target node: 5 (dij = dji, τij = τji and nk = 2) d23, τ23 d23, τ23
23 23
1515
44
Ant 1: x1(t) = {1,4,3,5} f(x1(t)) = d14 +d34 +d35
Ant 2: x2(t) = {1,4,2,3,5} f(x2(t)) = d14 +d42 +d23 +d35
DrH.K.Lam (KCL)
AntColonyOptimisation
NILAs2020-21
26/53
d12, τ12
d12, τ12
d24, τ24
d24, τ24
d34, τ34
d34, τ34
d14, τ14
d35, τ35
d14, τ14
d35, τ35
d45, τ45
d45, τ45

Simple Ant Colony Optimisation (SACO)
Example: Source node: 1; Target node: 5 (dij = dji, τij = τji and nk = 2) d23, τ23 d23, τ23
23 23
1515
44
Ant 1: x1(t) = {1,4,3,5} Ant 2: x2(t) = {1,4,2,3,5}
f(x1(t)) = d14 +d34 +d35 f(x2(t)) = d14 +d42 +d23 +d35 Pheromone update:
Pheromone evaporation: τij (t) ← (1 − ρ )τij (t) where ρ ∈ (0, 1) Update according to Ants’ solutions
QQ QQ τ14(t+1)=τ14(t)+ f(x1(t)) + f(x2(t)); τ35(t+1)=τ35(t)+ f(x1(t)) + f(x2(t));
􏰄 􏰃􏰂 􏰅 􏰄 􏰃􏰂 􏰅 􏰄 􏰃􏰂 􏰅 􏰄 􏰃􏰂 􏰅
Ant 1 Ant 2 Ant 1 Ant 2
QQQ τ23(t+1)=τ23(t)+ f(x2(t)); τ24(t+1)=τ24(t)+ f(x2(t)); τ34(t+1)=τ34(t)+ f(x1(t));
􏰄 􏰃􏰂 􏰅 􏰄 􏰃􏰂 􏰅 􏰄 􏰃􏰂 􏰅
Ant 2 Ant 2 Ant 1 otherwise τij (t + 1) = τij (t)
DrH.K.Lam (KCL)
AntColonyOptimisation NILAs2020-21
26/53
d12, τ12
d12, τ12
d24, τ24
d24, τ24
d34, τ34
d34, τ34
d14, τ14
d35, τ35
d14, τ14
d35, τ35
d45, τ45
d45, τ45

Simple Ant Colony Optimisation (SACO)
Simple Ant Colony Optimisation Algorithm
Initialise τij (0) to small random values; Let t = 0; Place nk ants on the origin node;
while STOP-CRIT do
foreachant k=1,···,nk do xk(t)=0/;
While destination has not been reached do
Select next node based on translation probability pkij(t);
Add (i, j) to path xk (t); end
Remove all loops from xk(t);
Calculate f (xk (t)); end
for each edge (i, j) of the graph do
Reduce the pheromone, τij (t) ← (1 − ρ )τij (t); end
for each edge (i, j) of the graph do
Update τij(t), i.e., τij(t+1) = τij(t)+
end
t ← t + 1; end
nk
∑ ij
Table 2: Pseudo Code of Simple Ant Colony Optimisation Algorithm.
k=1
∆τk(t);
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 27/53

Simple Ant Colony Optimisation (SACO)
Simple Ant Colony Optimisation Algorithm
Initialise τij (0) to small random values; Let t = 0; Place nk ants on the origin node;
while STOP-CRIT do
for each ant k = 1, ···, nk do xk(t)=0/;
While destination has not been reached do
Select next node based on translation probability pkij(t);
Add (i, j) to path xk (t); end
Remove all loops from xk(t);
Calculate f (xk (t)); end
for each edge (i, j) of the graph do
Reduce the pheromone, τij (t) ← (1 − ρ )τij (t); end
for each edge (i, j) of the graph do
Update τij(t), i.e., τij(t+1) = τij(t)+
end
t ← t + 1; end
no
Initialise parameters, counter
Place nk ants
Find xk(t) and f(xk(t))
Evaporate τij(t)
Update τij(t + 1)
Stopping criteria met? yes
nk
∑ ij
∆τk(t);
k=1
Table 2: Pseudo Code of Simple Ant Colony Optimisation Algorithm.
Return the best xk(t) Figure 1: Flowchart of Simple Ant Colony
Optimisation Algorithm.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 27/53

Simple Ant Colony Optimisation (SACO)
Stopping Criteria:
a maximum number of iterations has been exceeded. an acceptable solution has been found.
all (or most) ants follow the same path.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 28/53

Ant System (AS)
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 29/53

Ant System (AS)
Ant System was developed based on SACO.
Improvements:
Includes heuristic information to transition probability pkij(t).
Includes a tabu list to the set of feasible nodes, N k(t). i
May include only the immediate neighbours of node i.
May include all nodes not yet visited by ant k to prevent loops.
Different update strategies for pheromone intensity. Elitism is implemented.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 30/53

Ant System (AS)
Transition Probability (two methods):
Method 1:
αβ
 τij (t)ηij (t) if j ∈ N k(t)
 τα(t)ηβ(t) i pk (t) = ∑ iu iu
, k = 1, · · · , n
ηij(t): a priori effectiveness of the move from i to j (i.e. the attractiveness, or desirability, of the move).
α > 0, β > 0: predefined constants.
ηij(t) = 1 improves the attractiveness of the edge (i,j). dij (t)
dij(t): cost between edge (i,j).
k
ij
u∈N k(t) i
0 otherwise
τij(t): pheromone intensity/concentration.
DrH.K.Lam (KCL) AntColonyOptimisation
NILAs2020-21
31/53

Ant System (AS)
Transition Probability (two methods):
Method2: k 
pij(t) = u∈N k(t) i
0 otherwise 1,··· ,nk;α ∈ [0,1]
α τij (t)+(1−α )ηij (t)
∑ ατiu(t)+(1−α)ηiu(t) i
if j ∈ N k(t)
,k =
DrH.K.Lam (KCL)
AntColonyOptimisation
NILAs2020-21
32/53

Ant System (AS)
Pheromone evaporation:
τij(t) ← (1−ρ)τij(t)
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 33/53

Ant System (AS)
Update of pheromone intensity/concentration:
nk
τ (t+1) = τ (t)+ ∆τk(t),k = 1,··· ,n
ij ij∑ij k k=1
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 34/53

Ant System (AS)
Update of pheromone intensity/concentration:
nk
τ (t+1) =τ (t)+ ∆τk(t),k = 1,··· ,n
ij ij∑ij k k=1
 Q if edge (i,j) occurs in path xk(t) Ant-cycle AS: ∆τ k (t) = f (xk (t))
ij
Q > 0 is a constant.
ij
ij
dij(t): cost between edge (i,j).
0 otherwise
0 otherwise
 k
Ant-density AS: ∆τk(t) = Q if edge (i,j) occurs in path x (t)
 Q if edge (i,j) occurs in path xk(t) Ant-quantity AS: ∆τk(t) = dij(t)
0 otherwise
DrH.K.Lam (KCL)
AntColonyOptimisation
NILAs2020-21
34/53

Ant System (AS)
Elitist Strategy:
nk
∆τk(t)+n ∆τe(t)
x ̃(t): the current best path (solution) at generation/iteration t.
k=1,··· ,nk
ne: number of elite ants.
 Q if edge (i,j) ∈ x ̃(t) ∆τe(t)= f(x ̃(t))
τ (t+1)=τ (t)+
ij ij∑ijeij
k=1 f(x ̃(t))= min f(xk(t)).
ij
0 otherwise
DrH.K.Lam (KCL)
AntColonyOptimisation
NILAs2020-21
35/53

Ant System (AS)
Elitist Strategy:
τ (t+1)=τ (t)+
ij ij∑ijeij
k=1 f(x ̃(t))= min f(xk(t)).
k=1,··· ,nk
ne: number of elite ants.
 Q if edge (i,j) ∈ x ̃(t) ∆τe(t)= f(x ̃(t))
nk
∆τk(t)+n ∆τe(t)
x ̃(t): the current best path (solution) at generation/iteration t.
ij
d23, τ23
15
4
Ant 1: x1(t) = x ̃(t) = {1,4,3,5} (Assume this is the shortest path)
0 otherwise
2
3
d23, τ23 23
15
4
Ant 2: x2(t) = {1,4,2,3,5} f(x2(t)) = d14 +d42 +d23 +d35
f(x1(t)) = f(x ̃(t)) = d14 +d34 +d35
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 35/53
d12, τ12
d12, τ12
d34, τ34
d34, τ34
d14, τ14
d35, τ35
d14, τ14
d35, τ35
d24, τ24
d24, τ24
d45, τ45
d45, τ45

Ant System (AS)
Ant System Algorithm
Initialise τij(0) to small random values, and α, β, ρ, Q, ηij(t); Let t = 0; Place nk ants on the origin node;
while STOP-CRIT do
foreachant k=1,···,nk do xk(t)=0/;
While destination has not been reached do
Select next node based on translation probability pkij(t);
Add (i, j) to path xk (t); end
Remove all loops from xk(t) if tabu list is not used; Calculate f (xk (t));
end
for each edge (i,j) of the graph do
Reduce the pheromone, τij (t) ← (1 − ρ )τij (t); end
for each edge (i, j) of the graph do
if elitist strategy is not implemented
no
Initialise parameters, counter
Plance nk ants
Find xk(t) and f(xk(t))
Evaporate τij(t)
Update τij(t + 1)
Stopping criteria met? yes
nk
∑ ij
∆τk(t); nk k
τij(t+1) = τij(t)+
τij(t+1) = τij(t)+ ∑ ∆τij(t)+ne∆τij(t);
else
end end
t ← t + 1; end
k=1
k=1
e
Return the best xk(t) Figure 2: Flowchart of Ant System
Algorithm.
Table 3: Pseudo Code of Ant System Algorithm.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 36/53

Examples
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 37/53

Examples
Example 1 (travelling salesman problem (TSP)): Given a set of n cities, TSP requires a salesman to find the shortest route to return to the starting city while each city can be visited only once.
1. Place ants at different nodes.
2. Find the path for each ant.
3. Update pheromone intensity.
4. Go to step 2 until stopping criteria have be satisfied.
(a)
(b)
(c)
DrH.K.Lam (KCL)
AntColonyOptimisation
NILAs2020-21
38/53

Examples
Example 1 (travelling salesman problem (TSP)):
2 3
dij for edge (i,j)
1
i\j
1
2
3
4
5
1
–
10
3
6
18
2
10
–
2
20
9
3
3
2
–
12
7
4
6
20
12
–
15
5
18
9
7
15
–
4
5
DrH.K.Lam (KCL)
AntColonyOptimisation
NILAs2020-21
39/53

Examples
Example 1 (travelling salesman problem (TSP)):
2
dij for edge (i,j)
1
i\j
1
2
3
4
5
1
–
10
3
6
18
2
10
–
2
20
9
3
3
2
–
12
7
4
6
20
12
–
15
5
18
9
7
15
–
3
τij(t) for edge (i,j)
5
i\j
1
2
3
4
5
1
–
0.3
1.2
0.8
0.1
2
0.3
–
1.5
0.1
0.7
3
1.2
1.5
–
0.9
0.5
4
0.8
0.1
0.9
–
0.2
5
0.1
0.7
0.5
0.2
–
DrH.K.Lam (KCL)
4
x1(t) = {1} x2(t) = {2} x3(t) = {3} x4(t) = {4}
x5(t) = {5} AntColonyOptimisation
NILAs2020-21
40/53

Examples
Example 1 (travelling salesman problem (TSP)):
2
dij for edge (i,j)
1
i\j
1
2
3
4
5
1
–
10
3
6
18
2
10
–
2
20
9
3
3
2
–
12
7
4
6
20
12
–
15
5
18
9
7
15
–
3
τij(t) for edge (i,j)
5
i\j
1
2
3
4
5
1
–
0.3
1.2
0.8
0.1
2
0.3
–
1.5
0.1
0.7
3
1.2
1.5
–
0.9
0.5
4
0.8
0.1
0.9
–
0.2
5
0.1
0.7
0.5
0.2
–
4
x1(t) = {1,3,2,5,4,1}, f(x1(t)) = d13 +d32 +d25 +d54 +d41 x2(t) = {2,1,3,5,4,2}, f(x2(t)) = d21 +d13 +d35 +d54 +d42 x3(t) = {3,4,2,5,1,3}, f(x3(t)) = d34 +d42 +d25 +d51 +d13 x4(t) = {4,2,5,1,3,4}, f(x4(t)) = d42 +d25 +d51 +d13 +d34
x5(t) = {5,4,1,2,3,5}, f(x5(t)) = d54 +d41 +d12 +d23 +d35 AntColonyOptimisation
= 35 = 55 = 62 = 62
= 40
DrH.K.Lam (KCL)
NILAs2020-21
45/53

Examples
Example 1 (travelling salesman problem (TSP)):
Evaporation of Pheromone Intensity (negative feedback)
τij(t) ← (1−ρ)τij(t)
e.g., ρ = 0.2, τ54(t) = (1−0.2)τ54(t) = 0.8×0.2 = 0.16
Update of Pheromone Intensity (positive feedback)
nk  Q if edge (i,j) occurs in path xk(t)
τ54(t+1)=0.16+ 1 + 1 + 1 =0.2318 35 55 40
AS: e.g., edge (5, 4), Ant-quantity AS, elitism is implemented, Q = 1, ne = 1, τ54(t+1)=0.16+ 1 + 1 + 1 +1× 1 =0.3886
151515 35
SACO:τij(t+1)=τij(t)+ ∆τk(t), ∆τk(t)= f(xk(t))
∑ ij ij k=1
0 otherwise ∆τk(t)+ne∆τe(t)
AS: τij(t+1) = τij(t)+
SACO: e.g., edge (5, 4), nk = 5 (only ants 1, 2, 5 passed through), Q = 1,
nk
∑ ij ij
k=1
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 46/53

Ant Colony System (ACS)
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 47/53

Ant Colony System (ACS)
Ant Colony System was developed based on AS. Improvements:
Different transition rule, pkij(t).
Candidate lists are used to favour specific nodes.
Different pheromone update rule, τij(t). Local and global pheromone update rules. Local update rule: pheromone evaporation.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 48/53

Ant Colony System (ACS)
Transition Probability: The k-th ant moving from node i to node j is according to
arg max {τiu(t)ηβ(t)}ifr≤r0 u∈N k(t) iu
j= i (1) J otherwise
r ∈ [0, 1]: a random number.
r0 ∈ [0, 1]: user-specified parameter; used to balance exploration and exploitation.
N k(t): a set of valid nodes to be visited by the k-th ant sitting at node i. i
J ∈ N k(t) is a node randomly selected according to the probability: i
β
 τiJ (t)ηiJ (t) k
 τiu(t)ηβ (t) if J ∈ Ni (t) k ∑iu
,k = 1,··· ,nk.
piJ(t) = u∈N k(t) i
0 otherwise
r ≤ r0: the algorithm exploits by favouring the best edge. r > r0: the algorithm explores.
DrH.K.Lam (KCL) AntColonyOptimisation
NILAs2020-21
49/53

Ant Colony System (ACS)
Example:
Current node: i = 1 Ant 4, i.e., k = 4
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 50/53

Ant Colony System (ACS)
Example:
Current node: i = 1
Ant 4, i.e., k = 4
A set of valid nodes for ant 4: N14(t) = {2,3,7}
argmax{τ1,2(t)ηβ (t),τ1,3(t)ηβ (t),τ1,7(t)ηβ (t)}ifr≤r0 For ant 4: j = 1,2 1,3 1,7
J otherwise
Assume r0 = 0.2, r = 0.1.
Assume ηβ (t) = ηβ (t) = ηβ (t); τ1,2(t) = 0.22, τ1,3(t) = 0.33, τ1,7(t) = 0.44,
1,2 1,3 which node is chosen?
1,7
 τ1J(t)ηβ (t)
 1J
For ant 4: p4 (t) = τ (t)ηβ (t)+τ (t)ηβ (t)+τ (t)ηβ (t) , J ∈ N 4(t) = {2,3,7}
1J 1,2 1,2 1,3 1,3 1,7 1,7 1 0 otherwise
Probability of choosing nodes 2, 3, 7 for ant 4 (sitting at node 1 currently) are p412(t), p413(t) and p417(t), respectively.
Probability is 0 for choosing nodes other than nodes 2, 3, 7.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 50/53

Ant Colony System (ACS)
Local and Global Update Rules:
Local update rule: Pheromone concentrations are updated for
all edges (evaporation).
τij(t) ← (1 − ρL)τij(t) + ρLτ0
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 51/53

Ant Colony System (ACS)
Local and Global Update Rules:
Local update rule: Pheromone concentrations are updated for
all edges (evaporation).
τij(t) ← (1 − ρL)τij(t) + ρLτ0
ρL ∈ (0, 1) (0 and 1 are not inclusive): a user-specified parameter. τ0 > 0: a small constant specified by user.
Why 0 and 1 are not allowed in ρL? Why τ0 is not allowed to be 0?
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 51/53

Ant Colony System (ACS)
Local and Global Update Rules:
Global update rule: Reinforcement of pheromone concentrations is allowed on the edges of the best path.
τij(t + 1) = (1 − ρG)τij(t) + ρG∆τij(t)
 1 if (i,j) ∈ x+(t) ∆τij(t) = f (x+(t)) .
0 otherwise
ρG ∈ (0, 1) (0 and 1 are not inclusive, why?): a user-specified
parameter.
x+(t): the best solution(s) giving the shortest path(s).
iteration-best strategy: x+(t) represents the best path found during the current generation/iteration t, denoted as x ̃(t).
global-best strategy: x+(t) represents the best path found from the first iteration to the current generation/iteration t of the algorithm, denoted as xˆ(t).
f (x+(t)) denotes the cost(s) of the best solution(s).
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 52/53

Ant Colony System (ACS)
Ant Colony System Algorithm
Initialise τij(0) to small random values, and β, ρL, ρG, r0, τ0, ηij(t); Let t = 0;
Place nk ants on the origin node, initialize the best solution: x+ (t) = {}, f (x+ (t)) = 0 while STOP-CRIT do
foreachant k=1,···,nk do xk(t)=0/;
While destination has not been reached do Select next node based on equation (1); Add (i, j) to path xk (t);
end
Remove all loops from xk (t) if tabu list is not used;
Calculate f (xk (t)); end
for each edge (i, j) of the graph do
Apply local update rule: τij (t) ← (1 − ρL )τij (t) + ρL τ0 ; end
Update the global best solution xˆ(t) and its cost f (xˆ(t)); for each edge (i,j) ∈ x+(t) do
Update global update rule: τij (t + 1) = (1 − ρG )τij (t) + ρG ∆τij (t); end
t ← t + 1; end
Table 4: Pseudo Code of Ant Colony System Algorithm.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 53/53

Ant Colony System (ACS)
Ant Colony System Algorithm
Initialise τij(0) to small random values, and β, ρL, ρG, r0, τ0, ηij(t); Let t = 0;
Place nk ants on the origin node, initialize the best solution: x+ (t) = {}, f (x+ (t)) = 0 while STOP-CRIT do
foreachant k=1,···,nk do xk(t)=0/;
While destination has not been reached do Select next node based on equation (1); Add (i, j) to path xk (t);
end
Remove all loops from xk (t) if tabu list is not used;
Calculate f (xk (t));
end no for each edge (i, j) of the graph do
Initialise parameters, counter
Plance nk ants
Find xk(t) and f(xk(t))
Update τij(t) locally
+ Update the best solution, x (t)
Update τij(t + 1) globally
Stopping criteria met? yes
Return xˆ(t)
Figure 3: Flowchart of Ant Colony System
Algorithm.
end
Apply local update rule: τij (t) ← (1 − ρL )τij (t) + ρL τ0 ;
Update the global best solution xˆ(t) and its cost f (xˆ(t)); for each edge (i,j) ∈ x+(t) do
Update global update rule: τij (t + 1) = (1 − ρG )τij (t) + ρG ∆τij (t); end
t ← t + 1; end
Table 4: Pseudo Code of Ant Colony System Algorithm.
DrH.K.Lam (KCL) AntColonyOptimisation NILAs2020-21 53/53

Related Posts