蚁群算法实现TSP(共14页).doc

《蚁群算法实现TSP(共14页).doc》由会员分享，可在线阅读，更多相关《蚁群算法实现TSP(共14页).doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上蚁群算法求解TSP问题 目录蚁群算法求解TSP问题摘要：蚁群算法是通过蚂蚁觅食而发展出的一种新的启发算法，该算法已经成功的解决了诸如TSP问题。本文简要学习探讨了蚂蚁算法和TSP问题的基本内容，尝试通过matlab仿真解决一个实例问题。关键词： 蚁群算法；TSP问题；matlab。一 、引言 TSP（Travelling Salesman Problem）又称货郎担或巡回售货员问题。TSP问题可以描述为：有N个城市，一售货员从起始城市出发，访问所有的城市一次，最后回到起始城市，求最短路径。TSP问题除了具有明显的实际意义外，有许多问题都可以归结为TSP问题。目前针对这

2、一问题已有许多解法，如穷举搜索法（Exhaustive Search Method）, 贪心法（Greedy Method）, 动态规划法（Dynamic Programming Method）分支界定法（Branch-And-Bound），遗传算法（Genetic Agorithm）模拟退火法(simulated annealing),禁忌搜索。本文介绍了一种求解TSP问题的算法蚁群算法，并通过matlab仿真求解31个省会城市之间的最短距离，经过仿真试验，证明是一种解决TSP问题有效的方法。20世纪90年代，意大利学者M.Dorigo等人在新型算法研究的过程中，通过模拟自然界蚂蚁的觅食过程

3、：即通过信息素（pheromone）的相互交流从而找到由蚁巢至食物的最短路径，提出了一种基于信息正反馈原理的新型模拟进化算法蚁群算法（Ant Colony algorithm）。蚁群算法是继遗传算法、人工神经网络等算法之后的又一种启发式算法，它的基本原理借鉴了这样一个客观事实：蚂蚁由自组织的合作能力所产生的群体智能来寻找路径，它被认为是用于解决组合优化问题的又一种新方法。蚁群算法是一种适应性好、鲁棒性强,具有正反馈结构的并行算法。这些初步研究已显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的一些优越性,证明它是一种很有发展前景的方法。蚂蚁算法在各个领域的应用,说明该算法有着广泛的适

4、应性,但由于该算法出现的较晚,对其研究还处于起步阶段,远不如遗传算法、人工神经网络和模拟退火算法那样成熟。二、蚁群算法原理蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理，根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化（如原有路径上有了障碍物）后，自适应地搜索新的最佳路径。蚂蚁是如何做到这一点的呢？原来，单个的蚂蚁为了避免自己迷路，它在爬行时，同时也会释放一种特殊的分泌物信息素（Pheromone），而且它也能觉察到一定范围内的其它蚂蚁所分泌的信息素，并由此影响它自己的行为。当一条路上的信息素越来越多（当

5、然，随着时间的推移会逐渐减弱），后来的蚂蚁选择这条路径的概率也就越来越大，从而进一步增加了该路径的信息素浓度，这种选择过程称为蚂蚁的自催化过程，其原理是一种正反馈机制。这里我们可以用一个图来说明蚂蚁觅食的最短路径选择原理，如图2-1所示。图2-1 蚁群觅食原理如图2-1（a）所示，我们假设A点是食物，而E点是蚂蚁的巢穴，当A、E两点间没有任何障碍物阻挡时，蚂蚁不存在路径选择的问题，这种情况最简单：由于两点间直线距离最短，蚂蚁们搬运食物时，会以直线的形式往返爬行。但在图2-1（b）中的情形有所变化，若某时刻忽然有一个障碍物出现在蚂蚁经过的路径中，原有的路径被切断，那么从A点到E点的蚂蚁就必须在B

