基于视觉修正的改进最大最小蚂蚁系统求解TSP

李克文 徐延辉 张震涛 席英杰

(中国石油大学(华东) 山东 青岛 266580)

0 引 言

蚁群算法是由Dorigo等[1]提出的一种仿生优化算法,它与粒子群算法[2]、鲸鱼优化算法[3]等都属于群智能优化算法。蚁群算法的灵感来自于对自然界蚂蚁群体觅食行为中的路径探索的模拟。该算法具有典型的系统特性,其分散性、自组织性、正反馈性和并行性等优点为许多学者探索和研究提供了切入点。作为一种元启发式演化算法[4],在解决许多复杂的组合优化问题上具有明显的优势,应用范围也非常广泛,如TSP问题、调度问题[5]、图像特征提取[6]、路径规划[7-8]、地震断层识别[9]和软件缺陷预测[10]等。然而,蚁群算法也有收敛速度慢、容易陷入局部最优和过早停滞的缺点。

针对这些不足,许多学者提出了改进的方法。文献[11]提出了一种采用惰性蚂蚁概念的自动控制蚁群算法,通过将每个最佳路径上的蚂蚁设置为惰性蚂蚁,直到下一次找到该路径,它才会被激活;文献[12]提出了一种基于聚度的自适应动态混沌蚁群算法,在迭代前期利用聚度来衡量解的多样性,并引入混沌算子来增加种群多样性,提高了算法精度,在迭代后期去掉混沌算子,减少混沌扰动性,提高了算法的收敛速度;文献[13]提出了改进的蚁群与粒子群混合算法,采用了改进蚁群算法的信息素更新方式和全局最优粒子自适应交叉变异策略;文献[14]提出了一种基于可变天气因素的MMAS改进算法,参考天气变化因素对蚂蚁觅食的影响,设置信息素挥发系数和蚁群数量,提高了解的质量;文献[15]引入了一种称为单位距离信息素算子的新蚁群,并与ACS和MMAS共同构成了最终的算法,利用皮尔逊相关系数建立自适应频率的多群体通信;文献[16]提出了一种梯度下降选择策略,该策略不仅根据信息素的浓度按概率搜索下一步,而且根据一定概率采用梯度下降方法搜索下一步;文献[17]参照人类集体行动模型,为蚁群增加一个集体行动,在迭代过程中,每只蚂蚁根据自己的阈值决定是否加入到集体行动,避免了算法陷入局部最优;文献[18]将细菌觅食算法和蚁群算法相结合,在蚁群算法迭代过程中,引入细菌觅食算法的复制操作,以加快算法的收敛速度;引入细菌觅食算法的趋向操作,以增强算法的全局搜索能力。文献[19]提出了一种改进负反馈机制的伪动态搜索蚁群优化算法,算法在信息素传递规则中引入了一个角度,通过角度计算规则,多个角度较小的城市也被包括在下一个候选城市列表中,避免了局部优化;文献[20]在蚁群陷入局部最优时,利用信息素进行突变,帮助算法跳出局部最优。

MMAS是一种通用性较强,寻优效果较好的经典改进蚁群算法,本文在MMAS算法的基础上,针对MMAS收敛速度慢、容易陷入局部最优的问题,改进了信息素的初始化,在算法陷入局部最优后提出了局部寻优、新路径探索和“双优”策略更新信息素三个策略,增加了解的多样性,提高了求解精度。

1 相关概念

1.1 基本蚁群算法

