蚁群算法解决TSP问题程序.docx
《蚁群算法解决TSP问题程序.docx》由会员分享，可在线阅读，更多相关《蚁群算法解决TSP问题程序.docx（4页珍藏版）》请在冰点文库上搜索。
蚁群算法用于求解TSP问题，经过仿真测试，发现此程序的优化效率和鲁棒性都非常好。
这与在无线多媒体传感器网络路由算法应用到的寻找最佳路径的蚁群算法非常相似。
function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP（C,NC_max,m,Alpha,Beta,Rho,Q）
%%=========================================================================
%% 主要符号说明
%% C n个城市的坐标，n×2的矩阵
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%%=========================================================================
%%第一步：
变量初始化
n=size（*,1）;%*表示问题的规模（城市个数）
*=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）;
en*
*=*/（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
%% 画路线图的子函数
%%--------------------------------------------------------------------
%% C Coordinate 节点坐标，由一个N×2的矩阵存储
%% R Route 路线
%%====================================================================
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
升级会员 