游动的智能代理人

admin 发表于 2017年09月17日

游动的智能代理人

Eric Bonabeau，Guy Théráulaz

以蚂蚁和其它群居性昆虫为模型，计算机科学家开发了互相合作以解决复杂问题——例如在繁忙的通信网络中重新安排通信源——的软件代理人。

结群而居的昆虫——如蚂蚁、蜜蜂、黄蜂、白蚁等等——早就引起了从博物学家到艺术家的各色人等的极大兴趣。比利时诗人Maufice Maeterlinck曾写道，“是什么东西在支配着它们?是什么东西在维持秩序、预见未来、制定计划并保持平衡?”这的确是一些令人困惑不解的问题。

群落的每一只昆虫看来都有它自己的安排和计划，但是这些昆虫作为一个整体是有高度组织性的。把所有个体的活动综合成一个天衣无缝的整体似乎并不需要任何监督。事实上，研究群居性昆虫的行为的科学家们发现，昆虫群落一级上的合作基本上是自组织的：在许多场合中，个体之间的相互作用产生协调一致的行为。尽管这些相互作用可能很简单(例如一只蚂蚁就是紧跟着另一个蚂蚁留下来的路线而已)，但是它们合起来却可以解决棘手的问题(例如从通往一个食物源的无数条可能路径中找出最短的路径)。从一群群居性生物中产生出来的这样一种集体行为被称为“群集智能”(swarm intelligence)。

最近越来越多的研究人员着手设计新的方法以运用群集智能完成种种不同的任务。蚂蚁的觅食方式引导研究人员找到一种新的方法来为繁忙的通信系统中的网络通信重选路由。设法把一大堆食物运走的蚂蚁的合作相互作用可启发人们研究出更有利的机器人算法。昆虫把其群落中死去的同伴聚集成堆并清理出它们的幼虫的方式可能有助于分析银行资料。蜜蜂的分工或许可帮助工厂改进装配线的运行。

虚拟觅食

对群集智能进行的一项早期研究涉及到蚂蚁的觅食行为。布鲁塞尔自由大学的Jean-Louis Deneubourg及其同事证明，在自然界(以及在人们的厨房中)常可观察到的蚂蚁“道路”，其起因在于蚂蚁个体分泌出一种旨在吸引其它蚂蚁的化学物质，名为外激素。作为这一研究领域的开创者之一，Deneubourg也证明了蚂蚁留下其它蚂蚁能够跟踪行进的外激素径迹的过程为蚂蚁提供了一种巧妙方法来寻找蚁巢与食物源之间的最短路径。

在对阿根廷蚂蚁(Linepithema humile)进行的实验中，Deneubourg制造了一座有两个分支的桥——其中一个分支的长度是另一个分支的两倍——把蚁巢同食物源分隔开来。通常蚁群在几分钟之内就选择了较短的那条分支。

Deneubourg发现，蚂蚁在觅食的过程中留下外激素的径迹并循着这些外激素径迹行进。最先从食物源返回蚁巢的那一批蚂蚁肯定是在两个方向上(即从蚁巢到食物然后又从食物返回蚁巢)都沿着较短路径行进的蚂蚁。由于这条路径是第一个用外激素作了两次标记的路径，因此蚁巢内的蚂蚁都被吸引到这条路径上来。

然而，如果是在蚁群已接触了较长的路径之后再向它出示这条较短的分支，这些蚂蚁仍不会走这条捷径，因为较长的那条路径已经用外激素作了标记。但是在人工系统中，计算机科学家可以发明"外激素衰减"，从而克服这个问题:如果外激素迅速蒸发，那么较长的路径就难于维持稳定的外激素径迹。这样，即使较短的路径是后来才发现的，软件蚂蚁仍能够选择这条路径。这种性质具有一个很大的优点，那就是它可以防止系统收敛到一些并不高明的解法上。(在阿根廷蚂蚁中，外激素的浓度的确会减少，但下降的速率极为缓慢。)

在外激素蒸发的计算机模拟中(见图1)，研究人员向一个人工蚁群出示了若干个相同的食物源，但它们到蚁巢的距离远近不等。一开始这些虚拟蚂蚁随机地探索周围的坏境。然后它们就建立起把所有食物源同蚁巢连接起来的径迹。下一步它们只保持那些距蚁巢最近的食物源的路径，使它们能利用其中的食物供应。当这些食物源的食物被耗尽后，软件蚂蚁就去搜寻较远的食物源。

布鲁塞尔自由大学的计算机科学家Marco Dorigo和他的同事们推广了这一蚂蚁模型，设计出-种方法来解决著名的"推销员问题"(见图2)。这个问题要求找出经过若干个城市的一条最短路径，而且此路径经过每个城市恰好一次。这个问题之所以非常吸引人，是因为问题本身很容易表述，但却非常难于解决。它属于所谓"NP完备"问题，也就是说，它需要的计算步骤的数目其增长速度超过城市数目的任意有限次方。(NP代表non-deterministic polynomial，即"非确定性多项式"。)对于这类问题，人们通常尝试寻找一个足够好但不一定最好的答案(也就是说寻找一条足够近但可能不是最近的路径)。Dorigo证明，采用人工蚂蚁，他可以找到接近最优的路径。他把这些人工蚂蚁摆弄得使它们留下的外激素的浓度随它们行走过的总的距离而变化。

