蚁群算法及其应用实例

1、蚁群算法及其应用实例、,、刖百：本文章相关内容参考自包子阳等编著智能优化算法及其MATLAB实例(第2版)，将自己的理解写出来供读者参考，笔者将算法Matlab实例用Python改写，如存在不合理的地方评论指正。主要内容有：1.蚁群算法理论2.基本蚁群算法描述3蚁群算法TSP问题中的应用实例(Pyhton)、蚁群算法理论蚁群算法(antcolonyoptimization,ACO),又称蚂蚁算法，是一种对自然界蚂蚁的寻径方式进行模拟而得到的一种仿生算在图中寻找优化路径的机率型算法。蚂蚁在运动过程中，可以在行走的路径上留下信息素，后来的蚂蚁可以感知到信息素的存在，信息素浓度越高的路径越容易被后来

2、的蚂蚁选择，从而形成一种正反馈现象。它能够求出从原点出发，经过若干个给定的需求点，最终返回原点的最短路径。这也就是著名的旅行商问题(TravelingSalemanProblem，TSP)。1真实蚁群若蚂蚁从A点出发到D点觅食，它可以随机从ABD或ACD中选择一条路。假设初始时为每条路分配一只蚂蚁，每个时间单位行走一步，则经过8个时间单位后，情形如下图所示：ABD路线的蚂蚁到达D点，ACD路线的蚂蚁到达C点。蚂蚁出发后8个时间单位情形.png那么，再过8个时间单位，很容易可以得到下列情形：ABD路线的蚂蚁回到A点，ACD路线的蚂蚁到达D点。蚂蚁出发后16个时间单位情形.png经过32个单位时间

3、后，ABD路径上的蚂蚁往返两趟，ACD往返一趟，那么ABD与ACD路径上的信息素浓度比值为2:1。根据信息素的指导，接下来ABD路径就有2只蚂蚁选择，ACD路径仍然为1只，经过32个单位时间后信息素就会达到3:1。因此会有越来越多的蚂蚁选择ABD,ACD逐渐被放弃，这就形成了正反馈。2人工蚁群基于以上真实蚁群寻及食物时的鼓优路径选择问题，可以构造人工蚁聲，来解扶最优化问题，如TEP问题人工蚁群中把具有简单功能的工作单元看作虾蚁二者的相似之处在于都是优先选择信息素浓度大的路径。较短轉径的信息高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果两者贰区别在于人工蚁群有一-定贰记忆能力，能够记忆已经

4、访问过的节点.同时，人工蚁群再选择F条路径的时喉是按定算法规律有意识地寻找最短路径.而不是盲目的a倒如在TEP问题中，可以预先知道当前城市到下一个目的地的距离，在TSP问题的人工蚁群算假设闪只蚂蛻在图的相邻节点同移动，从而协乍异芳地得到问题的解。每只蚂蚁抽一步转移概率由阁中的每条边上的两类蔘数决定：一是信息素（5,也称信息素痕迹：二是可见度*即先验殖。信息素的更新方式有两种：-是挥发.也就是所有路径上的信息素以定的比率减少，模拟自然蚁群的信息素随时用挥发的过程：-是塩强，给评价價计（有蚂蚁走过）的边堪加信息素.蚂蚁向下一个目标的运动是通过一个随机原则来实现的.也就是运月当前所在节心存储的莖息，

5、计算出下“步可达节点的橇率，井按此槪率实现歩移动，如此往复，越来越接近最优認。蚂蚁在寻找过程中.或在找到个解后，会评怙该解或解的一部3蚁群算法特点-.蚁群算法是一种本质上的并行算法，每只蚂蚁独立运行，仅通过信息素通信。蚁群算法是一种自组织算法，自组织就是系统从无序到有序的变化过程蚁群算法具有较强的鲁棒性，求解结果不依赖于初始路线的选择，求解过程不需要人工调整，参数少，设置简单，易于应用到组合优化问题。蚁群算法是一种正反馈算法。二、基本蚁群算法1基本蚁群算法表述基本蚁群算法表述：在算法的初始时刻，将m只蚂蚁随机分配到n座城市，并将禁忌表(存放访问过的城市)的第一个元素设置为当前所在城市。初始化各

