acojan20cycle.m

蚂蚁算法解决流动货郎问题

node=9  %  node*node
ant=2    %  ants
gene=100  %  generation of ant
a=1   %  alpha
b=5    %  Beta
q0=1   %  original pheronome 
q1=5     %  pheronome left when ants pass
q2=10000   %  max pheronome
q3=1      %  the mininum pheronome
q4=100   
vr=0.99   %  volatilization rate

NODEPS=unifrnd(0,100,node,2); % sensor field [0,100], position matrix, 100 nodes

PS2=NODEPS;

for i=1:node
    for j=i:node
        if PS2(i,1)^2+PS2(i,2)^2>PS2(j,1)^2+PS2(j,2)^2
                s=PS2(i,:);
                PS2(i,:)=PS2(j,:);
                PS2(j,:)=s;
        end
     end
     PS2(i,3)=i;
 end
 
figure(1);
plot(PS2(:,1),PS2(:,2),':bo') 
% resort node position by the norm



for i=1:node
    for j=1:node
        HEUR(i,j)=1/((PS2(i,1)-PS2(j,1))^2+(PS2(i,2)-PS2(j,2))^2);
        DIST(i,j)=sqrt(1/HEUR(i,j))        ;
    end
end
% distance matrix

PHER=q0*(ones(node,node)-eye(node,node))  ;%pheromone matrix, q0=original pheromone

HIST=ones(node+1,ant);% history path for ants

for i=1:node
    HIST(i,:)=i;
end

optimalcost=node^5;

for i=1:gene  % cycle of ant generation
     
    for j=1:node-1 % one generation cycle, step is j
                
        for k=1:ant  % each ant's action in one step

            PH=zeros(node,1);
            P=zeros(node,1)  ;             % set the possibility of the left nodes which is 
            
            for m=j:node-1                 % set PH=unchosen nodes pheromone X heuristic
                PH(m+1)=(PHER(HIST(m+1,k),HIST(j,k))^a)*(HEUR(HIST(m+1,k),HIST(j,k))^b)
            end
            
            for m=j:node-1                 % set P is the possibility matrix    
                PH
                HIST(m+1,k)
                P(m+1)=PH(HIST(m+1,k))/sum(PH)
            end
            

            cp=unifrnd(0,1); % choose a possibility
            cn=2 ;           % choose a node
            
            while cp>0      % choose next node by posibility  
                cp=cp-P(cn)
                if cp>0
                   cn=cn+1
                end
            end
           % choose a node number
           
           cn
                                   
            if HIST(cn,k)>1
                for m=j:node
                    if HIST(m,k)==cn
                        h=HIST(m,k)
                        HIST(m,k)=HIST(j+1,k)
                        HIST(j+1,k)=h             
                    end
                end
            end  
            % switch chosen with unchosen
        end
     end
      %got history matrix of all the ant
     
     
    for j=1:ant
        cost(j)=0;
        for k=1:node
            cost(j)=(PS2(HIST(k,j),1)-PS2(HIST(k+1,j),1))^2+(PS2(HIST(k,j),2)-PS2(HIST(k+1,j),2))^2+cost(j);
        end
    
    end
    % cost of each ants

    mincost(i)=cost(1);
    for j=1:ant
      if cost(j)<mincost(i)
           mincost(i)=cost(j);
           M=HIST(:,j);
       end
    end
    % mincost(i) is the lowest cost path in each generation
   
  if mincost(i)<optimalcost
     optimalcost=mincost(i);
     optimalM=M;
     
     for j=1:node
         PHER(M(j),M(j+1))=PHER(M(j),M(j+1))+q4*node/DIST(M(j),M(j+1));
     end
     
  end 
     
     
  % change pheromone matrix
      
end    



PS3=PS2;
PS3(node+1,:)=PS2(1,:);
PS3(:,4)=M;

% display the shortest way in one generation

PS4=PS3;
for i=1:node+1
    PS4(i,:)=PS3(PS3(i,4),:);
end

for i=1:node+1
    PS5(i,:)=PS2(optimalM(i),:);
end

figure(2);
plot(PS4(:,1),PS4(:,2),':ko') 

figure(3);
plot(mincost)

figure(4);
plot(PS5(:,1),PS5(:,2),':ko')