转载

解密非凡的蚁群算法

Deborah Gordon 在斯坦福大学的校园里

　　英文原文：Decoding the Remarkable Algorithms of Ants

　　本文作者：Emily Singer。机器之心编译出品。参与：微胖，Angulia，郑劳蕾。

没有中心化的组织，蚁群何以进行高效地搜寻呢？生物学家 Deborah Gordon 揭开了其中的秘密，或许能改进计算机网络的能力。本文是《量子杂志》对她的采访。

　　蚁群协调能力非凡，它们能筑起穿过丛林的复杂小路，搭建精巧巢穴，以及根据所处环境调整觅食模式，所有这些都无需中央指挥。蚂蚁简单的个体行动产生出复杂的行为模式，斯坦福大学的生物学家 Deborah Gordon 希望揭开这背后的简单规则。

　　蚁群特别擅长集体搜索，能自动根据周围环境情况调整搜索策略，从而高效占领大面积地面。Gordon 发现这些蚁群的搜索算法和互联网背后的人造算法有相似之处。Gordon 希望能从蚁群解决此类问题的规律中找到一种新算法，从根本上降低大规模计算网络的成本，提升其性能。

　　在纽约州冷泉港的社会性昆虫会议上，我们碰到了 Gordon，稍后她立刻启程前往墨西哥继续研究树蚁寻路算法。以下是我们对话的精简版。

　　Gordon：我最初的兴趣是发育生物学，研究在没有任何中央控制的情况下，胚胎如何发育起来。当时，我正在寻找一种类似胚胎的系统，只有通过这个系统我才能观察到一切——理解能观察得到的对象要更容易些。因此，我选择了蚁群。如今，你可以看到很多发育中的胚胎。我那时可不是这样。

　　你研究亚利桑那州的同一个蚁群已经有三十多年了。你从一开始就注意到它们了吗？

　　Gordon：没有。研究之初，我对蚁群之间的差异很感兴趣，所以给蚁群做了记号以便来年继续观察。结果，我发现一些蚁群一年比一年壮大，所以我想搞清楚原因。那时，没人知道一个收获蚁群能活多久。我每年都回过头去重新检查蚁群——五年过去了，然后十年。我没有选择，只有继续研究。

　　什么让你印象最为深刻？

　　Gordon：我印象最深的是蚁群的协调性行动和单只蚂蚁的低效、不完整行动形成鲜明对比。易言之，蚁群可以完成很多工作，但是，不存在能干的个体蚂蚁。

　　比如，蚁群真的很擅长集体搜索工作；一群蚂蚁能在没有中央指挥的情况下彻底搜索整片地区。它们通过碰一下对方触角进行简单互动。当许多蚂蚁挤在一个小空间，会经常碰见，也倾向于铺条羊肠小道，大家都挤在一起。当宽敞空间里只有几只蚂蚁时，不经常碰面，蚂蚁们也会把路铺开点，覆盖更多地面。

　　就收获蚁群来说，我们已经知道蚂蚁会算出还有多久才会碰到携带食物回来的蚂蚁，据此决定是否离开蚁穴。这是一种正反馈形式；蚂蚁带回食物的速度越快，离开蚁穴的蚂蚁就越多。仅当交互频率（rate of interaction）够高时，蚂蚁才会决定离开蚁穴。整个体系帮助蚁群管理觅食行动，除非有足够多的食物值得出去一趟，否则它们不会离开蚁穴。

　　为什么你将收获蚁群的算法称为「anternet」？

　　Gordon：我和斯坦福的同事 Balaji Prabhakar 一起工作，目的就是搞清楚收获蚁群用来管理觅食的算法。他指出，算法和传输控制协议相似，后者是用来管理网络数据交通，确保在有足够带宽的情况下，数据不会丢失。两个系统都使用了简单的本地反馈来协调行动。我认为，我们可能找出蚂蚁用来解决工程问题的其他算法，这些算法目前还不为人所知。我对这个观点很感兴趣：进化可能会在不同系统中创造出用来解决相同问题的不同算法。

解密非凡的蚁群算法

　　收获蚁群

　　但是，多亏进化产生了有助于蚁群的算法，进化必须在集体层面，而不是个体层面发挥作用。

　　Gordon：从进化角度来看，蚁群才是真正的个体，是蚁群在繁殖，蚂蚁没有制造出更多的蚂蚁，但是蚁群制造出更多的蚁群。如果我们想了解蚂蚁行为进化之道，我们就必须观察蚁群。

　　单个蚂蚁做出的决定是如何改变整个蚁群的行为的？

　　Gordon：在沙漠中，水是极其有限的。蚂蚁身体中的水分会因其外出和四处爬行而被消耗，但能从它们的食物——种子中得到补充，所以它们不得不通过消耗水分（觅食）来补充水分（进食）。没有哪只蚂蚁会为了保存水分决定呆在巢穴内。

