ACA.zip_ACA_禁忌_禁忌 蚁群

function m_main() tic G=[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ; 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 ; 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 ; 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 ; 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 ; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ; 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 ; 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 ; 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 ; 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 ; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 ; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 ; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 ; 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ; 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 ; 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 ; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 ; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 ; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ; 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ; 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 ; 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 ; 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 ; 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 ; 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ; 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 ; 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 ; 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 ; ]; MM=size(G,1); % MM为电子地图的行值 NN=size(G,2); % NN为电子地图的列值 % G 地形图为01矩阵，如果为1表示障碍物 Tau=ones(MM*NN,MM*NN);%Tau初始信息素矩阵（认为前面的觅食活动中有残留的信息素） Tau=6.*Tau;%信息素矩阵中每个元素值均为8 Tau0=Tau; K=80; %%%% 120 %K迭代次数 Y=40; %%50 %Y蚂蚁个数 a=1; Qx=0.5; Qy=8.5; % Qx=0.5; % Qy=0.5; S=(Qx/a+0.5)+(MM-(Qy/a+0.5))*MM; Ex=25.5; Ey=28.5; E=(Ex/a+0.5)+(MM-(Ey/a+0.5))*MM; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% 改进一 ：更改信息素初始分布 %%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% if S<E Tau(S:E,S:E)=6.2; else Tau(E:S,E:S)=6.2; end %这里终止点由电子地图行值表示，为什么不是点坐标%%如何随意规定终止点 Alpha=10;%20 %%Alpha表征信息素重要程度的参数 Beta=30; %30 %Beta表征启发式因子重要程度的参数 Rho=0.3; %0.3 %Rho信息素蒸发系数 Q=6; %6 %Q信息素增加强度系数 minkl=inf; mink=0; minl=0; D=G2D(G); %邻接矩阵；具体数据表示可以行进距离 N=size(D,1); %N表示问题的规模（象素个数） t=1; a=1;%小方格象素的边长 %a应该会和N有关系，N决定a %%------------------------------------------------------------------------- % Ex=a*(mod(E,MM)-0.5);%终止点横坐标 % %E为行值的平方，看看这个横坐标怎么回事，mod取余Ex=19.5 % if Ex==-0.5 % Ex=MM-0.5; % end % %19.5情况 % Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标Ey=0.5 % %ceil为距离最近的整数（ceil0.5=1） %%------------------------------------------------------------------------- Eta=zeros(N);%启发式信息，取为至目标点的直线距离的倒数 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 下面构造启发式信息矩阵 % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% for i=1:N ix=a*(mod(i,NN)-0.5); % ix=a*(mod(i,MM)-0.5); if ix==-0.5 ix=NN-0.5; % ix=MM-0.5; end iy=a*(MM+0.5-ceil(i/MM)); if i~=E %E为400 Eta(i)=1/((ix-Ex)^2+(iy-Ey)^2)^0.5; %启发式信息，取为至目标点的直线距离的倒数 else Eta(i)=100; %仅为无穷大的意思 end end ROUTES=cell(K,Y); %K为蚂蚁出动多少波，M为蚂蚁有多少个 %用细胞结构存储每一代的每一只蚂蚁的爬行路线 ，看爬行路线是以何种形式存储的 PL=zeros(K,Y);%用矩阵存储每一代的每一只蚂蚁的爬行路线长度 %% -----------启动K轮蚂蚁觅食活动，每轮派出M只蚂蚁-------------------- for k=1:K for m=1:Y %%******** 第一步：状态初始化 W=S; %当前节点初始化为起始点 W=1 Path=S; %爬行路线初始化，Path=1 PLkm=0; %爬行路线长度初始化 TABUkm=ones(N); %禁忌表200*200的全一矩阵 TABUkm(S)=0; DD=D; %DD为400*400代表邻接矩阵初始化 %%***********第二步：下一步可以前往的节点 DW=DD(W,:); %DW=DD(1,:)，为行向量1*400 DW1=find(DW); %DW1返回DW中非零元素所在位置，即，下一步可以走的位置 for j=1:length(DW1) %length(DW1)表示非零的个数 if TABUkm(DW1(j))==0 %如果禁忌表中该位置的元素为0 DW(DW1(j))=0; %将DW（邻接矩阵）中非零元素化为零 end end LJD=find(DW); %LJD返回DW中非零元素所在位置 Len_LJD=length(LJD); %DW非零元素个数，即为可选节点的个数 %觅食停止条件：蚂蚁未遇到食物或者陷入死胡同 while W~=E&&Len_LJD>=1 %如果未到终点&&&所谓陷入死胡同为只有一条路可走 %第三步：转轮赌法选择下一步怎么走%%%%%%%%%%%%%%%%%%%改进地方一 PP=zeros(Len_LJD); %PP为3*3大的方阵，均为零 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%% 改进二：带方向感的蚂蚁 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% fx=ones(Len_LJD,1); if S<E sx=find(LJD>=S); else sx=find(LJD<=S); end if mod(S,MM)<mod(E,MM) zy=find(mod(LJD,MM)>=mod(S,MM)); else zy=find(mod(LJD,MM)<=mod(S,MM)); end fx(sx)=fx(sx)*(1.0005); fx(zy)=fx(zy)*(1.0005); %%%%%%%%%%%%%%%%%%%%%%%%% for i=1:Len_LJD %i从1开始到3 % PP(i)=(Tau(W,LJD(i))^Alpha)*((Eta(LJD(i)))^Beta); PP(i)=(Tau(W,LJD(i))^Alpha)*((Eta(LJD(i)))^Beta)*fx(i); %PP(1)=(Tau(1,3))^1*((Eta(3))^7) %PP=信息素*启发式信息^7 end %%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%% sumpp=sum(PP); %sumpp为1*3，每列求和 PP=PP/sumpp;%建立概率分布 %PP为3*1矩阵，且矩阵中的各元素为每个死胡同所占的比例 Pcum(1)=PP(1); %Pcum(1)为第一个死胡同占的概率 for i=2:Len_LJD Pcum(i)=Pcum(i-1)+PP(i); %每个概率依次相加 end