基于最小生成树扇度的蚁群算法

丁怡心 廖勇毅

(广州民航职业技术学院 计算机系，广东 广州 510800)

蚁群算法是一种寻找优化组合的概率型算法，由Marco Dorigo在他的博士论文中提出[1,2]。蚁群算法本质上是进化算法中的一种启发式全局优化算法，该算法具有鲁棒性强、并行计算和启发式搜索等特征，并广泛应用于旅行商、网络路由、任务调度等NP完全问题。然而，蚁群算法存在收敛速度慢，容易陷入局部最优解等问题，对此众多学者进行了深入研究并提出了各种改进方法[3,4,5,6]。

刘国宝等人提出精英蚁群算法[7,8]，此类算法的改良方法思路是：以某种策略选择较优的路径，并在更新信息素时在这些路径上增加额外的信息素，增强正反馈作用。

Gambardella、王芳等人提出自适应蚁群算法[9,10]，此类算法的改良思路是：动态调整信息素挥发因子，避免某些路径因信息素过少导致算法陷入“早熟”。

Ciornei、邓博等人提出智能融合算法[11,12]，此类算法的改良方法思路是：引入遗传算法、人工免疫算法、模拟退火算法等智能启发算法的优点对蚁群算法进行改良。

文章通过对TSPLIB已公布的最优解做统计，发现单源边与最优解的吻合率约为91.14%，多源边与最优解吻合率约为64.14%，以此为依据提出基于最小生成树扇度的蚁群算法。

1 蚁群算法

蚁群算法是一种模拟蚂蚁觅食行为的模拟优化算法，蚂蚁会在其经过的路径上释放信息素，蚁群内的蚂蚁对信息素具有感知能力，它们会沿着信息素浓度较高路径行走，而每只路过的蚂蚁都会在路上留下信息素，这就形成一种正反馈的机制，经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。其基本工作原理如下：

（1）蚂蚁在路径上释放信息素。

（2）碰到还没走过的路口，就随机挑选一条路走。同时释放与路径长度有关的信息素。

（3）信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高路径。

（4）信息素会随着时间挥发，于是较差路径上的信息素越来越淡，最优路径上的信息素越来越浓。

（5）最终蚁群找到最优寻食路径。

蚁群算法最核心的两个问题是路径选择和更新信息素。

1.1 选择路径

设蚂蚁k当前处于城市i，则其选择城市j为下一个访问对象的概率计算见公式(1)。

其中， τ(i,j)为城市i和城市j之间的信息素浓度，η(i,j)为i和j之间距离的倒数。

α是信息素启发因子，值越大信息素对路径的选择影响力越大，蚂蚁选择之前走过路径的可能性越大，容易造成“早熟”。

β是期望启发因子，值越大距离对路径选择的影响力越大，蚂蚁选择较短路径的可能性越大，收敛速度变快，但是容易陷入局部相对最优解。

1.2 信息素更新

所有蚂蚁完成一轮迭代后需要对所有路径的信息素进行更新，首先把原来的信息素按一定比例挥发，然后加入最后一轮每只蚂蚁产生的信息素.更新信息素计算见公式(3)。

其中，m为蚂蚁个数，Ck为蚂蚁k在本轮走完一圈的总距离。

ρ 是信息素挥发因子，(1- ρ)则为残留因子，残留因子值越大，路径上残留的信息素越多，导致无效的路径继续被搜索，影响算法的收敛速度。

2 基于最小生成树扇度的蚁群算法

2.1 名词解析

最小生成树节点扇度:对于最小生成树上的一个节点，连接该节点的边的数目称为该节点的扇度。

如图1所示，由于连接节点c的边有3条，则节点c的扇度为3，同理节点g的扇度为4，节点a的扇度为1。

图1 最小生成树

最小生成树单源边:对于最小生成树上的一条边，如果该边的两个节点扇度都小于或等于2，则该边为单源边。

最小生成树多源边：对于最小生成树上的一条边，如果该边有一个节点扇度都大于2，则该边为多源边。

例如图1中，边ef的两个节点的扇度都为2，所以为单源边；对于边ab，节点a的扇度为1，节点b的扇度为2，所以ab为单源边；对于边cd，节点c的扇度为3，所以cd为多源边。

通俗地说，单源边意味着从两个方向进入该边的路都只有一条或没有；多源边则表示从某个方向至少有2条路进入该边。

