蚁群算法TSP问题应用matlab.docxVIP

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(C,1);%n表示问题的规模（城市个数）D=zeros(n,n);%D用来存储各个城市之间的欧式距离%%以下计算任意2个城市间的距离，存储到D中for i=1:nfor j=1:nif i~=j %若i，j不重合，即为不同城市D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5; %计算欧氏距离，任意城市i与j的距离elseD(i,j)=eps;??????%i=j时不计算，应该为0，但后面的启发因子要取倒数，%用eps（浮点相对精度）表示eps=2.2204e-016，一个极小的数字end %if i~=jD(j,i)=D(i,j);???%对称矩阵对称TSP问题end% for j=1:nend% for i=1:nEta=1./D;??????????%Eta为能见度因子，这里设为距离的倒数Tau=ones(n,n);?????%Tau为信息素矩阵默认一开始为1 一个常数Tabu=zeros(m,n);???%存储并记录路径的生成第m只蚂蚁访问的第n座城市是城市xNC=1;???????????????%迭代计数器，记录迭代次数R_best=zeros(NC_max,n);???????%各代最佳路线假定为100代，31个城市，即从1-31-1一个线路L_best=inf.*ones(NC_max,1);???%各代最佳路线的长度L_ave=zeros(NC_max,1);????????%各代路线的平均长度while NC=NC_max????????%停止条件之一：达到最大迭代次数，停止%%第二步：将m只蚂蚁放到n个城市上Randpos=[];???%建立一个随机矩阵用以将m只蚂蚁放置到n个城市上for i=1:(ceil(m/n)) %ceil() 向上取整数，去掉小数部分，整数部分+1Randpos=[Randpos,randperm(n)];%randperm(n),随机产生1~n的序列即得到初始城市m个endTabu(:,1)=(Randpos(1,1:m));????%Tabu(:,1)所有行的第一列，Randpos(1,1:m)’第一行的1~m列，将Randpos的第一行1~m列，%共m个元素赋给矩阵Tabu的第一列，Tabu为m*n矩阵。即取了m只蚂蚁放置在初始城市中，%m只蚂蚁的初始城市，即初始城市由Randpos产生，随机的，此后Tabu就有值了，每只蚂蚁都%有了初始城市。%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游概率选择数学模型的实现for j=2:n?????%所在城市不计算从第二个城市开始for i=1:m????%蚂蚁1~m，m个蚂蚁统计选择概率并记录visited=Tabu(i,1:(j-1));? %第一次的时候，visited=Tabu(1,1);即初始城市是访问过的%记录已访问的城市，避免重复访问第i个蚂蚁已选择1~j-1个城市的记录J=zeros(1,(n-j+1));???????%待访问的城市一行 n-j+1列的零阵，还剩这么多城市未访问P=J;??????????????????????%待访问城市的选择概率分布计算这些城市的选择概率Jc=1; %待选择城市jc计数for k=1:n %若visited中所不包含的城市，即未访问的城市，此时会是if条件成立 %例如 visited=Tabu(1,1)=2,那么只有k=2时，不执行，其他均执行if后代码if length(find(visited==k))==0???%开始时置0 find() 寻找符合要求的元素的按列排序的序号位置J(Jc)=k;Jc=Jc+1;?????????????????????????%访问的城市个数自加1endend%下面计算待选城市的概率分布for k=1:length(J)P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta); % visited(end)