Scientists from Japan have presented a system that can quickly solve the traveling salesman problem – efficiently moving between different points. The behavior of the amoeba inspired the researchers.
Researchers at Hokkaido University in Japan took inspiration from the behavior of unicellular amoebas. They developed an analog computer to find a reliable and fast solution to the traveling salesman problem, a representative combinatorial optimization problem.
The scientists explained that conventional digital computers, including supercomputers, cannot solve these problems in a practically feasible time since the number of possible solutions that they need to evaluate increases exponentially with the size of the problem.
This problem can be avoided by using an “electronic amoeba” – an analog computer inspired by the single-celled amoeboid organism. It is known that the amoeba absorbs nutrients as efficiently as possible, deforming its body. She showed an approximate solution to the problem – given a map of a certain number of cities, the task is to find the shortest route to visit each city exactly once and return to the starting city.
This discovery inspired Professor Seiyu Kasai of Hokkaido University to mimic an amoeba’s behavior electronically using an analog circuit. By using baffles, researchers can easily re-plan a route by updating resistance values without complicated preprocessing.
The scheme then found a high-quality solution with a significantly shorter route length than the randomly sampled average. Also, the time required to find a high-quality solution did not increase significantly. Comparing the search time to a representative AI-based algorithm, the electronic amoeba was found to be faster.