作者：Marianne Freiberger
蚂蚁是一种令人惊奇的动物。
如果你在地上放一些好吃的食物，它们可以在很短时间内在食物和巢穴间建立高速通路，并将食物拖回去。尽管它们的视力很差甚至没有视力，也不能用声音交流，智商也不高。
蚂蚁善于构造高效的通路
今天，蚁群优化算法（ACOs）已被广泛用于统筹优化问题：无论是安排货车的送货路线，还是安排医生的时间表。
蚂蚁是如何做到的？
蚂蚁使用一种被称为信息素（费洛蒙）的物质进行交流。 蚂蚁在爬行时，会在地面上留下信息素， 布鲁塞尔自由大学的马可 多里戈（Marco Dorigo）解释道， 如果地上有信息素的痕迹，它们就更愿意沿着信息素形成的路径走下去。 如果足够多的蚂蚁都喜欢沿着这一路径爬行，那么将形成正反馈效应：这些蚂蚁释放的信息素会吸引更多的蚂蚁走这条路，而更多的蚂蚁会在这条路上留下更更多的信息素，结果就会吸引过来更更更多的蚂蚁。
有趣的是，生物学家早已揭示：只需这个机制，蚁群便可找到从食物源到巢穴的捷径。1990 年，让 路易 迪诺伯（Jean-Louis Deneubourg）和他的合作者给蚂蚁们提供了两条通往食物的路线，一条的长度是另一条的两倍。所有的蚂蚁之前都不曾到过食物所在地。结果表明，所有的蚂蚁都选择了更短的路径。
显然，蚂蚁有某种的天生测距能力来选择路径。但是如果只是这样，那么对于两条长度相同的路径，应该看不出蚂蚁更加喜欢哪条路径。然而实验表明，即便是对于长度相同的两条路径，蚂蚁仍然会偏爱其中一条。
生物学家认为，你只能靠信息素来解释这个现象， 多里戈说。刚开始，蚂蚁会随机选择其中一条路径；一旦某条路上的信息素比较多，蚂蚁就会偏爱这一条路。当一条路的长度是另一条的两倍时，短的那条可以更快地收集信息素：因为走这条路的蚂蚁会更快地到达终点并返回，依次往复，同样长的时间内可以重复更多次。这样长度更短的路径收集信息素的速度更快并产生正反馈。
如果所有路径长度一样，蚂蚁选择两条路的概率都是 50%。但是就像扔一枚硬币一样，当你扔硬币的次数不是无穷大时，你并不能保证正面朝上的概率是精确的 50%，随机涨落会导致其中一条路上的信息素更多，循环往复会导致它上面的信息素越来越多。
马可 多里戈
迪诺伯和他的合作者共同构建了描述信息素积累机制的数学模型。在这个模型中，蚂蚁选择某条路径的概率和这条路径上已经获取的信息素多少有关。在计算机上运行这个模型，科学家发现了和蚂蚁表现极其相似的现象。
这些都是协同机制（stigmergy）的一个例子：个体，在这个例子中是蚂蚁，在它们周围的环境上做标记，这些标记会引导其他个体的行为，构成 从蚂蚁到蚂蚁 的反馈环路。反馈环路进而导致系统演生出某些具有协作性和整体性的现象 在这个例子中，就是选择最短路径。
（演生：传统的还原论认为，系统特性都可归因于个体特性。凝聚态物理告诉我们，系统特性也可归因于个体间的协作关系。随着个体数量的增加，这些的特性会不断出现并增强。这一过程被称为演生。）
人们为何关注蚁群优化？
在迪诺伯的实验中，蚂蚁解决的是优化问题， 多里戈说。 这对于人类来说是简单的，因为人类在看到两条路径后，很容易就能分辨哪条更短。但在现实生活中，另有很多所谓的组合优化问题，其结果并非一目了然。
一个例子就是为车辆规划路线。你需要用货车把货物从仓库送到一系列指定地点。为了节省路费，货车该选择怎样的路线，有时候还要考虑其他因素，例如要求货车在晚上才能回家。
如果货车不多，也许你可以找到最优解，但是随着货车数量的增加，问题会变得非常困难，以至于最强大的电脑都无法解决它。若要得出最优解，所需的时间比宇宙寿命还要长。 多里戈解释道。另外还有许多有关时间安排的统筹优化问题同样难以解决。
这些问题的共同之处，除了都难以解决以外，是他们都可以用网络来表示。在货车运货的例子中，网络就是连接货车必经之处的道路网。在其他问题中，建立表示问题的网络稍微困难一点，但是一旦将这个网络建立起来，就可以清晰完整地描述我们需要解决的问题。
电脑该如何做？
蚁群优化背后的思想是创建模仿蚂蚁行为的算法，以找到解决此类问题的最佳或接近最佳的解决方案。对于一个给定的实际问题，首先要将其转换为网络上的优化问题。网络很容易在计算机中表示出来。人造蚂蚁，通常称为代理人（agent），可以在网络上四处移动。信息素由 人工信息素 取代，表示为网络中边的权重：数字越大，代表信息素越多。
蚂蚁的微距照片
开始，该系统所有的边上包含相同多的信息素，代理人随机选择它们要沿着哪条边行进。当代理人找到解决方案时，例如一条从起始节点到结束节点的通路，它将评估该解决方案的质量。然后，它将在通路中的每一条边上，添加与解决方案质量成正比的人工信息素。信息素越多，别的代理人沿着该边行进的概率就越大。
如果我是一个位于某节点上的代理人，那么一开始我对每条边的偏好是一样的，所以我会随机选择， 多里戈解释道， 过一会儿，某些边将具有更多的信息素，这是因为它们代表了更好的解决方案。然后，我选择这些边的可能性会稍高。这种操作会一直进行下去，最终系统可以找到足够好的解决方案。
多里戈、詹妮 迪卡罗（Gianni Di Caro）和卢卡 甘巴尔德拉（Luca Gambardella）用这个想法，不光开发了针对某个特定问题的算法，而且还开发了一种可以根据你要解决的组合优化问题量身定制的整体框架。
计算机做得如何？
在实际操作中，蚁群优化算法可用于解决现实生活中的组合优化难题。理想情况下，像多里戈这样的计算机科学家希望通过数学方式证明算法具有良好的性能，例如，证明这种算法找到问题的良好解决方案（例如调度卡车）所花费的时间不会随着问题规模（例如卡车数量）增大而迅速变长。
但是到目前为止，相关理论还不成熟。研究人员只能泛泛地证明：蚁群算法得到最优结果，需要无限长的时间。
多里戈承认： 这看起来是一个特别无用的结果。 无限长的时间正是人们解决实际问题时所不具备的。但是有意义的是：从理论上讲，至少排除了永远也找不到最优解的可能。对于蚁群优化中的某些特定算法，我们可以预测它需要多久才能解决问题，但这些算法在实践中往往表现不佳。 不光是蚁群优化，大多数针对组合优化的算法都是如此。 多里戈说。
关于蚁群优化算法的实用性研究仍然存在有趣的挑战。目前，你如果想使用该框架，则必须自己确定哪种蚁群优化算法最适合你的问题。多里戈说： 一个非常有前途的研究方向是使这一过程自动化。 这意味着要构造一个算法，针对特定问题，让该算法找到最佳的蚁群优化算法供您使用。
因此，那些不起眼的小生物不仅启发了解决复杂问题的方法，而且提出了具有挑战性的问题，锻炼了新一代研究人员的思维。
下次从野餐布上掸掉某只蚂蚁的时候，不妨想想小小蚂蚁带给人们的趣味。
原文链接：https://plus.maths.org/content/power-ants
