Excuse Me, I Have To Feed The Computer

It is a staple of science fiction to see a brain in a jar or other container, maybe used as some sort of computer device. You are probably imagining a brain-powered supercomputer with a room full of humans with electrodes in their heads, or maybe some other primate. The reality though is it might be just a small dish full of single-celled amoeba.

Researchers from China and Japan have successfully made a lowly amoeba solve the traveling salesman problem for 8 cities. We’ll be honest. We don’t totally understand the value to it over traditional methods, but it does prove that you can compute with organic matter. This isn’t just any amoeba, though. It is a particular kind, Physarum polycephalum, that has an unusual property — it can shapeshift, at least to a limited degree. The tiny creature is just like us in that it tries to get things it likes and avoid things it doesn’t like. It likes food, but it doesn’t like light.

Provide food, and the tiny creature will spread out. Shine light on it, and it will retract. That’s the property used to solve the thorny problem, but before we look at how that works it helps to understand the problem it is trying to solve.

The traveling salesman problem (often known as simply TSP) is possibly the most famous NP-hard problem known. The basic idea is that a salesman has to visit a number of cities. What is the shortest path to take? That sound simple, but as the number of cities grows, so do the number of possible paths. For 16 cities, there are more than a trillion paths. For 100 cities, it is 10¹⁵⁶ and the number increases from there rapidly. At 10,000 cities, the number climbs to10³⁵⁶⁵⁷ so for all but the smallest number of cities, it is impractical to just try all routes.

The researchers arranged to put the organism on a plate with 64 channels corresponding to 8 cities (A-H) and their order in the final result. So if the best route is ABCDEFGH, that would correspond to A1, B2, C3, and so on. Since the channels offer food, the amoeba tries to spread out into all of them. A camera reads the results and arranges for light to shine on channels that represent long-distance paths.

The amoeba will retract from those channels. However, the volume of the creature remains constant, so retracting in one spot will cause other spots to extend just as extending in one area will cause other spots to shrink. It can’t, after all, create new mass. Because the creature also has a bit of randomness, it will sometimes overreach and not get stuck in a local maximum.

If we are reading the paper correctly this is similar to a neural network whose weights are controlled by the amoeba rather than learned from a dataset. Maybe. The feedback — called the bounceback control — uses some neural network algorithms, but the amoeba is in the loop.

One surprising result? Unlike some schemes, as the number of cities gets larger, the computation time — if you can call it that — increases in a linear fashion. That’s surprising since the number of paths increases much more rapidly. Of course, for thousands of cities you would need a lot of little channels, so there must be some practical limit that probably isn’t much more than 8 cities.

Organic electronics aren’t exactly new. We’ve been using OLEDs now for a while, but they aren’t actually alive. We just hope these aren’t brain-eating amoeba. Can FPGAs (Field Programmable Gooey Arrays) be far behind?

from Hackaday http://bit.ly/2SurgH3
via IFTTT