Researchers in Japan have developed an analog, amoeba-based computer that offers efficient solutions to something called ‘The Traveling Salesman Problem’ — something which regular computers find impossible to solve.
Amoeba brain
Here’s a fun problem: let’s say you’re a traveling salesman. You have to go to a number of different cities and showcase your products, and then return back home. You only need to visit each city once, of course, and you know the distance between every two cities. So what’s the shortest possible route?
The problem was first formulated in 1930 and it’s a deceptively complex one. If you address it computationally (compute all the possibilities), it becomes extremely difficult to solve. Conventional digital computers, even digital computers, struggle to solve it for a very large number of cities, although algorithms do exist to solve it through approximations and heuristics.
The problem is also important for optimization challenges, something that often occurs in real-life logistics. A traveling salesman is unlikely to travel to a million cities in a day, but if you’re Amazon and you’re delivering billions of packages a year, you really want to know what’s the optimal route.
Optimization problems are so interesting and important to researchers that specialized computers (called Ising machines) are being used to better address tasks such as the Traveling Salesman Problem. However, these machines require complex pre-processing and can sometimes produce false solutions. As it turns out, there’s something else researchers can use to solve the problem: amoebas.
Amoebas have been shown to find the solution (with approximation) to the Traveling Salesman Problem. In a 2019 study, researchers developed a setup with 64 ‘cities’ — areas with nutrients that the amoeba wanted to get to — and found that the organism was able to find an almost-optimal solution. It was still slower than a computer, but the possibility of using an organism to compute such a complex task wasn’t lost on researchers.
Now, a team led by Professor Seiya Kasai at Hokkaido University mimicked the dynamics of the amoeba. They created an analog electronic amoeba-inspired circuit. It’s simple enough to be built on a regular breadboard.
“The amoeba core searches for a solution under the electronic environment where resistance values at intersections of crossbars represent constraints and requests of the TSP,” says Kasai.
“The analog circuit reproduces well the unique and efficient optimization capability of the amoeba, which the organism has acquired through natural selection,” Kasai adds.
The circuit was able to reliably find a high-quality solution, much like the organic amoeba. It was able to find the shortest route for 4 cities, and turned out to be substantially more effective than a commonly used algorithm called “2-opt”.
It’s not the fastest solver out there and it has still only been tested with a small number of cities, but the possibility of an organic-inspired computer is not only exciting, but it could enable researchers to solve important problems with real-world applications. We’re only now starting to explore the world of unconventional computers. Who knows what lies ahead?
“As the analog computer consists of a simple and compact circuit, it can tackle many real-world problems in which inputs, constraints, and requests dynamically change and can be embedded into IoT devices as a power-saving microchip,” says Masashi Aono who leads Amoeba Energy to promote the practical use of the amoeba-inspired computers.
The study has been published in Nature Scientific Reports.
