Physarum Optimization: A Biology-Inspired Algorithm for the Steiner Tree Problem in Networks

TLDR

Biological insights can inspire new optimization methods for longstanding computational problems. The study develops a low‑complexity, highly parallel Physarum Optimization algorithm, based on the slime mold *Physarum polycephalum*, to solve the NP‑hard Steiner tree problem in network design. The algorithm is implemented as a cellular computing model of *Physarum polycephalum* and evaluated on the Steiner tree problem and the minimal exposure problem in wireless sensor networks. Complexity analysis and simulations demonstrate that the Physarum Optimization algorithm achieves good performance with low complexity, and its core mechanism offers a promising basis for practical distributed network‑design algorithms.

Abstract

Using insights from biological processes could help to design new optimization techniques for long-standing computational problems. This paper exploits a cellular computing model in the slime mold physarum polycephalum to solve the Steiner tree problem which is an important NP-hard problem in various applications, especially in network design. Inspired by the path-finding and network formation capability of physarum, we develop a new optimization algorithm, named as the physarum optimization, with low complexity and high parallelism. To validate and evaluate our proposed models and algorithm, we further apply the physarum optimization to the minimal exposure problem which is a fundamental problem corresponding to the worst-case coverage in wireless sensor networks. Complexity analysis and simulation results show that our proposed algorithm could achieve good performance with low complexity. Moreover, the core mechanism of our physarum optimization also may provide a useful starting point to develop some practical distributed algorithms for network design.