6、路径上的信息素量，各路径上信息素量设为相同。接下来，每只蚂蚁根据路径上的信息素量和启发式信息独立地选择下一座城市。当所有蚂蚁完成次周游后，对各个路径上的信息素进行更新。在时刻t,蚂蚁k从城市i转移到城市j的概率为：概率公式f*=allowedk其中，a和卩分别表示信息素和期望启发式因子的相对重要程度。Tij(t)表示信息素量。表示启发式因子，通常取城市i与城市j的距离的倒数。表示蚂蚁k尚未访问城市的集合。蚂蚁周游一次后信息素按照下式进行更新:牛(f+町=(1一Q奇+A信息素更新公式其中，p表示信息素蒸发系数，i-p即为信息素残留系数G(+)表示n只蚂蚁周游后的信息素量ifJIfCl表示信息素的

7、增量根据信息素增量的不同计算规则，蚁群算法分为三种模型:Q是一个正常数Lk是蚂蚁k本次周游中所走过的路径的长度蚁周模型Ant-Cycle直当吗蚁斤在本次周游中经过边如寸0.其他蚁量模型Ant-QuantityZ,当蚂蚁k在时刻f和/十1经辽边帀时h其他*蚁密模型Ant-Density卜0,当蚂蚁无在时刻f和2+1经过边Ar.=勺0其他2各参数分析信息素启发式因子aa代表信息素量对是否选择当前路径的影响程度，反映了蚁群在路径搜索中随机性因素作用的强度。a越大，蚂蚁选择以前走过的路径的可能性越大，搜索的随机性就会减弱。a过小，会导致蚁群搜索过早陷入局部最优，取值范围通常为1,4。期望启发式因子BB

8、反映了启发式信息在指导蚁群搜索中的相对重要程度，蚁群寻优过程中先验性、确定性因素作用的强度。B过大，虽然收敛速度加快，但是易陷入局部最优。B过小，蚁群易陷入纯粹的随机搜索，很难找到最优解。通常取0,5。信息蒸发系数PP反映了信息素的蒸发程度，相反，1-Q表示信息素的保留水平P过大，信息素会发过快，容易导致最优路径被排除。P过小，各路径上信息素含量差别过小，以前搜索过的路径被在此选择的可能性过大，会影响算法的随机性和全局搜索能力。通常取0.2,0.5。蚂蚁数目mm过大，每条路径上信息素趋于平均，正反馈作用减弱，从而导致收敛速度减慢。m过小，可能导致一些从未搜索过的路径信息素浓度减小为0，导致过早

9、收敛，解的全局最优性降低信息素强度Q总信息量Q对算法性能的影响有赖于aBp的选取，以及算法模型的选择。Q对ant-cycle模型蚁群算法的性能没有明显影响，不必特别考虑，可任意选取。3算法步骤三、蚁群算法实例#-*-coding:utf-8-*-Author:WuXianTime:2020/10/3021:17File:antTSP.pyTitle:蚁群算法解决TSP的Python实现frommatplotlibimportpyplotaspltimportnumpyasnpimportmathimportrandom”符号注释：cities:数组，记录个城市坐标n:整型，城市数量m:整型，蚂

10、蚁个数，取城市数目的1.5倍NC:迭代计数器NC_MAX:最大迭代次数ALPHA:常数，a,信息素启发式因子，a选择1,4比较合适BETA:常数，B，期望启发因子，B选择345比较合适RHO:常数，p,信息素蒸发系数，p选择0.1,0.2,0.5比较合适Q:常数，信息素强度Eta(i,j):启发因子n，距离的倒数est_pathi各代最佳路toBest_Path_Len:各代最佳路线长度Best_Path_Len_Average:各代路线的平均长度Table_Phe=叩.ones(n,n)#n*n信息素矩阵，初始值都为1Table_Path=叩.zeros(m,n)#m*n路径记录表Dista

11、nce=叩.zeros(n,n)#n*n两城市间距离矩阵flHfl1.参数初始化cities=1304,2312,3639,1315,4177,2244,3712,1399,3488,1535,3326,1556,3238,1229,4196,1044,4312,790,4386,570,3007,1970,2562,1756,2788,1491,2381,1676,1332,695,3715,1678,3918,2179,4061,2370,3780,2212,3676,2578,4029,2838,4263,2931,3429,1908,3507,2376,3394,2643,3439,3

12、201,2935,3240,3140,3550,2545,2357,2778,2826,2370,2975#城市坐标矩阵n=len(cities)#城市数量m=int(n*1.5)#蚂蚁数量，取城市数的1.5倍NC=0#迭代计数器，从0开始，表示第NC+1次迭代NC_MAX=100#最大迭代次数，取100500之间ALPHA=1#常数，a,信息素启发式因子BETA=5#常数，B，期望启发因子RHO=0.1#常数，p,信息素蒸发系数Q=100#常数，信息素强度Best_Path=叩.zeros(NC_MAX,n)#NC_MAX*n矩阵，记录NC_MAX次迭代的所求最佳路径，每条记录表示一次迭代所

13、的最优路径Best_Path_Len=叩.zeros(NC_MAX,1)#NC_MAX*1矩阵，记录每次的最佳路径长度Best_Path_Len:,:=np.inf#暂时赋值为infBest_Path_Len_Average=叩.zeros(NC_MAX,1)#最优路径长度平均Table_Phe=叩.ones(n,n)#n*n信息素矩阵，初始值都为1Table_Path=叩.zeros(m,n)#m*n路径记录表Distance=叩.zeros(n,n)#n*n两城市间距离矩阵#计算两城市间的距离foriinrange(0,n):forjinrange(0,n):ifi!=j:Distance

14、i,j=math.sqrt(citiesj0-citiesi0)*2+(citiesj1-citiesi1)*2)else:Distanceij=1e-4Eta=1./Distance#启发因子，取距离的倒数2迭代寻找最佳路径whileNCrandom.random()to_visit=Unvisited:,int(SelectO)Table_Pathi,j=to_visit#将代访问城市加入Table_Path矩阵，代表该城市被访问2.3.记录本次迭代最佳路线Length=叩.zeros(m,1)#m*1矩阵，记录每只蚂蚁的路径长度foriinrangem):#计算每只蚂蚁的路径长度Rout

15、e=Table_Pathi,:#在Table_Path表中找到该蚂蚁的路径行，将整行赋给Routeforjinrange(0,n-1):#对路径长度求和Lengthi=Lengthi+Distanceint(Routej),int(Routej+1)Lengthi=Lengthi+Distanceint(Route0),int(Routen-1)#从最后一个节点回到起点的距离ifNC=0:#第一次迭代min_length=叩.min(Length)#m只蚂蚁路径长度最小值min_index=np.argmin(Length)#最小值索弓IBest_PathNC,:=Table_Pathmin_

16、index,:#最优路径表Best_Path_LenNC,:=min_length#最优路径长度为最小值Best_Path_Len_AverageNC,:=叩.mean(Length)#求平均print(f最短路径：Best_Path_LenNC,:)else:#第NC次迭代minength=np.min(Length)min_index=np.argmin(Length)Best_Path_LenNC,:=min(Best_Path_LenNC-1,minength)Best_Path_Len_AverageNC,:=叩.mean(Length)ifBest_Path_LenNC,:=min

17、ength:Best_PathNC,:=Table_Pathmin_index,:else:Best_PathNC,:=Best_PathNC-1,:print(f最短路径：Best_Path_LenNC,:)2.4.更新信息素Delta_Table_Phe=叩.zeros(n,n)#信息素变化量矩阵foriinrange(0,m):forjinrange(0,n-1):Delta_Table_Pheint(Table_Pathi,j),int(Table_Pathi,j+1)=Delta_Table_Pheint(Table_Pathi,j),int(Table_Pathi,j+1)+Q/L

18、engthi,:Delta_Table_Pheint(Table_Pathi,n-1),int(Table_Pathi,0)=Delta_Table_Pheint(Table_Pathi,n-1),int(Table_Pathi,0)+Q/Lengthi,:Table_Phe=(1-RHO)*Table_Phe+Delta_Table_Phe2.5.禁忌表清零Table_Path=np.zeros(m,n)print(*100)NC=NC+1#进入下一次迭代3.迭代结束，结果输出shortest_length=叩.min(Best_Path_Len)#在Best_Path_Len中找出最短长度

19、shortest_index=叩.argmin(Best_Path_Len)#取得该最短长的的路径在Best_Path_Len中的位置Shortest_Route=Best_Pathshortest_index,:#根据位置在bast_path中找到该路径print(f最短路径:Shortest_Route+1)print(f最短路径长度:shortest_length)4可视化输出4.1最短路径可视化#创建窗口fig1=plt.figure(figsize=(10,8),dpi=120)#这只图片大小figsize(len,width),dpi设置像素值#准备数据x=#存放各城市横坐标y=#

20、存放各城市纵坐标foriinrange(0,len(cities):#取值route=citiesint(Shortest_Routei)append(route0)y.append(route1)#绘制坐标plt.xticks(np.arange(O,5000,500)plt.yticks(np.arange(O,5000,500)plt.xlabel(x)plt.ylabel(y)plt.title(*最优路径图)c=0fori,jinzip(x,y):#给各个点标注plt.text(i+0.1,j+0.3,str(int(Shortest_Routec+1),ha=center,va=bottom,fontsize=10.5)c+=1plt.rcParamsfont.sans-serif=MicrosoftYaHei#解决matplotlib不显示中文plt.grid(alpha=0.2)#绘制网格,alpha=0.2表示透明度#画图plt.plot(x,y,color=orange)plt.scatter(x,y,c=black,marker=o)end2Start_x=凶len(x)-1,x0end2Start_y=ylen(y)-1,y0plt.plot(end2Start_x,end2Start_y,color