An Accelerated Physarum Solver for Network Optimization

Cai Gao, Xiaoge Zhang, Zhiying Yue, Daijun Wei

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

Abstract

As a novel computational paradigm, Physarum solver has received increasing attention from the researchers in tackling a plethora of network optimization problems. However, the convergence of Physarum solver is grounded by solving a system of linear equations iteratively, which often leads to low computational performance. Two factors have been highlighted along the process: 1) high time complexity in solving the system of linear equations and 2) extensive iterations required for convergence. Thus, Physarum solver has been largely restricted by its unsatisfactory computational performance. In this paper, we aim to address these two issues by developing two enhancement strategies: 1) pruning inactive nodes and 2) terminating Physarum solver in advance. First, extensive nodes and edges become and stay inactive after a few iterations in identifying the shortest path. Removing these inactive nodes and edges significantly decreases the graph size, thereby reducing computational complexity. Second, we define a transition phase for edges. All of the paths experiencing such a transition phase are dynamically aggregated to form a set of near-optimal paths among which the optimal path is included. Depth-first search is then leveraged to identify the optimal path from the near-optimal paths set. Earlier termination of Physarum solver saves considerable iterations while guaranteeing the optimality of the found solution. Empirically, 20 randomly generated sparse and complete graphs with network sizes ranging from 50 to 2000 as well as two real-world traffic networks are used to compare the performance of accelerated Physarum solver to the other two state-of-the-art algorithms.

Original languageEnglish
Pages (from-to)765-776
JournalIEEE Transactions on Cybernetics
Volume5
Issue number2
DOIs
Publication statusAccepted/In press - 2018
Externally publishedYes

Keywords

  • Acceleration
  • Adaptation models
  • Bio-inspired algorithm
  • Computational modeling
  • Conductivity
  • Electron tubes
  • Mathematical model
  • network optimization
  • Optimization
  • Physarum solver
  • shortest path problem

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'An Accelerated Physarum Solver for Network Optimization'. Together they form a unique fingerprint.

Cite this