基于TSP的蚁群算法参数选择问题分析

丁上凌++李斌

摘要：根据目前针对社会性动物群体活动的实验调查，发现其自组织行为广泛存在，例如群体活动较为频繁的蚂蚁，在群体觅食过程中能够找到蚁穴到食物的最短路径，即蚁群算法。文章围绕蚁群算法在TSP中的应用，就算法的参数选择进行了深入的研究。最后通过对全文的研究工作进行了总结，并展望了其应用价值及后期还需继续研究的问题。

关键词：蚁群算法 TSP 最短路径 参数选择

中图分类号：TP183 文献标识码：A 文章编号：1007-9416（2016）12-0131-02

蚁群算法是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo提出，它主要的依据就是蚂蚁在觅食过程中能够找到蚁穴到食物的最短路径。蚂蚁的视觉系统非常薄弱，几乎可以说是瞎子，但是它们却能发现食物与蚁穴之间最短的距离。生态学家的研究表明，蚂蚁是借助信息素来实现这一点的。蚁群算法也越来越多被应用到实际的问题中，并且取得了较好的效果，例如调度问题、着色问题、求解旅行商问题（TSP），并在大规模集成电路设计，通信路由控制等诸多领域表现出较好的性能。本文在介绍蚁群算法的基本原理的基础上，主要分析了蚁群算法参数的选择策略问题。

1 蚁群算法的基本原理

1.1 蚁群算法的原理

蚁群算法是从自然界启发中得到的一种新型的模拟进化算法，应用该算法求解TSP问题取得了较好的结果。科学家发现虽然单个蚂蚁无法掌握附近的地理信息，但整个蚁群却可以找到一条从巢穴到食物源之间的最优路线。经过大量研究发现：蚂蚁在运动过程中，能够留下一种称之为信息素的物质，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此，由大量蚂蚁组成的蚁群的集体行為便表现出一种信息正反馈现象：某一路径上单位时间走过的蚂蚁越多，表明该路线的可用性越好，则后来者选择该路径的概率就越大。蚁群算法具有实现简单、正反馈、分布式的优点。

人工蚁群和自然界蚁群的相似之处在于，两者优先选择的都是含“信息素”浓度较大的路径。这在两种情况下，较短的路径上都能聚集比较多的信息素，受到上述情况的启发，科研人员在此基础上提出了蚁群算法，它不仅具有蚁群觅食行为中的信息传递功能，还具有自然界蚁群所没有的记忆能力，即能够保存已经去过的地方和已经走过的路径，从而能够更加智能的选择下一地点和路径，并且按照一定的规律总结出特有的算法进行最短路径的选择。

1.2 基于TSP问题的蚁群算法数学模型

TSP问题又称为旅行商问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访M个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最终要回到原来出发的城市。路径的选择目标是要求旅行商人怎样才能得到最短的路径，取得最佳的利益。

根据信息素更新的策略不同，Dorigo M曾给出了不同的蚁群算法模型，分别称为ant-cycle模型，ant-quantity模型和ant-density模型。它们的差别在于循环中路径的信息素的增量的求法不同。

在ant-quantity模型中：

其中，是信息素强度，它影响算法的收敛速度是指两座城市之间的欧氏距离，是指第只蚂蚁所走的路径长度。ant-quantity和ant-density是利用局部信息完成求解运算，ant-cycle是利用整体信息完成求解运算。通过实验得到ant-cycle的模型比其他两种模型效果好。

2 参数优化策略

通过对蚁群算法基本原理及其数学模型的学习理解，可以使用MATLAB进行蚁群算法求解TSP最短路径问题的仿真试验工作，其主要任务是：根据城市的坐标，使用蚁群算法求解TSP最优化问题，并绘制最佳结果的路径图，生成平均距离和最短距离统计图。

算法中的主要参数有：城市的个数，城市的坐标（城市个数*2的矩阵），最大循环次数（即迭代的次数），蚂蚁个数，表征信息素重要程度的参数，表征启发因子（期望）重要程度的参数，信息素挥发系数，信息素强度的系数（一般是一个常量），最佳路线的长度。

