06TSP问题蚁群算法MATLAB源代码.doc

TSP问题蚁群算法MATLAB源代码
蚁群算法最早是用于求解TSP问题的,并获得极大成功,现已成为计算智能领域一个十分重要的算法和研究方向。本程序由GreenSim团队在2006年完成,按照标准蚁群算法进行编写,可以作为蚁群算法的一个参考模版。
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%
% Ant Colony Algorithm for Traveling Salesman Problem
% GreenSim团队——专业级算法设计&代写程序
% 欢迎访问GreenSim团队主页→http://blog./greensim
%%-------------------------------------------------------------------------
%% 主要符号说明
%% 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)^;
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