An Amoeba-Based Computer Calculated Approximate Solutions to a Very Hard Math Problem
These single-celled organisms have a strange computing capacity that allows them to generate approximate solutions to a computationally complex problem known as the “traveling salesman problem.”
Image: Royal Society Open Science
A team of Japanese researchers from Keio University in Tokyo have demonstrated that an amoeba is capable of generating approximate solutions to a remarkably difficult math problem known as the “traveling salesman problem.”
The traveling salesman problem goes like this: Given an arbitrary number of cities and the distances between them, what is the shortest route a salesman can take that visits each city and returns to the salesman’s city of origin. It is a classic problem in computer science and is used as a benchmark test for optimization algorithms.
The traveling salesman problem is considered “NP hard,” which means that the complexity of calculating a correct solution increases exponentially the more cities are added to the problem. For example, there are only three possible solutions if there are four cities, but there are 360 possible solutions if there are six cities. It continues to increase exponentially from there.
Despite the exponential increase in computational difficulty with each city added to the salesman’s itinerary, computer scientists have been able to calculate the optimal solution to this problem for thousands of cities since the early 90s and recent efforts have been able to calculate nearly optimal solutions for millions of cities.
Amoebas are single-celled organisms without anything remotely resembling a central nervous system, which makes them seem like less than suitable candidates for solving such a complex puzzle. Yet as these Japanese researchers demonstrated, a certain type of amoeba can be used to calculate nearly optimal solutions to the traveling salesman problem for up to eight cities. Even more remarkably, the amount of time it takes the amoeba to reach these nearly optimal solutions grows linearly, even though the number of possible solutions increases exponentially.
As detailed in a paper published this week in Royal Society Open Science, the amoeba used by the researchers is called Physarum polycephalum, which has been used as a biological computer in several other experiments. The reason this amoeba is considered especially useful in biological computing is because it can extend various regions of its body to find the most efficient way to a food source and hates light.
To turn this natural feeding mechanism into a computer, the Japanese researcher placed the amoeba on a special plate that had 64 channels that it could extend its body into. This plate is then placed on top of a nutrient rich medium. The amoeba tries to extend its body to cover as much of the plate as possible and soak up the nutrients. Yet each channel in the plate can be illuminated, which causes the light-averse amoeba to retract from that channel.
To model the traveling salesman problem, each of the 64 channels on the plate was assigned a city code between A and H, in addition to a number from 1 to 8 that indicates the order of the cities. So, for example, if the amoeba extended its body into the channels A3, B2, C4, and D1, the correct solution to the traveling salesman problem would be D, B, A, C, D. The reason for this is that D1 indicates that D should be the first city in the salesman’s itinerary, B2 indicates B should be the second city, A3 that A should be the third city and so on.
To guide the amoeba toward a solution to the traveling salesman problem, the researchers used a neural network that would incorporate data about the amoeba’s current position and distance between the cities to light up certain channels. The neural network was designed such that cities with greater distances between them are more likely to be illuminated than channels that are not.
When the algorithm manipulates the chip that the amoeba is on it is basically coaxing it into taking forms that represent approximate solutions to the traveling salesman problem. As the researchers told Phys.org, they expect that it would be possible to manufacture chips that contain tens of thousands of channels so that the amoeba is able to solve traveling salesman problems that involve hundreds of cities.
For now, however, the Japanese researchers’ experiment remains in the lab, but it provides the foundation for low-energy biological computers that harness the natural mechanisms of amoebas and other microorganisms to compute.