蚂蚁算法在TSP问题求解的有效利用

李明伟，李永芳

（云南开放大学 云南 昆明 650223）

1 问题的提出

计算机科学的出现，对人们的生活及行为方式带来了极大的改变。作为一个信息爆棚的时代，寻求组合优化的空间规模和时间级是巨大的，常规方法求解是难以实现的，属于NP完全问题。这一类问题不能使用精确算法，而需要寻求问题的有效近似算法[1]。

具体来讲，我们可以将TSP这样进行表述：假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市，简而言之就是求最短环路的问题。那么寻求TSP问题求解的优化算法可以说既具有理论意义，又具有时间价值。为了便于讨论优化算法的应用问题，这里将TSP问题转化为数学描述[2]：

假架设旅行商需要遍历的城市数量为n，那么N个城市的集合为c={c1，c2，…cn}，那么城市i，j间的距离D（ci，cj）的距离为正实数，且i≥1，j≤n，那么在每个城市仅访问一次的情况下，使函数（1）

达到最小城市序列 c={cρ（1），cρ（2），…，cρ（n）}。其中ρ（1），ρ（2），…ρ（n）为1，2，N的全排列。

2 TSP问题求解蚂蚁算法的模型建立

在解决TSP问题求解的算法上，以仿生学算法取得的效果最佳，目前已经应用的算法包括模拟退火法、遗传学法、人工神经网络法等。蚂蚁算法是近来来新提出的仿生进化算法，无论是个体局部收敛还是多个个体空间收敛的速度都比较快，算法设置也相较于简单，易于应用[3]。

那么针对本文所提出的TSP问题，我们需要建立人工的蚂蚁算法模型。那么假设建设有m个人工蚂蚁，将其随机分配在N个城市上，城市与城市之间形成一条边，且该边具有初始化信息素τij（0），将每个蚂蚁的禁忌表的第一个元素设置为该蚂蚁的初始城市。那么可以确定每只蚂蚁在选择路径时的概率函数，可以表达为：

其中禁忌表tabuk（k=1，2，…m）为蚂蚁k当前所走过的所有城市；τij（t）为城市i，j之间边弧上信息素的强度，设定i为起始城市，j为到达城市，ηij=1/dij表示为ij城市间的距离因子dij为经过城市边弧路径（i，j）所需的花费。α为信息启发因子，β为期望值启发因子，且α，β∈[0，+∞)。分别表示信息素、路径长度在选择概率上的作用。那么对于蚂蚁的城市选择概率而言，信息素和城市间路径的长短决定概率的大小。那么对于m个蚂蚁而言，在经过n次循环后，获得完整的禁忌表。也就是说每个蚂蚁所走过的路径长度中可以寻找最短路径并保存，记录这一最短路径并更改这一路径是哪个的信息素。不断重复这一过程到最大遍历值结束[4]，那么可以获得信息素的更新公式：

