自适应蚁群算法求解最短路径和TSP问题

自适应蚁群算法求解最短路径和TSP问题易正俊1李勇霞1易校石2(重庆大学数学与统计学院，重庆401331)1(重庆师范大学数学科学学院，重庆401331)2摘要：该文对传统蚁群算法的初始化信息素浓度加入方向引导，避免蚁群在初始阶段盲目的随机搜索浪费较多的时间；在全局信息素更新过程中加入双曲正切函数作为动态因子，自适应地更新每次迭代较优解路径的信息素浓度，增大算法获取全局最优解的可能性。文中的两个算例采用改进的蚁群算法进行优化，优化的结果与实际具有良好的一致性，说明了改进算法的有效性和实用性。关键词：蚁群算法；最短路径；方向引导；动态因子：TSPSolvingtheShortestPathProblemandTSPProblemwithAdaptiveAntColonyAlgorithmLIyong-xia1YIxiao-shi2YIzheng-jun1(ChongqingUniversity，chongqing401331)1(ChongqingNormalUniversity，chongqing401331)2Abstract:Directionguidingisutilizedintheinitialpheromoneavoidingantcolonyintheinitialstagetoblindlyrandomsearchandtowastemoretime.Moreover,Adynamicfactor(hyperbolictangentfunction)isinvitedtotheglobalrenewalprocesstoupdateadaptivelythepheromoneconcentrationontheoptimalpath.,inwhichwaythepossibilityofobtainingtheglobaloptimalsolutionisincreased.Thentwoexampleswiththeimprovedalgorithmwasoptimized,theoptimizationresultsinstepwiththeactual,illustratingtheeffectivenessandpracticabilityoftheimprovedalgorithm.Keywords:Antcolonyalgorithm,Shortestpath,Directionguiding,Pheromone:TSP0引言蚁群算法（ACS，AntColonySystemAlgorithm）是由意大利学者Dorigo等人于20世纪90年代初期提出的一种基于种群的启发式随机搜索算法[1-4]，蚁群算法具有正反馈、鲁棒性、并行性等优点,有很多的文献采用蚁群算法计算最短路径的问题.最短路径问题在交通运输、物流配送、网络分析、管道铺设、厂区选取等有广泛的应用.如交通运输往往需要尽可能降低运输成本,等价于搜索运输网中两节点的最短路径.但传统的蚁群算法在计算较复杂的网络图中两节点间的最短距离时容易陷入局部最优、且随着网络图的复杂程度的增加其收敛速度慢,还有可能出现停滞现象[5-6]。针对这些问题，有些学者对传统的蚁群算法做了一些相应的改进。有的将信息素浓度控制在一定范围内变化，避免蚂蚁都选择同一条路径，避免算法中的停滞现象。如Stuzle等提出“最大最小蚁群系统”（Max-MinAntSystem）[7];有的把蚁群算法与其它算法相结合,增强算法的寻优能力，如CLORNEI等结合了蚁群算法和遗传算法[8]；还有对较优信息素浓度进行奖励，对较差信息素浓度进行惩罚，如郑卫国等提出带奖罚的蚁群算法[9]。这些改进的蚁群算法虽然获得了较好的最优解，但初始搜索时间较长，全局更新规则中没有考虑较优解。本文对初始信息素浓度进行方向的改进：距离目标方向越近的路径，就提高此路径上信息素浓度比例，这样就会促进蚂蚁在寻找食物源时以最大概率沿着信息素浓度高的路径，用本文受基金项目1国家自然科学基金（No.69674012），基金项目2重庆市科技攻关计划（No.CSTC2009AC3037）资助。易正俊（1963-），男，博士，教授，全国专业学位研究生教育教指委专家,主要研究方向为人工智能，仿真系统，数据挖掘。李勇霞（1988-），女，硕士生，主要研究方向为智能算法;易校石（1991-），女，硕士生，主要研究方向为智能算法2016-11-2116:41:28最短的时间接近最优食物源的快速通道，避免初始搜索时间较长的缺陷；由于传统蚁群算法的动态因子在调节全局信息素浓度时不具有自适应性，因此引入双曲线正切函数在全局的信息素浓度更新中作为其自适应动态因子，每次迭代最优解路径的信息素浓度时具有一定的自适应性，使最优路径的信息素增大，从而增大了算法获取最优解的可能性，缩短了算法的收敛时间。1最短路径问题的描述设一个带权重的有向图G=（V，{L}）,其中V是含有n个节点的集合，L是边的集合，每条边(,)ijL都赋予一个非负权重ijd，表示节点i到节点j间的距离大小，其中,ijV。设B，E分别为V中的任意两点，最优路径问题就是在带有权重的有向图中，寻找从点B到E的一条具有最小权重总和的路径。2蚁群算法的改进一种仿生算法--蚁群算法，是模拟自然界蚂蚁寻找食物过程而得出。在此过程中，它们总能找到从巢穴到食物源之间的一条最短路径。其原因在于蚂蚁在路径上会释放一种信息激素（pheromone）进行信息传递，而这种物质在运动过程中蚂蚁还能够感知，由它来指导其运动方向。当它们碰到一个陌生路口时，就会随机地选出一条路径进行前行，于此同时蚂蚁会在这条路径上释放一定量的信息素，此时路径上的信息素浓度增大，后来的蚂蚁再次碰到这个路口的时候，就会遵循选择信息素浓度高的路径,这样就形成一种正反馈。最优路径上的激素浓度越来越大，最终整个蚁群就会搜索出一条最短路径。2.1算法初始时刻浓度改进传统的蚁群算法在初始迭代时给每条路径上的浓度是一个常数，那是蚂蚁不知道每条路径的长度，它只能随机的选择，产生了大量无关紧要的路径，阻碍最优路径搜索过程，同时对信息素浓度局部更新也会产生影响。但我们在求最短路径时，节点与节点之间的距离是已知的，因此在用蚁群算法求最短路径时，没有必要盲目的选择，可以对迭代开始时的初始浓度进行精确赋值。设在网络图中需要求出从点B到E的一条最短路径。其中的节点i和节点j之间路径上的初始信息素浓度为(0)ij应该反映靠近最短距离的程度,越靠近最短距离,浓度应该越大,,用BEd表示起点B到终点E的直线距离,Bjd表示节点B与节点的j直线距离,jEd表示节点j到终点E的直线距离,Bjd+jEd表示BJE的曲线距离,/()BEBjjEddd表示,BjjEdd就越趋向于BEd，/()BEBjjEddd表示越接近于1,此条路径上的浓度越大,蚂蚁就越偏向选择这些节点作为移动方向,因此节点i和节点j之间路径上的初始信息素浓度为(0)ij定义为:(0)BEijBjjEddd（1）算法的这种改进使得蚂蚁在搜索过程产生了比较合理的方向引导，进而对无关路径起到抑制作用，避免蚂蚁的盲目搜索,提高了搜索全局最优解的速率。2.2全局更新规则的改进传统蚁群算法在全局更新规则中只更新每次迭代的最优路径上的信息素浓度。这样就导致某些较短路径信息素浓度过分增加，全局最优路径与单次迭代的最优路径相关性较大[12]易陷入局部最优。在全局更新规则中本文引入自适应动态因子((0,1))，这样不仅可以实时动态更新每次迭代最优路径的全局信息素浓度，而且也要动态更新较优的局部最优解。经过自适应控制单次迭代最优解的信息素浓度在当前最优解中的比重，从而较优路径信息素浓度发挥了更大的作用以及更好的反应了路径信息，最优解逐渐凸现，加快全局最优解的收敛速度。传统算法的动态因子为11()sgn()22fxx，可以看出它仅仅在全局最优路径上取1，也就是说只加强最优路径上信息素浓度，而较优路径上的信息素浓度没有及时的更新。故对较优路径信息素浓度更新不具有自适应性，因此本文选用的自适应动态因子为双曲正切函数11()tanh()22fxx输出为平滑曲线，取值范围为[0,1]。为控制双曲正切函数形状的参数。不仅最优路径信息素浓度得到更新，更重要的是较优路径同时得到了自适应的更新。在完成每次迭代后，更新本次迭代最优解路径信息素浓度，规则如下：(1)()ijijijtt（2）minminmin11tanh()22localLLLL（3）其中L为当前局部最优解的平均长minlocalL为此次迭代的最优路径长度，minL为当前全局最优解，为给定参数。对于自适应因子，当minlocalL越大，即搜索路径越长时，动态因子越趋于0；而当minlocalL越小，搜索路径越短时，动态因子越趋于1。所以搜索到的路径长度越短，全局更新时它所遍历的路径信息素浓度越加强，信息量增加就会较快。如图1给出取不同值时，双曲正切函数曲线以及与传统蚁群算法动态因子的对比图图1动态因子函数曲线图对于双曲正切函数()fx，当(1,1)x时，可以看到()fx变化率最大，那么敏感度就较高，这样有效区分了不同迭代最优解对信息素加成的影响，加强局部最优解中路径更短的信息素浓度，加快收敛的全局最优解的速度；当1x时，()fx缓慢趋向于0，这样不但对不利解对信息素加成起到抑制作用，同时保留了其部分影响，进而也增加了解空间的多样性；当1x时，()fx缓慢趋于定值1，这样更好地避免部分较短但不是全局最优路径被过度增强，有效地防止算法陷入局部最优解。与此同时，对于自适应动态因子是平滑过渡，故不会对信息素浓度造成波动影响。从图中可以看出越大，()fx对x的灵敏度就越高。3.自适应蚁群算法的步骤以上是对传统蚁群算法的改进内容，其改进后的算法实现步骤如下：步骤1初始化信息启发因子（轨迹的相对重要性），期望启发因子，路径启发因子ij，1ijijd其中ijd为ij的欧氏距离；蚂蚁状态转移的阈值0q；设定最大迭代次数N,选定蚂蚁只数m。步骤2计算节点距离矩阵，初始化信息素浓度(0)ij，将m只蚂蚁放在起点B，将各蚂蚁的初始节点B置于当前解集ktabu中，第k只蚂蚁从i节点转移到下一个节点j的规则：在0与1之间随机生成一个实数q，把它与事先给定的阈值0(0,1))q进行比较：当0qq时，第k只蚂蚁选取下一个节点j为与i相连的边上的()()isistt最大值所对应的节点，即argmax()()ikisissallowedjtt当0qq时，以轮盘赌的方式计算第k只蚂蚁由i转移到下一个节点l的概率：()(),()()()0,ikiililkisiskilsallowedikttlallowedttptlallowed其中ikallowed=｛与i相连的节点｝-｛蚂蚁k已经访问过的节点｝，即每只蚂蚁对每个节点最多访问一次。选取概率最大的节点j，即：argmax()ikkijiallowedjpt步骤3信息素浓度的局部更新：在蚂蚁完成一次搜索后，信息素一方面要挥发掉一部分，另方面蚂蚁在走过的路径上要释放一定量的信息素，设挥发和增加信息素的系数均为，更新规则如下：(1)(1)()()ijijijttt（4）其中1()()mijkijktt()kijt为本次循环中蚂蚁k对边(,)ij的信息素增量，若蚂蚁没有经过此条路径，则()0kijt，否则，用Q表示增加浓度的总和，可视为一个常数，用kL为第k只蚂蚁在本次循环搜索中搜索到的路径长度，则定义()kijkQtL，公式（4）表示下一次迭代路径的信息素浓度为已挥发剩下的浓度与新释放的信息素浓度的和。步骤4重