This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
We have described above how ants act in the real world. We can formalise it
a little as follows
|
The above diagram represents the map that the ants have to traverse.
At each time unit, t, each ant moves a distance, d, of 1.
All ants are assumed to move at the same time. At the end of each time step
the ants lay down a pheromone trail of intensity 1 on the edge (route) they
have just travelled along.
At t=0 there is no pheromone on any edges of the graph (we can represent
this map as a graph).
Assume that sixteen ants are moving from E to A and another sixteen ants are
moving from A to E.
At t=1 there will be sixteen ants at B and sixteen ants at D. At this
point they have a 0.5 probability as to which way they will turn. We assume
that half go one way and half go the other way.
At t=2 there will be eight ants at D (who have travelled from B, via C) and eight ants at B (who have traveled from D, via C). There will be sixteen ants at H (eight from D and eight from B). The intensities on the edges will be as follows.
ED = 16, AB = 16, BH = 8, HD = 8, BC = 16 and CD = 16
If we now introduce another 32 ants into the system (16 from each direction) more ants are likely to follow the BCD rather than BHD as the pheromone trail is more intense on the BCD route.
But, as we are interested in exploring the search space, rather than simply plotting a route (in this case we get a form of randomised greedy search), we need to allow the ants to explore paths and follow the best paths with some probability in proportion to the intensity of the pheromone trail. That is, we do not want them simply to follow the route with the highest amount of pheromone on it, else our search will quickly settle on a sub-optimal (and probably very sub-optimal) solution.
Therefore, the probability of an ant following a certain route is a function,
not only of the pheromone intensity but also a function of what the ant can
see (which Dorigo calls visibility). Therefore, if an ant is at D (in the above
graph) and the pheromone trail is more intense on the route to H then the ant
would follow that route if we only considered the pheromone intensity. However,
by looking at the distances to the possible routes it would see that the shorter
route is to C. It would take this into account when deciding (proabalisticically)
which route to choose.
This idea is explored more fully in the discussions on the Traveling Salesman Problem. This is discussed in the following pages.
We also need to stop the pheromone trail building up without bound, because
that will ultimately lead to all the ants following the same route. Therefore,
we need implement some form of "evaporation" that reduces the pheromone
intensity at each time unit. This idea is also discussed in the following pages.
| Previous Page | Index Page | Next Page |
Last Updated : 26/01/2002