Feeds

Slime mould mashup models fiendish computing problem

A travelling salesman walks into a blob...

Build a business case: developing custom apps

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. ®

Secure remote control for conventional and virtual desktops

More from The Register

next story
Boffins attempt to prove the UNIVERSE IS JUST A HOLOGRAM
Is this the real life? Is this just fantasy?
Our LOHAN spaceplane ballocket Kickstarter climbs through £8000
Through 25 per cent but more is needed: Get your UNIQUE rewards!
China building SUPERSONIC SUBMARINE that travels in a BUBBLE
Shanghai to San Fran in two hours would be a trick, though
LOHAN tunes into ultra long range radio
And verily, Vultures shall speak status unto distant receivers
SpaceX prototype rocket EXPLODES over Texas. 'Tricky' biz, says Elon Musk
No injuries or near injuries. Flight stayed in designated area
Galileo, Galileo! Galileo, Galileo! Galileo fit to go. Magnifico
I'm just a poor boy, nobody loves me. But at least I can find my way with ESA GPS by 2017
EOS, Lockheed to track space junk from Oz
WA facility gets laser-eyes out of the fog
prev story

Whitepapers

Top 10 endpoint backup mistakes
Avoid the ten endpoint backup mistakes to ensure that your critical corporate data is protected and end user productivity is improved.
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.
Backing up distributed data
Eliminating the redundant use of bandwidth and storage capacity and application consolidation in the modern data center.
The essential guide to IT transformation
ServiceNow discusses three IT transformations that can help CIOs automate IT services to transform IT and the enterprise
Next gen security for virtualised datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.