6、点决定应该往左还是往右走，而从E点到A点的蚂蚁也必须在D点决定选择走哪条路径；这种决定会受到各条路径上以往蚂蚁留下的信息素浓度（即残留信息素浓度）的影响。如果往右走的路径上的信息素浓度比较大，那么右边的路径被蚂蚁选中的可能性也就大一些；但是对障碍出现后第一个到达B点或D点的蚂蚁而言，因为没有信息素的影响，所以它们选择向左或者向右的可能性是一样的，（b）图所表示的正是此时的情况。若以从A点到E点的蚂蚁为例进行说明（对于从E点到A点的蚂蚁而言，过程也基本是一样的），由于路径BCD比路径BHD要短，因此选择BCD路径的第一只蚂蚁要比选择BHD的第一只蚂蚁早到达D点；此时，从D点向B点看，路径DCB上

7、的信息素浓度要比路径DHB上的信息素浓度大。因此从下一时刻开始，从E点经D点到A点的蚂蚁，它们选择DCB路径的可能性要比选择DHB路径的可能性大得多，从而使路径BCD（或DCB）上信息素浓度与路径BHD（或DHB）上信息素浓度的差变大；而信息素浓度差变大的结果是选择路径BCD（或DCB）的蚂蚁进一步增加，这又导致信息素浓度差进一步加大。如图2-1（c）所示，随着时间的推移，几乎所有的蚂蚁都会选择路径BCD搬运食物，而我们同时也会发现：BCD路径也正是事实上的最短路径。这种蚁群寻径的原理可简单理解为：对于单个的蚂蚁来说，它并没有要寻找到最短路径的主观上的故意；但对于整个蚁群系统来说，它们又确实达

8、到了寻找到最短路径的客观上的效果。在自然界中，蚁群的这种寻找路径的过程表现为一种正反馈的过程，与蚁群算法中人工蚁群的寻优算法极为一致。例如，我们把只具备了简单功能的工作单元视为“蚂蚁”，那么上述寻找路径的过程可以用于解释蚁群算法中人工蚁群的寻优过程。三、蚁群算法解决问题我们来介绍一下如何用蚁群算法求解个城市的TSP设为城市，之间的几何距离，。设 表示时刻位于城市的蚂蚁的个数，蚂蚁总数，表示时刻在连线上残留的信息量，初始时刻各条路径上的信息量为（为常数）。用参数表示信息量的保留度，则经过个时刻后，路径上的信息量根据下式作调整： 表示第只蚂蚁在本次循环中留在路径上的信息量，表示本次循环所有经过的蚂

9、蚁留在上的信息量。 定义。蚂蚁（，）在运动过程中，表示在时刻蚂蚁由位置转移到位置的概率： 我们用记录蚂蚁目前已经走过的城市集合，allow表示蚂蚁下一步允许选择的城市集合，它等于全部的城市集合除去第只蚂蚁已走过的集合。 定义为第只蚂蚁在本次循环中走过的路径和。 用蚁群算法解决问题是一个递推过程 ，当时，将蚂蚁放在各城市，设定每条路径上的信息量初值，每只蚂蚁根据公式决定的概率从城市到城市。表示曾经有多少蚂蚁经过路径（，）；说明较近的城市有更大的可能性被选中。，用来控制两者对蚂蚁选择的影响力程度。经过一个循环后，根据公式计算更新每条路径的信息量。将所有的复原，最后求出本次循环的最短路径min。这个

10、过程不断重复，直到所有的蚂蚁都选择同样的路径，或者循环次数达到预先设定的最高次数。四、解决个城市的TSP问题的算法步骤1.初始化：设定t=0，循环计数器nc=0，对每条路径设定初始信息量C,将只蚂蚁放在个城市上（为了使问题简化，设定）。2.设定taub集合的索引，对从到，把第只蚂蚁放在起始位置，对应的设定集合3.重复下面的步骤，直到集合tabu满为止（这一步将重复次）：设定；对从到，根据公式确定的概率，选择下一步移动的目标城市在时间时，第只蚂蚁所在的城市是；将第只蚂蚁移到城市；把加入到集合中。4.对从到：将第只蚂蚁从移动到；计算第只蚂蚁所走过的路程和，并更新最小路径min；对每条路径（,）：

