The Power of Many: A Physarum Swarm Steiner Tree Algorithm

This paper presents a novel explore-and-fuse approach to solving a large array of problems that cannot be solved by traditional divide-and-conquer. This approach is inspired by Physarum, a unicellular slime mold capable of solving the traveling salesman and Steiner tree problems. Besides exhibiting individual intelligence, Physarum can also share information with other Physarum organisms through fusion. Inspired by the characteristics of Physarum, we spawn many Physarum organisms to explore the problem space in parallel, each gathering information and forming partial solutions pertaining to a local region of the problem space. When the organisms meet, they fuse and share information, eventually forming one organism which has a global view of the problem and can apply its intelligence to find an overall solution to the problem. We demonstrate this novel approach on the NP-hard Steiner tree problem, developing the Physarum Steiner Algorithm. This algorithm is of particular interest due to its ability to leverage parallel processing, avoid obstacles, and operate on various shapes and topological surfaces including the rectilinear grid.