2.2 算法启发

基于最小生成树扇度的蚁群算法灵感源于以下统计数据的启发。

文章作者统计了TSPLIB上已公布最优解的数据集，分析最小生成树与最优解之间的吻合情况。图2截取了部分统计实验界面效果图。

图2 部分统计实验效果截图

见表1，统计结果如下：最小生成树的边与最优解的边吻合率为75.76 %，其中单源边吻合率为91.14 %，多源边吻合率为64.14%。

表1 最小生成树与最优解吻合统计

2.3 算法思想

以上统计结果表明最小生成树的边对最优解有很强的导向性，于是提出算法思想如下：通过初始化信息素实现对蚁群的导向，并且对单源边、多源边及其它边初始化不同量的信息素，以体现不同强度的导向性。

最小生成树单源边的强导向性在一定程度上降低了问题的规模，同时一定程度上把原先的问题分割成若干个规模更小的问题，结合蚁群算法的全局搜索能力及对小规模问题良好解决能力，可以实现快速收敛并能得到较优的解。

如图3所示，bayg29.tsp是规模为29的TSP问题，确定单源边后规模近似地降至16，同时单源边近似地把它们分割成A、B、C和D 4个规模分别为3、4、4和5的问题。

图3 单源边降低问题规模

2.4 算法流程

图4 算法流程

单源边的强导向性可能会导致若干与最优解不吻合的单源边被构建到最终路径中，通过去交叉、点交换、点转移等局部优化方法可以有效地优化最终解。

3 实验

3.1 实验一 参数调优

实验目的是调整参数τsingle、τmulti及 τbase到适合的值，使算法效果最佳。

实验选取数据集为ch150.tsp，蚁群算法的基本参数设置见表2。为了更纯粹地比较蚁群的寻路能力，该实验屏蔽了点交换、点转移、去交叉等辅助优化方法。

表2 蚁群算法基本参数设置

表3 各组实验参数设置

表4 第1组实验数据

表5 第2组实验数据

第3组实验的10次测试数据见表6。

表6 第3组实验数据

第4组实验的10次测试数据见表7。

表7 第4组实验数据

4组实验结果表明，当最小生成树边的导向性较强时，算法收敛速度快，同时也会导致“早熟”，从而陷入局部最优解，如第1组实验结果所示。当导向性比较弱时，算法收敛速度慢，蚁群的寻路表现起伏比较大，如第4组实验结果所示。其中，第3组实验中，蚁群寻路能力及收敛速度综合表现最优，因此后面的实验参数设置都参考第3组实验的参数。

3.2 实验二 对比精英蚂蚁算法

精英蚂蚁算法是综合表现比较好的蚁群算法，该实验目的是对比文章算法与精英蚂蚁算法的效果。实验同样选取数据集ch150.tsp，用精英蚂蚁算法进行10次测试。为了更纯粹地比较蚁群的寻路能力，该实验也屏蔽了点交换、点转移、去交叉等辅助优化方法。

实验的部分运行效果如图5所示，10次测试结果见表8。

图5 精英蚂蚁算法部分实验截图

表8 精英蚂蚁算法实验数据

见表9，文章算法在实验一第3组测试结果与精英蚂蚁算法测试结果对比，两种算法的寻路能力相当，文章提出算法则在收敛速度上有明显优势。

表9 改进蚁群算法vs精英蚂蚁算法

3.3 实验三 寻路能力测试

该实验从TSPLIB中选取了若干数据集，测试算法在不同数据集中的表现，算法加入了点交换、点转移、去交叉等辅助优化方法。

实验共选取14个数据集，对每个数据集做10次测试，以下图、表展示10次测试中最优的结果。

图6-8展示程序运行界面，表10是测试数据汇总。

图7 寻路能力测试界面截图二

图8 寻路能力测试界面截图三

该实验表明，算法在中小规模问题中寻路能力及收敛速度都表现非常优秀。

4 结论

文章对TSPLIB已公布的最优解进行统计，分析最优解路径与最小生成树边之间的关系，以此为基础提出基于最小生成树扇度的蚁群算法。算法根据单源边、多源边及其它边为路径赋予不同量的信息素，为蚁群提供不同强度的导向作用，从而加快蚁群寻路速度及寻路精度。实验表明算法在收敛速度及寻路能力方面都有显著提高。下一步工作，针对最小生成树边的强导向作用引起的误导问题进行改进。