类似的方法已成功地用于解决其它一系列的优化任务。例如，人工蚂蚁为经典的二次分配问题提供了最优解峰。所谓二次分配问题，就是把制造一批产品的任务分配给若干家不同的工厂，使物品在各工厂间运送的总距离为最小。在一项相关的应用中，英国联合利华公司的David Gregg和美国新墨西哥州圣菲的Bios集团的Vincent Darley报导说他们已开发出一项以蚂蚁为基础的方站来减少在联合利华的一家大工厂中完成一定数量的工作所需的时间。该系统必须高效地安排各储罐、化学混合器、包装线及其它设备。

除了解决基本上属于静态的优化问题外，模拟蚂蚁的代理人也能够对付故障和动态的环境——例如某台机器出了问题的一家工厂。由于人工蚂蚁保存了外激素的径迹并不断地探索新的路径，因此它们会凭运气建立一项备用的方案，从而准备好对其环境的变化作出反应。这一性质可以解释真正的蚂蚁为何获得生态上的成功，而它对于许多应用场合也是至关重要的。

试考虑电话网络动态的不可预测性。从A地打到B地的电话通常必须经过一系列的中间结点(即交换站)，因此，为了使A地与B地接通，需要有一种机制来指挥通话下一步送往何处。这过程的算法显然应当避开通活拥挤的区域以尽量减少延迟。这样，在情况急剧变化的环境中，备用路径就变得特别宝贵了。当某一机场的天气恶劣或电视上的热线电话十分拥挤时，局部网络通信量将出现短时的剧增，这就要求迅速地把通话转移到网络中不那么拥挤的地方去。

为了应付这类情况，英国布里斯托尔的惠普公司研究实验室的Ruud Schoonderwoerd和两英格兰大学的Owen Holland发明了一种寻径方法，即让模拟蚂蚁的代理人在网络结点留下一些相当于“虚拟外激素”的信息位，以增强经过通信流较稀少的区域的路径。与此同时，设计一种蒸发机制对结点信息进行调节，使模拟蚂蚁不再选择那些穿过繁忙地区的路径。

具体地说就是，每个结点都存有一张寻径表，该表根据来话的目的地告诉它们下一步该往何处走。模仿蚂蚁的机器人根据网络的当前状况连续不断地调整寻径表内的各项(即分数)。如果一位代理人因为经过了网络的一个非常拥挤的区域而被耽搁了很长的时间，那么它就向寻表中将这个拥挤区域的那些项加入很少量的一点“外激素”，用数学语言来说就是，相应结点的分数只增加很少一点。一方面，如果代理人很快就从一个结点到了另一个结点，那么它将留下相当多的外激素(也就是大幅度增加相应的分数)，从而提高这条路径的利用率。寻径表内分数的计算应当产生这样的结果：即使条繁忙的路径可能有许多代理人从其上经过，但它们累积的“外激素”仍将少于一条没有多少代理人经过的通信量不多的路径上的累积外激素。

这个系统采用了一种数学蒸发——寻径表内的所有各项定期地减掉某一较小的值——以去掉那些落后的解。这一蒸发过程与模仿蚂蚁的代理人提高分数的方法联合起来，可以保证繁忙路径上的蒸发过程胜过增强的过程，而在通信不拥挤的路径上则是增强过程胜过蒸发过程。

蒸发与增强之间的平衡很容易被打破。当先前的一条比较好的路径开始变得拥挤时，走这条路径的代理人的时间将会被耽搁，这样蒸发就将胜过增强。很快地代理人将抛弃这条路径，转而寻找(或重新找到)替代的路径并利用它们。这样做有两方面的好处：当来话经过网络中比较畅通的区域传送时，不但可以让来话更快地传送到目的地，而且也可以使通信拥挤的区域逐渐摆脱通信量过大的重负。

若干家公司正在探索这一方法以处理它们的网络通信流。法国电信公司和英国电信公司早就带头把以蚂蚁为基础的寻径方法用到了它们的系统中。而在美国，MCI Worldcorn公司一直在研究人工蚂蚁，不仅用它来管理该公司的电话网，而且还用它来完成其它一些任务，如对客户的记帐收费等，不过，人工蚂蚁最终的用途大概是在因特网上。因特网的通信流是特别难于预测的。

为了应付网络上要求较高的各种局面，布鲁塞尔自由大学的Dorigo和他的同事Gianni Di Caro使蚂蚁代理人向更高级的方向发展：他们把其它若干种因素——包括信息从其出发地到目的地所需要的总的时间——也纳入考虑的范围内。(电话网络所用的方法仅考虑了从一个结点到另一个结点所用的时间，而且假定相反方向上的通信量是相同的。)模拟结果表明，在使通过能力达到最大并尽量减少延误这两项指标上，Dorigo和Dicaro的系统的性能优于其它所有的寻径方法。事实上，广泛进行的试验提示，以蚂蚁为基础的方法优于“首先打开最短路径”法（Open shortest Path First）。后者是目前英特网上使用的一个协议，它要求各个结点必须不停地彼此通报与它们连接的各线路的情况。

