论文标题
容量约束物理求解器
The Capacity Constraint Physarum Solver
论文作者
论文摘要
Physarum多头球灵感算法（PPA），也称为Physarum求解器，引起了极大的关注。通过将现实世界中的问题建模为具有网络流的图形并采用适当的方程式来计算图中的节点之间的距离，PPA可用于求解系统优化问题或用户平衡问题。但是，某些问题，例如最大流量（MF）问题，最小成本最大最低流量（MCMF）问题和链接负载的流量分配问题（CTAP），都需要流过链接以遵循容量约束。提出了一个新型框架，即受电容性多头化算法（CPPA）的动力，提出了一种新型框架，以允许容量限制PPA中的链路流量。为了证明CPPA的有效性，我们开发了CPPA的三个应用，即MF问题的CPPA（CPPA-MF），MCFC问题的CPPA和CPPA的CPPA，用于链接启用的流量分配问题（CPPA-CTAP）。在实验中，CPPA的所有应用都成功地解决了问题。与基线算法相比，其中一些证明了效率。实验结果证明了使用CPPA框架控制PPA中的链路流的验证是有效的。 CPPA也非常强大且易于实现，因为它可以在三种不同的情况下成功应用。提出的方法表明：具有控制通过PPA中链路流动的最大流量的能力，CPPA将来可以解决更复杂的现实世界问题。
Physarum polycephalum inspired algorithm (PPA), also known as the Physarum Solver, has attracted great attention. By modelling real-world problems into a graph with network flow and adopting proper equations to calculate the distance between the nodes in the graph, PPA could be used to solve system optimization problems or user equilibrium problems. However, some problems such as the maximum flow (MF) problem, minimum-cost-maximum-flow (MCMF) problem, and link-capacitated traffic assignment problem (CTAP), require the flow flowing through links to follow capacity constraints. Motivated by the lack of related PPA-based research, a novel framework, the capacitated physarum polycephalum inspired algorithm (CPPA), is proposed to allow capacity constraints toward link flow in the PPA. To prove the validity of the CPPA, we developed three applications of the CPPA, i.e., the CPPA for the MF problem (CPPA-MF), the CPPA for the MCFC problem, and the CPPA for the link-capacitated traffic assignment problem (CPPA-CTAP). In the experiments, all the applications of the CPPA solve the problems successfully. Some of them demonstrate efficiency compared to the baseline algorithms. The experimental results prove the validation of using the CPPA framework to control link flow in the PPA is valid. The CPPA is also very robust and easy to implement since it could be successfully applied in three different scenarios. The proposed method shows that: having the ability to control the maximum among flow flowing through links in the PPA, the CPPA could tackle more complex real-world problems in the future.
