An Improved Physarum polycephalum Algorithm for the Shortest Path Problem
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...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/487069 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832551802860470272 |
|---|---|
| author | Xiaoge Zhang Qing Wang Andrew Adamatzky Felix T. S. Chan Sankaran Mahadevan Yong Deng |
| author_facet | Xiaoge Zhang Qing Wang Andrew Adamatzky Felix T. S. Chan Sankaran Mahadevan Yong Deng |
| author_sort | Xiaoge Zhang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-58dfc048699f46bea9c0388a492efe9b |
| institution | Kabale University |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-58dfc048699f46bea9c0388a492efe9b2025-02-03T06:00:28ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/487069487069An Improved Physarum polycephalum Algorithm for the Shortest Path ProblemXiaoge Zhang0Qing Wang1Andrew Adamatzky2Felix T. S. Chan3Sankaran Mahadevan4Yong Deng5School of Computer and Information Science, Southwest University, Chongqing 400715, ChinaSchool of Computer and Information Science, Southwest University, Chongqing 400715, ChinaUnconventional Computing Center, University of the West of England, Bristol BS16 1QY, UKDepartment of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hum, Kowloon, Hong KongSchool of Engineering, Vanderbilt University, Nashville, TN 37235, USASchool of Computer and Information Science, Southwest University, Chongqing 400715, ChinaShortest 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.http://dx.doi.org/10.1155/2014/487069 |
| spellingShingle | Xiaoge Zhang Qing Wang Andrew Adamatzky Felix T. S. Chan Sankaran Mahadevan Yong Deng An Improved Physarum polycephalum Algorithm for the Shortest Path Problem The Scientific World Journal |
| title | An Improved Physarum polycephalum Algorithm for the Shortest Path Problem |
| title_full | An Improved Physarum polycephalum Algorithm for the Shortest Path Problem |
| title_fullStr | An Improved Physarum polycephalum Algorithm for the Shortest Path Problem |
| title_full_unstemmed | An Improved Physarum polycephalum Algorithm for the Shortest Path Problem |
| title_short | An Improved Physarum polycephalum Algorithm for the Shortest Path Problem |
| title_sort | improved physarum polycephalum algorithm for the shortest path problem |
| url | http://dx.doi.org/10.1155/2014/487069 |
| work_keys_str_mv | AT xiaogezhang animprovedphysarumpolycephalumalgorithmfortheshortestpathproblem AT qingwang animprovedphysarumpolycephalumalgorithmfortheshortestpathproblem AT andrewadamatzky animprovedphysarumpolycephalumalgorithmfortheshortestpathproblem AT felixtschan animprovedphysarumpolycephalumalgorithmfortheshortestpathproblem AT sankaranmahadevan animprovedphysarumpolycephalumalgorithmfortheshortestpathproblem AT yongdeng animprovedphysarumpolycephalumalgorithmfortheshortestpathproblem AT xiaogezhang improvedphysarumpolycephalumalgorithmfortheshortestpathproblem AT qingwang improvedphysarumpolycephalumalgorithmfortheshortestpathproblem AT andrewadamatzky improvedphysarumpolycephalumalgorithmfortheshortestpathproblem AT felixtschan improvedphysarumpolycephalumalgorithmfortheshortestpathproblem AT sankaranmahadevan improvedphysarumpolycephalumalgorithmfortheshortestpathproblem AT yongdeng improvedphysarumpolycephalumalgorithmfortheshortestpathproblem |