Traveling Amoeba for Better Traveling Salesman Solutions

Traveling Salesman Problems are in a class of very difficult mathematical problems called NP-Complete problems. The possible solutions scales at insanely high levels that go far beyond current supercomputers. Better solutions for these problems could enable postal services, airlines and package delivery to be far more efficient. Better solutions could boost the overall efficiency of the world economy by substantial amounts. Now amoeba are being harnessed for better solutions to these problems.

Once researchers can fabricate a larger chip, the plasmodium would solve larger TSP (Traveling Salesman Problem) instances with several hundred cities, as the number of its branches would be estimated to scale to several tens of thousands. Researchers believe by creating an actual physical map to be traversed, then Amoeba’s could produce better solutions to NP-Complete problems. Creating NP-problems in a physical representation could allow Amoeba’s to provide us with superior solutions.

Biologically inspired computing devices and architectures are expected to complement and in some cases surpass conventional technologies for solving computationally demanding problems, because of their ability to make correct decisions in uncertain environments and to reduce energy consumption. The plasmodium of the true slime mould Physarum polycephalum has been actively investigated for this purpose because of its intriguing decentralized computing capabilities. Deforming its amorphous body, the plasmodium searches for the optimum route among food sources, forms regular graphs and anticipates periodic events.

is to examine whether the linear-time search ability of the plasmodium could be confirmed even when using different maps in which their tour lengths are not distributed normally as can be seen in real-world applications. Informally, the randomly chosen maps with normally distributed inter-city distances that we used in this study might be ‘harder’ than the ones with abnormally distributed distances that reflect the real-world situations. In the results shown, solving randomly constructed TSP instances with normally distributed tour lengths defined on the Euclidean plane tended to require longer CPU time than to solving the benchmark instances provided at TSPLIB that includes a variety of industrial applications and geographical point sets.

The reason why in this study the number of cities n was limited to eight was that we were not able to fabricate the chip with more than 64 lanes, owing to the size limit of the photolithography equipment. The width of each lane of the chip had to be 0.45 mm; below this width, the branch of the plasmodium was not able to enter the lane, and above this width, we could not avoid the growth of more than one branch in a lane. In nature, it is observed that the area of the plasmodium grows up to several square meters wide.

Once they can fabricate the larger chip, the plasmodium would solve larger TSP instances with several hundred cities, as the number of its branches would be estimated to scale to several tens of thousands.

The oscillatory movements of distant branches of the plasmodium are spatially correlated, as they exhibit phase synchronizations that produce various spatio-temporal patterns of travelling phase waves. We have experimentally shown that a shorter TSP tour can be found when the plasmodium exhibits a lower number of the travelling phase waves, indicating that the dynamics are highly coherent and correlated throughout the global body. Although our computational model, AmoebaTSP, in its current form does not introduce any correlation among the fluctuations of the branches, a modification of the branch dynamics to involve the spatio-temporal correlations may further enhance the ability to find a high-quality solution.

AmoebaTSP was formulated in such a way that it is scheduled to reach one of the feasible solutions after the number of iterations that grows linearly as a function of n; for that purpose, we introduced a constraint that the constant amount of resource has to be distributed to the non-illuminated branches for every iteration by extinguishing the stock of retreated resources from the illuminated branches. It was confirmed that this constraint ensures the linear growth in terms of the number of iterations. When AmoebaTSP is simulated on a traditional digital computer, however, the CPU time required to reach a feasible solution grows nonlinearly. A major reason is that the weight matrix of the recurrent neural network dynamics to determine the illumination pattern has n4 elements, which are to be processed serially in CPU. The CPU-simulated AmoebaTSP, therefore, would not be used to obtain an approximate solution of TSP in linear practical time for the problem size larger than several hundred cities.

But, using some other computing platforms whose physical processes allow us to update the states of all AmoebaTSP branches in parallel when computing the neural network dynamics and constant-rate resource distribution dynamics, we expect that the approximate solution of TSP would become available in linear practical time. A promising candidate of such a computing platform is an analogue electronic circuit. In fact, some authors have explored the use of the amoeba-inspired electronic circuits for tackling the constraint satisfaction problem, satisfiability problem, analogue-to-digital conversion and finding walking manoeuvre of a multi-legged robot. Such an approach to exploit physical parallelism may develop a novel analogue computing paradigm, providing powerful approximation methods for solving complex optimization problems appearing in a wide spectrum of real-world applications.

Choosing a better move correctly and quickly is a fundamental skill of living organisms that corresponds to solving a computationally demanding problem. A unicellular plasmodium of Physarum polycephalum searches for a solution to the travelling salesman problem (TSP) by changing its shape to minimize the risk of being exposed to aversive light stimuli. In our previous studies, we reported the results on the eight-city TSP solution. In this study, we show that the time taken by plasmodium to find a reasonably high-quality TSP solution grows linearly as the problem size increases from four to eight. Interestingly, the quality of the solution does not degrade despite the explosive expansion of the search space. Formulating a computational model, we show that the linear-time solution can be achieved if the intrinsic dynamics could allocate intracellular resources to grow the plasmodium terminals with a constant rate, even while responding to the stimuli. These results may lead to the development of novel analogue computers enabling approximate solutions of complex optimization problems in linear time.

Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism