Title: An improved Physarum polycephalum algorithm for the Steiner tree problem

Authors: Yi Zhang; Zhengquan Yang; Xin Qi

Addresses: College of Electrical and Computer Science, Jilin Jianzhu University, No. 5088 Xincheng Street, Changchun City, China ' College of Electrical and Computer Science, Jilin Jianzhu University, No. 5088 Xincheng Street, Changchun City, China ' Jilin International Studies University, No. 3658 Jingyue Dajie, Changchun, China; Jilin Jianzhu University, No. 5088 Xincheng Street, Changchun City, China

Abstract: In this paper, we present an improved algorithm based on the Physarum polycephalum model (PPM) to solve Steiner tree problem (STP). We use the improved method to calculate the minimum Steiner tree according to the faster convergence speed and higher precision of the origin PPM in solving the problem of network structure. We can maintain a stable output when calculating the optimal value in this model. Experiments show that the model has strong convergence efficiency, and the optimal value can be obtained in a small number of iterations. We can get more improvements compared with the optimal solutions of some datasets.

Keywords: Physarum polycephalum; Steiner tree problem; integrated circuits routing.

DOI: 10.1504/IJBIC.2022.120753

International Journal of Bio-Inspired Computation, 2022 Vol.19 No.1, pp.40 - 47

Received: 11 May 2021
Accepted: 30 Aug 2021
Published online: 07 Feb 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article