关键词：群体行为，群体决策，分布式算法，随机游走
论文题目：Distributed algorithms from arboreal ants for the shortest path problem
论文链接：https://www.pnas.org/doi/10.1073/pnas.2207959120
生物系统，如蚂蚁踪迹网络，是自然界中分布式算法的迷人例子，通常使用个体之间简单的局部交互来寻找全局最优解，而无需中央控制。树栖龟蚁在热带森林的树冠中筑巢和觅食，它们的踪迹网络被限制在由缠结的树枝和藤蔓形成的自然网络上，并且没有任何蚂蚁拥有关于该网络的任何全局信息。
龟蚁在穿越树枝和藤曼时会释放一种挥发性的信息素。在每个自然网络的顶点上，蚂蚁会基于当前信息素水平的决策规则来选择要遍历的下一条边。并且，蚂蚁在网络中是双向移动。在以往的实地研究中，观察到踪迹网络近似地最小化顶点的数量，解决了流行的最短路径问题的变体，而没有任何中央控制并且具有最小的计算资源。
PNAS这篇论文提出了一个生物学上较为合理的模型，该模型是基于图的强化随机游走的变体。能够解释上述观察结果，并为最短路径问题及其变体提出了新的算法。
这个研究通过模拟和分析表明：当蚂蚁的移动速率不改变时，动力学收敛到具有最小顶点数的路径，就像实际观察到的那样；当速率随时间增加时，群体动力学收敛于最短路径。因此蚁群只需增加移动速率就可以解决最短路径问题。文章还证明了，为了保证收敛到最短路径，双向移动和一个按信息素水平比例划分流的决策规则是必要的，但使用其它决策规则也可以收敛到近似短路径。
图2. 当流入流量不随时间变化时，由线性决策规则控制的流体动力学收敛于具有最小泄漏的路径。
集智斑图顶刊论文速递栏目上线以来，持续收录来自Nature、Science等顶刊的最新论文，追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能，每周通过微信服务号「我的集智」推送论文信息。扫描下方二维码即可一键订阅：
