title: An improved Physarum polycephalum algorithm for the shortest path problem.
abstract: Shortest path is among classical problems of computer science. The problems are solved by hundreds of algorithms, silicon computing architectures and novel substrate, unconventional, computing devices. Acellular slime mould P. polycephalum is originally famous as a computing biological substrate due to its alleged ability to approximate shortest path from its inoculation site to a source of nutrients. Several algorithms were designed based on properties of the slime mould. Many of the Physarum-inspired algorithms suffer from a low converge speed. To accelerate the search of a solution and reduce a number of iterations we combined an original model of Physarum-inspired path solver with a new a parameter, called energy. We undertook a series of computational experiments on approximating shortest paths in networks with different topologies, and number of nodes varying from 15 to 2000. We found that the improved Physarum algorithm matches well with existing Physarum-inspired approaches yet outperforms them in number of iterations executed and a total running time. We also compare our algorithm with other existing algorithms, including the ant colony optimization algorithm and Dijkstra algorithm.
authors: School of Computer and Information Science, Southwest University, Chongqing 400715, China.
authors: Xiaoge
authors: 0000-0001-6831-3175
authors: X
authors: Zhang
authors: School of Computer and Information Science, Southwest University, Chongqing 400715, China.
authors: Qing
authors: Q
authors: Wang
authors: Unconventional Computing Center, University of the West of England, Bristol BS16 1QY, UK.
authors: Andrew
authors: A
authors: Adamatzky
authors: Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hum, Kowloon, Hong Kong.
authors: Felix T S
authors: FT
authors: Chan
authors: School of Engineering, Vanderbilt University, Nashville, TN 37235, USA.
authors: Sankaran
authors: S
authors: Mahadevan
authors: School of Computer and Information Science, Southwest University, Chongqing 400715, China ; School of Engineering, Vanderbilt University, Nashville, TN 37235, USA.
authors: Yong
authors: 0000-0002-5481-5673
authors: Y
authors: Deng
mesh_terms: D000465:Algorithms; D008962:Models, Theoretical; D016839:Physarum polycephalum