The Ant Colony Optimisation (ACO) algorithm is a heuristic method of finding “good” solutions to optimization problems.
Introduction to ACO
This algorithm is based on the simple stochastic model that Deneubourg and colleagues [1] proposed as a description of the dynamics of an ant colony crossing two parallel bridges of different lengths. These dynamics were first observed in the double bridge experiment conducted on the Argentine Ant [2].
Just like in algorithms we have seen before, such as Genetic Algorithms or DFO, we assume that the problems we want to tackle are of the nature Π = (S,f,Ω), where:
- S: set of solutions
- f : objective (or fitness) function
- Ω: set of constraints
- S′ ⊆ S: set of possible solutions (with respect to Ω)
And the task is to find globally optimal feasible solution ( s∗ )
Contrarily to previously examined agent-based algorithms though, ACO revolves around indirect communication where interaction happens with the environment rather than agent-to-agent.
In particular, the algorithm uses ants as a source of inspiration by keeping the following ant-behaviours into account:
- Ants communicate by using pheromones
- By laying trails of pheromone, other ants have a sense of direction
- Each ant individually lays pheromone trails as they travel from the food source to the nest and the other way around
- Pheromone evaporates over time
- The more ants travel across any one path, the more this path will attract even more ants
In particular, the algorithm states that: when a valid solution is created, pheromone is laid on the path. By path here we mean a sequence of “nodes” or “features values” that are “proposed” to solve the problem. In other words, when an agent-subprogram “finishes” building a solution, a pheromone-indicating index associated with such sequence of nodes is increased. Of course, for the optimisation to make sense, the amount of pheromones should depend on the quality of the solution.
In pseudo-code:
While (ind_attempt == max_attempts || solution == target) constructAntSolutions() # Ants build solutions and evaluate them with a fitness function updatePheromone() # Apply the two opposing mechanisms: deposit and evaporate pheromones DaemonActions() # Possible local optimisation and ant-elitism mechanisms end While
Thought Problem Case-Study
In this thought case-study, there are 13 people and 10 tasks to be performed. Each task must be performed by one person, A to M. The table below shows how well each person performs each task.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
A | 34 | 31 | 20 | 27 | 24 | 24 | 18 | 33 | 35 | 19 |
B | 14 | 14 | 22 | 34 | 26 | 19 | 22 | 29 | 22 | 19 |
C | 22 | 16 | 21 | 27 | 35 | 25 | 30 | 22 | 23 | 23 |
D | 17 | 21 | 24 | 16 | 31 | 22 | 20 | 27 | 26 | 17 |
E | 17 | 29 | 22 | 31 | 18 | 19 | 26 | 24 | 25 | 14 |
F | 26 | 29 | 37 | 34 | 37 | 20 | 21 | 25 | 27 | 27 |
G | 30 | 28 | 37 | 28 | 29 | 23 | 19 | 33 | 30 | 21 |
H | 28 | 21 | 30 | 24 | 35 | 20 | 24 | 24 | 32 | 24 |
I | 19 | 18 | 19 | 28 | 28 | 27 | 26 | 32 | 23 | 22 |
J | 30 | 22 | 29 | 19 | 30 | 29 | 29 | 21 | 20 | 18 |
K | 29 | 25 | 35 | 29 | 27 | 18 | 30 | 28 | 19 | 23 |
L | 15 | 19 | 19 | 33 | 22 | 24 | 25 | 31 | 33 | 21 |
M | 27 | 32 | 27 | 29 | 29 | 21 | 19 | 25 | 20 | 27 |
We want to build an algorithm that can find the person-job assignment that produces the best score.
Now, utilising linear programming or just pen, paper and a calculator, we can easily work out that the best possible result for this problem is 323. This website here proposed a way to tackle the problem with GA.
Can we work out a way to use ACO instead?
Of course we can! For a start, it is useful to visualise the above data as a network of paths going from the task 1 assignment to the task 10 assignment. One of these possible paths for instance would start with task 1 being given to person A and finish with task 10 being given to person L.
One thing we know for sure is that once a person is assigned to a task, that person cannot perform any other task. Therefore, say, person I cannot tackle both tasks 4 and 5, just like person A and person G cannot both tackle task 8 just because they are both the best at it.
By looking at this mathematically, we can quickly realise that there are 13 possible “openings stations” or nodes for each path, then 12 possible alternative “bridges” at the second step, then 11 alternatives for step three, and so forth. Since there are 10 tasks to assign, or 10 steps on each path, we can see that there are 13*12*11…*4, or 13! – 3! or 6,227,020,794 possible different paths in this problem.
By this point, it may become clear why the website we linked to before stated that “in practice, this problem should be solved using linear programming!” : 6 billion possibilities is not that big of a number for a computer, although it is a pretty big number, but most of all, this problem can be represented by a matrix. In particular we can say that the form of the problems is:
Where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients, A is a (known) matrix of coefficients, and is the matrix transpose. The expression to be maximized or minimized is called the objective function (cTx in this case). The inequalities Ax ≤ b and x ≥ 0 are the constraints which specify a convex polytope over which the objective function is to be optimized.
Due to the convex shape of the multidimensional region of feasible solutions (with any maxima which must equal to the global maxima), we could apply something like gradient descent or any other linear algorithm to solve this problem.
Let’s pretend, however, that we were not allowed to use linear programming, but that we had to come up with assignment proposals a-priori and then check their efficacy.
Building it
A review of Natural Computing – Goldsmiths University Course 2017
With this blog post, I am concluding the series “Natural Computing Blog”, where I’ve been writing about Nature-inspired algorithms and sharing related tutorials.
The blog series itself was mainly a consequence of the programming discoveries I made through the Natural Computing course held by Mohammad Majid al-Rifaie at Goldsmiths University of London.
The best thing I’ve learned through this curse has not really been one particular algorithm or programming strategy. Instead, what I thank Mohammad for (other than the Pandoro he got me and my fellow students for our last lab session) is a new way of looking at solving optimisation problems.
Before taking this course lasted 4 months, I was familiar with evolution-inspired optimisers such as Genetic Algorithms. I was also familiar with the biology-inspired Machine Learning algorithm known as Neural Networks, but I had never realised how many more Nature-inspired algorithms there could be – and how many more are still to be invented. Taking this course has definitely helped me realise how much we can learn from nature when it comes to engineer programmatic solutions to real-life problems. It is therefore an area of computer science research that I would strongly recommend anyone reading this post to explore.
Was there anything else I would have liked the course to cover, but that was not included? Hard to say. Considering the very short time available, I think the course balanced pretty well the presenting of learning materials and thought-provoking programming challenges. Perhaps it would have been interesting to see and program together more real-life applications where the algorithms presented had produced results that were better or substantially different from simpler, “hard-coded”, non-stochastic solutions. I appreciate though that time was limited and that to present and understand all the algorithms was hardly compatible with developing lab exercise into a “state-of-the art” level.
One thing that I think would work though is some group work during the labs. Small groups of 3/4 people could be given tasks that each person could “specialise” in whilst the whole group in the end comes up with a more powerful program than what an individual could do on its own – Swarm Spirit after all 😉
Reference
1) Deneubourg et al., 1990
2) Goss et al., 1989