A new analog computer to find a quick and reliable solution to the traveling salesman problem that was formulated in the 1930s.
The traveling salesman problem, or TSP, is one of the most intensively studied problems in computational mathematics. The problem states, “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” TSP is a representative combinatorial optimization problem.
Now researchers from Hokkaido University and Amoeba Energy in Japan developed an analog computer, the electronic amoeba, to solve the TSP. They took inspiration from the efficient foraging behavior of a single-celled amoeba for their solution.
A combinatorial problem is an optimization problem rather than a decision problem. The solution to the problem is additionally evaluated for solution quality. Classic examples of combinatorial optimization problems are logistical planning and scheduling.
In this digital age, we think that our digital computers can solve these problems pretty easily; on the contrary, today’s computers, including the supercomputers, are inadequate to solve these in practically permissible time. As the size of the problem increases, the number of solutions to evaluate increases exponentially. Newly developed computers like Ising machines, including quantum annealers, require complicated pre-processing of the task and also run the risk of presenting solutions that do not meet certain constraints.
Amoeba is known to employ efficient nutrient-acquisition methodology by deforming their body. This behavior inspired Professor Seiya Kasai at Hokkaido University to design an analog circuit to mimic amoeba’s dynamics. The circuit fabricated on a breadboard by Kenta Saito, a Ph.D. student in Kasai’s lab, successfully found the shortest route for the 4-city TSP. Circuit simulations showed the circuit could reliably find a high-quality legal solution with a significantly shorter route length than the average length obtained by random sampling. Also, the time required to find this solution grew only linearly to the number of complexities giving an advantage over other computing solutions.
“The analog circuit reproduces well the unique and efficient optimization capability of the amoeba, which the organism has acquired through natural selection,” said Kasai.
According to Masashi Aono, who leads Amoeba Energy, due to the analog circuit’s simplicity and compactness, it can be used to tackle many real-world problems. Also, it can be embedded in IoT devices as a power-saving microchip.
Do you want to publish on Apple News, Google News, and more? Join our writing community, improve your writing skills, and be read by hundreds of thousands around the world!