Breakthrough Electronic Amoeba Analog Computer For Approximate Solving Traveling Salesman Problems

Many important and valuable planning and scheduling problems in logistics and automation are combinatorial optimization problems. The most famous problem of this type is the traveling salesman problem.

The salesman problem is this question: “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?”. Having really good solutions for this class of problems means the US postal service, Fedex, UPS, airlines and the US military would save huge amounts of money. It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

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. This is a combinatorial explosion. D-Wave Systems and others have created “Ising machines” and “quantum annealers,” have been actively developed in recent years. There is 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.

Approximation Algorithms

Various heuristics and approximation algorithms, which quickly yield good solutions, have been devised. These include the Multi-fragment algorithm. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability just 2–3% away from the optimal solution.

Exact algorithms
The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using brute-force search). The running time for this approach lies within a polynomial factor of {\displaystyle O(n!)}O(n!), the factorial of the number of cities, so this solution becomes impractical even for only 20 cities.

Other approaches include:

Various branch-and-bound algorithms, which can be used to process TSPs containing 40–60 cities.

Solution of a TSP with 7 cities using a simple Branch and bound algorithm. The number of permutations is much less than Brute force search.
Progressive improvement algorithms which use techniques reminiscent of linear programming. Works well for up to 200 cities.
Implementations of branch-and-bound and problem-specific cut generation. This is the method of choice for solving large instances. This approach holds the current record, solving an instance with 85,900 cities.

New Breakthrough Linear Scaling Approximate Solver

Japanese researchers have developed a breakthrough called the “electronic amoeba”. It is 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.

Amoeba Energy is a robotics company that is commercializing this solution.

The new analog solver solving time seems to remain linear even as they scaled from 10 to 30 cities. We will need a scaled-up analog chip to see if this does out-perform the other approximation solutions to the millions of cities scale. Getting a high-quality approximation answer in microseconds might be used to generate starting points to speed up exact algorithm solvers. It seems like a guaranteed substantially better than random solution that 100% following constraints would be a better starting point for Progressive improvement algorithms or the branch and bound problem-specific cut generation.

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.

Scientific Reports – Amoeba-inspired analog electronic computing system integrating resistance crossbar for solving the traveling salesman problem

Abstract
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 behavior 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.

SOURCES- Scientific Reports, Hokkaido University, Wikipedia, Amoeba Energy
Written By Brian Wang, Nextbigfuture.com