In the previous chapter we looked at a number of examples of distributed systems. Among others, we saw that ants are capable of finding the shortest path to a food source via a process of self-organization, mediated through pheromone trails (chapter 3. section 3.2). Through such stigmergic interactions1, i.e. interactions mediated by modifications of the environment (depositing pheromones), they solve complex optimization problems. In addition to solving these problems, their behavior is robust, i.e. the "solution" is immune to noise. The ants also remain adaptive, i.e. if the environmental situation changes, for example a path is no longer, or a shortcut becomes available, they find different solutions. These characteristics have lead to the development of artificial systems, which were inspired by the observation of colonies of social insects in nature. These systems consist of several agents (e.g. artificial ants) with simple basic capabilities, which lead to a highly complex structure of the whole system as resulting emergent behavior.

Ant Based Control

The remarkable properties of ants have encouraged researchers at Hewlett-Packard and British Telecom to try and apply these concepts to the problem of load balancing and message routing in telecommunications networks. Their network model is populated by agents (artificial ants) that make use of the trail-laying principles, i.e. they deposit pheromone on each node they pass during their trip through the network. The routing of calls is then decided based on the distribution of pheromone. Load balancing is essentially the construction of phone-call routing schemes that distribute the changing load over the system and minimize lost calls. Lost calls are those that never reach their destination (the caller gets only a beep signal).

Schoonderwoerd, Holland, Bruten, and Rothkrantz (1997) developed the following basic idea. Electronic ants are continuously generated at any node in the network and are assigned random destination nodes. On their way to the respective destination node ants move around in the network and leave their (electronic) "pheromone trails". They do this by updating the so-called pheromone tables in the routers (routing tables). Every node has a pheromone table for every possible destination in the network and the destinations' neighbor nodes. Thus a node with k neighbors in a network with n nodes has a pheromone table with (n-1) rows, where each row corresponds to a destination node, and has k entries. The pheromone table contains probabilities (representing the strength of pheromone), which get regularly updated as soon as an ant reaches a node (see figure 1 below). Updating the probabilities thus represents pheromone laying.

As ants at every step have good recent information about their trip from the source node to their current node, the entries in the pheromone tables are updated referring to the source node. Thus ants directly influence those ants traveling towards their source node and only indirectly those traveling in their same direction.

The probabilities p in the pheromone table are updated according to the following formulas: The entry corresponding to the node from which the ant just came is increased

In order to distinguish the length of the different routes taken ants get older with every time step while moving along the network or getting delayed at congested nodes. The older an ant gets the smaller the amount of pheromone it is able to lay and thus the influence it has on updating the pheromone tables. The value dp used to change the entries in the pheromone tables is reduced in accordance with the age of an ant.

Ants knowing their source and destination node choose their path according to the probabilities stated in the pheromone tables. Further details of how this is done, are given in the paper. The pheromone tables are then used to route an incoming phone call. Calls operate independently of the ants. The route of an incoming call is decided according probabilities looked up in the pheromone table. The node with the largest probability will be the next node on its way to its destination node. Calls influence the loads on the nodes and thus delay, and thereby influence the age of the ants visiting the same node. Thus there is a complex interaction between the electronic ants and the calls that are routed over the network.

The pheromone mechanism of the natural ants had to be changed so that there are different pheromones in the routing tables for each destination node. When trying to realize ideas from nature for technology, it is normal that nature's solutions cannot be applied directly, but need to be appropriately modified. The authors also compare the ant-based control method to other methods (shortest path routing, and a software agent based method). Although there are some tradeoffs, ant-based control scores well in these comparisons. One problem with ant-based control is that whenever there is a significant change in the network, it takes some time before the ants "discover" and mark the new routes with pheromones.

Ant Algorithms for Optimization Problems

Based on the way ant colonies function new algorithms have been developed called ant algorithms or ant colony optimization algorithms. These algorithms are especially suited to find solutions to difficult discrete optimization problems. A colony of artificial ants cooperates to find good solutions, which are an emergent property of the ants' cooperative interaction. Based on their similarities with ant colonies in nature ant algorithms are adaptive and robust and can be applied to different versions of the same problem as well as to different optimization problems.

The main traits of artificial ants are taken from their natural model. Such main traits are: (1) artificial ants exist in colonies of cooperating individuals, (2) they communicate indirectly by depositing (artificial) pheromone (stigmergic communication), (3) they use a sequence of local moves to find the shortest path from a starting, to a destination point (i.e. the optimal solution to a given problem), and (4) they apply a stochastic decision policy using local information only (i.e. they do not look ahead) to find such best solution. If necessary in order to solve a particular optimization problem artificial ants have been enriched with some additional capabilities not present in their natural counterparts.

