Natural Computing Blog

Ants and Reflections on Nature-Inspired Artificial Intelligence

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 {\displaystyle (\cdot )^{\mathrm {T} }} (\cdot )^{\mathrm {T} } 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.

The way I would choose to go about solving the algorithm is by using ant-agents and by letting them find an optimal path from trial and error. For instance we may start with a population 50 ants, which will be “placed” at the imaginary beginning of our path.
Each ant-agent would then need to start its journey by selecting an “edge”, that is a path to the second step (or node) of its path. The probability (p) of an ant(k) choosing any given edge(xy) on the path is given by the formula:
Where Tau(of alpha) is the “trail level” or the amount of “pheromone” present on the edge, and Eta(of beta) is the “attractiveness” (optional) of a given edge as obtained by some a-priori knowledge of the problem.

Building it

First of all we need a “map” or a network, which can simply be a database of “node” objects, each with a pointer to another object. Nodes represent persons in this problem. So, for instance, we would have node A that stores references to nodes B to M, then we will have node B, which will store references to node A, C, etc, then we would have node C and so forth. We will also need an initial node “START” which links to all the nodes and will be the starting point for all the ants.
Each node will also store a list of indices of attractiveness for the nodes it can connect to.  This indices will be proportional to the score that would result from associating the following task with that node. In other words, say that we are at step 5 and that we are in node B (task 5 is being proposed to be associated with person B), then the next task will be task 6, therefore node A will have a higher index than node E because person A is better at task 6 than node E.
Each node will also store another list of indices, which symbolises the amount of pheromone present on the edge between the current node and the connected nodes associated with such indices.  Initially these values will be randomised for each node.
An agent is another type of object that will visit 10 nodes in a random order whilst storing the sequence of visited nodes. The starting and point and the number of steps are fixed. Furthermore, an agent cannot visit a node twice.
Let’s imagine what could happen to any of our initial ants. Ant “K” is at the start of its journey and needs to select its first node. It will compute the attractiveness of each node based on how the person they represent would score at task 1. It will then check the amount of pheromone associated to each node. After doing so, the ant will sum all of these values and come up with a normalisation factor. Then, the ant would compute the probability of choosing each node by adding the attractiveness and pheromone values in each node and then dividing them by the normalisation factor. Finally, the ant would randomly choose which node to go into and add this node to its “memory of visited nodes”. Going forward, before calculating pheromone and attractiveness, the ant would only consider non-visited nodes, then repeat the above process ten times, so that a sequence of 10 unique nodes/persons will be obtained at the end.
Once an ant has completed a path, the fitness of such path will be calculated by adding together all the scores for each match task/person as indicated by the path-sequence. The ant will also increase the pheromone index in each node that was associated with the subsequently visited node in the path just finished.
The algorithm will wait for all the ants to finish and then decrease all the pheromone indices in all the nodes by a fixed amount to simulate the pheromone evaporation over time. It will then “restart” the ants over and over and let good paths emerge due to “more” pheromone accumulating there over time.

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

Leave a Reply

Your e-mail address will not be published. Required fields are marked *