アドホックネットワーク，ユビキタス・ネットワーク

同期現象（シンクロニゼーション）の解明，同期システムへの応用

ネットワークダイナミクス, 粘菌の分散知能の研究

A Simplistic Dynamic Circuit Analogue of Adaptive Transport Networks in True Slime Mold

Hisa-Aki Tanaka, Kazuki Nakada, Yuta Kondo, Tomoyuki Morikawa, and Isao Nishikawa
Nonlinear Theory and Its Applications (NOLTA), IEICE, Apr. 2016.

Keyword

Biology-inspired Algorithm, Shortest Path Search Methods, Nonlinear Resistive Circuits

Abstract

This paper presents a simplistic dynamic circuit analogue for an adaptive transport network model in true slime mold by Tero et al. This circuit analogue model is derived from Tero's model through nontrivial simplification under certain assumptions, and it realizes less computational complexity through a reduction of the number of variables. Despite of its simplicity, systematic simulations confirm that the shortest path search task is efficiently accomplished with this model; (i) the shortest path is always identified, for various random networks; (ii) if there are multiple, competing shortest paths in the network, they are simultaneously identified; and (iii) for random deletions of a link in the shortest path, a new shortest path is quickly identified accordingly. The model proposed here is easily implemented on the circuit simulator SPICE for instance, and hence the path search time will be further reduced with certain numerical devices including automatic adaptive numerical integration schemes as well as an acceleration method proposed in the end of the paper.

Download PDF

Figures at a glance

References

  1. A. Tero, R. Kobayashi, and T. Nakagaki, "Physarum solver: A biologically inspired method of roadnetwork navigation," Physica A, 363, pp. 115-119, 2006.
  2. A. Tero, R. Kobayashi, and T. Nakagaki, "A mathematical model for adaptive transport network in path finding by true slime mold," J. Theor. Biol., 224, pp. 553-564, 2007.
  3. T. Nakagaki, H. Yamada, and Á. Tóth, "Intelligence: Maze-solving by an amoeboid organism," Nature, vol. 407, p. 470, 2000.
  4. T. Miyaji and I. Ohnishi, "Physarum can solve the shortest path problem on Riemannian surface mathematically rigorously," Int. J. Pure and Applied Mathematics, vol. 47, no.3, pp. 353-369, 2008.
  5. V. Bonifaci, K. Mehlhorn, and G. Varma, "Physarum can compute shortest paths," J. Theor. Biol., vol. 309, pp. 121-133, 2012.
  6. L. Becchetti, V. Bonifaci, M. Dirnberger, A. Karrenbauer, and K. Mehlhorn, "Physarum can compute shortest paths: convergence proofs and complexity bounds," Automata, Languages, and Programming, pp. 472-483, Springer, Berlin Heidelberg, 2013.
  7. L. Zhu, M. Aono, S.-J. Kim, and M. Hara "Amoeba-based computing for traveling salesman problem: Long-term correlations between spatially separated individual cells of Physarum polycephalum," BioSystems vol. 112, no.1, pp. 1-10, 2013.
  8. Y. Kondo and H.-A. Tanaka, "An Electric Circuit Analogue of a Mathematical Model for Adaptive Transport Network in True Slime Mold," Proc. NOLTA'07, pp. 521-524, Vancouver, Canada, 16-19 Sep. 2007.
  9. DIMACS, Ninth DIMACS Implementation Challenge — Shortest Paths, 2006. http://www.dis.uniroma1.it/challenge9/.
  10. T. Ibaraki, Algorithms and Data Structures in C, Shokohdo, 1999 (in Japanese).
  11. S. Umetani, private communications, 2015.