实现步骤为：第一步：变量初始化；第二步：循环开始，判断变量是否达到最大迭代次数，如果没有达到，继续下一步运行，否则，循环结束；第三步：将所有蚂蚁随机放到所有城市上；第四步：所有蚂蚁按概率函数选择下一座城市，完成各自的周游；第五步：记录本次迭代最佳路线；第六步：更新信息素；禁忌表清零，回到第二步，达到停止条件时跳到第七步；第七步：输出结果。

仿真中采用最短路径作为参考项，进行多目标测试得出结果，并由结果分析出蚁群算法中的参数如何选择优化。

2.1 缺省值的选择

在实验过程中，本文在进行参数选择时，取城市个数为20，迭代次数为100，蚂蚁个数为15，信息素重要程度为1，启发因子重要程度为1，信息素挥发系数为0.15，信息素强度的系数为100，并设定20个城市坐标为（602，972）（989，483）（54，550）（95，868）（529，430）（982，351）（654，23）（738，372）（539，594）（560，850）（229，806）（411，710）（83，706）（937，801）（12，994）（694，809）（795，759）（339，148）（956，644）（346，726）。

多次运行程序后，求得最佳路线的长度的最优解为4148.6，使用其作为缺省值，以此在下面进行参数关系选择时作为对比参考值。

2.2 迭代次数的选择

由于蚁群算法中迭代的重要性，所以选取合适的迭代次数可以在较少耗费系统资源的同时得到较优的解。经过试验可以得出在迭代次数太少时，求出的解与最优解相差很大，这是由于迭代次数太少时，解还未收敛造成的。当迭代次数太多时，其耗费了大量系统资源，但是求出的解已基本不再变化，甚至有时出现抖动，求出不优解。所以合适选取迭代次数的值非常重要，在其他参数采用缺省值的情况下，可以通过实验得出选取110次左右的迭代次数较好。

2.3 信息素重要程度与启发因子重要程度参数的关系选择

从上述分析过程来看，我们所取的参数只是针对某一方面，参数较为单一，没有考虑不同参数值的组合所能呈现的不同效果，所以，接下来，本文就这一问题的缺陷性，对信息素重要程度与启发因子重要程度参数的关系选择进行了重新组合，在试验过程中，取不同组合的信息素重要程度α与启发因子重要程度β参数组合，求最短路径长度的最优解，其中，α在1到3之间取值，β在3到5之间取值，进行排列组合取值，特别地，α和β同时取1作为缺省值，即总共有10种情况。经过多次试验得出：α和β的值为（1，1）、（1，4）、（1，5）时均能取得较好的解。

2.4 螞蚁个数与城市个数的关系选择

经过实际应用可以知道，蚂蚁的个数与城市个数影响着TSP的求解，当少数蚂蚁在较大的城市中运动，它们所能得到的信息是有限的，这时算法不稳定，容易出现早停滞现象。相反，当大量的蚂蚁在较小的城市运动，它们虽然能够搜索的较为全面的信息，但是浪费了资源，收敛速度慢。本文选取蚂蚁个数/城市个数为0.5、1.5、2.5进行比较，经多次实验可以得出在城市数较少的系统中，蚂蚁数的变化对其影响较小，而在城市数较多的系统中时，蚂蚁数/城市数为1.5时可以取得较好的解，如表1所示。

在通信系统中，路由是关键的组件之一，它涉及到建立和使用路由表来指导数据通信量在网络范围内的分配活动。普通路由问题可以理解为是要建立一个路由表使得网络性能的一些量度最大化，是基于TSP的蚁群算法的重要应用。

3 结论和展望

蚁群算法易于与其他算法融合，在实际应用中参数对最优路径的选择有较大的影响，本文针对蚁群的参数选择问题进行分析，经过试验得到了一些参数的最佳取值范围。在以后的研究中可以将其应用于路由选择协议中，并考虑更多的网络实际情况，加入流量控制、网络拥塞等将其应用于实际之中，以取得更为准确的测试结果。

参考文献

[1]高博，卢辉斌.改进型粒子蚁群算法的应用研究[J].计算机安全，2010（11）：11-13.

[2]王戈，徐俊刚.基于路径选择的自适应蚁群算法研究[J].电子技术，2010，37（1）：14-16.

[3]叶菁.基于免疫-蚁群算法的TSP问题研究.[J].计算机工程，2010，36（24）：156-157+160.