基于蚁群算法的旅行商问题研究VIP

学年论文(课程设计) 题 目 基于蚁群算法的旅行商问题研究 学生姓名 魏倩 学 号 20071336124 学 院 信息与控制学院专 业 自动化指导教师 申晓宁二一 年 12 月 3 日基于蚁群算法的旅行商问题研究魏倩南京信息工程大学信息与控制学院自动化系，南京 210044摘要：介绍了蚂蚁算法的背景，原理及其算法流程。基于matlab软件，采用蚁群算法，求解一个具有30个城市的旅行商问题，并对算法中的三个参数设置问题进行了详细分析，讨论了单一参数变化时对算法性能的影响,并进一步指出了算法改进的思路和方向。 关键词： 蚁群算法，旅行商问题，性能分析，matlabResearch on TSP Based on Ant Colony Algorithm weiqianSchool of information and control, Nanjing University of Information Science & Technology, Nanjing 210044ABSTRACT：This paper presents the background of ant colony algorithm, its principle and its algorithm process. It discusses the three parameters and the relationship between the parameter and the performance of the algorithm when the algorithm is used to solve t he TSP problem of 30 cities on the basis of matlab software in detail . What is more , it points out the thought and direction to improve the method. Key word: ant colony algorithm ; traveling salesman problem; performance analysis; matlab 1. 引言：研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是自组织的。许多场合，尽管这些合作是很简单的，但是其能解决复杂的问题。这种由群居性生物产生出来的一种集体性行为即群体智能，引起了包括计算机科学家在内的很多研究人员的兴趣。而蚁群优化算法（Ant Colony Optimization，ACO）就是一种在蚁群的群居性觅食的基础上形成的一种模拟进化算法，是20世纪90年代意大利的M.Dorigo等学者提出的，并且取得了较好的实验结果。受他们的影响许多的学者也在该算法上得到了许多的研究成果1。10多年来，对蚁群算法的研究表明：蚁群算法不仅能够智能搜索全局最优而且具有鲁棒性、正反馈、分布式计算、易于与其他算法融合等特点。利用正反馈原理可以加快进化过程， 分布式计算使该算法易于并行实现， 蚁群算法易于与其他算法结合可以改善算法的性能，由其鲁棒性，故在基本算法的基础上稍作修改，便可以应用于其他问题，所以，蚁群算法问世以来，为诸多领域解决复杂优化问题提供了有力的工具。M.Dorigo等人将蚁群算法应用于求解旅行商问题、资源的二次分配等经典问题得到较好的结果2。后来的好多的学者将算法进行改进后应用于其他方面。如：将蚁群算法改进后应用于求解连续的优化问题、智能交通、电信路由控制、机器人的路径选择以及图像分割中等3。10多年来，人们对于蚁群算法的研究不断深入，其解决优化问题的作用不断提高，但是蚁群算法存在搜索时间长、易于停滞以及陷入局部最优的缺点，为了克服这些缺点不少学者提出了改进算法4。本文以TSP问题为例进行测试，实验结果表明此算法具有较好的性质。2TSP问题和蚁群算法2.1 TSP问题TSP 问题即旅行售货商问题 ( traveling salesman problem)。描述如下:给定 n个城市的集合 1 ,2 , , n及城市之间环游的费用。TSP问题是指找到一条经过每个城市至少一次且回到起点的最小费用的环游。若将每个城市看成是图上的一个顶点 ,费用看成连接顶点 和 的边上的权,则 TSP问题就是在一个具有 n个顶点的图上找到一条费用最小的Hamilton 回路。任意两个城市 A , B ,如果 A 到 B 的旅行代价和 B 到 A旅行代价相等,称这样的TSP问题是对称的TSP问题，否则称为不对称的TSP问题。通常,在没有特别申明的情况下所提及的 TSP问题指对称的 TSP 间题。自TSP问题提出以来 其求解方法得到了不断的改进，目前已经可以对上万个城市的TS P 问题进行求解。近年来,以蚁群行为为基础的蚁群算法已成为一种较为有效的TSP问题求解方法。2.2基本蚁群算法2.2.1蚁群算法原理蚁群算法 (Ant Colony algorithm ,ACA)是 Dorigo M等人于1991年提出的。经观察发现, 蚂蚁个体之间是通过一种称之为信息素 (pheromone)的物质进行信息传递的。在运动过程中,蚂蚁能够在它所经过的路径上留下该种信息素, 而且能够感知信息素的浓度, 并以此指导自己的运动方向, 倾向于朝着信息素浓度高的方向移动。 因此, 蚁群的集体行为便表现出一种信息正反馈现象: 某一路径上走过的蚂蚁越多, 则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的5。2.2.2蚁群算法基本模型以具有代表性的TSP问题为例,设有n个城市,蚂蚁数量为 m, 表示城市i 和j之间的距离, 表示在t时刻城市i和j之间的路径上残留的信息量, 来模拟实际蚂蚁的信息素浓度。初始化时, m个蚂蚁被放置在不同的城市上, 并赋予每条边上的信息量为。蚂蚁k的tabuk(禁忌表)的第一个元素赋值为它所在的城市。用表示在 t 时刻蚂蚁 k 由城市 i 转移到城市 j 的概率, 则 (1) 其中 表示蚂蚁 k 下一步允许走过的城市的集合, 它随蚂蚁k的行进过程而动态改变;信息量随时间的推移会逐步衰减, , 分别表示蚂蚁在运动过程中所积累的信息量及启发式因子在蚂蚁选择路径中所起的不同作用; 为由城市i 转移到城市 j 的期望程度, 可根据某种启发算法而定。经过n个时刻, 蚂蚁k走完所有的点,完成一次循环。此时,要根据下面公式更新各路径上的信息量: （2） 其中 （3） 表示信息素挥发系数， 表示蚂蚁k在本次循环中在点i和点j之间留下的信息量, 其计算方法根据计算模型而定, 在最常用的 ant cycle system模型中： （4） 其中 Q为常数, 为蚂蚁k在本次循环中所走路径的长度。2.2.3蚁群算法流程步骤 1：nc=0(nc为迭代步数或搜索次数); 每条边上的, 并且; 放置m个蚂蚁到n个城市上。步骤 2：将各蚂蚁的初始出发点置于当前解集tabuk(s)中;对每个蚂蚁 k(k=1,m),按概率移至下一城市j;将城市j置于tabuk(s)中。步骤 3：经过n个时刻,蚂蚁k可走完所有的城市,完成一次循环。计算每个蚂蚁走过的总路径长度, 更新找到的最短路径。步骤 4：更新每条边上的信息量。步骤 5：对每一条边置; nc=nc+1。步骤 6: 若nc预定的迭代次数, 则转步骤2; 否则, 打印出最短路径,终止整个程序。2.2.4影响蚁群算法效果的因素6(1)局部搜索策略。人工蚂蚁在选择将要行走的路线时, 所采用的策略是随机的局部搜索策略。这个策略主要基于以下两点:蚂蚁个体保留的“ 经验” ;问题中公开可用的信息素轨迹和局部信息。(2)蚂蚁的内部状态。内部状态主要保留了对决策有用的信息,用于计算生成解的价值、优劣度和每个执行步的贡献。(3)信息素轨迹。由于信息素轨迹的正反馈机制, 选择某路径的蚂蚁越多, 一个执行步得到的回报就越多, 该路径对于后继蚂蚁的吸引力也就越大。(4)蚂蚁决策策略。蚂蚁的决策策略是由信息素函数与启发信息函数共同决定的, 即概率表。利用基于概率的原理再配合信息素挥发机制, 避免了所有蚂蚁都过早地早熟收敛。3仿真研究3.1 任务要求基于antcycle模型，采用蚁群算法求解具有30个城市的TSP问题。各城市坐标如下：41 ，94；37，84；54，67；25，62；7，64；2，99；68，58；71，44；54，62；83，69；64，60；18，54；22，60；83，46；91，38；25，38；24，42；58，69；71，71；74，78；87，76；18，40；13，40；82，7；62，32；58，35；45，21；41，26；44，35；4，50要求：1.采用Matlab 7.1实现上述优化程序。给出得到的最短路径，用Matlab画出最短路径所连接的城市地图。2分析3个参数：信息激素的启发因子、自启发量因子、信息激素残留系数取不同值时对算法性能的影响。3.2程序分析function R_best,L_best,L_ave,Shortest_Route,Shortest_Length=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)%=%ACATSP.m%Ant Colony Algorithm for Traveling Salesman Problem%-%主要符号说明%C n个城市的坐标，n2的矩阵%NC_max 最大迭代次数%m 蚂蚁个数%Alpha 表征信息素重要程度的参数%Beta 表征启发式因子重要程度的参数%Rho 信息素蒸发系数%Q 信息素增加强度系数%R_best 各代最佳路线%L_best 各代最佳路线的长度%=C=41 ，94；37，84；54，67；25，62；7，64；2，99；68，58；71，44；54，62；83，69；64，60；18，54；22，60；83，46；91，38；25，38；24，42；58，69；71，71；74，78；87，76；18，40；13，40；82，7；62，32；58，35；45，21；41，26；44，35；4，50;m=31;Alpha=1;Beta=5;Rho=.7;NC_max=30;Q=100;%第一步：变量初始化n=size(C,1);%表示问题的规模（城市个数）D=zeros(n,n);%D表示完全图的赋权邻接矩阵for i=1:n for j=1:n if i=j D(i,j)=(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2)0.5; 两个城市之间的距离 else D(i,j)=eps; end D(j,i)=D(i,j); endendEta=1./D;%Eta为启发因子，这里设为距离的倒数Tau=ones(n,n);%Tau为信息素矩阵Tabu=zeros(m,n);%存储并记录路径的生成NC=1;%迭代计数器R_best=zeros(NC_max,n);%各代最佳路线L_best=inf.*ones(NC_max,1);%各代最佳路线的长度L_ave=zeros(NC_max,1);%各代路线的平均长度while NC=rand); to_visit=J(Select(1); Tabu(i,j)=to_visit; end end if NC=2 Tabu(1,:)=R_best(NC-1,:); end %第四步：记录本次迭代最佳路线 L=zeros(m,1); for i=1:m R=Tabu(i,:); for j=1:(n-1) L(i)=L(i)+D(R(j),R(j+1); end L(i)=L(i)+D(R(1),R(n); end L_best(NC)=min(L); pos=find(L=L_best(NC); R_best(NC,:)=Tabu(pos(1),:); L_ave(NC)=mean(L); NC=NC+1 %第五步：更新信息素 Delta_Tau=zeros(n,n); for i=1:m for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i); end Delta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i); end Tau=(1-Rho).*Tau+Delta_Tau; %第六步：禁忌表清零 Tabu=zeros(m,n);end%第七步：输出结果Pos=find(L_best=min(L_best);Shortest_Route=R_best(Pos(1),:);Shortest_Length=L_best(Pos(1);subplot(1,2,1)DrawRoute(C,Shortest_Route)subplot(1,2,2)plot(L_best)hold onplot(L_ave,r)title(平均距离与最短距离)function DrawRoute(C,R)%=%DrawRoute.m%画路线图的子函数%-%C Coordinate 节点坐标，由一个N2的矩阵存储%R Route 路线%=N=length(R)scatter(C(:,1),C(:,2)hold onplot(C(R(1),1),C(R(N),1),C(R(1),2),C(R(N),2)hold onfor ii=2:N plot(C(R(ii-1),1),C(R(ii),1),C(R(ii-1),2),C(R(ii),2) hold onendtitle(旅行商问题优化结果)在MATLAB中运行上述程序，得出下图3.1： 图3.1 旅行商优化结果及最短距离注：红线为平均距离，蓝线为最短距离。由图形可知，当=1，=5，=0.7时，得到的最短距离为428，远小于平均距离，城市的遍历顺序为(41,94)(37,84)(2,99)(7,64)(25,62)(22,60)(18,54)(4,50)(13,40)(18,40)(24,42)(25,38)(45,21)(41,26)(44,35)(58,35)(62,32)(82,7)(91,38)(83,46)(71,44)(68,58)(64,60)(54,62)(54,67)(58,69)(71,71)(83,69)(87,76)(74,78)。由此可知，蚁群算法可以很好地解决旅行商问题。3.3参数分析需要指出的是,下述分析是在确定其他参数的前提下,调整其中某一参数来考察算法的收敛效果和性能的。如何针对参数的组合变化情况对算法的性能进行分析,目前仍没有明确的结论和理论指导。3.3.1信息激素的启发因子当取=5 ，=0.7时，TSP优化结果及最短距离随着的变化相应地如图3.23.5所示： 图3.2 =0图3.3 =1图3.4 =50图3.5 =100表示信息素轨迹的相对重要性，0，通过对以上四幅图的对比可知取1时得到的最优解最好。但是随着的增大，收敛速度会随着加快。 3.3.2自启发量因子 当取=1，=0.7时，TSP优化结果及最短距离随着的变化相应地如图3.63.9所示： 图3.6=0图3.7=0.5图3.8=5图3.9=50表示能见度的相对重要性，0。由上面四幅图的对比可知，对算法的性能影响较大，这也表明城市之间的局部路径在蚂蚁算法中得到了充分考虑。其中在5左右时算法性能最优，收敛速度也最快。3.3.3信息激素残留系数 当取=5，=1时，TSP优化结果及最