用蚁群算法求解有线路约束TSP问题.docVIP

用蚁群算法求解有线路约束TSP问题 　　【摘要】本文利用01矩阵，设计了新型的蚁群算法，用于解决有线路约束的经典旅行商问题，并求出了在有线路约束下，走遍不同城市的行程最短的最佳路线和最佳路线的长度。 　　【关键词】蚁群算法;01矩阵;matlab;最佳路线;最佳路线长度 　　 　　本文将结合一个具体的事例，给出相关的解决方案的蚁群算法的matlab代码。 　　１．问题的提出 　　给定76个城市的坐标，城市之间相互通路信息如图1所示，请设计线路，能走遍所有城市，行程最短，并用画图的方式展示所求结果。 　　图1 相互联系信息 　　2.问题分析与求解 　　这是一个最短路优化问题，如果没有线路的约束，我们可以运用原始的蚁群算法，求得最佳路线。但是现在城市之间有了线路约束，所以需要改进原来的算法。 　　原始蚁群算法分析： 　　原始的蚁群算法中有一个启发因子Eta，算法中Eta=1./D，其中D是城市之间的距离矩阵，D（i,j）为D的元素。可以看出，启发因子是跟距离有关的唯一量，D(i,j)越小，Eta（i,j）越大，i,j两个城市之间的线路进入最佳路线的可能性就越大。另外，若i≠j，显然有D(i，j)≥1，从而有Eta（i，j）≤1。 　　解决方案： 　　首先建立01矩阵a，i、j之间存在通路，a（i，j）=1，i、j之间不存在通路，a（i，j）=0。令Eta=1./D+a(i,j),显然有当i、j之间存在通路，l、m之间不存在通路时有：Eta（i，j）＞Eta(l，m)，这样就使得新的算法可以求解有路线约束的TSP问题。 　　3.符号说明 　　R_best：各代最佳路线 　　L_best：各代最佳路线的长度 　　DrawRoute(C,R)：画路线图的子函数 　　a：表示76*76的0 1矩阵，若第i个城市与第j个城市之间有通路则a(i,j)为1，否则a（i，j）为0。 　　a． txt : 存放数据a的文件。 　　c：表示76*2的矩阵，用于存取76个城市的坐标。 　　c.txt 存放c的文件。 　　4.新型蚁群算法matlab代码 　　%%第一步：变量初始化. 　　m=76; %%蚂蚁个数 　　Alpha=1;%% 表征信息素重要程度的参数 　　Beta=5; 表征启发式因子重要程度的参数 　　Rho=0.1;%% 信息素蒸发系数 　　NC_max=500;%% 最大迭代次数 　　Q=100; %%信息素增加强度系数 　　load c.txt 　　C=c; 　　n=size(C,1);%n表示问题的规模（城市个数） 　　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); 　　end 　　end 　　load a.txt 　　Eta=1./D+a(i,j);%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);%各代最佳路线的长度 　　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),:); 　　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