蚁群算法解决TSP问题的MATLAB程序(共5页).doc

精选优质文档-倾情为你奉上蚁群算法TSP(旅行商问题)通用matlab程序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% ChengAihua,PLA Information Engineering University,ZhengZhou,China% Email:aihuacheng% All rights reserved%-% 主要符号说明% C n个城市的坐标，n×2的矩阵% NC_max 最大迭代次数% m 蚂蚁个数% Alpha 表征信息素重要程度的参数% Beta 表征启发式因子重要程度的参数% Rho 信息素蒸发系数% Q 信息素增加强度系数% R_best 各代最佳路线% L_best 各代最佳路线的长度%=%第一步：变量初始化n=size(C,1);%n表示问题的规模（城市个数）D=zeros(n,n);%D表示完全图的赋权邻接矩阵for i=1:nfor j=1:nif i=jD(i,j)=(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2)0.5;elseD(i,j)=eps;endD(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<=NC_max%停止条件之一：达到最大迭代次数%第二步：将m只蚂蚁放到n个城市上Randpos=;for i=1:(ceil(m/n)Randpos=Randpos,randperm(n);endTabu(:,1)=(Randpos(1,1:m)'%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游for j=2:nfor i=1:mvisited=Tabu(i,1:(j-1);%已访问的城市J=zeros(1,(n-j+1);%待访问的城市P=J;%待访问城市的选择概率分布Jc=1;for k=1:nif length(find(visited=k)=0J(Jc)=k;Jc=Jc+1;endend%下面计算待选城市的概率分布for k=1:length(J)P(k)=(Tau(visited(end),J(k)Alpha)*(Eta(visited(end),J(k)Beta);endP=P/(sum(P);%按概率原则选取下一个城市Pcum=cumsum(P);Select=find(Pcum>=rand);to_visit=J(Select(1);Tabu(i,j)=to_visit;endendif NC>=2Tabu(1,:)=R_best(NC-1,:);end%第四步：记录本次迭代最佳路线L=zeros(m,1);for i=1:mR=Tabu(i,:);for j=1:(n-1)L(i)=L(i)+D(R(j),R(j+1);endL(i)=L(i)+D(R(1),R(n);endL_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:mfor 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);endDelta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);endTau=(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)function DrawRoute(C,R)%=% DrawRoute.m% 画路线图的子函数%-% C Coordinate 节点坐标，由一个N×2的矩阵存储% 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:Nplot(C(R(ii-1),1),C(R(ii),1),C(R(ii-1),2),C(R(ii),2)hold onend设置初始参数如下：m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;31城市坐标为：1304  23123639  13154177  22443712  13993488  15353326  15563238  12294196  10044312  7904386  5703007  19702562  17562788  14912381  16761332  6953715  16783918  21794061  23703780  22123676  25784029  28384263  29313429  19083507  23673394  26433439  32012935  32403140  35502545  23572778  28262370  2975运行后得到15602的巡游路径，路线图和收敛曲线如下专心-专注-专业