计算智能课程作业

PAGE第13页共13页利用蚁群算法求解tsp问题

TSP问题又称最短路径问题，还称为旅行商问题，是一种比较经典的

NP

难题，问题描述较简单，而获得最优解却十分困难。求解

TSP

问题不仅为其他算法提供了使用平台，而且算法的优劣性能也可通过其求得

TSP

问题的解集来验证。旅行商问题的经典描述为：已知N

个城市及相互间的距离，旅行商从某城市出发遍历这

N

个城市后再回到原点，在旅行商每个城市都只访问一次的前提下确定一条最短路径。

蚁群算法是一种基于种群的启发式仿生进化系统。该算法通过模拟自然界的蚂蚁觅食过程对目标进行搜索，而在搜索过程中人工蚂蚁会在其经过的路径上释放信息素，蚁群依赖于同类散发在周围环境中的特殊物质—信息素的轨迹来决定自己的去向。当某些路径上走过的蚂蚁越来越多时，留下的信息素也会越来越多，以致后蚂蚁选择该路径的概率也越来越高，从而更增加了该路径的吸引强度，逐渐形成了一条它们自己事先并未意识到的最短路线。

蚁群算法实现TSP

过程为：将

m

只蚂蚁放入到

n

个随机选择的城市中，那么每个蚂蚁每步的行动是：根据一定的依据选择下一个它还没有访问的城市；同时在完成一步（从一个城市到达另一个城市）或者一个循环（完成对所有

n

个城市的访问）后，更新所有路径上的信息素浓度蚁群算法的实现步骤步骤1初始化相关参数如蚂蚁的数目。步骤2将蚂蚁随机或均匀分布到各个城市。步骤3每只蚂蚁通过访问各个城市而形成一个解并在访问的过程中将已访问到的城市保留在i中。在城市i中每只蚂蚁要从没有访问的城市中选择访问下一个城市j时须根据概率公式(1)进行选择如此循环直到所有的蚂蚁访问完所有的城市。步骤4计算每只蚂蚁行走的总路径长度Lk并保存最优解。数学模型的建立蚁群算法解决TSP问题的MATLAB实现出动m只蚂蚁，每只蚂蚁各随机选择一条路径，记为I=[123···m]，长度记为long(I);计算出每条路径的信息素浓度，记为P(I)=1/long(I)，并进行归一化处理;重新出动m只蚂蚁，按如下规则选择路径：1,每只蚂蚁都以一个概率p1选择新路径(路径随机)2,未选择新路径的蚂蚁以概率P(I)选择路径I；3,所有蚂蚁都以一个小概率p2对自己的路径进行局部变化；更新所有路径，计算出每条路径的信息素浓度；重复上述步骤，直至仅剩一条路径。Matlab算法实现function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

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

%%ACATSP.m

%%AntColonyAlgorithmforTravelingSalesmanProblem

%%ChengAihua,PLAInformationEngineeringUniversity,ZhengZhou,China

%%Email:aihuacheng@

%%Allrightsreserved

%%

%%主要符号说明

%%Cn个城市的坐标，n×2的矩阵

%%NC_max最大迭代次数

%%m蚂蚁个数

%%Alpha表征信息素重要程度的参数

%%Beta表征启发式因子重要程度的参数

%%Rho信息素蒸发系数

%%Q信息素增加强度系数

%%R_best各代最佳路线

%%L_best各代最佳路线的长度

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

n=size(C,1);%n表示问题的规模（城市个数）

D=zeros(n,n);%D表示完全图的赋权邻接矩阵

fori=1:n

forj=1:n

ifi~=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

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);%各代路线的平均长度whileNC<=NC_max%停止条件之一：达到最大迭代次数

第二步：将m只蚂蚁放到n个城市上

Randpos=[];

fori=1:(ceil(m/n))

Randpos=[Randpos,randperm(n)];

end

Tabu(:,1)=(Randpos(1,1:m))';第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游

forj=2:n

fori=1:m

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

J=zeros(1,(n-j+1));%待访问的城市

P=J;%待访问城市的选择概率分布

Jc=1;

fork=1:n

iflength(find(visited==k))==0

J(Jc)=k;

Jc=Jc+1;

end

end

%下面计算待选城市的概率分布

fork=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);

Select=find(Pcum>=rand);

to_visit=J(Select(1));

Tabu(i,j)=to_visit;

end

end

ifNC>=2

Tabu(1,:)=R_best(NC-1,:);

end第四步：记录本次迭代最佳路线

L=zeros(m,1);

fori=1:m

R=Tabu(i,:);

forj=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);

fori=1:m

forj=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)

holdon

plot(L_ave)functionDrawRoute(C,R)

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

%%DrawRoute.m

%%画路线图的子函数

%%

%%CCoordinate节点坐标，由一个N×2的矩阵存储

%%RRoute路线

%%=========================================================================N=length(R);

scatter(C(:,1),C(:,2));

holdon

plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])

holdon

forii=2:N

plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])

holdon

end代码运行：现在输入31个城市的坐标进行计算设置初始参数如下：

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，791，83)(83，46)(71，44)(64，60)(68，58)(83，69)(87，76)(74，78)(71，71)(58，69)(54，6