How the Ant Colony Optimization algorithm works

Summary

This 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

00:00

🐜 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.

05:03

📊 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.

10:03

📐 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.

15:04

🎯 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.

20:06

🔚 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.

Keywords

💡Ant Colony Optimization (ACO)

Ant Colony Optimization (ACO) is a metaheuristic algorithm used to solve combinatorial optimization problems. It is inspired by the foraging behavior of ants, which deposit pheromones to communicate with each other. In the video, ACO is used to find the shortest path in a graph, simulating how ants find the shortest path from their nest to food sources. The script discusses mathematical models for simulating pheromone trails and evaporation, which are key components of the ACO algorithm.

💡Pheromone

Pheromone, in the context of ACO, refers to the chemical substances that ants deposit on their paths. These substances are used by other ants to determine the most efficient route to a food source. In the video script, pheromone is used to mathematically model the process of finding a short path on a graph, where the amount of pheromone deposited on each edge of the graph is represented by a matrix.

💡Evaporation

Evaporation in ACO refers to the process where pheromone trails gradually disappear over time, simulating the natural evaporation of pheromones in ant colonies. This concept is crucial for preventing the algorithm from becoming stuck in local optima. The script mentions how evaporation can be mathematically modeled using a constant (Rho) to define the evaporation rate, which is a key factor in the pheromone update rule.

💡Decision Making

Decision making in ACO involves using the pheromone levels to choose the next path or node. The script discusses how ants use the pheromone levels and the quality of the path to make decisions, increasing the probability of choosing a short path. This decision-making process is essential for the algorithm's ability to find optimal solutions.

💡Graph

A graph in the video represents a network of nodes (or vertices) connected by edges, which is a common way to model problems in combinatorial optimization. The script describes how to mathematically model the process of finding a short path on a graph using pheromone matrices and how ants use these graphs to navigate.

💡Famish

Famish, as used in the script, seems to be a typographical error and likely refers to 'pheromone'. It is used to describe the substance deposited by ants, which is central to the ACO algorithm. The script discusses how to mathematically model the deposition of famish (pheromone) on the ground and how it is represented in the algorithm.

💡Path Length

Path length is a measure of the distance or cost associated with moving from one node to another in a graph. In the video script, the length of each path is used to determine the amount of pheromone deposited by ants, with shorter paths receiving more pheromone, thus encouraging other ants to follow the same path.

💡Matrix

A matrix is a mathematical structure used to represent data in a tabular form. In the context of the video, matrices are used to represent the pheromone levels and path lengths on a graph. The script mentions how these matrices are updated as ants traverse the graph, which is essential for the functioning of the ACO algorithm.

💡Rho (ρ)

Rho (ρ) is a constant used in the ACO algorithm to control the evaporation rate of pheromones. A higher value of Rho means a higher evaporation rate, which can prevent the algorithm from converging too quickly on a suboptimal solution. The script explains how Rho is used in the mathematical model to simulate the evaporation process.

💡Quality of a Path

Quality of a path refers to the desirability of a particular route based on certain criteria, such as its length or the amount of pheromone deposited. In the video script, the quality of a path is considered when modeling the pheromone deposition process, with higher quality paths receiving more pheromone.

💡Combinatorial Optimization

Combinatorial Optimization is a type of mathematical optimization problem where the goal is to find the best solution from a finite set of possible solutions. The video script discusses how ACO is applied to solve such problems, specifically focusing on finding the shortest path in a graph.

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