蚂蚁能找到最近的路

著名的旅行推销商问题

　　

　　假设您准备去全国10个城市推销您的新产品，从北京出发，途径上海、兰州、大连等城市，每个城市只经过一次，再返回北京，怎么走路途最短、最省事?您也许觉得这事很简单，笔算一下或者拿地图量一下不就得出结果了么?您可以按照这个思路尝试一下，将会发现事情不像您想的那么简单。因为，所有可能的路线就有10X9X8XTX6X5X4X3X2X1=3628800条!

　　这么多路线，即使用计算机计算，也需要耗费极长的时间。这就是组合优化问题中有名的旅行推销商问题，由意大利数学家孟戈于1930年首次提出，其实质就是要找出一条既行遍所有城市，又使总的行程最小的路线。

　　

　　神奇的蚂蚁算法

　　

　　马科·多利戈于1992年在他的博士论文中引入了蚂蚁算法。蚂蚁算法思想的萌芽至今不过短短17年的时间，然而这种新型的优化算法很快就得到了广泛的认可，对它的研究已从欧洲的一个实验室迅速传播到全球千千万万个实验室。下面我们简要介绍蚂蚁算法的思想：

　　蚂蚁算法利用的最基本的原理是蚂蚁会在行走的过程中释放信息素——信息素可以是蚂蚁的气味或分泌物。通过一个简单的例子，您就会明白信息素的作用何在：假设有两条路通向食物。刚开始的时候，这两条路径上的蚂蚁数目一样多。当一只蚂蚁沿着较短的路径到达食物并返回时，由于路径较短，所以蚂蚁来回的时间短，这就意味着重复的频率快，因此在单位时间里，与较长的路径相比较，在较短的路径上走过的蚂蚁就多，从而洒下的信息素自然也更多。因此会有越来越多的蚂蚁倾向于选择信息素较多——即被走过的次数较多的路径。直到最终，所有蚂蚁都“不约而同”地选择同一条路径，即最短的路径。

　　

　　让蚂蚁帮你找到最佳路线

　　

　　那么，是否我们也可以像蚂蚁一样，通过在走过的路径上释放“信息素”来寻找到最优的路径?当然可以。以本文开头的10个城市推销巡游为例，首先设置如下参数：各个城市之间的距离，初始时刻各条路径上的信息量，还有蚂蚁的数目。对于旅行推销商问题，蚂蚁要在走过的路径上留下信息素，蚂蚁数目过多，会使各个城市之间的路径上的信息素数量平均化，不利于快速找到最佳解；但是如果蚂蚁数目过少，会使从未被搜索到的路径上的信息量减小到接近于0，可能最终找到的是一个次优解。所以在具体的实践中，针对具体问题来对蚂蚁的数目作出折中的选择。

　　接着，蚂蚁开始巡游各个城市。假设从北京出发，那么就需要计算下一步要走的是上海、广州，还是其他城市?这是根据北京到各个城市的转移函数来计算的。转移函数是到各个城市的路径上的信息素的函数。显然到哪个城市信息素比较高，哪个城市被选择的概率就比较大。这就需要用到我们上文设置的初始时刻的信息量，初始时刻的信息量可以设为各城市之间距离的倒数，也可以设为一般的常数，根据具体情况有不同的设置。

　　在所有蚂蚁根据转移函数选择了“下一个城市”并且走过所有城市，即完成了一次循环之后，记下这次循环得到的最优解，就是所有蚂蚁得出的10个城市巡游路线中最短的那条路线。同时要对所有路径上的信息素进行调整。在实际的蚂蚁寻食过程中，随着时间推移，留在各个路径上的信息素必然会部分地挥发，因此在蚂蚁算法中更新路径上的信息素时要考虑各个路径上信息素的部分消逝。具体地，以城市甲乙之间的路径为例，将甲乙路径上挥发后剩下的信息素，再加上本次循环中所有走过该路径的蚂蚁留在该路径上的信息素，就得到更新后的信息素。举例来说，第一只蚂蚁留在甲乙路径上的信息素可以考虑甲乙路径的长短、以及这只蚂蚁走过的10个城市的总路线长度来确定。也就是说，甲乙路径长度越短、走过甲乙路径的蚂蚁越多、含有甲乙路径的路线的长度越短，甲乙路径上的信息素就越多。从而，在下一个循环中，从城市甲出发，到城市乙的转移函数也越大，城市乙被选择的几率也更大。

　　然后所有蚂蚁从北京(也可以是其他城市)开始，根据更新的信息素再次巡游10个城市。以多次循环中最短的路线作为10个城市巡游的最优解。

　　

　　未来展望

　　

　　上面介绍了旅行推销商问题以及解决该问题的一种新颖算法——蚂蚁算法。旅行推销商问题在许多领域中有着十分广泛的应用，例如邮递员投递路线选择、推销员推销路线选择、生产作业排序、物流运输路线选择、航空飞行科目排序、vLsi芯片设计和机器人控制等。由于蚂蚁算法的很多问题还有待解决，比如如何克服局部最优化、参数如何选取等，因此目前尚处于理论研究阶段，还没有真正地登上实际应用的舞台。但是，我们相信，理论研究会为实际的应用扎下深厚坚实的基础——理论研究就像一棵大树的根，只有根坚固、牢靠、扎得深，土地上才能长得枝繁叶茂。

　　

　　责任编辑　尹莹莹