关键词:群体行为,群体决策,分布式算法,随机游走



论文题目:Distributed algorithms from arboreal ants for the shortest path problem
论文来源:PNAS
论文链接:https://www.pnas.org/doi/10.1073/pnas.2207959120

生物系统,如蚂蚁踪迹网络,是自然界中分布式算法的迷人例子,通常使用个体之间简单的局部交互来寻找全局最优解,而无需中央控制。树栖龟蚁在热带森林的树冠中筑巢和觅食,它们的踪迹网络被限制在由缠结的树枝和藤蔓形成的自然网络上,并且没有任何蚂蚁拥有关于该网络的任何全局信息。

龟蚁在穿越树枝和藤曼时会释放一种挥发性的信息素。在每个自然网络的顶点上,蚂蚁会基于当前信息素水平的决策规则来选择要遍历的下一条边。并且,蚂蚁在网络中是双向移动。在以往的实地研究中,观察到踪迹网络近似地最小化顶点的数量,解决了流行的最短路径问题的变体,而没有任何中央控制并且具有最小的计算资源。

PNAS这篇论文提出了一个生物学上较为合理的模型,该模型是基于图的强化随机游走的变体。能够解释上述观察结果,并为最短路径问题及其变体提出了新的算法。

这个研究通过模拟和分析表明:当蚂蚁的移动速率不改变时,动力学收敛到具有最小顶点数的路径,就像实际观察到的那样;当速率随时间增加时,群体动力学收敛于最短路径。因此蚁群只需增加移动速率就可以解决最短路径问题。文章还证明了,为了保证收敛到最短路径,双向移动和一个按信息素水平比例划分流的决策规则是必要的,但使用其它决策规则也可以收敛到近似短路径。

图1. 具有平行路径的图中的前向流和反向流。

图2. 当流入流量不随时间变化时,由线性决策规则控制的流体动力学收敛于具有最小泄漏的路径。


图3. 非线性二次型决策准则下的漏出与增入效应。


复杂科学最新论文


集智斑图顶刊论文速递栏目上线以来,持续收录来自Nature、Science等顶刊的最新论文,追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能,每周通过微信服务号「我的集智」推送论文信息。扫描下方二维码即可一键订阅:




推荐阅读



点击“阅读原文”,追踪复杂科学顶刊论文