Researchers have, inspired by the efficient foraging behavior of a single-celled amoeba, developed an analog computer for finding a reliable and swift solution to the traveling salesman problem — a representative combinatorial optimization problem.
Many real-world application tasks such as planning and scheduling in logistics and automation are mathematically formulated as combinatorial optimization problems. Conventional digital computers, including supercomputers, are inadequate to solve these complex problems in practically permissible time as the number of candidate solutions they need to evaluate increases exponentially with the problem size — also known as combinatorial explosion. Thus new computers called “Ising machines,” including “quantum annealers,” have been actively developed in recent years. These machines, however, require complicated pre-processing to convert each task to the form they can handle and have a risk of presenting illegal solutions that do not meet some constraints and requests, resulting in major obstacles to the practical applications.
These obstacles can be avoided using the newly developed “electronic amoeba,” an analog computer inspired by a single-celled amoeboid organism. The amoeba is known to maximize nutrient acquisition efficiently by deforming its body. It has shown to find an approximate solution to the traveling salesman problem (TSP), i.e., given a map of a certain number of cities, the problem is to find the shortest route for visiting each city exactly once and returning to the starting city. This finding inspired Professor Seiya Kasai at Hokkaido University to mimic the dynamics of the amoeba electronically using an analog circuit, as described in the journal Scientific Reports. “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. Using the crossbars, the city layout can be easily altered by updating the resistance values without complicated pre-processing.
Kenta Saito, a PhD student in Kasai’s lab, fabricated the circuit on a breadboard and succeeded in finding the shortest route for the 4-city TSP. He evaluated the performance for larger-sized problems using a circuit simulator. Then the circuit reliably found a high-quality legal solution with a significantly shorter route length than the average length obtained by the random sampling. Moreover, the time required to find a high-quality legal solution grew only linearly to the numbers of cities. Comparing the search time with a representative TSP algorithm “2-opt,” the electronic amoeba becomes more advantageous as the number of cities increases. “The analog circuit reproduces well the unique and efficient optimization capability of the amoeba, which the organism has acquired through natural selection,” says Kasai.
“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.
Using a circuit simulator, we have investigated the solution-searching performance of the electronic amoeba for 𝑁 ranging from 10 to 30. We performed 50 trials for each instance for 𝑁 not greater than 20 but only once for each 𝑁 more than 20 because the simulation time increased rapidly; it took 5 h for the 20-city instances but took 6 days for the 30-city cases. In each trial, resistances in the units were randomly assigned from 1 Ω to 10 kΩ to lead the electronic amoeba to explore a wider state space. To evaluate the rate of finding a legal solution in the electronic amoeba, we performed 560 trials for solving the TSP of 10–30 cities. The rate was found to be 100%; the system certainly converged to one of the legal solutions for every try. This is because the amoeba core always stabilizes at a steady state in which no variable violates the TSP constraints in such a state, no further change in all units in the amoeba core is induced by the bounceback signals. The vertical axis is normalized by the average route length obtained from random sampling of 10,000 trials; if a value on the vertical axis is less than 1.0, it implies that the quality of the legal solution found is higher than that found by random sampling. The results indicate that the electronic amoeba finds higher-quality solutions than random sampling. Moreover, the average of the route length was on a declining trend; the quality did not degrade even when the problem size 𝑁 became larger.
