Feeds

Slime mould mashup models fiendish computing problem

A travelling salesman walks into a blob...

Beginner's guide to SSL certificates

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

Internet Security Threat Report 2014

More from The Register

next story
GRAV WAVE DRAMA: 'Big Bang echo' may have been grit on the scanner – boffins
Exit Planet Dust on faster-than-light expansion of universe
SpaceX Dragon cargo truck flies 3D printer to ISS: Clawdown in 3, 2...
Craft berths at space station with supplies, experiments, toys
That glass of water you just drank? It was OLDER than the SUN
One MEELLION years older. Some of it anyway
Big dinosaur wowed females with its ENORMOUS HOOTER
That's right, Doris, I've got biggest snout in the prehistoric world
Japanese volcano eruption reportedly leaves 31 people presumed dead
Hopes fade of finding survivors on Mount Ontake
Relive the death of Earth over and over again in Extinction Game
Apocalypse now, and tomorrow, and the next day, and the day after that ...
prev story

Whitepapers

Providing a secure and efficient Helpdesk
A single remote control platform for user support is be key to providing an efficient helpdesk. Retain full control over the way in which screen and keystroke data is transmitted.
Intelligent flash storage arrays
Tegile Intelligent Storage Arrays with IntelliFlash helps IT boost storage utilization and effciency while delivering unmatched storage savings and performance.
Beginner's guide to SSL certificates
De-mystify the technology involved and give you the information you need to make the best decision when considering your online security options.
Security for virtualized datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.
Secure remote control for conventional and virtual desktops
Balancing user privacy and privileged access, in accordance with compliance frameworks and legislation. Evaluating any potential remote control choice.