Some biological experiments show that the tubular structures of Physarum polycephalum are often analogous to those of Steiner trees. Therefore, the emerging Physarum-inspired Algorithms (PAs) have the potential of computing Steiner trees. In this paper, we propose two PAs to solve the Steiner Tree Problem in Graphs (STPG). We apply some widely-used artificial and real-world VLSI design instances to evaluate the performance of our PAs. The experimental results show that: 1) for instances with hundreds of vertices, our first PA can find feasible solutions with an average error of 0.19 , while the Genetic Algorithm (GA), the Discrete Particle Swarm Optimization (DPSO) algorithm and a widely-used Steiner tree approximation algorithm: the Shortest Path Heuristic (SPH) algorithm can only find feasible solutions with an average error above 4.96 ; and 2) for larger instances with up to tens of thousands of vertices, where our first PA, GA and DPSO are too slow to be used, our second PA can find feasible solutions with an average error of 3.69 , while SPH can only find feasible solutions with an average error of 6.42 . These experimental results indicate that PAs can compute Steiner trees, and it may be preferable to apply our PAs to solve STPG in some cases.
Use @math to signify the threshold value of edge conductivity. Edges with conductivities smaller than @math will be cut from the network. Ultimately, if there is a unique shortest path between the source node and the sink node, then this path can be found by iteratively updating edge conductivities and cutting edges @cite_26 . However, even though Physarum Solver can solve the shortest path problem, it cannot solve STPG directly because there are only two terminals in its model, which are the source node and the sink node, while there are multiple terminals in STPG. Thus, new PAs are required to solve STPG.
@cite_26
1964894406
Physarum polycephalum is a unicellular, multinucleate slime mold in the Mycetozoa group that exhibits remarkable capabilities, including the ability to construct efficient networks when foraging food [1]. The Physarum cell grows, as long as nutrition is abundant. When nutrition is limited, Physarum forms a network of interconnected veins; the veins are gel-like tubes in which the cytoplasm flows. It has been experimentally observed that, with two food sources, Physarum's tubular network often retracts to the shortest path between the food sources. Tero, Kobayashi and Nakagaki [2] proposed a model for the dynamics of the Physarum, which in the computer simulations converged to the shortest path on any initial network. We analytically prove that, under this model, the mass of the mold has to eventually converge to the shortest path in the initial network between the two food sources, independently of the structure of the initial network or of the initial mass distribution. This presentation is based on the work in [3,4] and is supported by the Italian Flagship Initiative "InterOmics" (PB.P05). References [1] Toshiyuki Nakagaki, Hiroyasu Yamada, Agota Toth: Maze-solving by an amoeboid organism. Nature 407:470 (2000) [2] Atsushi Tero, Ryo Kobayashi, Toshiyuki Nakagaki: A mathematical model for adaptive transport network in path finding by true slime mold. Journal of Theoretical Biology 244: 553-564 (2007) [3] Vincenzo Bonifaci, Kurt Mehlhorn, Girish Varma: Physarum can compute shortest paths. Journal of Theoretical Biology 309: 121-133 (2012) [4] Vincenzo Bonifaci: Physarum can compute shortest paths: A short proof. Information Processing Letters 113(1-2): 4-7 (2013)