Feeds

Slime mould mashup models fiendish computing problem

A travelling salesman walks into a blob...

High performance access to file storage

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

High performance access to file storage

More from The Register

next story
Elon Musk's LEAKY THRUSTER gas stalls Space Station supply run
Helium seeps from Falcon 9 first stage, delays new legs for NASA robonaut
Solar-powered aircraft unveiled for round-the-world flight
It's going to be a slow and sleepy flight for the pilots
Russian deputy PM: 'We are coming to the Moon FOREVER'
Plans to annex Earth's satellite with permanent base by 2030
LOHAN's Punch and Judy show relaunches Thursday
Weather looking good for second pop at test flights
Saturn spotted spawning new FEMTO-MOON
Icy 'Peggy' looks to be leaving the outer rings
Discovery time for 200m WONDER MATERIALS shaved from 4 MILLENNIA... to 4 years
Alloy, Alloy: Boffins in speed-classification breakthrough
India's GPS alternative launches second satellite
Closed satnav system due to have all seven birds aloft by 2016
Curiosity finds not-very-Australian-shaped rock on Mars
File under 'messianic pastries' and move on, people
Top Secret US payload launched into space successfully
Clandestine NRO spacecraft sets off on its unknown mission
prev story

Whitepapers

Securing web applications made simple and scalable
In this whitepaper learn how automated security testing can provide a simple and scalable way to protect your web applications.
Five 3D headsets to be won!
We were so impressed by the Durovis Dive headset we’ve asked the company to give some away to Reg readers.
HP ArcSight ESM solution helps Finansbank
Based on their experience using HP ArcSight Enterprise Security Manager for IT security operations, Finansbank moved to HP ArcSight ESM for fraud management.
The benefits of software based PBX
Why you should break free from your proprietary PBX and how to leverage your existing server hardware.
Mobile application security study
Download this report to see the alarming realities regarding the sheer number of applications vulnerable to attack, as well as the most common and easily addressable vulnerability errors.