蚂蚁觅食和互联网算法

zhixun

2012-8-28, 11:10 | 积木

人类和蚂蚁的区别是什么？蚂蚁没有互联网。

相对于拥有创造性思维的人类，蚂蚁看起来不过是依赖于本能的生物。不过，斯坦福大学两位科学家发现，蚂蚁比我们想象的要聪明的多，虽然它们没有发明互联网，但是却懂得互联网上的算法。在斯坦福大学网站上，讲述了这个有趣的发现。

生物学教授 Deborah Gordon 在观察亚利桑那州的农田蚁时，发现了它们在寻食时的特别行为，于是找到了计算机科学家 Balaji Prabhakar 探讨这件事情。Balaji Probhakar 虽然是网络文件传输方面的专家，但是并没有立刻意识到这跟计算机有何关联。到了第二天，灵感突然来袭，他突然想到，蚂蚁的行为和互联网上文件传输竟然非常相似。Prabhaker 说，“蚂蚁用来了解可获得食物数量的算法，从本质上和 TCP 中使用的算法一样。”

TCP，即传输控制协议，是互联网最重要的协议之一。它被用来管理互联网上的数据拥塞。正是由于 TCP 协议，我们的网络才能从最早的几十个节点发展到今天的上亿个节点。它的工作原理是这样的：作为数据源的 A 将文件传送到终点 B，文件被分解成无数的数据包。当 B 接受到一个数据包后，向 A 发送一条确认，以表示数据包已经送达。

这样做的好处是可以避免数据拥塞。如果 B 确认速度慢，证明现在带宽不够，A 可以根据情况减缓数据传输；如果 B 确认的速度快，A 则会加快传输速度。通过这个过程可以确定可使用的带宽，并相应增减传输速度。

Gordon 发现农田蚁的行为非常类似。它们派出觅食蚁前去觅食。如果食物多的话，觅食蚁会很快回来，然后更多的蚂蚁离开巢穴去觅食；如果觅食蚁空手回来，蚁群的觅食行为将减少，甚至停止。

根据这种情况，Probkahar 编写了一个算法，根据食物的数量来预测蚁群的觅食行为，而 Gordon 通过实验来进行证实。他们发现，以 TCP 为基础的算法几乎准确的预测了蚂蚁的行为。

“蚂蚁们发现了我们熟知的算法，而且他们已经使用了百万年了”。Prabhakar 说。

他们还发现了蚂蚁遵循 TCP 算法的另两个规则。一个叫做慢启动，在数据传输开始的时候，数据源会发出大量的数据包来估测带宽；同样，当蚁群开始觅食之前，他们会放出觅食蚁去侦测食物数量。

另一个叫做超时。当数据传输的链接中断或被干扰，数据源会停止发生数据包；同样，当觅食蚁超过 20 分钟没有回巢，其它的觅食蚂蚁将不会离开巢穴。

Gordon 则认为，在蚁群行为如何帮助我们设计网络系统上，科学家们刚刚接触到了表层部分。目前有 1 万 1 千种蚂蚁，生活在各种环境中，处理着各种不同的生态问题，蚂蚁们做事的方式是我们所料想不到的，但是可能被用于计算机系统中。每个蚂蚁的能力有限，但是蚁群能够完成复杂的任务。

“因此蚂蚁的算法必定是简单、分布式、可扩展的，这正是我们在设计庞大的人工分布式系统时所需要的特性。”她说，“我认为，当我们更多的了解不同类型的蚂蚁是如何规范自身行为后，能够为网络算法找到许多有用的例子。”

蚂蚁和算法，看起来是不可思议的联系，但是自然的奇妙之处常常超越我们的想象。人类发现的各种算法和模型，看似是自己思维的创造，却常常能够在自然中找到各种实例。这不禁让人产生奇特的幻想。或者，我们生活的世界真的是一部由算法驱动的机器，谁知道呢？