15.8 蚂蚁的算法天赋

意大利米兰的一组研究员提出了一些新的进化和学习方法。他们的方法填补了艾克利所提到的「所有可能的计算空间」中的一些空白。这些研究员们把自己的搜索方法称为「蚁群算法」,是因为他们受到了蚁群集体行为的启迪。

蚂蚁把分布式并行系统摸了个门清。蚂蚁既代表了社会组织的历史,也代表了计算机的未来。一个蚁群也许包含百只万工蚁和数百只蚁后,它们能建起一座城市,尽管每个个体只是模模糊糊地感觉到其他个体的存在。蚂蚁能成群结队地穿过田野找到上佳食物,仿佛它们就是一只巨大的复眼。它们排成协调的并行行列,穿行在草木之间,并共同使其巢穴保持衡温,尽管世上从未有任何一只蚂蚁知道如何调节温度。

广告:个人专属 VPN,独立 IP,流量大,速度快,连接稳定,多机房切换,每月最低仅 5 美元

一个蚂蚁军团,智愚而不知测量,视短而不及远望,却能迅速找到穿越崎岖地面的最短路径。这种计算正是对进化搜索的完美映射:一群无知而短视的个体们在数学意义上崎岖不平的地形上同时作业,试图找出一条最优路径。蚁群就是一个并行处理机。

真正的蚂蚁通过名为信息素的化学系统来彼此交流。蚂蚁在彼此之间以及自己的环境中散发信息素。这些芳香的气味随着时间的推移而消散。它还能通过一连串的蚂蚁来接力传播:它们嗅到某种气味,复制它并传给其它蚂蚁。信息素可以被看作是在蚂蚁系统内部传播或交流的信息。

米兰小组(成员为阿尔贝托·克罗尼、马可·多利古和维多里奥·马涅索)按照蚂蚁的逻辑构建了方程式。他们的虚拟蚂蚁是一大群并行运转的愚笨处理器。每个虚拟蚂蚁有一个微不足道的记忆系统,可以进行本地沟通。如果干得好的话,所获得的奖赏也以一种分布式计算的方式与其他同类分享。

意大利人用标准的旅行商问题来测试他们的蚂蚁机。这个问题是这样描述的:你需要拜访很多城市,但每座城市只能拜访一次,那么哪条路径最短?为了求解这个问题,蚁群中的每个虚拟蚂蚁会动身从一座城市漫游到另一座城市,并在沿途留下信息素的气味。路径越短的话,信息素挥发得越少。而信息素的信号越强,循迹而来的蚂蚁就越多。那些较短的路径由此得到自我强化。运行5000回合之后,蚂蚁的群体思维就会进化出一条相当理想的路径。

米兰小组还尝试了各种变化。如果虚拟蚂蚁都由一座城市出发或均匀分布在各个城市,会有什么不同吗?(分布的效果要好一些。)一个回合中虚拟蚂蚁的数量会有影响么?(越多越好,直到蚂蚁与城市的数量比为1: 1。)通过改变参数,米兰小组得到了一系列蚂蚁搜索算法。

蚂蚁算法是拉马克搜索的一种形式。当某只蚂蚁偶然发现一条短路径,这个信息通过信息素的气味间接地传播给其它虚拟蚂蚁。这样,单只蚂蚁毕生的学习所得就间接地成为整个蚁群信息遗产的一部分。蚂蚁个体把它学习到的知识有效地传播给自己的群体。与文化教导一样,传播也是拉马克搜索的一部分。艾克利说:「除了交配,信息交换还有许多方式。比如晚间新闻。」

无论是真实的蚂蚁,还是虚拟的蚂蚁,它们的聪明在于,投入「传播」的信息量非常少,范围非常小,信号也非常弱。将弱传播引入进化的提法相当有吸引力。即使地球的生物界中存在拉马克进化,那它也一定被埋藏得很深。不过,仍然存在充满了各种稀奇古怪算法的空间,各种拉马克式的传播尽可以在那里找到用武之地。我听说有的程序员整天在鼓捣「弥母(文化基因)」式的进化算法——即模仿思想流(弥母)从一个大脑进入另一个大脑,试图捕捉到文化革命的精髓和力量。连接分布式计算机节点的方法有千千万万,迄今为止,只有极少数的方法(如蚂蚁算法)被人们考察过。

直到1990年,并行计算机还遭到专家们的嘲笑,认为它尚有很多地方值得商榷,过于专业,属于狂热派的玩物。它们结构混乱,难以编程。但狂热派却不这么看。1989年,丹尼·希利斯与一个知名计算机专家公开打赌,预测到1995年,并行机每月处理的数据量将超过串行机。看来他是对的。当串行计算机由于其狭窄的冯·诺依曼通道不堪复杂任务的重负而痛苦呻吟时,专家的看法一夜之间就发生了变化,并迅速席卷了整个计算机产业。彼得·丹宁[1]在《科学》杂志上撰文(《高度并行的计算》[2],1990年11月30日),称,「解决高级科学问题所需的计算速度,只能通过高度并行的计算架构来获得。」斯坦福大学计算机科学系的约翰·柯扎[3]更直截了当,「并行计算机是计算的未来。句号。」

然而,并行计算机还是很难掌控。并行软件是水平的、并发的、错综复杂的因果网络。你无法从这样的非线性特性中找出缺陷所在,它们都隐藏了起来。没有清晰的步骤可循,代码无从分解,事件此起彼伏。制造并行计算机很容易,但要为其编程却很难。

并行计算机所面对的挑战是所有分布式群系统都会面对的——包括电话网络、军事系统、全球24小时金融网络,以及庞大的计算机网络。它们的复杂性考验着我们掌控它们的能力。「为一个大规模并行机编程的复杂度可能超过了我们的能力。」汤姆·雷对我说。「我认为我们永远也写不出能充分利用并行处理能力的软件。」

并行的愚昧的小东西能够「写」出比人类更好的软件,这让雷想到了一个能得到我们想要的并行软件的办法。「你看,」他说,「生态的相互作用就是并行的最优化技术。多细胞生物本质上就是在宇宙尺度上运行大规模的并行代码。进化能够『想出』我们穷尽一生也无法想清楚的并行编程。如果我们能够进化软件,那我们就能大大往前迈进一步。」对于分布式网络这类事物,雷说,「进化是最自然的编程方式。」

自然的编程方式!这听起来真让人有些泄气。人类就应该只做自己最擅长的工作:那些小而灵的、快而精的系统。让(人工注入的)自然进化去做那些杂乱无章的大事吧。

彼得·丹宁(Peter J.Denning, 1942~):美国计算机科学家,多产的作家。他最有名的发明是提出了工作集模型(Working-Set Model),该模型成为所有内存管理策略的参考标准。

《高度并行的计算》:Highly Parallel Computation

约翰·柯扎(John Koza):美国计算机科学家,斯坦福大学顾问教授,以利用遗传算法对复杂问题进行优化的开拓性工作而著称。他是科学游戏公司的创始人之一,该公司开发了美国博彩业的计算机系统。