Amoeba-Based Computer Solves Traveling Salesman Puzzle

Most people probably won’t hold the amoeba in high regard: these simple organisms often consist of a single cell, and they are best known for their characteristically slow movements, generated by them amorphously projecting out their cytoplasm — a phenomenon also known as pseudopodia (“false feet”).

But according to a study done by researchers over at Keio University in Tokyo, Japan, these humble organisms were able to generate solutions to a notoriously tough math puzzle known as the “traveling salesman problem” (TSP), and therefore, may someday help to form the basis for energy-efficient, biological computers that use biological components, such as DNA or proteins, for computational processes.

Amoebic Optimization

The traveling salesman problem is a well-known test for evaluating optimization algorithms. It asks this deceptively simple question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that a traveling salesman can use to visit each city, before returning to the origin city?”

With only four cities, the solution is only three possible routes. But as the number of cities increases, the number of possible answers increases exponentially: for six cities, that would be 360 routes; for eight cities, that number swells to 2520. The TSP is classified as an NP-hard problem (non-deterministic polynomial-time hardness), meaning that as the number of cities grows, the time needed for a conventional computer to solve it grows exponentially as well, due to its increased complexity.

Published in a recent issue of the journal Royal Society Open Science, the work describes how researchers were able to get a Physarum polycephalum amoeba or “true slime mold” to tackle this complex problem, by placing a 12-milligram specimen of this amoeba on a stellate chip, a round plate with 64 narrow channels that radiate out from a center. The amoeba can move but is constrained to the boundaries of the channels, each of which is meant to represent a city on the salesman’s journey. Moreover, each channel can be individually lit up to influence the way the amoeba will move.

The amoeba and its chip are then put on a nutrient-rich agar plate. The organism will naturally expand and project parts of itself to move toward positive stimuli (such as food), or away from negative stimuli (in this case, light) in order to maximize nutrient absorption. Thus, the experiment takes advantage of the amoeba’s natural shapeshifting abilities, and translates it into an “amoeba-based computing system” where it “tries to deform into an optimal shape, maximizing the body area for maximal nutrient absorption while minimizing the risk of being exposed to aversive light stimuli.”

In addition, the researchers used a neural network model to illuminate certain chip channels every six seconds. The model parses data about the distance between each pair of “cities” and the position of the amoeba in order to determine which channels need to be lit. For instance, if part of the amoeba is already in channel “B3”, the neural network will illuminate the other “B” channels, as well as any other channels numbered “3” will be lit up,  in order to prevent the amoeba from visiting the same cities more than once.

Solutions in Linear Time

While the idea of such an amoeba-based computing system might seem dubious at first, what is remarkable is that the time it takes the system to calculate optimal solutions to the TSP grows in a linear fashion, even though the number of possible answers is amplified exponentially, and the amoeba seems to do so by processing information in parallel, rather than serially, though the team still isn’t quite sure what exactly makes this system work the way it does.

“The mechanism by which how the amoeba maintains the quality of the approximate solution, that is, the short route length, remains a mystery,” study lead author Masashi Aono told Phys.org. “It seems that spatially and temporally correlated movements of the branched parts of the amoeba located at distant channels are the key. Each of these branches is oscillating its volume with some temporal ‘memory’ on illuminated experiences. Groups of the branches perform synchronization and desynchronization for sharing information even though they are spatially distant.”

While regular computers will still be able to solve a smaller version of the TSP quicker than an amoeba, the study’s results point to the possible development of analog computers capable of solving much more computationally complex optimization problems in linear time, and in a decentralized way. The team is now working to develop a system that will solve more advanced optimization problems.

Images: Keio University