A classic problem in computational mathematics is known as the Traveling Salesman Problem (TSP). Suppose a traveling salesman wishes to visit a predetermined N number of cities. Each city is represented as a vertex of a given graph and each two vertices are joined by an edge. The traveling salesman must find the most efficient, cost-limiting itinerary such that he visits each city once and only once before returning to the same starting point. The distance and travel costs are symmetric, i.e. the distance from city X to city Y is the same as the distance from city Y to city X, and equally the travel costs from city X to city Y are the same as the travel costs from city Y to city X. This problem of finding a circuit that visits each vertex only once but at the same time minimizes cost, distance, and time is known as the Problem of the Traveling Salesman. In essence, it seeks to find the Hamiltonian cycle that most minimises the sum of the value of its edges.

The problem might sound simple but mathematicians and computer scientists have worked hard for decades for a solution but no general method for one has, as of yet, been attained. Indeed, there are (N – 1)! possible routes in an N-vertex problem. The number of possible solutions to explore is too large to for an optimal solution to be achieved. One might wonder why a solution would even be entailed. But, besides a better understanding of combinatorial optimisation, the practical significance of a solution for such a problem rests in a wide variety of potential applications, ranging from time-effective bus routes and cost-effective ways of customer delivery to more optimal design engineering practices and more efficient assembly line processes.

Studies of animal behavior, in particular ant colony structure, might possibly yield some insights as to how such a problem might be tackled. When foraging for foods, ants lay down pheromone trails in order to trace the shortest possible routes for food (Deneubourg et al., 1990). The pheromone trail is deposited in varying concentrations and other ants make use of this by following the trail that contains the higher concentrations. These traces lay out coordination activities and social interactions that occur amidst the ant colony. Indeed, the longer the trail, the more that the pheromone evaporates. As such, ants would be predisposed to follow the shortest pathways possible and an ant that finds an even shorter route would optimise ant traffic even further. The route that maximises adaptive fitness, as mediated by environmental heterogeneity, is selected for.

A study of the elaborate nest building behaviour of termites can perhaps demonstrate this (Grasse, 1959). In particular, termites use soil pellets which they inject with a termite-attracting pheromone and which they then deposit on the ground. The termites work individually and independently but as a result of local stimuli, elaborate structures emerge. If enough pellets, deposited at random, converge and collect in a specific place, the termites respond to the resulting local increase in pheromone concentration by constructing a pillar. In a feedback mechanism, the accumulation of material on top of the pellet perpetuates the depositing activity due to the pheromone emitted from the pellets. Eventually, arches are constructed between the pillars. In essence, the construction activity is mediated by the resulting spatial structure of the nest, which in turn transforms the behaviour of everyone in the colony. Trail pheromones direct workers to construction sites. Such ability for self-organization as a result of neighbor interaction is often called “swarm intelligence”. And, indeed, optimisation problems, such as the Traveling Salesman, might be tackled by simulating such collaborative interactions employed by social animals to form colonies.

It is possible to program artificial ants such that they are distributed around the graph and such that they stochastically but probabilistically walk around the graph and select their route. Each city corresponds to a colony of ants that are predisposed to visit another colony of ants (city) as per intensity of pheromone trail. Over time, shorter and shorter routs are selected for due to their accumulation of more virtual pheromone, as opposed to the undesirable and less taken shorter routes, whose pheromone trails consequently evaporate. It would be quite an intriguing thing if such insights from biological systems could find an answer to one of the hardest combinatorial optimization problems.

Bibliography

Deneubourg, J. L., S. Aron, S. Goss, and J. M. Pasteels. 1990. The self-organizing exploratory pattern of the Argentine ant. J. Ins. Behav. 3: 159-168.

Grasse, P. P. 1959. Reconstruction of the nest and coordination between individuals in Bellicositermes natalensis and Cubitermes sp. The theory of stigmergy: Test interpretation of the Behaviour of Termites Manufacturers. Insectes Sociaux 6: 41 – 81.

Featured image courtesy of: McHenry County Historical Society