Swarm Intelligence

Glen Upton

CS Senior Seminar

10/01/02

Despite the current technology, and rapid advances in every field, there are still some problems that continue to elude scientists. Complex NP complete problems, vehicle routing, network maintenance, the traveling salesperson, and computing the shortest route between two points are just a couple of examples of these types of problems. Learning algorithms have been developed in conjunction with artificial intelligence systems such as neural networks to try and solve some of these problems, but imperfections and inefficiencies in both the hardware and software have prevent reliable results. Genetic algorithms also made an attempt at these problems, and had some success. The algorithms were considered too complex to re-implement, realizing the random nature of the mutation operations (Tarasewich p.63). Genetic algorithms were also not reliable enough to be considered the best source for solving these complex problems. Scientists, now, are looking into the world of insects in search of new methods and approaches of attacking complex problems.

If you have ever been to a picnic, you have undoubtedly encountered ants. It is not the individual ant that draws your attention, but the collective behavior of the line of ants, as they walk off with your food that is impressive. Ants are considered a social insect, a group that contains other insects such as bees, and some caterpillars. It is their social structure and how ants make use of it that peaks the scientists’ interests. An individual ant is relatively unintelligent, but when they are part of a colony, “complex group behavior emerges from the interactions of individuals who exhibit simple behaviors by themselves (Tarasewich p.63).” This phenomenon is indicative of all swarm intelligences such as bees, birds, fish, and the economy, which is another example of swarm intelligence, where something is created that is greater than the sum of its parts. One of the complex behaviors that naturally emerges from individual any behavior is the ability to determine the shortest path between two points.

The ants at the picnic must leave their nest in search of food, but the colony doesn’t know where any food is currently located. The individual ants make their decisions on which direction to go just on chance, they have just as much probability of going one direction as another (Fedoriw p. 2). As soon as an ant finds food it will take some back to the nest. As ants move they leave behind a chemical substance called pheromone, which other ants can smell and identify that an ant has been there before (Dorigo p. 2).

Figure 1: Ants converging on the shortest path between a food source and the nest

