How the Ant Colony Optimization algorithm works
Summary
TLDRThis video delves into the mathematical models behind ant colony optimization, focusing on how ants find the shortest path to food. It explains two key concepts: pheromone deposition and evaporation. The video introduces a matrix to represent pheromone levels on a graph and discusses methods for depositing pheromones based on path quality. It also covers the decision-making process ants use to select paths, influenced by pheromone levels and path costs. The speaker provides a detailed numerical example to illustrate these concepts, highlighting the interplay between pheromone levels, path quality, and the probability of choosing a particular path.
Takeaways
- 🐜 The video discusses mathematical models for ant colony optimization (ACO), focusing on how ants find the shortest path from a source to food.
- 📐 It introduces two main concepts: pheromone deposition and vaporization, which are crucial for simulating the ants' behavior on a graph.
- 🔢 A mathematical model is presented to represent pheromone levels on a graph, where the amount of pheromone deposited by an ant is inversely proportional to the path length.
- 🌟 Pheromone levels can be adjusted based on the quality of the path found, with higher quality paths receiving more pheromone.
- 🌀 The concept of evaporation is included in the model, where a certain percentage of pheromone evaporates over time to simulate real-world conditions.
- 📉 The video provides a numerical example to demonstrate how pheromone levels are calculated and updated on a graph, including the effects of evaporation.
- 📈 A decision-making process is discussed, where ants use pheromone levels and path quality to choose the most promising path.
- 🎯 The probability of choosing a path is calculated using a formula that considers both pheromone levels and path quality, with parameters to adjust their relative importance.
- 🔄 The video explains how to use the calculated probabilities to select paths using a roulette wheel selection method, which is part of the ACO algorithm.
- 💻 The presenter mentions that these mathematical models will be implemented in code for the ACO algorithm, indicating practical application in computer simulations.
Q & A
What are the two main concepts discussed in the video regarding ant colony optimization?
-The two main concepts discussed are the mathematical modeling of pheromone deposition and the simulation of pheromone evaporation.
How is pheromone deposition mathematically modeled in the context of ant colony optimization?
-Pheromone deposition is modeled using the equation Delta Tau(i, j, k) = 1 / L(k) if an ant k travels on the edge connecting node i to node j, otherwise it's 0. L(k) represents the length of the path found by ant k.
What does the variable 'LK' represent in the mathematical model?
-In the mathematical model, 'LK' represents the length of the path found by the ant k.
How is pheromone evaporation simulated in the mathematical model?
-Pheromone evaporation is simulated by including a term (1 - Rho) * Tau(i, j) in the equation, where Rho is a constant that defines the evaporation rate.
What is the significance of the constant 'Rho' in the evaporation equation?
-The constant 'Rho' signifies the evaporation rate. When Rho is 0, there is no evaporation, and when it is 1, all pheromones evaporate before new ones can be deposited.
How does the quality of a path influence pheromone deposition according to the video?
-The quality of a path influences pheromone deposition because ants deposit more pheromones on shorter paths or paths leading to high-quality food sources.
What is the role of the 'eta' term in the decision-making process of ant colony optimization?
-The 'eta' term represents the quality of the edge (i, j) on the graph. It is used in the probability calculation to decide which path to choose, with the formula considering both pheromone levels and edge quality.
How is the probability of choosing an edge calculated in the ant colony optimization algorithm?
-The probability of choosing an edge (i, j) is calculated using the formula: (Tau(i, j)^alpha * ETA(i, j)^beta) / sum(Tau(i, k)^alpha * ETA(i, k)^beta for all edges k from node i), where alpha and beta are parameters that control the relative importance of pheromone levels and edge quality.
What technique is used to select an edge based on the calculated probabilities?
-The roulette wheel selection technique is used to choose an edge based on the calculated probabilities.
Can you explain the concept of a 'roulette wheel' in the context of ant colony optimization?
-In the context of ant colony optimization, the 'roulette wheel' concept involves generating a random number and using the cumulative sum of probabilities to determine which edge to choose, simulating a probabilistic decision-making process.
What is the importance of the parameters alpha and beta in the probability calculation?
-The parameters alpha and beta allow for the adjustment of the influence of pheromone levels (Tau) and edge quality (ETA) on the decision-making process. They help in fine-tuning the algorithm to emphasize either pheromone trails or path quality.
Outlines
🐜 Introduction to Mathematical Models of Ant Colony Optimization
The paragraph introduces the mathematical models used in ant colony optimization (ACO) for finding the shortest path in a graph. It discusses the need to model the deposition of pheromones by ants and the process of pheromone evaporation. The focus is on two main concepts: how to mathematically represent pheromone deposition and how to simulate the evaporation process. The explanation includes the decision-making process of ants when choosing a path, increasing the likelihood of selecting a short path by considering pheromone levels and path quality.
📊 Pheromone Deposition and Evaporation Equations
This section delves into the equations governing pheromone deposition and evaporation. It explains how the amount of pheromone deposited by ants can be represented mathematically, taking into account the quality of the path found. The concept of pheromone evaporation is introduced with an equation that includes a constant, 'Rho', which defines the evaporation rate. The paragraph provides a numerical example to illustrate how pheromone levels are calculated and updated on a graph, emphasizing the impact of evaporation on these levels.
📐 Calculating Pheromone Levels and Choosing Paths
The paragraph explains how to calculate pheromone levels on each edge of a graph and how ants use these levels to choose paths. It introduces a mathematical model that represents pheromone levels and discusses the use of matrices to store and update this information. The process of selecting a path using probabilities based on pheromone levels and edge quality is outlined, with an equation that considers both pheromone levels (Tau) and edge quality (ETA). The role of parameters alpha and beta in decision-making is highlighted, along with a numerical example that demonstrates how probabilities are calculated for different edges.
🎯 Probability Calculation and Path Selection
This section focuses on the calculation of probabilities for choosing a path and how these probabilities guide ants in selecting the next edge to traverse. It provides a detailed numerical example that shows how probabilities are computed based on pheromone levels and edge costs. The example illustrates how ants are more likely to choose paths with higher pheromone levels and lower costs. The paragraph also discusses the impact of varying pheromone levels on these probabilities and how the roulette wheel technique can be used to select a path based on these probabilities.
🔚 Summary and Implementation of ACO
The final paragraph summarizes the key points covered in the video script, which include the mathematical models for simulating pheromones, evaporation, and the use of these values to calculate the probability of choosing a path. It mentions the upcoming implementation of these mathematical equations in code for the ant colony optimization algorithm. The speaker thanks the viewers for watching and teases the next video in the series.
Mindmap
Keywords
💡Ant Colony Optimization (ACO)
💡Pheromone
💡Evaporation
💡Decision Making
💡Graph
💡Famish
💡Path Length
💡Matrix
💡Rho (ρ)
💡Quality of a Path
💡Combinatorial Optimization
Highlights
Introduction to mathematical models for ant colony optimization technique.
Explanation of how to mathematically model the process of finding a short path on a graph.
Discussion on the two main concepts from the previous video: pheromone deposition and vaporization.
How to mathematically model pheromone deposition by ants on the ground.
Simulation of pheromone vaporization based on time, duration, and other factors.
The decision-making process using pheromone and graph models to increase the probability of choosing a short path.
Cosmetics matrix defining the length of each path on the graph.
Introduction of a matrix to represent the amount of pheromone on each edge of the graph.
Different methods for depositing pheromone and how they affect the model.
Mathematical model representing pheromone level on a graph and the role of Delta Tau.
Explanation of how pheromone is deposited based on the quality of the path found by an ant.
The concept of pheromone evaporation and its role in the蚁 colony optimization algorithm.
Numerical example to understand pheromone level and evaporation rate.
Calculation of the length of pathways and how it affects pheromone deposition.
Impact of multiple ants on the pheromone level of an edge.
Introduction to the equation for calculating the probability of choosing an edge.
Role of parameters alpha and beta in the decision-making process.
Numerical example demonstrating the process of calculating the probability of choosing each edge.
How the roulette wheel technique is used to choose a destination based on probabilities.
Summary of the mathematical models used in ant colony optimization for combinatorial optimization problems.
Conclusion and预告 of the next video in the series.
Transcripts
hello everyone and welcome back in the
last video we talked about the process
of finding the shortest path in an ant
colony from an s to food sirs in this
video we're going to be focusing on the
mathematical models developed for this
technique so we'll see how we can
mathematically model the process of
finding a short path on a graph so there
are two things that we have to focus and
there were two main concepts in the last
video the first one was as you can see
here famine so we have famine of course
ant deposit famine on the ground but how
do we mathematically model this that's
the first question that we are going to
answer second one how do we simulate
vaporization right let's say we simulate
the famine right on a graph how do we
then vaporize it based on time based on
duration based on what that's the second
question and finally as you can see over
here we're going to be talking about the
decision making process so we'll see how
we can use you know a famine and a graph
let's say Furman famine values or famine
simulation to make a decision and to
increase the probability of choosing a
short path so these are the thing that
we are going to find out in this video
let's discuss the details of the
mathematical models with the drawn
example we have a cosmetics defining the
length of each path on the left hand
side as you can see now I'm going to
also add another matrix to represent the
famine the amount of famine on each edge
of this graph but this matrix allows us
to store the amount of famine on each
edge of the graph but the question is
how do we add famine to each of those
pathways there are different methods out
there some methods deposit the same
amount of famine recall these of the
paths found by the end for example if an
ant goes this way
they're gonna add
one to each of those edges however there
are also other models that deposit
Furman based on the quality of a path
found by an ant and in fact there are
some species of ants that deposit more
pheromones
if the food source is big or of high
quality so in this lesson I'll show you
how to define the thermal level based on
the quality of the path because it's
obviously more promising for example if
I have an end that goes on this path and
this path is already very good I'm going
to deposit more pheromone to be able to
attract more ants to that path so yeah
that's what we are going to consider and
assume in this slice and in this course
here's the mathematical model used to
represent a pheromone level on a graph
so basically Delta Tau shows the amount
of pheromone that an ant deposit but
remember an ant walks on a graph right
so it goes from one point to the next
and that's exactly what we need those
subscripts right so I and J shows the
edge connecting the node ID to the node
J and what is KK is basically the case
and so Delta Tau I and J and K shows the
amount of pheromone deposited by the
cave and on the I on the edge connecting
I the node I to the node J and as you
can see it's equal to 0 if the ant dozen
go on an edge right so for example if
it's one and two and this unders and go
there the pheromone level should be
equal to zero otherwise it's equal to
one divided by L K so what is LK
basically LK is the length of the path
found by the cave end and why do we have
to divide 1 by L K remember we are
trying to find a shortest path so the
shorter the path the higher pheromone
should be deposited by the end
so this is exactly what is simulated
here or I should say this is exactly
what has been mathematically model here
so 1 divided by K so if I have a path
with 5 edges
you're gonna deposit you know those 5
edges with high famine or high value
here because that's a good path right so
we have multiple ends of course how do
we now calculate the amount of famine on
each edge of course we need to add a
summation so summation of K is equal to
1 to M where m is equal to the total
number of ends Delta Tau I and J K or
super-sorry superscript K so this is
where we don't have any evaporation
right because we keep adding famine over
time if you want to simulate the
evaporation you have to add this part to
your equation so 1 1 is Rho times the
current thermal level plus the new
famine the pole that should be deposited
by all ends now as you can see we've got
a constant here Rho is a constant that
allows you to define the evaporation
rate when Rho is equal to 0 there is no
operation because 1 minus 0 times tau I
and J so gonna add you know the current
the new amount of pheromones to the
current every time when Rho is equal to
1 then that will be 1 minus 1 times tau
that is where they have operation is at
the maximum level Oh everything all the
pheromones evaporates for the next step
before it gets to even get deposited
next time
so people normally use a number between
0 to 1 of course you're gonna choose
small ones and sub-problem big ones for
others it depends on the problem people
normally use evaporation the equation
with the evaporation to be able to
simulate what happens in reality
otherwise if there is no firm one on the
ground you know the end
cannot communicate so let's have a look
at a numerical example to better
understand the idea behind pheromone
level and the evaporation rate so I've
got two hands on the left hand side a
pepper and a green so that is the path
by the purple and that is a path
traveled by the green and the first step
is to calculate the length of those
pathways so l1 is equal to 14 4 plus 5
plus 4 plus 1 so Delta Tau 1 I and J is
equal to 1 divided by 14 the second one
at the second and l2 is equal to 31 so 4
plus 8 plus 4 plus 15 will give you 30 1
and Delta Tau 2 equals 2 1 divided by 31
now how do we add that to our graph
which is called Feynman graph easy look
at these green lines without any pepper
that's where I have to add 1 divided by
31 ok
no pepper color just green one because
the pepper and doesn't walk on these
edges of the graph for by contrast these
sites where we have only pepper color we
have to add 1 divided by 14 which we
calculated already here for the other
two edges this one and this one as you
can see on the cost graph we have both
ants trouble on them right so that's
where I have to add 1/4 14 plus 1
divided by 31 so as you get the idea now
if multiple ants go through on one edge
we're going to consider or calculate the
sum of their pheromones as the farmer
famine level of that edge so I'm using
this equation and remember there is no
evaporation and we're going to calculate
this so that would be zero point zero
seven zero point zero three and these
are a zero point one basically zero
point yeah one there we go so these are
the final famine values for our famine
graph so quick
question for you let's say I've got now
an ant here that's the next time let's
say I have a red ant starting from the
tent which path is more likely to be
taken by that end one Fairmont zero
point seven one zero point three one
zero point one which one has a higher
famine deposited of course this one so
the array the red ant is more likely to
choose this one just like the analogy
that I talked about it before in one of
the videos now let's consider the firm
the firm one I need an initial firm on
level let's say we have an end that walk
around and deposit one on each of the
edges now I'm going to consider a
pheromone they have operation so one one
is basically Rho times tau tau I and J
and we're going to assume that the
problem I mean the Rho is equal to 0.5
that means every time 50% of the current
ephemeral level evaporates so see what
happens now remember these are the
initial value or we caught one so 0.5
times 1 that was the current value plus
1 divided by 14 coming from the peple
and this one again same value the ones
the diagonals 0.5 times 1 plus 1 divided
by 13 and the ones at the top and the
bottom 0.5 times one plus one day what
about 14 plus 1 divided by 31 so these
are the final values that we can
consider for this this this Fairmont
graph so again still if you considered
this note this side is more likely but
as you can see we have more bigan begin
numbers for these ones so again the idea
evaporation removes a little bit of
pheromone every time and deposit again
depending on you know the graphs or the
edges that the ants travel so far this
is how we calculate the pheromone level
for each of dance remember when you want
to implement this this mathematical
model you cannot have graph
you can visualize them of course but you
need a matrix so basically you need a
matrix for your cost you need a matrix
for your pheromones as well so we
eventually these numbers will be updated
to fare more matrix so that's about it
for any combinatorial optimization
problem that we want to solve using the
ant colony optimization algorithm such
pheremones matrices and updating
processes should be considered the next
step is to use the pheromones calculated
in the first step to choose a path as
discussed before and choose a path using
probabilities here's an equation to
simulate this you can see in this is lot
that the probability of choosing the
edge I and J is equal to tau I and J to
the power alpha multiplied by ETA I and
J to the power of beta divided by the
sum of the same equation in the
nominator of course tau is the pheromone
level but what does Ito indicates
basically ETA indicates the quality of
the RJ edge on the graph with the
parameters alpha and beta we can
increase or decrease the impact of tau
or ETA in the process of decision making
the denominator of this equation as the
pheromone and quality of all edges that
can be considered from the node I this
probability is calculated for all the
edges connected to the current node and
is a number in the interval of 0 & 1
if you just want to make a decision
based on the pheromone level then you
can remove Ito from that equation so
it's up to you if you want to consider
the quality of an edge then this part
should be there if not just remove it
and remember we are interested in the
shortest path so ETA I and J is equal to
1 divided by L I and J so that means the
length of an edge or the cost of n H
indicates how good it is in the process
of calculating the probability of
choosing
let's consider another numerical example
to better understand the process of
calculating the probability of choosing
each of the edges on a graph so I've got
two graphs here this one shows the costs
right for each edge and this one shows
the famines remember I'm going to assume
that the alpha and beta and these
equations are all equal to or both equal
to one for the simplicity of course and
normally people assume they are one
unless they want to highlight the impact
of one of them on calculating the
probabilities but to make it simple I
assume that they are both equal to one
so how do we calculate this this
probability so let's say we have a
yellow end who is trying to find one of
these passes or make a decision which
one to pick so probability of choosing
the pond is equal to so here's the pond
here's the tenth is equal to the family
level 1 times 1 divided by the cost
which is 1 so 1 times 1 divided by 1
that's the nominator what about the
denominator basically the denominator is
where we need to calculate the same
equation for all these edges but the
first one is the pond already so the
same as the nominator but this one is
for the tree so look at it 1 times 1
divided by 15 which is its cost and last
one is famine which is 1/2 the car of
course plus 1/4 so that give us 0.75 and
95 let's calculate the probability of
choosing the car the nominator is
different now 1 divided by 1 times 1/4
but the denominator is identical because
you're going to calculate all of them
write the equation for all the edges and
finally this is the probability of
choosing the tree so it's equal to 0.05
this one is equal to 0.18 roughly so
what does that mean that means the ant
is large
to choose the pawn 76% with the
probability of 76 percent five percent
for the 319 percent for the car why we
have very small percentage for the tree
that's obvious because the weight the
connection weight or the path is longer
than the other think about 15 as
compared to 1 and 4 and look at the
probability of choosing the pond
seventy-six percent right and that's a
good indication of it you know the
impact of the pheromone and at the same
time the cost on calculating the
probability of choosing one of the
destinations in this example so see
seventy-six percent this pie chart looks
very good and shows you you know how big
the probability of choosing the pond is
seventy-six percent as compared to 19
and five remember the pheromones level
were identical so the impact where I
similar on each of these probabilities
to show what happens and how and then
gravitates towards you know higher
pheromones in addition to of course the
costs are lower cuz I should say I'm
going to replace this by five let's say
the initial pheromone value for this
edge is equal to five so what will
happen in my equation so I have now 5
times 1 divided by 4 or 5 times 1
divided by 4
this one just in the denominator not
denominator because the pheromone level
when you go from the tenth to the tree
is equal to 1 and finally for that one
so what are the probabilities now there
we go
43% for the pond 3% for the tree and 54%
for the car they calculate the
probability of choosing the car was 90
percent and now it is equal to 54
percent even more than the pond because
the thermal level is 5 times as compared
to the pheromone level of this edge so
this is the idea of this equation and I
hope these examples and these
visualization a numerical example I
should
allow you to get your head around you
know these this mathematical model it's
fair to straightforward but very
fascinating and beautiful from my port
of perspective so that summarize
everything I've got basically both of
the graphs look at the comparison of the
car
in both cases from 19% to 54% so in the
mathematical model of the ACO and
consider both the quality of a path and
also the amount of Fairmont deposited on
you know that path so this is how the
ACO you know to make a decision and
choose one notes of each craft you know
when trying to find the lowest-cost path
or the shortest path in this example
when a graph example a question that you
might be asking now is how do we use
these probabilities to choose one of
those destinations okay
we know that 76% of the times we have to
choose the pond 5% the tree and 90% the
car but how do we mathematically choose
them well the answer is using a
technique called roulette wheel I
covered this completely in my course on
the genetic algorithm if you haven't
enrolled to that course that's fine I
briefly take you through the steps of
using a roulette wheel but if you want
more details if you want to get into the
details and basically implemented I
highly recommend you to have a look at
the lecture in my course on the genetic
algorithm I think it is in the selection
operator of the the genetic algorithm I
believe it is in the selection so
remember we have those probabilities
0.76 0.19 and 0.5 the first step is to
calculate the cumulative sum how do we
calculate the cumulative sum is
basically you're going to add the
current probability to each of the ones
under 2 itself and each of the ones on
the right hand side so 76 plus 19 plus
0.5 is required to basically one
next up we have nineteen plus 0.5 so
that's gonna give us zero point twenty
four and finally last one nothing is on
the right hand side so that's gonna give
us zero point zero five now we don't use
the probability vectors anymore we'll be
using just the cumulative sum to pick
one of them how do we pick one of the
destinations well the answer is by
generating a random number between zero
and one so we generate a random number
in the interval of zero and one if that
random number is between zero point two
to one as you can see in this comparison
then we are gonna choose the pond if it
is between 0.5 to 0.24 we're gonna
choose the car otherwise we if the radio
is numb if the random number not the
radius number what am I saying
if the random number is between 0 to 0.5
then we are gonna choose the tree so
think about the probability of choosing
pond between zero point two two zero
point one if I generate an random number
in that interval between 0 to 1 there
are roughly 75 76% that it goes it lies
in this in this interval right sub
interval so that's how we simulate the
roulette wheel and use it to select one
of the destinations in our graph using
the ant colony optimization and that's
pretty much everything guys for this
video so let's quickly summarize
everything that was a long video so we
started with the mathematical models to
be able to simulate pheromones on a
graph evaporation and we ended up using
those values to calculate the
probability of choosing a destination or
an edge basically on a graph so I'm
going to be using these mathematical
equations in my code later on when we
you know implement the ant colony
optimization that is the end of this
video thanks for watching and I will see
you in the next one
you
تصفح المزيد من مقاطع الفيديو ذات الصلة
Inspiration of Ant Colony Optimization
Learn Ant Colony Optimization Algorithm step-by-step with Example (ACO) ~xRay Pixy 🌿🍰🐜🐜🐜🌞
How to Migrate Your Ants Into Your New Habitat Nest - AntsCanada Tutorial #6
The Science of Pheromones: How men can enhance natural attraction markers.
Projeto e Análise de Algoritmos - Aula 13 - Problema do caminho mais curto
Projeto e Análise de Algoritmos - Aula 14 - Classes de problemas: Problemas P, NP e NP-completos
5.0 / 5 (0 votes)