【GreenSim.C原创】TSP问题蚁群算法通用Matlab程序（附图）(2007-03-10 09:28:51)转载
蚁群算法是当前研究非常火热的一种智能算法，下面的蚁群算法程序专门用于求解TSP问题，此程序由GreenSim团队于2006年初完成，最初公开发表于研学论坛，我们经过仿真检验，发现此程序的优化效率和鲁棒性都非常好。
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@https://www.doczj.com/doc/8e1721466.html,
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符号说明
%% C n个城市的坐标，n×2的矩阵
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%%=========================================================================
%%第一步：变量初始化
n=size(*,1);%*表示问题的规模（城市个数）
*=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
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))
Randpos=[Randpos,randperm(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
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);
en*
*=*/(sum(P));
%按概率原则选取下一个城市
Pcum=cumsum(P)
;
Select=find(Pcum>=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),:);
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;
运行后得到15602的巡游路径，路线图和收敛曲线如下：
附中国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
旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
求解算法：
在过去出现了一下逼近最优解的算法：最近邻居、贪婪算法、最近插入、等算法，但因
此也有局限性，故需要一下启发式算法。能绝佳此问题的启发式算法有遗传算法、粒群算法、蚁群算法等。
在这个实验中选择一种改进策略的遗传算法来解决此问题。这种算法的应用范围广，适合处理传统搜索难以解决的复杂和非线性问题，可广泛地应用于组合优化等领域。
遗传算法：
遗传算法是通过借鉴生物界自然选择和自然遗传机制而产生的一种计算方法，与其他的优化算法一样，遗传算法也是一种迭代算法。遗传算法是一种自适应全局优化概率搜索算法。该算法利用生物进化和遗传思想实现优化过程，能够有效地解决组合优化问题。
运行结果和分析：
inn=100;%初始种群大小
pc=0.6; %交叉概率
pm=0.6; %变异概率
结果：
1.交叉概率 pc=0.6；变异概率 pm=0.6； CityNum=30；
a.最大代数gnmax=50
b.最大代数gnmax=100
c.最大代数gnmax=150
经比较可得当城市数不变时，随着迭代次数的增加，最短距离逐步趋于最优，最佳个体的适应度函数值逐步增加，最后收敛于一个相对稳定值。
2.交叉概率 pc=0.6；变异概率 pm=0.6；最大代数gnmax=100；
a.CityNum=30；
b.CityNum=50；
经实验可知当最大代数不变时，随着城市规模的变大，可以方便找到最优解，但太大的话，则计算时间较长。
3.最大代数gnmax=100；CityNum=50；
a.交叉概率 pc=0.6；变异概率 pm=0.6
b. 交叉概率 pc=0.8；变异概率 pm=0.8
经实验可知对于交叉概率来说，如果取值过大，能会破坏以前的遗传结果，因而交叉概率不大。对于突变概率，其目的是为了保证算法对空间的覆盖，但突变概率太大，会破坏遗传和交叉选出的染色体而变成随机搜索；反之，染色体种群又会过于单调，从而陷入局部极值。
综上可得，遗传算法有较好的全局最优解的求解能力，但遗传算法在这类问题的应用上，两个遗传算子都是在一定发生概率的条件下，随机的、没有指导的迭代搜索；因此它们在位群体中的个体提供里进化机会的同时也不可避免地产生了退化的可能。遗传算法的过早收敛，即“早熟”问题，会严重影响算法的执行效果。防止算法过早收敛，就要保持种群的多样性。用遗传算法得到较好的解，必须要具备足够的遗传代数。当遗传代数比较少时，算法很难得到优解，其对TSP问题的求解也只能是求得近似最优解。