Amoeba-based Neurocomputing for 8-City Traveling Salesman Problem
Masashi Aono, Liping Zhu and Masahiko Hara
A single-celled amoeboid organism, the true slime mold Physarum polycephalum, exhibits rich spatio-temporal oscillatory behavior and sophisticated computational capabilities. We explore potentials of the organism as a computing substrate for performing efficient and adaptive information processing with the expectation that our studies on the spatio-temporal dynamics will contribute to the development of unconventional man-made devices consisting of masses of interacting molecular elements. Previously the authors demonstrated an experimental computing system that uses the organism to search for a solution to the 4-city Traveling Salesman Problem (TSP). With the assistance of optical feedback to implement a recurrent neural network model, the organism changes its shape by alternately expanding and shrinking its photosensitive branches so that its body area can be maximized and the risk of being illuminated can be minimized. Consequently the system succeeded in finding the optimal solution with a high probability. If this system exhibits high performances even when scaled up, our scheme to utilize the spatio-temporal dynamics for computing will become an attractive solution to many application problems. In this study, we show that our system can be extended to the 8-city TSP solver and is capable of finding good solutions.
Keywords: Physarum Polycephalum, Biocomputing, Neural Network, Spatiotemporal Dynamics, Coupled Oscillators, Traveling Salesman Problem, Combinatorial Optimization, Decision Making, Resource Allocation