基于蚁群算法的TSP问题

基于蚁群算法的TSP问题求解1引言1.1问题描述设计求解以下两个TSP问题的蚁群优化（ACO）算法。其中城市的坐标见附件（kroA100.tsp和kroB100.tsp）。1.2理论基础1.2.1蚁群算法简介蚁群算法是由意大利学者M.Dorigo等人于20世纪90年代初提出的一种新的模拟进化算法，其真实地模拟了自然界蚂蚁群体的觅食行为。M.Dorigo等人将其用于解决旅行商问题（travelingsalesmanproblem,TSP），并取得了较好的实验结果。近年来，许多专家学者致力于蚁群算法的研究，并将其应用于交通、通信、化工、电力等领域，成功解决了许多组合优化问题，如调度问题（job–shopschedulingproblem）、指派问题（quadraticassignmentproblem）、旅行商问题（travelingsalesmanproblem）等。1.2.2蚁群算法基本思想生物学家研究发现，自然界中的蚂蚁觅食是一种群体性行为，并非单只蚂蚁自行寻找食物源。蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。通常，蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径上的信息素浓度，这样会形成一个正反馈。最终，蚂蚁能够找到一条从巢穴到食物源的最佳路径，即是最短距离。值得一提的是，生物学家同时发现，路径上的信息素浓度会随着时间的推进而逐渐衰减。将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。较短的路径上蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上积累的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。1.2.3蚁群算法解决TSP问题的基本原理为不失一般性，设整个蚂蚁群体中蚂蚁的数量为m，城市的数量为n，城市i与城市j之间的距离为ijd(,1,2,...,)ijm，t时刻城市i与城市j连接路径上的信息素浓度为()ijt。初始时刻，各个城市连接路径上的信息素浓度相同，不妨设为0(0)ij。蚂蚁(1,2...,)kkm根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设()kijpt表示t时刻蚂蚁k从城市j的概率，其计算公式为：()(),()()0,kijijkkijisissallowkttsallowpttsallow（1-1）其中()ijt为启发函数，()1/ijijtd，表示蚂蚁从城市i转移到城市j的期望程度；(1,2,...,)kallowkm为蚂蚁k待访问城市的集合，开始时，kallow中有(1)n个元素，即包括除了蚂蚁k出发城市的其它所有城市，随着时间的推进，kallow中的元素不断减少，直至为空，即表示所有的城市均访问完毕；为信息素重要程度因子，其值越大，表示信息素的浓度在转移中起的作用越大；为启发函数重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁会以较大的概率转移到距离短的城市。如前文所述，在蚂蚁释放信息素的同时，各个城市间连接路径上的信息素逐渐消失，设参数(01)表示信息素的挥发程度。因此，当所有蚂蚁完成一次循环后，各个城市间连接路径上的信息素浓度需进行实时更新，即：1(1)(1)(),01ijijijnkijijktt（1-2）其中，kij表示第k只蚂蚁在城市i与城市j连接路径上释放的信息素浓度；ij表示所有蚂蚁在城市i与城市j连接路径上释放的信息素浓度之和。针对蚂蚁释放信息素问题，M.Dorigo等人曾给出了三种不同的模型，分别称之为Antcyclesystem，Antquantitysystem和Antdensitysystem，其计算公式分别如下。（1）Antcyclesystem模型Antcyclesystem模型中，kij的计算公式为：/,0,kkijQLkij第只蚂蚁从城市访问城市其他（1-3）其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；kL为第k只蚂蚁经过路径的长度。（2）Antquantitysystem模型Antquantitysystem模型中，kij的计算公式为：/,=0,ijkijQdkij第只蚂蚁从城市访问城市其他（1-4）（3）Antdensitysystem模型Antdensitysystem模型中，kij的计算公式为：,=0,kijQkij第只蚂蚁从城市访问城市其他（1-5）上述3种模型中，Antcyclesystem模型利用蚂蚁经过路径的整体信息（经过路径的总长）计算释放的信息素浓度；Antquantitysystem模型则利用蚂蚁经过路径的局部信息（经过各个城市间的距离）计算释放的信息素浓度；而Antdensitysystem模型则更为简单地将信息素释放的浓度取为恒值，并没有考虑不同蚂蚁经过路径长短的影响。因此，一般选用Antcyclesystem模型计算释放的信息素浓度，即蚂蚁经过的路径越短，释放的信息素浓度越高。1.2.4蚁群算法的特点基于蚁群算法的基本思想及解决TSP问题的基本原理，不难发现，与其它优化算法相比，蚁群算法具有以下几个特点：（1）采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解。（2）每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯。（3）搜索过程采用分布式计算方式，多个个体同时进行并计算，大大提高了算法的计算能力和运行效率。（4）启发式的概率搜索方式不容易陷入局部最优，易于寻找到全局最优解。1算法设计蚁群算法应用于解决TSP问题一般需要以下几个步骤，如图1所示。开始初始化参数构建解空间更新信息素达到最大迭代次数？输出最优解结束当前迭代次数加1清空路径记录表NY图1蚁群算法解决TSP问题的基本步骤（1）初始化参数在计算之初，需要对相关的参数进行初始化，如蚁群规模（蚂蚁数量）m、信息素重要程度因子、启发函数重要程度因子、信息素挥发因子、信息素释放总量Q、最大迭代次数iter_max、迭代次数初值iter=1。（2）构建解空间将各个蚂蚁随机地置于不同出发点，对每个蚂蚁(1,2...,)kkm，按式（1-1）计算其下一个待访问的城市，直到所有蚂蚁访问完所有的城市。（3）更新信息素计算各个蚂蚁经过的路径长度(1,2...,)kLkm，记录当前迭代次数中的最优解（最短路径）。同时，根据式（1-2）和式（1-3）对各个城市连接路径上的信息素浓度进行更新。（4）判断是否终止若iteriter_max，则令iter=iter+1，清空蚂蚁经过路径的记录表，并返回步骤（2）；否则，终止计算，输出最优解。2算例设计依据蚁群算法解决TSP问题的基本原理及步骤，实现该TSP问题求解大体上可以分为以下几个步骤，如图2所示。计算城市间相互距离初始化参数迭代寻找最佳路径结果分析图2蚁群算法求解TSP问题一般步骤（1）计算城市间相互距离根据城市的坐标位置，计算两两城市间的相互距离，从而得到对称的距离矩阵（维数为100的方阵）。需要说明的是，计算出的矩阵对角线上的元素为0，然而如前文所述，由于启发函数()1/ijijtd，因此，为了保证分母不为零，将对角线上的元素修正为一个非常小的正数。（2）初始化参数如前文所述，在计算之前，需要对相关的参数进行初始化。（3）迭代寻找最佳路径首先构建解空间，即各个蚂蚁根据转移概率公式（1-1）访问所有的城市。然后计算各个蚂蚁经过路径的长度，并在每次迭代后根据式（1-2）和式（1-3）实时更新各个城市连接路径上的信息素浓度。经过循环迭代，记录下最优的路径及长度。（4）结果分析找到最优路径后，可以将之与其它方法得出的结果进行比较，从而对蚁群算法的性能进行评价。同时，也可以研究不同取值的参数对优化结果的影响，从而找到一组最佳或者较佳的参数组合。3仿真实验设计与结果分析4.1仿真实验结果编写MATLAB程序，分别载入两个附件中100个城市的坐标，得到基于蚁群算法的TSP问题的最优解如下：（1）KroA100最短距离：22756.0988最短路径：91982345321117155974217210843699382418795388162294706665426197597568031894289216364990479328675861258169644054244507368853930967852537137633958248100714114343462934835512278635205779875177626091（2）KorB100最短距离：23537.4394最短路径：96921944411745361824771621378633148516414428233156483876074668943525458847579461357112983259769982997912831193857353703940675622610056697530802038864968102190195462592734723765798147882223555096运行结果对应的路径如图3和图4所示，各代的最短距离与平均距离如图5和图6所示。从图中不难发现，随着迭代次数的增加，最短距离与平均距离均呈现下降趋势。当迭代次数大于某一数值后最短距离已不再变化，说明已经找到了最优解。图3KroA优化路径图4KroB优化路径图5KroA各代最短距离与平均距离图6KroB各代最短距离与平均距离4.2参数对优化结果的影响（1）蚂蚁数量m的影响为研究蚂蚁数m对计算结果的影响，比较10组不同蚂蚁数的计算结果，每组计算10次取平均值。同时，由于计算次数多达100次，为提高程序运行速度，暂将最大迭代次数减少为20次，仅对m变化引起结果变化的趋势作以研究（下同）。取α=1，β=5，ρ=0.1，Q=1，研究结果如图7和图8所示。图7蚂蚁数对计算结果的影响图8蚂蚁数对平均最短距离的影响可见，随着蚂蚁数的增加，平均最短距离呈减小的趋势，图中蚂蚁数为45时，得到最小的平均最短距离为27056。（2）信息素重要程度因子α的影响为研究信息素重要程度因子α对计算结果的影响，比较10组不同α值的计算结果，每组计算10次取平均值。取m=45，β=5，ρ=0.1，Q=1，研究结果如图9和图10所示。图9信息素重要程度因子对计算结果的影响图10信息素重要程度因子对平均最短距离的影响可见，随α增大，平均最短距离大体呈下降趋势，当α=10时，得到最小的平均最短距离为27004。（3）启发函数重要程度因子β的影响为研究启发函数重要程度因子β对计算结果的影响，比较10组不同β值的计算结果，每组计算10次取平均值。取m=45，α=10，ρ=0.1，Q=1，研究结果如图11和图12所示。图11启发函数重要程度因子对计算结果的影响图12启发函数重要程度因子对平均最短距离的影响可见，随β增大，平均最短距离呈下降趋势，而当β=10时，得到最小的平均最短距离为24438。（4）信息素挥发因子ρ的影响为研究信息素挥发因子ρ对计算结果的影响，比较10组不同ρ值的计算结果，每组计算10次取平均值。取m=45，α=10，β=10，Q=1，研究结果如图13和图14所示。图13信息素挥发因子对计算结果的影响图14信息素挥发因子对平均最短距离的影响可见，随ρ增大，平均最短距离呈先下降后上升趋势，而当ρ=0.2时，得到最小的平均最短距离为24068。（5）信息素释放量Q的影响为研究信息素释放总量Q对计算结果的影响，比较10组不同Q值的计算结果，每组计算10次取平均值。取m=45，α=10，β=10，