In ant systems (ant algorithms) an ant colony of a finite size searches collectively for a good solution to a given optimization problem. Each ant can already on its own find a solution or at least part of a solution to the optimization problem but only together they find the optimal solution. Since the optimal solution can only be found through the global cooperation of all the ants of a colony, it is an emergent result of such cooperation. In searching for a solution the ants do not communicate directly but indirectly by adding pheromone to the environment. Based on the specific problem an ant is given a starting state and moves through a sequence of neighboring states trying to find the shortest path. It moves based on a stochastic local search policy directed by its internal state (private information),the pheromone-trails and local information encoded in the environment (together public information). Such private and public information is also used by an ant to decide when to deposit pheromone. In most applications the amount of pheromone deposited is proportional to the quality of a move an ant has made. Thus the more pheromone the better the solution found. After an ant has found a solution it dies, i.e. it is deleted from the system.

Applications of such ant algorithms can be divided into two classes: ant algorithms for static, and ant algorithms for dynamic combinatorial optimization problems. In static problems the key-points of the problem are defined at the beginning and do not change while the problem is being solved. In dynamic problems the problem changes as a function of itself, thus the algorithms used to solve such problems must be able to adapt "online" to the changes.

Examples of applications to the first class of problems, i.e. to static combinatorial optimization problems are:

1. Traveling Salesman Problem where a salesman must find the shortest route by which to visit a given number of cities, each city exactly once;

2. Quadratic Assignment Problem, the problem of assigning n facilities to n locations so that the costs of the assignment are minimized;

3. Job-Shop Scheduling Problem where - given a set of machines and a set of jobs - operations must be assigned to time intervals in such a way that no two jobs are processed at the same time on the same machine and the maximum of the completion times of all operations is minimized;

4. Vehicle Routing Problem, the object is to find minimum cost vehicle routes such that (a) every customer is visited exactly once by exactly one vehicle, (b) for every vehicle the total demand does not exceed the vehicle capacity, (c) the total tour length of each vehicle does not exceed a given limit, and (d) every vehicle starts and ends its tour at the same position (the depot);

5. Shortest Common Supersequence Problem, where - given a set of strings over an alphabet - a string of minimal length that is a supersequence of each string of the given set has to be found (a supersequence S of string A can be obtained from A by inserting zero or more characters in A);

6. Graph-Coloring Problem which is the problem of finding a coloring of a graph so that the number of colors used is minimal;

7. Sequential Ordering Problem, which consists of finding a minimum weight Hamiltonian path2 on a directed graph with weights on the arcs and on the nodes, subject to precedent constraints among the nodes.

The main focus of applications to the second class of problems, to dynamic combinatorial optimization problems is on communication networks in particular on routing problems. Routing answers the question how to direct data traffic (e.g. phone calls) through a network, i.e. which node to choose next by a data packet entering the network. Routing mainly consists of building, using and updating routing-tables. Implementations for communication networks can be divided in two classes

The main focus of applications to the second class of problems, to dynamic combinatorial optimization problems is on communication networks in particular on routing problems. Routing answers the question how to direct data traffic (e.g. phone calls) through a network, i.e. which node to choose next by a data packet entering the network. Routing mainly consists of building, using and updating routing-tables. Implementations for communication networks can be divided in two classes: (a) Connection-Oriented Network Routing, where all packets of the same session follow the same path selected by a preliminary setup phase (see the Ant Base Control algorithm as explained in section 4.1 above), and (b) Connectionless Network Routing where data packets of the same session can follow different paths (Internet-type networks).

Conclusion

Ant Algorithms are good examples of the application of swarm intelligence. They show that algorithms inspired by the observation of, and applying basic principles of particular natural phenomena lead to good solutions to diverse optimization tasks. One main characteristic of these algorithms is the fact that good solutions are an emergent property of the cooperative interaction of simple agents. Another characteristic is the indirect stygmergetic communication (indirect communication mediated by changes in the environment) used by the agents.

Beside the examples shown above there are a variety of current research efforts using swarm-intelligence approaches. Insect swarms are - among others - studied to devise different techniques for controlling groups of robots which have to cooperatively transport heavy goods, to find more efficient methods to assign jobs in factories, to solve manufacturing problems, to find information over the World Wide Web and in other large networks and to analyze financial data. In addition thereto there still is a large number of potential applications to be explored.

Bibliography

1. Dorigo, M., Maniezzo, V., Colorni, A., Ant System: Optimization by a Colony of Cooperating Agents, in: IEEE Transactions on Systems, Man and Cybernetics- Part B: Cybernetic, Vol. 26, No. 1, February 1996, 29-41.

2. Dorigo, M., Di Caro, G., Gambarella, L.M., Ant Algorithms for Discrete Optimization, in: Artificial Life 5, 137-172, 1999 Massachusetts Institute of Technology.

3. Schoonderwoerd, R., Holland, O.E.; Bruten, J.L., Rothkrantz, L.J.M., Ant-Based Load Balancing in Telecommunications Networks, in: Adaptive Behavior Vol. 5, No. 2, 169-207, 1997, Massachusetts Institute of Technology.