March 26, 2013 report
Shrinking blob speeds traveling salesman on his way
(Phys.org) —What is the shortest route that a traveling salesman must take to visit a number of specified cities in a tour, stopping at each city once and only once before returning to the starting point? The most accurate way to answer this question is to measure every possible route, then determine which one is shortest. However, this method becomes unfeasible when there are too many cities on the salesman's tour. Jeff Jones and Andrew Adamatzky of the University of the West of England have discovered that they can use a virtual shrinking blob to find a reasonable solution.
The traveling salesman problem is a frequently studied mathematical problem. Mathematicians have developed many algorithms that provide reasonably good solutions; however, they tend to agree that no algorithm will solve the problem perfectly every time.
In developing their own algorithm, Jones and Adamatzky looked to the slime mold for inspiration. The slime mold, Physarum polycephalum, is a giant, single-celled organism that, during part of its lifecycle, survives by extending parts of its body toward nutrients and engulfing them. Slime molds can solve simple mazes.
The computer scientists simulated a slime mold by creating a virtual blob, made up of individual particles, which they placed inside a lattice containing virtual cities. Jones and Adamatzky projected a chemoattractant near the cities. They programmed each particle to move toward the region with the highest concentration of chemoattractant and to leave behind a trace of chemoattractant that the other particles would follow. When its particles followed these simple rules, the entire blob shrank so that it occupied the smallest possible surface area while still covering all of the cities.
After testing their blob 6 times on 20 different scenarios, each of which used 20 different cities, Jones and Adamatzky found once the blob had stopped shrinking, its circumference created a map of a route that provided a reasonable solution to the traveling salesman problem.
The two were not the first to use slime mold to solve the traveling salesman problem. However, they were the first to do so without encoding the problem in the slime. Jones and Adamatzky's blob arrived at the solution by following simple rules, unrelated to the problem, and in doing so, developed emergent behavior, such as the ability to reduce its surface area.
While a human measuring each route separately is still more likely to provide an accurate solution than the blob, Jones and Adamatzky's method is notable for its simplicity.
The researchers say that understanding how emergent behavior develops is important for both the computational and biological sciences. Their proposed next step is to create a physical model of the blob.
More information: Computation of the Travelling Salesman Problem by a Shrinking Blob, arXiv:1303.4969 [cs.ET] arxiv.org/abs/1303.4969
Abstract
The Travelling Salesman Problem (TSP) is a well known and challenging combinatorial optimisation problem. Its computational intractability has attracted a number of heuristic approaches to generate satisfactory, if not optimal, candidate solutions. In this paper we demonstrate a simple unconventional computation method to approximate the Euclidean TSP using a virtual material approach. The morphological adaptation behaviour of the material emerges from the low-level interactions of a population of particles moving within a diffusive lattice. A `blob' of this material is placed over a set of data points projected into the lattice, representing TSP city locations, and the blob is reduced in size over time. As the blob shrinks it morphologically adapts to the configuration of the cities. The shrinkage process automatically stops when the blob no longer completely covers all cities. By manually tracing the perimeter of the blob a path between cities is elicited corresponding to a TSP tour. Over 6 runs on 20 randomly generated datasets of 20 cities this simple and unguided method found tours with a mean best tour length of 1.04, mean average tour length of 1.07 and mean worst tour length of 1.09 when expressed as a fraction of the minimal tour computed by an exact TSP solver. We examine the insertion mechanism by which the blob constructs a tour, note some properties and limitations of its performance, and discuss the relationship between the blob TSP and proximity graphs which group points on the plane. The method is notable for its simplicity and the spatially represented mechanical mode of its operation. We discuss similarities between this method and previously suggested models of human performance on the TSP and suggest possibilities for further improvement.
© 2013 Phys.org
