An Accelerated Physarum Solver for Network Optimization

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 com...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on cybernetics 2020-02, Vol.50 (2), p.765-776
Main Authors: Gao, Cai, Zhang, Xiaoge, Yue, Zhiying, Wei, Daijun
Format: Article
Language:English
Subjects:
<italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">Physarum solver
Acceleration
Adaptation models
Algorithms
Bio-inspired algorithm
Complexity
Computational modeling
Conductivity
Convergence
Electron tubes
Graph theory
Linear equations
Mathematical analysis
Mathematical model
Network management systems
network optimization
Nodes
Optimization
Phase transitions
shortest path problem
Shortest-path problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 realworld traffic networks are used to compare the performance of accelerated Physarum solver to the other two state-of-the-art algorithms.
ISSN:2168-2267
2168-2275
DOI:10.1109/TCYB.2018.2872808