Shrinking blob speeds traveling salesman on his way

Mar 26, 2013 by Marcia Malory report
Foraging plasmodium of Physarum does not approximate the Travelling Salesman Problem in both unconstrained and constrained environments. Credit: arXiv:1303.4969 [cs.ET]

( —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 . 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 simulated a slime mold by creating a virtual blob, made up of individual particles, which they placed inside a 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.

Visualisation of the shrinking blob method. Credit: arXiv:1303.4969 [cs.ET]

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 created a map of a route that provided a reasonable solution to the traveling salesman problem.

The two were not the first to use 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 .

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.

Explore further: The internet was delivered to the masses; parallel computing is not far behind

More information: Computation of the Travelling Salesman Problem by a Shrinking Blob, arXiv:1303.4969 [cs.ET]

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.

Related Stories

Slime mold prefers sleeping pills

Jun 13, 2011

In a new paper published in Nature Precedings, Andrew Adamatzky from the University of the West of England shows that slime molds like Physarum polycephalum prefers sleeping pills and their sedative effects over ...

Study shows slime molds have spatial memory

Oct 09, 2012

(—Biology researchers from the University of Sydney, working with colleagues from Paul Sabatier Université in Toulouse have found that the brainless slime mold Physarum polycephalum, is able t ...

Slime design mimics Tokyo's rail system

Jan 21, 2010

What could human engineers possibly learn from the lowly slime mold? Reliable, cost-efficient network construction, apparently: a recent experiment suggests that Physarum polycephalum, a gelatinous fungus ...

Japan scientists hope slime holds intelligence key

Dec 28, 2011

A brainless, primeval organism able to navigate a maze might help Japanese scientists devise the ideal transport network design. Not bad for a mono-cellular being that lives on rotting leaves.

Recommended for you

Enabling a new future for cloud computing

1 hour ago

The National Science Foundation (NSF) today announced two $10 million projects to create cloud computing testbeds—to be called "Chameleon" and "CloudLab"—that will enable the academic research community ...

Hacking Gmail with 92 percent success

13 hours ago

( —A team of researchers, including an assistant professor at the University of California, Riverside Bourns College of Engineering, have identified a weakness believed to exist in Android, Windows ...

User comments : 2

Adjust slider to filter visible comments by rank

Display comments: newest first

5 / 5 (1) Mar 26, 2013
Looks quite adiabatic, in process.
not rated yet Mar 26, 2013
Looks quite adiabatic, in process. - Tek

Every point not lying on the shortest line connecting two points (on the 'solid curve' - see link)adds length.

When humans locate at a point (dwelling) on the surface of an earth the points are points of probability density.

The general solution will involve - as always - the greatest imagination. TSP is an exercise in imagination.

Interesting to note that TSP and N vs. NP share the exact same fundamentals for solutions - space and time.

Can this be adapted to quantum computation before a general solution is found?