Amoeba-based computing for traveling salesman problem: Long-term correlations between spatially separated individual cells of Physarum polycephalum

Liping Zhu, Masashi Aono, Song Ju Kim, Masahiko Hara

Research output: Contribution to journalArticlepeer-review

47 Citations (Scopus)


A single-celled, multi-nucleated amoeboid organism, a plasmodium of the true slime mold Physarum polycephalum, can perform sophisticated computing by exhibiting complex spatiotemporal oscillatory dynamics while deforming its amorphous body. We previously devised an " amoeba-based computer (ABC)" to quantitatively evaluate the optimization capability of the amoeboid organism in searching for a solution to the traveling salesman problem (TSP) under optical feedback control. In ABC, the organism changes its shape to find a high quality solution (a relatively shorter TSP route) by alternately expanding and contracting its pseudopod-like branches that exhibit local photoavoidance behavior. The quality of the solution serves as a measure of the optimality of which the organism maximizes its global body area (nutrient absorption) while minimizing the risk of being illuminated (exposure to aversive stimuli). ABC found a high quality solution for the 8-city TSP with a high probability. However, it remains unclear whether intracellular communication among the branches of the organism is essential for computing. In this study, we conducted a series of control experiments using two individual cells (two single-celled organisms) to perform parallel searches in the absence of intercellular communication. We found that ABC drastically lost its ability to find a solution when it used two independent individuals. However, interestingly, when two individuals were prepared by dividing one individual, they found a solution for a few tens of minutes. That is, the two divided individuals remained correlated even though they were spatially separated. These results suggest the presence of a long-term memory in the intrinsic dynamics of this organism and its significance in performing sophisticated computing.

Original languageEnglish
Pages (from-to)1-10
Number of pages10
Issue number1
Publication statusPublished - 2013 Apr
Externally publishedYes


  • Chaos
  • Combinatorial optimization
  • Coupled oscillators
  • Natural computing
  • Neural network
  • Spatiotemporal dynamics

ASJC Scopus subject areas

  • Statistics and Probability
  • Modelling and Simulation
  • General Biochemistry,Genetics and Molecular Biology
  • Applied Mathematics


Dive into the research topics of 'Amoeba-based computing for traveling salesman problem: Long-term correlations between spatially separated individual cells of Physarum polycephalum'. Together they form a unique fingerprint.

Cite this