.png){kind=icon}
返回
An Accelerated Physarum Solver for Network Optimization
.png){kind=icon}
PRE
AI
DOI：10.1109/TCYB.2018.2872808.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Bio-inspired algorithm
network optimization
Physarum solver
shortest path problem
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.5
论文数:
1.1W
被引数:
5.0W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容