Collective Intelligence in Social Insects
By ai-depot | January 20, 2003
Ant-based Algorithms
Ant-based Algorithms
Deneubourg showed that self organisation enables ants and other social insects to succeed in complex activities using simple algorithms and minimal individual intelligence. It was therefore a natural step to apply antlike approaches to solving antlike problems, specifically the very general AI problem of search. Since ants� everyday activities tend to involve discovering shortest paths between food sources and nests, they map well to problems representable as graphs, such as the Travelling Salesman Problem.
An excellent tutorial on ant search algorithms is available on this very web site[5], so I will not go into too much detail here. Instead we�ll look at Ant System, one of the earliest ant-based algorithms, and at the work of Ruud Schoonderwoerd, one of the first �real world� applications of ants.
The Travelling Salesman Problem
The Travelling Salesman Problem (TSP) is a popular �toy problem� in the AI community since it is at once simple to understand and very difficult (NP-hard) to solve. A salesman needs to complete a tour of a certain number of cities using the most efficient path possible. The salesman can travel from any city to any other city, but must visit each city once and only once. It doesn�t sound like a difficult problem until you consider the sheer number of possible solutions, even for a small fifteen city problem. Marco Dorigo and his associates Gianni Di Caro and Luca Gambardella[6] realised that ants� inherent ability to discover shortest paths could be put to use on the TSP and, it turned out, with some success.
The first TSP solution they developed was called Ant System and works like this: ants first make a number of random tours starting from a random city, depositing pheromone as they go. At each city an ant picks its next destination using a combination of probability and the amount of pheromone present on that route to inform its decision. Every ant must visit every city once, as per the criteria of the TSP. After a tour is completed, an ant deposits a certain amount of pheromone on each edge of the graph, depending on how far the ant travelled during its tour � shorter tours lead to more pheromone being deposited. A certain amount of pheromone will also decay, causing older solutions to fade away and be replaced by new ones.
After this process has run for some time, the pheromone present on the edges of the graph will tend to influence any ant traversing the graph towards an optimal solution. Ant System and subsequent versions of the algorithm such as Ant Colony Optimisation do not always find optimal solutions, but are effective in finding good solutions in a reasonable number of iterations.
An interesting thing to note about the design of these algorithms is that although they are inspired by the behaviour of ants, they implement features unused by mother nature. For example, while pheromone decay is present in natural ant pheromones, it is generally much faster in ant algorithms since it aids the dynamic nature of the algorithms in finding new solutions. Real ants however would not benefit if all their trails disappeared overnight! But some aspects of the algorithms are very rigorously reproduced from nature. The variables controlling trail-laying in some algorithms have derived from studies, such as Deneubourg�s Argentine ant research which yielded very precise probabilities controlling the ants� chances of choosing trails based on pheromone strength.
Ants, Phones and Pheromones
The foraging metaphor has been put to work successfully in solving the problem of telecommunications routing. Ruud Schoonderwoerd of Hewlett-Packard labs[7] collaborated with a group of scientists to create the world’s first ant-based routing system. As anyone who has used the Internet will know, communications networks are characteristically unpredictable. Sudden interest in a particular web site or a local crisis will lead to surges of network activity which must somehow be routed efficiently, minimising both delays and congestion. The network must therefore dynamically route calls/requests through quieter sections of the network.
Congestion in a particular section of the network can be seen as analogous to depletion of a food source near an ant colony, causing the ants to search for new routes, dynamically updating the virtual pheromone trail between nodes. In the system developed by Schoonderwoerd et al., antlike agents are sent randomly between nodes from time to time, updating each node’s routing table as they go with information regarding how long the journey from their origin took, and which nodes they have used on the way. The routing table contains a list of the node’s immediate neighbours, and probabilities associated with using that neighbour as the next step on the journey to each target node on the network. The fastest ants will have a positive effect on the probability scores of the nodes they have used, while slow ants will have a negative effect.
A more recent algorithm for Internet routing designed by Dorigo and Di Caro[8] has, in simulation, outperformed all other routing methods, including the current standard routing protocol of the Internet, Open Shortest Path First.
Tags: none
Category: essay |