　　但是，蚂蚁之间互动的微小差异累加起来，就会形成蚁群觅食行动上的巨大差异，也会影响蚁群后代数量。我们发现自然会倾向于选择那些节约水资源的蚁群。我称之为「克制的奖励」。我认为这是首个能够追踪一个动物种群集体行为进化的研究。一个简单的身体局部动作之所以被选为蚂蚁相遇时的互动方式，是整个蚁群进化的产物。

　　进化是否还产生了其他的算法？

　　Gordon：我和另一位计算机科学家正在研究蚂蚁使用的寻路网络。墨西哥树蚁巢穴和食物源之间的路径因为树木、滕条和其他植物的缠结而显得异常复杂。这条小路总会被打断，比如树枝忽然断裂，或者有动物穿过，但它又能轻易地就被修复。它们怎样在如此短的时间——通常就数分钟——就在众多不同的选择中选择了这一条呢？

　　我们认为它们的策略是：不选择最短的路径，而是选择能够迅速重建和让蚁群恢复正常流动的路径。某种程度上，它们为了弹性，牺牲了人类所谓的效率。目前我们已建立起一个有意义的模型，正在实地工作中测试这个模型。

　　在计算方面，这会有多重要？

　　Gordon：计算中，信息数量和维护管理成本之间会有一个平衡。我们对蚁群进化而来的解决方案很感兴趣。我们有兴趣将蚂蚁解决方案与机算机系统中的寻路算法——在寻求最直或最短路径时，需要大量的信息——进行类比。比如你在陌生地方开车，路口被堵了。如果带了地图，你可以找到其他的路。但是，如果你没有任何路线信息、没有任何地址名称，怎么办？

　　群体搜索就面临着类似的难题。现在，机器人学研究中，人们对使用最廉价的机器人——仅需尽可能少的信息就能与人类协同工作——很感兴趣。这样的系统会更具稳健性不容易崩溃。相比派遣一个足够复杂的机器人去探索火星或者在着火大楼进行搜寻工作，派遣一组即使单个出现故障，团队仍能正常协作的廉价机器人更有意义。也许蚁群还进化出许多人类未知的办法来解决类似问题。我们所能做的就是继续观察。

　　蚁群如何随着时间而变化？

　　Gordon：随着群体越来越衰老，规模越来越大，收获蚁群行为也会改变。群体行为的某些方面仅取决于集体规模大小。就收获蚁而言，单个工蚁（除蚁后外）只能活一年，所以不是蚂蚁越来越老，越来越智慧，而是整个蚁群。这个谜团促使我开始研究交互网络，因为当时我正在寻找某种事情，虽然规模变大后的蚁群方式还是会用老办法去做这件事，但会产生不同结果。

　　比如，我是一只蚂蚁，遵循着上述规则，在给定频率下遇到其他蚂蚁时，我会做的事情是X。在大蚁群中，我会遇到更多的蚂蚁。如果蚁群的规模变大了，遵循着相同的规则（去做这件事情）也许会产生不同的结果，因为与其他蚂蚁互动的频率发生了改变。

　　我们身处巨大的网络之中——互联网，人类大脑，我也因此对其他系统很感兴趣。网络行为如何随着网络规模扩大而变化？

　　如何变化呢？

　　Gordon：我发现，年长的蚁群比年轻的蚁群稳定得多。如果你制造一个干扰，比如在他们中间制造一点骚乱——我放了一叠牙签——年长的蚁群最后忽视了这个扰乱，重新开始觅食。我认为，在这些拥有更多觅食蚂蚁的蚁群中，蚁群会优先选择继续觅食而不是回应扰乱。

　　你也正在探索蚁群和神经元的相似之处。

　　Gordon：一只蚂蚁会积累近期互动信息，决定做什么，一个神经元也会积累来自其他神经元的近期刺激，决定是否放电。目前，神经科学已有一个复杂模型框架来理解该系统运作原理。我正在与理论神经科学家合作，把这个框架应用到蚁群上。

　　你发起了一个「公民科学计划（ citizen science project）」鼓励公众研究不同种类的蚁群，研究新蚂蚁种类有什么好处呢？

　　Gordon：大约 14000 种蚁群中，仅有 50 种被研究过，研究新种类有可能会发现新算法。我们为学生开发了一个小型工具箱来观察不同种类的蚁群如何进行集体搜寻。当孩子们用工具尝试观察不同蚂蚁种类时，他们也许能从中发掘一些新东西。

　　转载请联系公众号：机器之心（almosthuman2014）获得授权，个人微信号“jiqizhixin2014”

正文到此结束