Feeds

Slime mould mashup models fiendish computing problem

A travelling salesman walks into a blob...

Bridging the IT gap between rising business demands and ageing tools

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

Mobile application security vulnerability report

More from The Register

next story
Malaysian Airlines flight MH17 claimed lives of HIV/AIDS cure scientists
Researchers, advocates, health workers among those on shot-down plane
Mwa-ha-ha-ha! Eccentric billionaire Musk gets his PRIVATE SPACEPORT
In the Lone Star State, perhaps appropriately enough
All those new '5G standards'? Here's the science they rely on
Radio professor tells us how wireless will get faster in the real world
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?
Microsoft's anti-bug breakthrough: Wire devs to BRAIN SCANNERS
Clippy: It looks your hands are shaking, are you sure you want to commit this code?
prev story

Whitepapers

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.
How modern custom applications can spur business growth
Learn how to create, deploy and manage custom applications without consuming or expanding the need for scarce, expensive IT resources.
Reducing security risks from open source software
Follow a few strategies and your organization can gain the full benefits of open source and the cloud without compromising the security of your applications.
Boost IT visibility and business value
How building a great service catalog relieves pressure points and demonstrates the value of IT service management.
Consolidation: the foundation for IT and business transformation
In this whitepaper learn how effective consolidation of IT and business resources can enable multiple, meaningful business benefits.