Hi Everyone.
How often do we use graph algorithms in your daily coding? Not so often if you are a software developer as I am, most of the tasks are business logic, framework integration, or bug fixing. However, it possible to face with kind of task where graph algo is perfectly suitable certainly it is finding a short path.
Interesting? I will demonstrate a simple approach to implement the Ant colony optimization algorithm or just AOC. Hope you will find something useful for yourself in this article.
AOC has many variations some of them you can read in wiki. I'm gonna describe two of them Ant System (AS) and Ant Colony System (ACS) these approaches allow us to understand the common ideas of AOC and if you want to implement another variant or invent your own I think it is not getting trouble.
First of all, there is the application where you can generate a random Kn graph and test these algos. Kn means complete graph. In other words, every vertex connects to all and self.
The main idea of AOS is the simulation of real ant behavior as all articles said. But actually, we write code based on math functions and heuristic methods and there are no ants. What we really use is the idea of pheromones that ants leave on the way and this is the major point.
Unfortunately, most ACO articles describe the algorithm only from the mathematical side, if there is code it is not applicable it is just a pseudocode. I'll try to explain each math function and each algorithm step with the working code it should help you to figure out and apply in no time because our time is cost.
Overall view of the algorithm:
fill pheromones by initial values
while iterations {
choice start vertex
while all vertices {
calculate the transition probability for each available passes
choice the next vertex based on the transition probability
}
update pheromones based on the passed path
}
choice path with the shortest length
Fill pheromones by initial values
This is the first step. The initial pheromone value typically depends on the distance.
\[\tau_{ij}\ = {1 \over L_{ij}} \]
\(\tau_{ij}\) is pheromone on edge ij
\(L_{ij}\) is distance between i-j
Pheromones conveniently represented as a two-dimensional array.
readonly float[,] pheromones;
void FillInitialPheromones() {
for (int i = 0; i < edges.Length; i++) {
var edge = edges[i];
var Lij = edge.Value;
pheromones[edge.From.Index, edge.To.Index] = (1 / Lij);
}
}
Choice start vertex
There are many ways to do that it depends on your requirement. If there is not a requirement to use fixed vertex for starting so use random it allows the algorithm to analyze paths even better.
Calculate the transition probability for each available passes
After taking the start vertex we have to decide what will be the next vertex. For that we calculate the transition probability factor for each potential vertices. This is the formula:
\[p_{ij}=\frac{\tau_{ij}^\alpha \cdot \eta_{ij}^\beta}{\sum_{c_{ij}\in N(s^p)}{\tau_{ij}^\alpha \cdot \eta_{ij}^\beta}}, \forall{c_{ij} \in N(s^p)}\ ,\]
\(\alpha \beta\) are coefficients for fine configuration of the algorithm, will see below
\(\eta_{ij}^\beta\) is move attractiveness, typically \(1 \over L_{ij}\)
\(\tau_{ij}\) - pheromone
Step 1. Calculate the sum for each available vertices from the current one by this formula.
\[\sum_{c_{ij}\in N(s^p)}{\tau_{ij}^\alpha \cdot \eta_{ij}^\beta}\]
float SumiN = 0f;
var neighbors = graph.GetNeighbors(currentVertex);
foreach (var edgeij in neighbors) {
if (!processedVertices.Contains(edgeij.To)) {
var Lij = edgeij.Value;
var nij = 1f / Lij;
var rij = pheromones[edgeij.From.Index, edgeij.To.Index];
SumiN += MathF.Pow(rij, settings.Alfa) * MathF.Pow(nij, settings.Beta);
}
}
Step 2. Calculate the transition probability for each available vertices using that sum.
foreach (var edgeij in neighbors) {
if (!processedVertices.Contains(edgeij.To)) {
var Lij = edgeij.Value;
var nij = 1f / Lij;
var rij = pheromones[edgeij.From.Index, edgeij.To.Index];
var Pij = (MathF.Pow(rij, settings.Alfa) * MathF.Pow(nij, settings.Beta)) / SumiN;
}
}
Choice the next vertex based on the transition probability
In this part, we have different approaches depending on variations of ACO.
Ant System
In Ant System choosing the next vertex is simple we just take vertex with the max Pij.
Ant Colony System
In Ant Colony System decision is more complex. It based on random choice but with the priority of better Pij values for this reason transition probability calculation is changed a bit to get value in the range 0-100%.
var PiN = new List<Tuple<float, GraphEdge>>();
var checkSumm = 0f;
foreach (var edgeij in neighbors) {
if (!processedVertices.Contains(edgeij.To)) {
...
var Pij = ((MathF.Pow(rij, settings.Alfa) * MathF.Pow(nij, settings.Beta)) / SumiN) * 100f;
checkSumm += Pij;
PiN.Add(Tuple.Create(Pij, edgeij));
}
}
if (MathF.Abs(checkSumm - 100f) > 0.01f) {
throw new Exception("Sum of all changes must be equal 100%");
}
As you can see, all probabilities in the sum equal 100% and this is important if in your case it is not equal it means there is a mistake in calculating. The percentage directly depends on the transition probability value if it big we have more chances to hit in it.
Also, we should do a local pheromone update it means to update the pheromone of the vertex that was chosen as next.
\[\tau_{ij} = (1-\rho) \cdot\tau_{ij}+\rho \cdot\tau_0\ ,\]
\(\rho \in (0,1)\) - evaporation factor
\(\tau_{ij}\) - current pheromone value of edge
\(\tau_0\) - initial pheromone value in our case \(1 \over L_{ij}\)
//generate random value 0 - 100%
var hit = random.Next(0, 100);
var prev = 0f;
foreach (var chance in PiN) {
//search result which hits in range
if (prev <= hit && hit < (prev + chance.Item1)) {
bestEdgeToMove = chance.Item2;
var i = bestEdgeToMove.From.Index;
var j = bestEdgeToMove.To.Index;
var Lij = bestEdgeToMove.Value;
var r0 = 1f / Lij;
var rij = pheromones[i, j];
//the local pheromone update.
pheromones[i, j] = (1f - p) * rij + p * r0
break;
}
prev += chance.Item1;
}
Update pheromones based on the passed path
After traversing from all vertices we have complete path of one ant. Updating pheromones depends on variations of ACO.
Ant System
For Ant System case we update pheromones after each found path by the following formula.\[\tau_{ij} \leftarrow (1-\rho)\cdot \tau_{ij} + \sum_{k=1}^m \Delta \tau_{ij}^k~\ ,\]
\(\Delta \tau_{ij}^k\) - new pheromone value based on current path, \(\frac{1}{L_k}\)
\(L_k\) - length of the current path
Important, Updating pheromone must be for all edges even if current path doesn't traverse from it. In this case \(\Delta \tau_{ij}^k\) is set to 0
var dr = 1 / currentPathLength;
for (int i = 0; i < edges.Length; i++) {
var edge = edges[i];
var key = new Edge(edge.From.Index, edge.To.Index);
//new pheromones rate
var drij = currentPathEdges.Contains(key) ?
dr //if edge was used, apply new pheromones value
: 0f;//only evaporation will effect on pheromone
var rij = pheromones[key.IndexFrom, key.IndexTo];
//update pheromones
pheromones[key.IndexFrom, key.IndexTo] =
(1f - p) * rij // evaporation
+ drij; // increase value of pheromones based on found path
}
Ant Colony System
In Ant Colony System we update pheromones only if the current path is the best path in comparison with previous it means it is the shortest. The formula is a bit different as well.
\[\tau_{ij} \leftarrow (1-\rho) \cdot\tau_{ij} + \rho \cdot\Delta \tau_{ij}^{best}\]
\(\Delta \tau_{ij}^{best}\) - new pheromone value based on the best path, \(\frac{1}{L_{best}}\)
The same update process as in Ant System. We need to update pheromone of each edge.
if (minPathLength > currentPathLength) {
for (int i = 0; i < edges.Length; i++) {
var edge = edges[i];
var key = new Edge(edge.From.Index, edge.To.Index);
var drij = currentPathEdges.Contains(key) ? dr : 0f;
var rij = pheromones[key.IndexFrom, key.IndexTo];
pheromones[key.IndexFrom, key.IndexTo] = (1f - p) * rij + p * drij;
}
}
Choice path with the shortest length
There is no any special approach to do that, the shortest path is the best path.
I think this is the all that I wanted to write and the only I have left are some notes and source code.
Tips
- \(\alpha \beta\) - affect on which values will have priority in choosing next vertex if \(\alpha \) is increasing then priority on pheromone if \( \beta\) then priority on edge length.
- Algorithm finds a better path with using random start vertex by less iterations than if using fixed vertex as eccentricity center/border by the same iteration count, you can check this in app.
- Iteration count depends on vertex count, for better result need to figure out how many iteration you need. It is a battle of speed and precision.
- if set evaporation factor to the small value we get very fast decreasing of pheromones, it is not good for finding the best path but still, we have the right to do this but the algorithm will calculate SiN = 0 and many potential paths didn't pass through all vertices.
- If you look at the code of algorithm you find many duplications and it is not a bad style it was coded by purpose to keep readability of each variation of ACO algorithms.
- I use some magnification factor for pheromones because of evaporation the pheromone value rolls down to very small float value. It directly depends on the iteration count that is why I use iteration count as the magnification factor. It was done only for the readability of debugging.
Thanks for reading
