  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.
