An anticipation mechanism for the shortest path problem based on Physarum polycephalum

Qing Wang, Xi Lu, Xiaoge Zhang, Yong Deng, Can Xiao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

In this paper, we put forward an anticipation mechanism for the existing Physarum-inspired shortest path finding method. The Physarum-based shortest path finding model can be implemented by an iterative algorithm and has wide applications in many fundamental network optimization problems. In this paper, we mainly focus on the Physarum-inspired shortest path tree model. Normally, we stop the program when the difference between two consecutive iterations is less than a predefined threshold. However, we do not know how to set the specific value for the threshold variable. In order to find out the optimal solution, we need to set the threshold as a very small number. This in turn will consume a lot of time. From this point of view, this algorithm lacks an efficient and reliable mechanism to judge when the optimal solution will be found. In this paper, we introduce an anticipation mechanism to address this issue. Numerical examples are used to demonstrate its reliability and efficiency.

Original languageEnglish
Pages (from-to)326-340
Number of pages15
JournalInternational Journal of General Systems
Volume44
Issue number3
DOIs
Publication statusPublished - 3 Apr 2015
Externally publishedYes

Keywords

  • anticipation mechanism
  • optimization
  • Physarum
  • shortest paths tree

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Theoretical Computer Science
  • Information Systems
  • Modelling and Simulation
  • Computer Science Applications

Cite this