In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks. For the shortest path problem, a mathematical model for the evolution of the slime is available and it has been shown in computer experiments and through mathematical analysis that the dynamics solves the shortest path problem. In this paper, we introduce a dynamics for the network design problem. We formulate network design as the problem of constructing a network that efficiently supports a multi-commodity flow problem. We investigate the dynamics in computer simulations and analytically. The simulations show that the dynamics is able to construct efficient and elegant networks. In the theoretical part we show that the dynamics minimizes an objective combining the cost of the network and the cost of routing the demands through the network. We also give alternative characterization of the optimum solution.
翻译:在湿实验室实验中,粘泥模模具的Physarum 多元石块证明了其解决最短路径问题和设计高效网络的能力。对于最短路径问题,有一个关于粘液进化的数学模型,在计算机实验和数学分析中显示,动态解决了最短路径问题。在本文中,我们为网络设计问题引入了动态。我们将网络设计设计设计设计设计设计作为构建一个有效支持多通量流动问题的网络的问题。我们研究了计算机模拟和分析中的动态。模拟表明,动态能够建设高效和优雅的网络。在理论部分,我们显示,动态最大限度地降低了将网络成本和通过网络处理需求的成本相结合的目标。我们还对最佳解决方案作了其他描述。