BIOLOGICAL INSPIRATION FOR COMPUTING 279
finding the best solution to the Traveling Salesman Problem and its relatives, and instead look for
algorithms that find an acceptable solution in an acceptable amount of time. Many such algorithms have
been developed over the years, and the Ant Colony Optimization algorithm has proved to rank among
the best—especially after Dorigo and his colleagues introduced several refinements during the 1990s to
improve its scaling behavior.^98
Variations of the algorithm have also been developed for practical applications such as vehicle
routing, scheduling, routing of traffic through a data network, or the design of connections between
components on a microchip, and the scheduling of special orders in a factory.^99 The technique is
particularly useful in such cases because it allows for very rapid rerouting in the face of unexpected
disruptions in the network. Among the successful commercial applications are plant scheduling for the
consumer products giant Unilever; truck routing for the Italian oil company Pina Petroli; supply chain
optimization and control for the French industrial gas supplier Air Liquide; and network routing for
British Telecom, France Telecom, and MCI.^100
8.3.4.2 Other Ant Algorithms
Ant algorithms are based on two essential principles: (1) self-organization, in which global behavior
arises from a myriad of low-level interactions, and (2) stigmergy, in which the individuals interact with
one another indirectly using the environment as an intermediary.^101 That is, one individual changes its
surroundings (e.g., by laying a pheromone trail), and other individuals then react to those changes at a
later time. As researchers have looked to other ant colony behaviors for inspiration, moreover, those
same two principles turn up again and again.^102 For example:
- Sorting behavior. Certain species of ants apparently have an instinct to keep their surroundings
clean; if dead ants are scattered through the nest at random, the workers will immediately begin moving
all the corpses into neat little piles (albeit piles in random locations). These ants likewise seem to have an
instinct for keeping the brood chambers well organized; if workers are presented with a random jumble
of ants-to-be, they will quickly see to it that the eggs and micropupae are in the center, while the larger
and more developed pupae and larvae are toward the outside where they have more room. Simulated
ants can produce much the same results by following a simple local rule: pick up any item that is
isolated—that is, any item that has no others like it in the neighborhood—and drop it whenever many
of those items are encountered. Picking things up and then dropping them modifies the environment,
while the constant shifting causes the piles and/or broods to self-organize fairly rapidly.
(^98) The algorithm and its refinements are discussed at length in Chapter 2 of E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm
Intelligence: From Natural to Artificial Systems, Oxford University Press, New York, 1999.
(^99) Many of their key papers are available for downloading at M. Dorigo, “Ant Colony Optimization,” 2003, available at http://
iridia.ulb.ac.be/~mdorigo/ACO/about.html.
(^100) E. Bonabeau, “Swarm Intelligence,” presented at the O’Reilly Emerging Technology Conference, 2003, April 22-25, 2003,
Santa Clara, CA, available at http://conferences.oreillynet.com/presentations/et2003/Bonabeau_eric.ppt.
(^101) E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press,
New York, 1999.
(^102) Among the most notable of these investigators have been entomologist Guy Theraulaz of the French National Center for
Scientific Research (CNRS) and telecommunications engineer Eric Bonabeau, formally of France Telecom. Bonabeau, in particu-
lar, has been among the most active in the promotion and commercialization of ant algorithms, first as head of European
operations for the Santa Fe-based BiosGroup and since 2000 as head of his own company, Icosystem, Inc., of Cambridge,
Massachusetts. Details of the various ant behaviors under study, and the algorithms drawn from them, can be found in E.
Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, New York,
1999; E. Bonabeau and G. Theraulez, “Swarm Smarts,” Scientific American 282(3):72-79, 2000; and E. Bonabeau, “Swarm Intelli-
gence,” presented at the O’Reilly Emerging Technology Conference, 2003, available at http://conferences.oreillynet.com/
presentations/et2003/Bonabeau_eric.ppt.