4.txt

基本蚁群算法求解TSP问题 该程序是运行过的没有问题的

%最近找工作，有点烦。这是很久前写的，贴出来供各位大虾品评指点，错误难免，欢迎指正。
%还有欢迎研究智能算法的与我交流，QQ124141866

function [OptTour,BestTourLength,OptITime,tau]=BACO(CityMatrix,AntNum,MaxITime,alpha,beta,rho)
%:基本蚁群算法 (ant colony optization)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 参考文献: ～～～～～～～～～～
% Write by [e-mail] 2005
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%input
% -CityMatrix 城市位置矩阵
% -AntNum 蚂蚁数
% -MaxITime 最大迭代次数
% -alpha 残留信息指数(信息启发因子),(0.05,1)
% alpha=0,算法等价于贪心算法
% -beta 期望值指数(期望启发因子),(1,4)
% beta=0,算法为正反馈启发式算法
% -rho 信息素挥发系数，区间(0.01,0.8)
% 1-rho=残留系数
%:Output
% -BestTourLength 最优路径长度
% -OptTour 最优游历序列
% -OptITime 第一次达到最优的迭代次数
% -tau 信息素状态矩阵

%:输入参数初始化
n=max(size(CityMatrix)); %城市数
Q=1; %信息素常量，游历一周所释放的总信息量
ITime=1; %迭代次数
tau=(ones(n,n)-eye(n,n))*Q; %城市间信息素浓度矩阵
DistanceMatrix=CalDist(CityMatrix); %城市间距离矩阵
%:返回参数初始化
OptTourLength=inf;
OptTour=zeros(n+1,1);
OptITime=1;
BestTourLength=zeros(1,MaxITime);%迭代最优解

%:游历开始
while ITime<=MaxITime
AntTours=zeros(AntNum,n+1); %所有蚂蚁游历序列
AntTours(:,1)=randint(AntNum,1,[1,n]); %随机选择游历序列起点
ToursLength=zeros(AntNum,1); %所有蚂蚁游历路径长度
for step=2:n %:第step个将访问的城市
for k=1:AntNum %:第k只蚂蚁开始寻优
%:生成蚂蚁k第step步的搜索表,ToVisit=allowd_k
CurrentCity=AntTours(k,step-1); %当前所在城市
Visited=AntTours(k,:); %已访问城市 tabu_k
ToVisit=setdiff([1:n],Visited); %未访问的城市
NumToVisit=length(ToVisit); %蚂蚁k未访问城市数
P=zeros(1,NumToVisit); %到所有未访问城市的概率
%:计算蚂蚁k从当前城市到所有未访问城市的概率
for i=1:NumToVisit
P(i)=(tau(CurrentCity,ToVisit(i)))^alpha*...
(1/DistanceMatrix(CurrentCity,ToVisit(i)))^beta;
end
sumP=sum(P);
P=P/sumP;
%:轮盘赌策略选择下一步访问的城市
?? j = 1;
?? sumP = 0;
?? while sumP<rand
????sumP = sumP+P(j);
????j = j+1;
?? end
?? Select = ToVisit(j-1);
?? %:记录路径
AntTours(k,step)=Select;
end
end
%:将游历起点置尾,形成游历回路
AntTours(:,n+1)=AntTours(:,1);
%:计算游历路径长度ToursLength
ToursLength=CalToursLength(AntTours,DistanceMatrix);
%:更新径信息素矩阵AntTours
tau=Refreshtau(tau,AntTours,ToursLength,rho,Q);
%:记录最优游历序列及其长度OptTour,OptTourLength
[BestTourLength(1,ITime),AntIndex]=min(ToursLength);
if BestTourLength(1,ITime)<=OptTourLength 
OptTourLength=BestTourLength(1,ITime);
OptTour=AntTours(AntIndex,:)';
OptITime=ITime;
end
%BestTour(:,ITime)=OptTour;
%:迭代次数加一
ITime=ITime+1;
end
ITime=ITime-1;
%--------------------------------------------------------------------------
function Distances=CalDist(Citys)
%:计算任意城市之间的距离矩阵
Citys(:,1)=[];
n=max(size(Citys));
Distances=zeros(n,n);
for i=2:n
for j=1:i
if(i==j) %对角元为零
continue;
else
dij=Citys(i,:)-Citys(j,:);
Distances(i,j)=sqrt(dij(1)^2+dij(2)^2);
Distances(j,i)=Distances(i,j); %对称矩阵
end
end
end

%--------------------------------------------------------------------------
function TL=CalToursLength(AT,DM)
%:计算游历路径长度
[m,nc]=size(AT);
TL=zeros(m,1);
for k=1:m
for i=1:nc-1
TL(k)=TL(k)+DM(AT(k,i),AT(k,i+1));
end
end

%--------------------------------------------------------------------------
function tau=Refreshtau(tau,AT,TL,rho,Q)
%:更新径信息素矩阵
[m,nc]=size(AT);
sumdtau=zeros(nc-1,nc-1); %对角元为零
for k=1:m
for i=1:nc-1 % Q/TL(k):ant circle system
sumdtau(AT(k,i),AT(k,i+1))=sumdtau(AT(k,i),AT(k,i+1))+Q/TL(k);
sumdtau(AT(k,i+1),AT(k,i))=sumdtau(AT(k,i),AT(k,i+1)); %对称矩阵
end
end
tau=tau*(1-rho)+sumdtau;