Friday, December 11, 2020

Electronic Amoeba for solving TSPs?


Combinatorial optimization to search for the best solution across a vast number of legal candidates requires the development of a domain-specific computing architecture that can exploit the computational power of physical processes, as conventional general-purpose computers are not powerful enough. Recently, Ising machines that execute quantum annealing or related mechanisms for rapid search have attracted attention. These machines, however, are hard to map application problems into their architecture, and often converge even at an illegal candidate. Here, we demonstrate an analogue electronic computing system for solving the travelling salesman problem, which mimics efficient foraging behaviour of an amoeboid organism by the spontaneous dynamics of an electric current in its core and enables a high problem-mapping flexibility and resilience using a resistance crossbar circuit. The system has high application potential, as it can determine a high-quality legal solution in a time that grows proportionally to the problem size without suffering from the weaknesses of Ising machines.

Picture of the electronic amoeba (from [2])

"Electronic amoeba" sounds awful. Furthermore, the paper talks about "legal solutions". Now the lawyers even get involved... 


  1. 'Electronic amoeba' finds approximate solution to traveling salesman problem in linear time,
  2. Kenta Saito, Masashi Aono and Seiya Kasai, Amoeba-inspired analog electronic computing system integrating resistance crossbar for solving the travelling salesman problem,


No comments:

Post a Comment