蚁群算法(Ant Colony Optimization)的典型应用是TSP问题求解。TSP是一个经典的组合优化问题。n个城市的TSP求解可以描述为：给定一个城市集合V={v1,v2,…,vn},求解遍历V中所有城市各一次且最后回到出发城市的一个最短旅行哈密尔顿回路g∈G(V,A),其中G(V,A)为满足上述求解约束条件的哈密尔顿回路集合,A={aij=(vi,vj)|0

给定如下相关参数,蚁群数量m,信息素启发因子α,期望启发因子β,信息素挥发系数ρ,各路径上的信息素τij,算法在初始时刻,每条路径的信息素浓度为同一个常数,即τij=C(C为较小的常数);在每次迭代过程中,每只蚂蚁随机选择一个城市作为起始城市,再使用轮盘赌的方法,按照式(1)选择下一个城市。

(1)

τij(t)=(1-ρ)τij(t-1)+Δτij(t)

(2)

1.2 最大最小蚂蚁系统

最大最小蚂蚁系统(MMAS)是在ACO基础上进行改进的,它改进了ACO容易陷入局部最优、收敛速度慢等缺点,其主要改进方向包括以下3个方面：

(1) 将信息素τij限制在τmin与τmax之间,即τmin≤τij≤τmax,该策略避免了最优路径上的信息素和未访问路径的信息素差距过大,导致搜索的停滞。

(2) 将初始信息素设置为τmax,该策略使得算法在初始阶段有更多的搜索可能。

(3) 在每次迭代之后,只允许最优路径更新信息素,可以是当前迭代最优,也可以是历史最优,其信息素更新方式按照式(3)进行。

(3)

2 基于视觉修正的MMAS算法

自然界中蚂蚁认路的本领很强,其认路能力主要依靠两种路标进行导航,一是大家熟知的气味路标,是蚂蚁一边走路,一边分泌的一种信息素;二是天文路标,蚂蚁用眼睛凭借太阳来定位,实现导航。蚂蚁的眼睛是一双复眼,由数量不等的单眼组成。复眼越大,蚂蚁看得越远。本文引入天文蚁,即一种主要使用眼睛探索路径的具有大复眼的蚂蚁,在算法陷入局部最优时,由天文蚁检查当前路径的情况,并根据不同路径情况调整搜索方案,使算法及时跳出局部最优。

2.1 基于启发式信息的信息素初始化

本文在信息素进行初始化时,综合考虑启发式信息,依据城市间的欧氏距离初始化信息素,每条路径上的信息素τij初始化为基础信息素与期望信息素两部分,按照式(4)进行初始化,既满足了算法在初始阶段有较多的搜索可能,又避免了算法初期的盲目搜索,提高了算法的收敛速度。

(4)

式中：τ0表示基础信息素;τ0+(1/dij)的值在τmax附近。

2.2 基于视觉修正的MMAS算法

蚁群算法最大的缺点是容易陷入局部最优,导致算法停滞。在最大最小蚂蚁系统中,每次迭代结束,只允许最优路径有信息素的留下,使得其他路径的信息素随着迭代的进行而减少,蚁群的搜索方向极易向历史最优路径靠近,一旦长时间陷入局部最优,其他路径信息素将始终保持为τmin,算法难以找到新解。针对此问题,设置阈值nt并统计历史最优路径出现的次数,当该次数达到nt时,算法陷入局部最优的可能性较大。此时,天文蚁检查历史最优路径中是否存在路径交叉,若存在,则消除交叉路径;若不存在,则进行新路径探索。

2.2.1局部路径优化

蚁群在路径搜索过程中,极易出现路径交叉的现象。对于TSP问题,要找的是一条最短的哈密尔顿回路,由三角形的任意两边之和大于第三边,如果存在交叉路径,此路径一定不是最短路径(AE+BE>AB,DE+CE>CD,所以AC+BD>AB+CD),如图1所示,其中,ABCD为4个城市,E为交叉点。

图1 路径交叉图

当算法陷入局部最优时,若天文蚁检查到历史最优路径存在交叉,根据两交叉路径的相对位置,将交叉路径分以下两种情况,如图2所示。其中,ABCDEF为6个城市。

(a) (b)图2 路径交叉分类图

(1) 若交叉路径相邻较近,如图2(a)所示,则选择交叉路径临近的6个城市重新追踪该段路径,由于路径涉及的城市很少,采取组合遍历的方式找到该段最短路径,然后更新历史最优路径及其距离,同时,用式(5)更新路径信息素,并挥发交叉路径信息素。

(5)

(2) 若交叉路径相邻较远,如图2(b)所示,则重新构建路径,消除交叉路径AC和BD,构建新路径AB和CD,实现路径的进一步优化,然后更新历史最优路径及其距离,同时,用式(6)更新新路径信息素,并挥发交叉路径信息素。

(6)

基于数学原理的交叉路径消除策略,有利于算法及时消除交叉路径,用最短的时间快速跳出局部最优。

2.2.2新解探索

当第t-1代算法陷入局部最优且天文蚁检查到历史最优路径Tbest不存在交叉时,调整信息素,保持历史最优路径信息素不变,增加其他路径信息素,如式(7)所示。天文蚁在第t代进行新路径的探索,当所有蚂蚁随机选择完成起始城市v1后,再采用轮盘赌的方式,按照式(1)选择第二个城市v2,其中,(v1,v2)∉Tbest。之后,每当算法运行nt代,进行一次新解的探索,直到找到更优解。

(7)

在新解探索之前调整信息素,增加了除历史最优路径之外的其他路径信息素,以平均距离为界,采用不同方式增加路径信息素,减小了路径间信息素的浓度差距,较大幅度提升较近城市的选中概率,既扩大了新解探索时的搜索范围,又避免了全局盲目搜索。新解探索策略使算法主动跳出局部最优,寻找新解,避免了算法的停滞。

2.2.3“双优”策略改善信息素更新方式

当算法陷入局部最优且天文蚁检查的历史最优路径不存在交叉时,用式(8)进行信息素的补充,直至算法找到更优解,跳出当前局部最优。该策略在保持最优路径信息素不变的前提下,增加了当前迭代最优路径中新路径的信息素,增加当前迭代最优路径的引导能力,在迭代过程中增加了解的可能性,有利于找到新的全局最优解。

(8)

2.3 算法流程

步骤1初始化各参数α、β、Q、τmin、τmax、x、τ0、nt、最大迭代次数T,迭代次数t=0。

步骤2初始化信息素。

步骤3将m只蚂蚁随机放入到n个城市中,并将城市放入禁忌表中。

步骤4每只蚂蚁按照概率(见式(1))选择下一个要访问的城市,并将该城市放入禁忌表中,直到遍历完所有城市,计算其路径长度,并将每只蚂蚁的路径及其长度保存。

步骤5所有蚂蚁遍历完城市之后,保存全局最优路径best_route以及对应最短路径长度min_distance。

步骤6按照式(3)将更新全局信息素。

步骤7判断历史最优路径长度出现的次数是否大于nt,如果是,利用天文蚁检查历史最优路径中是否存在路径交叉的情况,若存在,转到步骤8,若不存在,转到步骤11。

步骤8判断交叉路径类型,若属于图(2)a类,转到步骤9,若属于图(2)b类,转到步骤10。

步骤9采取组合遍历的方式找到交叉路径附近x个城市的最短路径,并更新历史最优路径及其距离,按照式(5)更新该段新路径信息素,转到步骤13。

步骤10对交叉线上的四个城市构建新路径,并更新历史最优路径及其距离,按照式(6)更新该段新路径信息素,转到步骤13。

步骤11判断历史最优路径长度出现的次数是否等于k×nt(k=0,1,…),如果等于,按照式(7)调整信息素,探索新路径,否则,转到步骤12。

步骤12按照式(8)进行更新信息素。

步骤13禁忌表清空,迭代次数t=t+1。如果迭代次数没有达到最大值,则转向步骤3,否则输出最优解并退出循环。

3 实验与结果分析

为了验证本文提出的VC-MMAS算法的有效性,本文对TSPLIB数据库中的TSP问题进行了求解,为了比较VC-MMAS算法的性能,将实验结果与遗传算法(GA)、粒子群算法(PSO)、自组织神经网络(SOM)和最大最小蚂蚁系统(MMAS)进行了比较,实验中所使用的参数均经过试验确定。各算法实验参数分别如下：GA中的重要参数取值为：交叉概率为0.9,变异概率为0.2,种群数量为50;PSO中的重要参数取值为：α=0.9,β=0.9,粒子数量为150;SOM中的重要参数为：初始学习率为0.8,神经元数量m=8×n,最大迭代次数为8 000;MMAS中重要参数取值为：α=0.9,β=2,Q=100,τmin=0.001,τmax=1,ρ=0.05,种群数量m=n;VC-MMAS中各参数的取值为：α=0.9,β=2,Q=100,τmin=0.001,τmax=1,ρ=0.05,x=6,τ0=0.9,nt=50。针对10个TSP问题,除SOM外,其他每种算法最大迭代次数T=1 000。不同TSP问题对应算法的实验结果见表1。

续表1

表1 不同TSP问题对应算法的实验结果对比

表1展示了对于每一个数据集,每种算法独立运行十次,求得每种算法的最优路径长度(Best Length)、最差路径长度(Worst Length)、平均路径长度(Average Length)、标准差(Standard Deviation)。其中Best Length、Worst Length体现了算法的有效性,Average Length、Standard Deviation体现了算法的稳定性,标准差越小,表示该算法稳定性越好,反之,标准差越大,表示算法的稳定性越差,寻优结果波动越大。根据实验的数据,图3展示了CV-MMAS算法在部分数据集上求解TSP问题时的最优路径。由表1可知,VC-MMAS在10个数据集上都获解了最优路径,MMAS在berlin52、gr96上也获解了最优路径,但在这两个数据集上VC-MMAS获解的最差路径优于MMAS;在att48、eil51、berlin52、st70、eil76、gr96、gr202上,VC-MMAS的标准差小于其他4种算法;在eil101、gr666上,VC-MMAS的标准差略大于MMAS。由此可见,VC-MMAS改进效果显著,相较于其他4种算法,在求解TSP问题上有较高的稳定性,不易陷入局部最优。

(a) att(48) (b) eil(51)

5种算法在att48上的仿真收敛对比情况如图4所示,其中,SOM算法每8代取一次数据。可以看出,VC-MMAS算法在迭代前20代就得到了较短的路径;在第400代,GA、SOM算法和MMAS算法就已经陷入了局部最优;直到迭代结束,PSO则经历了400多代,在算法后期跳出了当前迭代最优;VC-MMAS算法在迭代过程中不断跳出局部最优,每100多代就能更新历史最优解,最终找到了最优解。VC-MMAS算法利用启发式信息初始化信息素,避免了算法初期的盲目搜索;在算法陷入局部最优后引入天文蚁消除局部最优、探索新路径,并使用“双优”策略更新信息素,增加了解的多样性,避免了算法陷入停滞状态。

图4 att48的收敛对比图

上述10个TSP问题的仿真实验结果表明,本文提出的VC-MMAS算法在解决TSP问题时具有更好的精度,与其他算法相比,提供的最优路径长度最小且在大多数情况下标准差也最小。

4 结 语

针对蚁群算法在求解TSP问题时表现出的收敛速度慢,易陷入局部最优的现象,本文在MMAS算法的基础上提出了VC-MMAS算法,该算法引入了以下机制：

(1) 结合启发式信息进行信息素的初始化,既符合MMAS算法在初始阶段有较多的搜索可能,又避免了算法初期的盲目搜索,提高了算法的收敛速度。

(2) 在算法陷入局部最优时,引入依靠太阳而非信息素导航的天文蚁,对历史最优路径进行检查和修正。当存在路径交叉时,根据交叉路径的相对位置情况采用不同方式直接消除交叉路径,以较小的时间代价找到更优的路径;当不存在路径交叉时,首先调整信息素,缩小路径间信息素的差距,其次,天文蚁对路径寻优进行干预,强制算法进行新路径的探索,帮助算法找到与历史最优路径差别较大的新的最优路径,避免算法进入停滞状态;使用“双优”策略更新信息素,增加解的可能性,帮助算法找到历史最优路径或当前迭代最优路径相似的更优路径。

在经典TSP问题上的仿真对比实验表明,VC-MMAS算法较其他4种算法具有更强的寻优能力和更高的稳定性。下一步工作将针对大型的TSP数据集,进一步提升算法性能。