11、5.对每条路径（,）根据计算；设定；设定；对每条路径（,），设定。6.如果，则清空所有的集合tabu,转到第二步；否则,得出最短的路径。算法的流程如下图: 五、仿真结果参考文献:1 黄丽韶,朱喜基.基于MATLAB的蚁群算法求解旅行商问题J.计算机世界.2 李志伟.基于群集智能的蚁群优化算法研究J.计算机工程与设计，2003，08. 3王源.蚂蚁算法求解TSP问题.4杨殿生. TSP问题的蚁群算法求解.鄂州大学报.5尹晓峰,刘春煌. 基于MATLAB的混合型蚁群算法求解旅行商问题J.铁路计算机应用，2005,09.附录附录一： Matlab实现程序如下： %一始化变量clear;Alpha=1

12、; %信息素重要程度的参数(对路径选择有很大影响)Beta=5; %启发式因子重要程度的参数(对路径选择有很大影响)Rho=0.95; %信息素蒸发系数NC_max=200; %最大迭代次数(循环多结果更优适度即可)Q=100; %信息素增加强度系数 (对结果影响小)CityNum=31; %问题的规模（城市个数）dislist,Clist=tsp(CityNum);m=CityNum; %蚂蚁个数Eta=1./dislist;%Eta为启发因子，这里设为距离的倒数Tau=ones(CityNum,CityNum);%Tau为信息素矩阵Tabu=zeros(m,CityNum);%存储并记录路

13、径的生成NC=1;%迭代计数器R_best=zeros(NC_max,CityNum); %各代最佳路线L_best=inf.*ones(NC_max,1);%各代最佳路线的长度L_ave=zeros(NC_max,1);%各代路线的平均长度figure(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,:); L(i)=CalDist(di

14、slist,R); end L_best(NC)=min(L); pos=find(L=L_best(NC); R_best(NC,:)=Tabu(pos(1),:); L_ave(NC)=mean(L); drawTSP(Clist,R_best(NC,:),L_best(NC),NC,0); NC=NC+1; %五更新信息素 Delta_Tau=zeros(CityNum,CityNum); for i=1:m for j=1:(CityNum-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i)

15、; end Delta_Tau(Tabu(i,CityNum),Tabu(i,1)=Delta_Tau(Tabu(i,CityNum),Tabu(i,1)+Q/L(i); end Tau=(1-Rho).*Tau+Delta_Tau; %六禁忌表清零 Tabu=zeros(m,CityNum); %pause; tauji(NC)=Tau(1,2);end%七输出结果Pos=find(L_best=min(L_best);Shortest_Route=R_best(Pos(1),:);Shortest_Length=L_best(Pos(1);figure(2);plot(L_best L_a

16、ve);legend(最短距离,平均距离)；附录二：function DLn,cityn=tsp(n)if n=31 city31=1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1004; 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

17、2367; 3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975;%31 cities d=423.741 by D B Fogel for i=1:31 for j=1:31 DL31(i,j)=(city31(i,1)-city31(j,1)2+(city31(i,2)-city31(j,2)2)0.5; end end DLn=DL31; cityn=city31;end附录三：function m=drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);for

18、i=1:CityNum-1 plot(Clist(BSF(i),1),Clist(BSF(i+1),1),Clist(BSF(i),2),Clist(BSF(i+1),2),ms-,LineWidth,2,MarkerEdgeColor,k,MarkerFaceColor,g); hold on;endplot(Clist(BSF(CityNum),1),Clist(BSF(1),1),Clist(BSF(CityNum),2),Clist(BSF(1),2),ms-,LineWidth,2,MarkerEdgeColor,k,MarkerFaceColor,g);title(num2str(

19、CityNum),城市TSP);if f=0 text(1000,200,第 ,int2str(p), 步, 最短距离为 ,num2str(bsf);else text(1000,100,最终搜索结果：最短距离 ,num2str(bsf);endhold off;pause(0.05);附录四：function F=CalDist(dislist,s)DistanV=0;n=size(s,2);for i=1:(n-1) DistanV=DistanV+dislist(s(i),s(i+1);endDistanV=DistanV+dislist(s(n),s(1);F=DistanV;专心-专注-专业