蚁群优化算法及其应用

 蚁群优化算法及其应用

刘逸

浙江省宁波市海曙区集士港镇

1.引言

1.1蚁群行为

一只蚂蚁看起来微不足道，但多个蚂蚁形成的蚁群似乎就是一个非常规整的军队，在很多情况下，他可以完成很多单只蚂蚁完成不到的事。这种行为可以看成多个蚂蚁之间的合作，最典型的一个例子就是寻找食物。在我们的生活中，我们经常可以观察到蚂蚁排成一条直线非常有规整的搬运食物，它是一条直线而不是别的形状。当蚁群的行进路线出现障碍的时候，蚂蚁的位置总是非常规整而又均匀。只要等待时间一会儿，蚂蚁就能找到回蚁穴的最短路径。蚂蚁可以利用这个信息。当蚂蚁出去觅食会释放信息素，并且沿着行进的路线释放，而且蚂蚁之间都可以互相感应信息素。信息素的浓度多少决定了食物与蚁穴之间的距离。信息素浓度越高，食物与蚁穴距离就越短。

1.2一个关于寻路行为的简单例子

            戈斯S等人在1989年进行了“双桥”实验。这个实验说明了，蚁群会选择出食物与蚁穴的最短的距离。下面的例子也能解释它。

图 1

如图1所示，如果路线是从A点到D点，有俩个选择ABD和ACD路线，假如现在有俩只蚂蚁B和C分别在ABD路线和ACD路线上，一个时间单位进一步，8个时间单位后，情况如图2所示：从ABD路线最后到D的蚂蚁，从ACD路线最后到C的蚂蚁. 再过8个单位时间后，可以得到以下情况：B蚂蚁已经到A点了，而C蚂蚁才到D点.

图 2

32个单位时间后，在ABD路线上的蚂蚁已经折返了两次，而在ACD路线上的蚂蚁只有折返一次，是不是可以说明ABD上面的信息素比ACD多出了一倍。接下来，受信息素的影响，ABD路径会被两倍多的蚂蚁选择，所以ABD路线上会有更多的蚂蚁，也会有更多的信息素。最后，在32个单位的时间后，信息素浓度的比值将达到3：1。信息素浓度越来越高蚂蚁也会相应越来越多，而ACD路径将逐渐被放弃。这就是蚂蚁如何依赖信息素来形成积极反馈的方式。 由于前一条蚂蚁在一开始的路径上没有留下信息素，所以蚂蚁向两个方向移动的概率是相等的。但是，蚂蚁移动的时候，它会释放信息素。信息素是蚂蚁之间合作的重要因素。之后的蚂蚁就是根据信息素的浓度来判辨方向和之后的行进路线。实现表明短侧的路线信息素浓度更高，更多蚂蚁也会追随这条路线.

1.3信息素的挥发性

一个非常自然的问题是：为什么蚂蚁的运动方式会不断得到优化？这是因为蚂蚁信息素的挥发性，信息素是会挥发的，时间越久他的浓度也就越低，降低了它对蚂蚁的吸引力。蚂蚁出去的路线越长，时间越久，那信息素浓度会降低。这么一看，蚂蚁更适合在短的前进路线上行动，因为短的路线上的信息素浓度会因为时间关系明显高于长的路线。这也变向说明了信息素挥发性的作用。如果信息素不会挥发，那最开始的蚂蚁行进的路线上的信息素浓度肯定是最高的，越来越多的蚂蚁只会沿着这一条路线前进。而不会发现出一条更短的路径。由于信息素蒸发的性质，很多蚂蚁的行为表现也可以表明蚂蚁之间一直有在信息沟通。当一条路线上有很多的蚂蚁前进，后面的蚂蚁选择这条路径的概率更大。蚂蚁之间以这样的方式来互相沟通，找到最短的路径。

2.ACO算法和TSP问题

2.1旅行推销员的问题

旅行推销员（TSP）问题是1959年提出的一个数学规划问题。在一个有N个城市的图表中，游历参观的人想要只访问每个城市一次，并最终返回第一个城市。这次旅行的总费用是观赏每个城市的费用的总和，旅客希望整个旅游的费用是最低的。TSP的问题是找到最实惠的路径，这也可以被理解为最短的路径。 显然，对于TSP问题，有一些解决方案的组合。M. Dorigo等人首先利用蚁群算法解决了旅行推销员问题（TSP），并取得了良好的实验结果。 20世纪90年代初，意大利学者M. Dorigo等人研究了类似于蚁群的一种计算方法。他的大致的思路就是，用蚂蚁的行进路线来代表解决问题的答案，并由所有蚁群的前进路线所形成。

2.2 ACO算法的作用机理

在算法的初始时刻，蚂蚁被随机分配到一个特定的城市。在第一个实验中，由于蚂蚁没有路径行走，蚂蚁没有根据信息素选择方向，而是随机选择的。在所有的蚂蚁爬过所有的城市之后，我们记录了小路上信息素的浓度。我们已经知道，如果信息素的挥发速率是恒定的，那在短的路线上蚂蚁释放信息素的浓度肯定更高。现在，我们让这些蚂蚁从它们开始生活的城市出发，这次我们会记录下它们的路径。这是计算机算法中的第二次迭代。在第二次迭代中，蚂蚁不会无规则的去选择路线，它是根据信息素来判别方向和路线的。 是否有可能是最后一批蚂蚁选出了错误的路径，所以在更长的路径上就会有更高的信息素？这是可能的。为了防止这种情况发生，我们将把此迭代中生成的路径长度与上一次迭代进行比较，并保持较短的路径长度。我们可以观察到，蚁群算法的本质不是依赖于一个“聪明的个体”来立即做出正确的决定，而是利用群体活动的正反馈来进行操作

3.结论

本文主要介绍了受蚁群系统启发的ACO算法。本文从信息素出发，重点阐述了ACO的算法。蚁群算法的核心就是信息素。蚁群之间就是用信息素来互相沟通，同心协力解决复杂的问题。因此，如果要继续研究这个算法，如何用数学公式更好地模拟信息素是非常重要的。我相信，随着仿生学研究的不断深入，其他学科也可以通过分析昆虫的群体行为，找到更多解决复杂问题的方法。

参考文献

[1]Mohsen Paniri MLACO: A multi-label feature selection algorithm based on ant colony optimization

[2]Dorigo M;ST(U)TZLE T;张军;胡晓敏,罗旭耀 蚁群优化 2007

[3] 李凯齐.刁兴春.曹建军. 蚁群优化算法在求解随机组合优化问题中的应用综述[期刊论文]-计算机应用研究2010,27(12)