蚁群算法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@gmail.com %% All rights reserved

%%------------------------------------------------------------------------- %% 主要符号说明

%% C n个城市的坐标，n×4的矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数

%% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度

%%========================================================================= %%第一步：变量初始化

n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j

D(i,j)=max( ((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5,min(abs(C(i,3)-C(j,3)),144- abs(C(i,3)-C(j,3))) );%计算城市间距离 else D(i,j)=eps; end

D(j,i)=D(i,j); end end

Eta=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)) ?il(A)生成大于等于A的最小整数

Randpos=[Randpos,randperm(n)]; %randperm(n)生成1到n的随机排列 end

Tabu(:,1)=(Randpos(1,1:m))';

%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游 for j=2:n for i=1:m

visited=Tabu(i,1:(j-1));%已访问的城市

J=zeros(1,(n-j+1));%待访问的城市，应该可以省 P=J;%待访问城市的选择概率分布 Jc=1; for k=1:n

if length(find(visited==k))==0 %如果visited里没有k J(Jc)=k; Jc=Jc+1; end end

%下面计算待选城市的概率分布 for k=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);%需要修改 end

P=P/(sum(P));

%按概率原则选取下一个城市

Pcum=cumsum(P); %这样做是为了使Pcum能取到1 Select=find(Pcum>=rand);

to_visit=J(Select(1)); %把大于rand的第一个数的序号作为下一个城市在J中的序号 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 on plot(L_ave)

function DrawRoute(C,R)

%%========================================================================= %% DrawRoute.m %% 画路线图的子函数

%%------------------------------------------------------------------------- %% C Coordinate 节点坐标，由一个N×2的矩阵存储 %% R Route 路线

%%=========================================================================

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

设置初始参数如下：

m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100; 31城市坐标为： 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 2367 3394 2643 3439 3201 2935 3240 3140 3550 2545 2357 2778 2826 2370 2975

运行后得到15602的巡游路径，路线图和收敛曲线如下：

87，7 91，83) (83，46) (71，44) (64，60) (68，58) (83，69) (87，76) (74，78) (71，71) (58，69) (54，62) (51，67) (37，84) (41，94) (2，99) (7，64) (22，60) (25，62) (18，54) (4，50) (13，40) (18，40) (24，42) (25，38) (41，26) (45，21) (44，35) (58，35) (62，32)