【用蚁群算法求解有线路约束的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,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)
　　%% M文件:
　　function DrawRoute(C,R)
　　%% DrawRoute.m
　　%% 画路线图的子函数
　　N=length(R);
　　scatter(C(:,1),C(:,2));
　　hold on
　　plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
　　hold on
　　for ii=2:N
　　plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
　　hold on
　　end
　　5.结果分析
　　运行结果：
　　Shortest_Route =
　　Columns 1 through 19
　　1516111213147410
　　9 6 7 8 3 4 520193130
　　Columns 20 through 38
　　292843425453525166
　　65504955565758596041
　　Columns 39 through 57
　　403435323327262521
　　2223 1 2757624464544
　　Columns 58 through 76
　　484769686770717273
　　64636261393836371817
　　Shortest_Length =1.1799e+005
　　通过所求结果的线路图与原始的线路联系信息图的比较，基本可以确定所得结果是正确的，但是蚁群算法是一个通过迭代收敛的方法，它本身是一个估计值，所以存在一定误差，但是随着迭代次数越高所得出的结果越精确，所以可以调整NC_max的大小来提高精确度。■
　　
　　【参考文献】
　　［１］徐伯庆，宣国荣，柴佩琪．中国旅行商问题的二叉树描述及其求解[J]．模式识别与人工智能，2000，13(2)：373-376．
　　［２］杨忠，鲍明，张阿舟．求解中国旅行商问题的新结果[J]．数据采集与处理，1993，8(3)：177-184.
　　［３］电路与系统学报.2004,6,9(3).
　　［４］燕忠，袁春伟.用蚁群优化算法求解中国旅行商问题.东南大学生物医学工程系分子与生物分子电子学教育部重点实验室,江苏南京210096.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文