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 10156 and the number increases from there rapidly. At 10,000 cities, the number climbs to1035657 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?
One of the greatest joys of college was the semester where the networking courses taught BGP, math courses taught NP-hard, NP-complete, and the halting problem, while Comp-Sci taught Knuth’s solutions to some of these problems.
If each additional node in the TSP brings it’s own computation unit to the party, the problem doesn’t progress at the same rate; as long as the graph is not complete. Complete graphs are a bane to my existence when programming.
Very interesting but I think I’ll just stick to my ants, thanks.
The slime mold acts similar to a soap bubble computer: http://highscalability.com/blog/2012/6/13/why-my-soap-film-is-better-than-your-hadoop-cluster.html
So basically this is proving that an amoeba is more intelligent than your average salesman ?
Then there’s also the oil drop computer, which solves mazes by using acidity gradients:
https://www.newscientist.com/article/dn18391-intelligent-oil-droplet-navigates-chemical-maze/
The trick in all these analog computers is that the setup of the problem contains the solution of the problem, so the computation is actually done with plenty of time when the problem is constructed and the chemicals diffuse through the network, and then the star of the show, the slime mold or the drop of oil, is brought to the scene and appears to solve the problem with surprising ease.
Even serious researchers fall victim to these sort of party tricks all the time.
It seemed to me that the real setup here was the feedback network which is sort of what you are saying, I think. It would be like saying “We’ll shock this monkey until he presses button #3.” Look! The monkey figured out that he needs to press button #3! Of course, I’ve made the same comment on some popular quantum computing algorithms, too. If you provide a function that says “is the answer 3?” It gives you a 3. Amazing! lol. Now if you have a way to measure the “goodness” of an answer but you don’t know a good answer, that’s a different situation (like most chess programs, for example). But if you know the answer and just keep asking the system “Did you get the right answer yet?” as part of the algorithm that doesn’t seem like a good trick to me.
I don’t think solving unsolvable problems has ever been the point of the TSP. Managing computational explosion while retaining a useful answer has.
This should not come as a surprise. The slime Molds name is Fred.
He appears frequently at gpf-comics.com
He woks for Fred-Ex.
I remember over a decade ago Scientific America covering DNA being used to sole the TSP. I think the larger context is that digital may hit more walls when it comes to solving real-world (which biological usually is) problems. Digital is modeling the real-world, while analog IS the real-world.
I’m not clear on what’s going on here. So, is the amoeba actually solving a problem or are the humans solving the problem then directing the amoeba where to go via food & light? I’d love to see a better explanation of how this test actually works. If the amoeba is actually solving some problem then this is impressive. If it’s just going toward food in one channel and avoiding light in other channels because a human setup those conditions then this has nothing to do with computation on the amoeba’s part.
It’s a combination of the two. The Amoeba follow a set series of known rules, much like a computer. The researchers then set up a situation where the rules of the amoeba could be used to find a solution to the problem. The scientists knew the way to the solution, used the amoeba as a model, and read the result. The amoeba are good at solving this type of problem because of the way the experiment was set up.
“Food-programmable”