其中Vτij是城市边弧上新增信息素累加和，φ表示信息素消散的等级，残留信息的保留部分。那么1—φ表示已经消散或削弱的部分，其中φ∈[0，1），这能够避免信息大量无用的积累。

蚂蚁k遍历（i，j）（4）来获得，其中Q代表蚂蚁遍历一周所释放的信息总量，该参数为常量。由此依据上述算法的模型公式，确定参数α、β、φ、Q、蚂蚁数量m的最优组合值需要通过实现确定，并得出以下结论：

①α作为信息启发因子，其数值是每个节点上信息量受重视的程度，数值越大蚂蚁选择重复点的可能性越大。但该值不加以限制，则会出现局部最优解，该解过早得出，不利于解的最优化。

②同理β作为期望值启发因子，代表了启发式信息受重视的程度。其数值越大也就表明蚂蚁选择最近城市的可能性越大。

③φ值是路径上信息素的保留情况，显然该数值的大小会影响信息素的累积及选择，取值不良则会产生相应的不良结果，难以取得最优组合。

④蚂蚁数量m值对算法的收敛速度产生影响。当这一数量规模接近于问题研究的总量时，其所获得的结果也就越精确。但是这也就代表了实验过程中需要进行的循环次数会增加，算法的收敛速度就会减慢。相同蚂蚁数量时，问题的规模越大，全局搜索能力越低。而参数Q则与之相反，Q值越大，算法的收敛速度也就越快，但不代表Q值可以无限增大，要与其他参数相适应[5]。

总的来说，当最终搜索达到预先定义的NCmax或者当所有实验的蚂蚁均已经选择了同一最短路径时，这一搜索循环可以停止。在计算机程序逻辑上可以这样描述：

第一步为初始化，设定t=0，NC=0。城市间边弧上的信息素强度及信息累加参数均为0.将m个蚂蚁分散到n个城市上。NC表示迭代循环数。

第二步把第k个蚂蚁的初始城市值放入到禁忌表tabu（s）。重复这一过程直到所有的禁忌表均已填满。

第三步根据概率公式将蚂蚁k移送到城市j中，j属于求解的城市集合。

第四步计算第k个蚂蚁遍历的总路径长度Lk，确定最短路径，并更新最短路径及相应的信息素浓度。

第五步对各边弧（i，j）设置信息素强度变量为0及信息累计参数为NC+1.如果不是所有的蚂蚁均选择同一路径或者未达到最大值，则清空禁忌表重新返回执行第二步。若达到NCmax或所有蚂蚁均选择同一路径则程序终止[6]。

3 实证分析

根据蚂蚁算法的基本执行方式及相关参数，通过相关实证对各参数对实验结果的影响进行验证。

（1）信息素的保留程度φ

设置问题研究规模为N=51，α=0.1，β=2，Q=0.5，m=20。对φ进行不同取值，分别为0.1，0.2，0.3，05，0.7，0.9，并进行实验。当φ值为0.2～0.5之间时期所所得的最优路径长度在434.9～436.0之间，数值比较接近。搜索循环次数依次为61/103/141.当φ值增加为0.9时，路径上消散的信息量为0.1，所获得的最优路径长度为454.2，循环次数达567次。可见φ值的大小对算法的收敛速度中重要影响，过小会提早产生局部最优解，但是过大会增加收敛时间。

（2）蚂蚁数量m

设置问题研究规模为N=51，α=0.1，β=2，Q=0.5，φ=0.2。对m进行不同取值，分别为 10，20，25，30，35，40，45，50，并进行实验。当m值在 20～30之间时期获得最优路径长度为440～450之间，且循环次数比较少，位于43到86之间，虽然当m值增加到35～50之间，其所取得的最优路径结果与m=20时比较相近，但是循环次数达到200～550次之间，收敛速度大大下降。

（3）信息总量Q

设置问题研究规模为N=51，α=0.1，β=2，m=20，φ=0.2。对进行不同取值，分别为1，10，100并进行实验。当信息总量为100时，搜寻最佳路径长度为446.5，循环次数为91次。大参数分别为1，10得到结果分别为446.8/447.1，搜索次数比较接近，分别为89/86，可以看出，信息总量Q值越大，信息积累越快，所得到的正反馈性能也就越好。

（4）α、β因子

α、β因子对求解的影响我们一般将两个参数放在一起研究，其根据组合的不同，对算法的性能产生影响。其中α分别取值0.1，0.1，0.2，0.3，1.0，5.0，10.0。β分别取值0.5，1，2，3，4，8，10。当α、β均为最小值0.1/0.5时，搜索循环次数最大为157次，最优路径长度为454.8.而当两个参数均取最大值时，搜索次数最小，但所获得的最优路径长度出现局部最优解为469.7.所以可以看出当α、β取值不合理时会造成算法性能下降会过早出现最优解，不利于正常的取值。

4 结语

综上所述，蚂蚁算法是一种有效的仿生算法，适用于TSP问题求解及其相关衍生问题。但是在应用过程中要注意信息启发因子、期望式启发因子α、β，信息素的保留程度φ，蚂蚁数量m，信息总量Q等参数的合理取值，提升算法的优越性。对于基本蚂蚁算法而言，可在对参数性能的研究上进行优化。

[1]陈灵佳.蚁群算法在解决TSP问题中的应用[J].电子技术与软件工程，2017(10)：145-146.

[2]高志娥，薛艳锋，兰静.混合型蚁群算法及其应用--以旅行商问题为例[J].软件导刊，2015(4)：138-142.

[3]颜颖.基于蚁群算法的TSP问题研究[J].哈尔滨职业技术学院学报，2017(2)：83-86.

[4]易正俊，李勇霞，易校石.自适应蚁群算法求解最短路径和TSP问题[J].计算机技术与发展，2016，26(12)：1-5.

[5]张弛，涂立，王加阳.新型蚁群算法在TSP问题中的应用[J].中南大学学报(自然科学版)，2015(8)：2944-2949.

[6]张开碧，张洋川，万素波，等.一种改进的竞争型蚁群算法在TSP问题中的应用[J].计算机与数字工程，2016，44(3)：396-399.