[14a-A301-1~11] 31.1 Focused Session "AI Electronics"

△ [14a-A301-10] Solution Search Performance on an Amoeba Electronic Computing System for the Traveling Salesman Problem

〇Kenta Saito¹, Seiya Kasai¹, Masashi Aono² (1.Hokkaido Univ., 2.Keio Univ.)

Keywords:optimization problem, traveling salesman problem, electronic amoeba

Development of a computing system dedicated to solving optimization problems has increased. Optimization problems are difficult to solve efficiently using the conventional von Neumann computer because optimization problems have enormous combinations. We have been inspired by an amoeba computing system and developed an electronic amoeba implemented by simple electronic circuit. The electronic amoeba can solve optimization problems, such as satisfiability problem, maximum cut problem and traveling salesman problem. In this paper, we report solution search performance of the electronic amoeba for the traveling salesman problem. When increasing the number of cities, solution quality (path length) of the electronic amoeba did not degrade against random sampling and time until obtaining the solution was linear time increasing.