广泛的用途

群居性昆虫的其他行为引出了一大批各种各样的研究项目。计算机科学家们正在研究移动的大群昆虫，试图借此设计出控制一组机器人的不同方法。另外一个热门课题是合作搬运（见图3）。运用这类方法，工程师们可以设计出比较简单又便宜的机器人，通过他们的相互合作来完成越来越复杂的任务。还有一个项目涉及到分析金融资料的一种新方法，而该方法的基础则是当初用来解释蚂蚁如何把死蚂蚁聚集成堆以及如何清理蚂蚁幼虫的一个模型（参看图4）。通过考察蜜蜂如何灵活的分配它们的任务，可以获得一种更为有效的安排工厂内工作的方法（参看图5）。

其他的例子不胜枚举。运用关于黄蜂如何筑巢的知识，俄亥俄州载顿空军技术研究所的Dan Pctrovich设计出了一大群微小的机动卫星，它们能自行组合成一个较大的、事先确定的结构。安纳波尔的密执安环境研究所的H. Van Dyke Parunak正在运行各种各样的昆虫式软件代理人解决制造方面的问题，列如安排一家工厂的复杂供应商网络。卢特格斯大学的Paul B. Kantor开发出了一种以群聚智能为基础的方法以进行万维网和其他大网络上的信息检索。网络冲浪者如果属于某一用户“群”。那么他们在搜寻自己感兴趣的网站时，可以通过一群内其它成员在先前检索过程中留下的数字外激素（实际上就是评分）来获取信息。

事实上，群聚智能的潜力非常大。对于那些传统上需要控制和大量预编程序的系统。群聚智能提供了一种替代的系统设计方法，它依靠的是各个简单的代理人之间或间接的相互作用，具有自主和自给自足等优点。这样的相互作用使系统能够很快地适应迅速变化的条件。

但是这个领域仍然处于其萌芽阶段，由于研究人员缺乏对于大群昆虫的内部运行机制的详细了解，找出大群昆虫中个体如何相互作用的规则一直是一个巨大的挑战，而如果没有这方面的知识，计算机科学家就难于开发出合适的软件。此外，虽然以群聚智能为基础的方法已有效地用于执行多种多样的优化与控制任务，但已开发出的系统本质上都属于反应型的，对于那些需要借助深入推理方法才能解决的问题，这类系统缺乏必要的综合能力。而且，批评这一领域的人认为，使用自主的昆虫式代理人使它们所栖居的计算机系统产生无法预料的行为，然而，这一特性实际上可能是昆虫式代理人的一大优点，因为它有可能使这些系统具有解决未曾预料到的新问题的适应能力，而这种随机应变的灵活性正是传统软件所缺乏的。

许多未来学家顶测，很快芯片将植入到日常用品中，从信封到垃圾罐到纸币等。使所有这些芯片以一种有意义的方式彼此通信，将要求我们发明一种全新的群聚方法。正如高技术作家Kevin Kelly所说那样，“呆笨的部件，只要正确的连结起求成为一个群体，就将得出聪明的成果。”当然，奥妙在于如何把所有部件确地连接起来。

[郭凯声／译冉隆华／校]

游动的智能代理人1.png 游动的智能代理人2.png

游动的智能代理人3.png

图1外激素径迹使蚂蚁能够有效地觅食。两只蚂蚁同时离开蚁巢(上)，各自沿一条不同的路径行进并用它们的外激素给路径作标记。沿着较短的一条路径行进的蚂蚁首先返回(下)。由于现在这条路径上留下的外激素的量多了一倍，因此它所吸引的蚂蚁将多于另一条路径所吸引的蚂蚁。由于外激素蒸发的缘故，蚂蚁对不同的食物源采取依次搜寻的方式。图2在这幅计算机模拟图中，三个完全一样的食物源分布在离蚁巢远近不同的地方。经过漫无目标的一阵觅食后(a)，蚂蚁群开始从最近的食物源取得食物(b、c)。随着这些食物源中的食物逐渐减少，沿着其路径的外激素的浓度也通过蒸发而下降(d)。此后蚂蚁将探寻较远的食物源。借助于模拟蚂蚁的软件代理人，可以为网络通信迅速地重选路由。需要由A地发到B地的一项信息传送必须经过一系列中间结点。如果这两地之间的最短路径(橙色)有一部分出现堵塞，则该系统必须经过另一段替代路径(绿色)传送通信。软件代理人可以自动地进行这一重选路由的工作，其方式与蚂蚁搜寻不同食物源的方式相似(上图)。在蚂蚁与通信的对比中，拥挤的通信路径相当于已经被蚂蚁觅食一空的食物源。

游动的智能代理人5.png