蚂蚁觅食和互联网算法

特稿

2012-08-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 千种蚂蚁,生活在各种环境中,处理着各种不同的生态问题,蚂蚁们做事的方式是我们所料想不到的,但是可能被用于计算机系统中。每个蚂蚁的能力有限,但是蚁群能够完成复杂的任务。

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

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

登录,参与讨论前请先登录

评论在审核通过后将对所有人可见

正在加载中