(Taken from Tarasewich, P “Swarm Intelligence”, Communications of the ACM, August 2002

The ants that find the closest food source will be able to leave more amounts of pheromone since their travel time is less then the other ants. When other ants finally return to the nest, they will decide where to go based upon the amount of pheromone that they smell. “The stronger the pheromone level, the more likely an ant is to take that route (Fedoriw p.2).” As more and more ants take the shorter path, the pheromone level increases until every ant is taking the same shorter path (see Figure 1).

The natural behavior of these ants and be programmed into an ant algorithm, which we can use to find the shortest path within graphs. Since most problems can be reduced to a graph, being able to find the shortest path through a graph often provides the simplest and fastest solution to the problem. Each ant can be represented by an agent in the program that has only has limited abilities, such as sensing and dispensing pheromone, and a memory so that any agent can trace its steps backwards through the graph in order to determine the length of the tour. When an agent senses another agents pheromone it will receive positive feedback in decided to choose the popular path. The positive feedback triggers autocatalysis, meaning that a small amount of positive feedback results in more positive feedback and so on and so forth (Dorigo p.2).

There are a couple of conditions that must be met in order for the agents the successfully navigate any kind of graph. The pheromone must have an evaporation period because it allows for the agents to converge in the first place. If the pheromone did not evaporate, then agents will always be choosing between multiple paths that seem equally as popular. As the agents converge on a path, they must become less and less influenced by other paths, especially if there are no longer any agents that are traversing them. There is a second subtle problem of the agents converging on a sub-optimal path before the shortest path is discovered. In the example of the picnic ants, it is possible that there is a food source closer to the nest, but it had not been found before the colony converged on a different food source. This problem is remedied by the fact that the agent’s/ant’s decision is not fixed, it always has a chance of not choosing the popular route, and thus exploring for alternate routes (Dorigo 3). The construction of alternate paths is of great importance when it comes to using ant algorithms for problems other than shortest route.

The TSP (Traveling Salesperson) problem is probably the most famous NP complete problem. The traveling salesperson needs to visit cities in order to make sales, but to save on travel costs, the traveling salesperson can only visit each city once, this is also known as a Hamiltonian circuit. The traveling salesperson also wants to save time, so what needs to be found is the shortest path that visits each city only once, the optimal Hamiltonian circuit (Feodriw p.4). This problem can be represented easily in a graph, where nodes are cities, and edges are the roads or paths between those cities. Since this problem can be represented as a graph we can use the ant agents to solve it.

The agents for the TSP problem would function slightly differently from the shortest path problem. Again the agents will need to be able to sense and dispense pheromone, and have a memory to be able to back step through the graph. Each agent would start at a random starting city and would traverse the graph in a Hamiltonian circuit. The agent does not constantly leave pheromones however, because the agent will not know the value of the tour it’s traversing until it’s finished, and it doesn’t want to mislead other agents. Once an agent finishes a tour, it will back step through the tour counting the number of steps or the lengths of the edges depending on how the size of a tour is calculated. Then once the size of the tour is determined, pheromone is added to the tour, the shorter the tour, the higher the pheromone level. This use of variable pheromone level to prevent premature convergence is know as the Max-Min Ant System (MMAS) (Stutzle, p. 2).

As the algorithm runs, the agents will converge on a tour that is suspected of the shortest length. There is no guarantee that the first tour the agents converge on will be the shortest, however, so having alternate paths being stored is crucial. Agents still have the chance to explore other tours while the collective converges, and it may be that the “stray” agent finds a shorter tour, and so adjusts the pheromone levels for that path so that it will attract more and more agents. The algorithm is very robust for it can function with a few “rouge” agents in operation, in fact, the “rouge” agents are the one who usually find an alternate optimal path. The algorithm needs plenty of computing time in order to converge on the optimal tour, which is true for all algorithms that try and solve the TSP problem. The ant algorithm approach, however, does not require as much computing power as other techniques, so it will use fewer resources, and still solve faster than other algorithms. After examining Figure 2, it becomes clear that the use of agents produces faster and more optimal solutions to problems.

Figure 2: Overall performance of ant approach compared to other techniques for several problems.

There are, of course, plenty of questions still to be explored about the ant approach that may affect the utility of this algorithm. Some questions that arise are, how powerful should the pheromone be? “How does the level of pheromone correspond to the probability that an ant would take a particular path? How often would a new ant leave the nest in search of the goal? How many ants would be needed before a particular route became a ‘popular’ route? Would and initial level of pheromone on a particular path effect the ant’s behavior? (Fedoriw p.3)” These variables are usually different in each implementation of an ant algorithm, and so there has yet to be a standardized optimal setting for each of those variables.

Usually when an algorithm can be used to solve complex problems such as the TSP problem, it can also be used in some practical situations besides in the world of traveling salespeople. Ant agents have numerous applications in the real world, such as industry, design, vehicle routing, networks, and gaming to name only a few. Vehicle routing is similar to the TSP problem, where each customer must be services by an employee who needs to travel to each customer. In order to minimize cost and time we need the same optimal Hamiltonian circuit as in the TSP problem. A practical example of this is news paper delivery, where the vans need a route where they can visit each customer and deliver one paper each, and then at the end of their route end up back at the printing press.

The use of ant algorithms also shows potential in the field of networking in solving the problem of routing. Packets of data traveling over a network can be represented in a graph with nodes of the graph representing nodes of the network, and the edges of the graph representing the physically connections of the network (Dorigo p. 12). Although this problem is similar to the TSP problem there are important differences. One being that instead of each ant trying to traverse the entire network, each ant is given a starting node in the network and a destination node. Also, the edges cannot have a static value for their cost, because edges may have additional traffic at any given time. The S-AntNet algorithm helps resolve these problems.

“In S-AntNet each ant searches for a minimal cost path between a pair of nodes on the network (Dorigo p.12).” Ants are released using the same “link queues” as the data, so as to simulate actually traffic. Since each ant has a source and a destination, and S-AntNet guarantees that it will find the shortest path between the source and destination and given enough ants with enough variance in sources and destinations, eventually the ants will have found the shortest paths from every source to every destination, thus giving data packets a map to follow through the network to achieve optimal efficiency. Consider however, if the ants actually carried the data, like food from your picnic. If this were the case, then instead of building the map, the ants would become agents of the data packets. Moreover, if a node on the network becomes unavailable, or traffic is particularly heavy, the natural of the ant algorithm allows for alternate paths to be stored while the optimal one is being developed, so the network does not have to be re-mapped from the start (Bieszczad p. 5). The ability to transform a problem into a graph is a powerful tool in developing ant algorithm based solutions, but it is not the only way to solve them.

We have discussed how ants can naturally find the shortest distance between two points. So far we have only used this property in the realms of graphs, but solving for the shortest path also is key is solving for the optimal path in a multipath maze. A multipath maze can be thought of as a specific type of graph, where the destination is always the same, but the sources can be numerous. These multipath mazes can be applied toward assembly line design, where the goal is always s fully assembled product, and so the ants can optimize the assembly, by decided what can happen in parallel and what needs to be handled sequentially (Dorigo p. 15). Mulipath mazes can also be applied toward gaming and the artificial intelligence that appears in gaming. The ant agents could determine the shortest path to the enemy base, or determine the shortest path through an off-road racecourse. Of course, they could be used to solve actually multipath mazes as well. There is, however, an application of swarm intelligence and that has yet to be explored.

The economy is an example of swarm intelligence that most researchers either forget or neglect to consider. The economy falls directly into our definition of swarm intelligence wherein it demonstrates complex behavior that arises from simple individual interactions (Tarasewich p.63). There is no one individual who can control the economy, for that matter there are no group that can consistently control the economy, for if there were, then why would there ever be a depression or recession if the economy were merely acting on the will of the individuals; no one wants a depression. It is possible to argue that individuals or group do exert control over the economy, people such as Enron, or Martha Stewart for example. In fact, it was the reaction of the population (colony) to those individual interactions that caused the complex behavior of the economy slowing down. If it were possible to simulate an economy within a system using ant algorithms, then it might be possible to control or at least predict the ebb and flow of this complex behavior, which we all help to create. Swarm intelligence, as with most technologies, is still in its infancy, and so a project such as simulating the economy is still far beyond the its capability.

Swarm intelligence offers researchers and scientists a tool for solving very difficult NP class problems. Swarm intelligence’s ability to solve these problems leads to various practical real world applications such as, traffic routing, networking, games, industry, robotics, and perhaps even simulating the global economy. Although the technology is relatively new, already scientists are realizing its potential. The use of ant algorithms within computing systems has helped to solidify swarm intelligence’s place in the computing world. Already researchers are observing other social animals, such as bees and schools of fish in order to discover how swarm behavior of those animals might be utilized in future applications and algorithms.

Bibliography

1. A. Bieszczad, B. Paguerk, and T. White, “Mobile Agents for Network Management”, Proc IEEE Communications Surveys, vol 1, no. 1, Fourth Quarter 1998, pp. 1-9

2. E. Bonabeau, M. Dorigo, and G. Théraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, 1999.

3. M. Dorigo and G. Di Caro, "Ant colony optimization: a new meta-heuristic", Proc. 1999 Congress on Evolutionary Computation, July 6-9, 1999, pp. 1470-1477.

4. M. Dorigo, G. Di Caro, and L. M. Gambardella, "Ant algorithms for discrete optimization", Artificial Life, vol. 5. no. 2, pp. 137-172, 1999.

5. G. Fedoriw, C. Fehr, M. Good, S. Keown, “Application of Swarm Intelligence Solving the Shortest Route Problem”, University of Calgary

6. S. Johnson, Emergence: the connected lives of ants, brains, cities, and software, Scribner, New York, 2001.

7. J. Kennedy, R. Eberhart, and Y. Shi, Swarm intelligence, Morgan Kaufmann Publishers, San Francisco 2001.

8. T. Stützle and H. Hoos, "The MAX-MIN ant system and local search for the traveling salesman problem", Proc. IEEE International Conference on Evolutionary Computation, April 13-16 1997, pp. 309-314.

9. P. Tarasewich and P. McMullen, "Swarm intelligence power in numbers", Communications of the ACM, vol. 45, issue 8, pp. 62-67, August 2000.