Feeds

Slime mould mashup models fiendish computing problem

A travelling salesman walks into a blob...

The smart choice: opportunity from uncertainty

A pair of English researchers have offered up a “virtual slime mould” as a technique for one of mathematics' – and computer science's – classic problems, the travelling salesman problem.

In the travelling salesman problem, the challenge is to find the shortest possible route that includes a given set of locations or cities: as the number of cities scales up, it becomes increasingly difficult to test a solution in polynomial time (that is, the travelling salesman problem is NP-hard).

Enter the slime mould (Physarum polycephalum), already known to be able to solve simple mazes. The researchers, Jeff Jones and Andrew Adamatzky of the University of the West of England's Centre for Unconventional Computing, decided to model the slime mould in a computer and see if its behaviour would provide a travelling salesman solution.

Their “virtual blob” was programmed with the simple behaviours of a slime mould: the “cities” in the model represented food sources. Individual particles of the blob were placed in a lattice and programmed to move towards the highest concentrations of the “chemoattractors” in the model (the cities), leaving behind them a trail of chemoattractors for other particles to follow.

As the paper (Arxiv) puts it: “The city nodes act as attractants to the material, effectively `snagging' the material at the locations of uncovered nodes and affecting its subsequent morphological adaptation. As the material continues to shrink its innate minimising properties conform to the locations of the city nodes and the area occupied by the material is reduced, becoming a concave area covering the nodes”.

The result – only tested for relatively small sets of 20 or so cities, so that the results could be checked against computer-calculated optimum routes – was that the virtual blobs would shrink towards a smallest-possible circumference that turned out to be a fairly good solution to the problem (see picture).

Virtual Slime Mould solving the travelling salesman problem

Virtual slime mould solving the travelling salesman problem

Image: Jeff Jones & Adam Adamatzky, University of West England

A key decision in the computer model slime mould turned out to be knowing when to stop. A real slime mould colony, the researchers found, will continue shrinking to a point where some “cities” are left out of its tour.

While not the first “virtual slime mould” solution proposed to the travelling salesman problem, the Jones-Adamatzky model is unguided, relying only on the emergent behaviour of the model to arrive at a solution.

Watch Video

The test yielded solutions very close to the well-known Concorde TSP solver: its mean best tour length was only 1.04 times as long as the results from an established algorithm, and the mean worst was 1.09 times as long. ®

The Power of One Infographic

More from The Register

next story
World Solar Challenge contender claims new speed record
One charge sees Sunswift travel 500kms at over 100 km/h
SMELL YOU LATER, LOSERS – Dumbo tells rats, dogs... humans
Junk in the trunk? That's what people have
The Sun took a day off last week and made NO sunspots
Someone needs to get that lazy star cooking again before things get cold around here
Boffins discuss AI space program at hush-hush IARPA confab
IBM, MIT, plenty of others invited to fill Uncle Sam's spy toolchest, but where's Google?
Bad back? Show some spine and stop popping paracetamol
Study finds common pain-killer doesn't reduce pain or shorten recovery
Forty-five years ago: FOOTPRINTS FOUND ON MOON
NASA won't be back any time soon, sadly
Jurassic squawk: Dinos were Earth's early FEATHERED friends
Boffins research: Ancient dinos may all have had 'potential' fluff
prev story

Whitepapers

Top three mobile application threats
Prevent sensitive data leakage over insecure channels or stolen mobile devices.
Implementing global e-invoicing with guaranteed legal certainty
Explaining the role local tax compliance plays in successful supply chain management and e-business and how leading global brands are addressing this.
Boost IT visibility and business value
How building a great service catalog relieves pressure points and demonstrates the value of IT service management.
Designing a Defense for Mobile Applications
Learn about the various considerations for defending mobile applications - from the application architecture itself to the myriad testing technologies.
Build a business case: developing custom apps
Learn how to maximize the value of custom applications by accelerating and simplifying their development.