人工知能の最適化アルゴリズム1-蟻群最適化アルゴリズム

原文の著者:

『蟻群アルゴリズム原理とその応用』:段浜、科学出版社.

《知能蟻群アルゴリズムとその応用》:呉啓迪、汪ラジウム、上海科学技術教育出版社.

リンク:
http://www.nocow.cn/index.php/%E8%9A%81%E7%BE%A4%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95
蟻群アルゴリズムの提案:

                        ，              。                      ，          
                                     。    ，               ，            
                   ，     、    、      。               ，                 
                 。
                    ，          ，          ，         ，    ，              ，
                。                                  ，         、         
 、             。                 ，               ，                     
      (TSP)            ，                          ，                       
  ，                             。

人工アリと真実アリの異同比較
同一点の比較

                                ，             ，                         。
  （1）                   
                            ：                ，                    ，      
         ，                  ，              。                         ， 
                       。  ，             ，                             。
                            ，                        “  ”。
   （2）           
                       ，         （  ）     （   ）     。                ，   
           ，         。                 ，            。
   （3）                   
                                      ，                      ，          。
  ，                             。

異なる点の比較

                          ，                     ：
  （1）               ，                    ；
  （2）                      ；
  （3）                   ；
  （4）           ，             。                       ，       ，          
       ；
  （5）           ，           ，     、    、   ，               。        ，    
               ，                       。

蟻群アルゴリズムのフローチャート
基本蟻群アルゴリズムの実現手順

 TSP  ，               ：
（1）     。   t=0     τ=0，        Nc=0， m     n   （  ） ，        

(i,j)の初期化情報量τij(t) = const、constは定数を表し、初期時刻Δτij(0) = 0 .

（2）     。
（3）         k=1。
（4）    。
（5）                       （  ）j   ，。

   ，    t    k   （  ）i     （  ）j       。 allowedk = C − tabuk    k          。α       ，
          ，                            ，    ，              
     ，          。β        ，           ，                          
   ，    ，                ；ηij(t)      ，     。  ，dij              。
（6）       ，                （  ），     （  ）             。
（7）	   C   （  ）    ， k 
  
τij(t + n) = (1 − ρ) * τij(t) + Δτij(t)
  
 
  
（9）	       ，        ，              ，            （2） 。
  
  アルゴリズムのmatlabソースプログラム
1.  アルゴリズムメインプログラム:main.m
%function [bestroute,routelength]=Ant
clc
clear
tic
%              
CooCity = load( 'CooCity.txt' ) ;%            ，txt    
NC=length(CooCity);           %     
for i=1:NC       %          
    for j=1:NC
        distance(i,j)=sqrt((CooCity(i,2)-CooCity(j,2))^2+(CooCity(i,3)-CooCity(j,3))^2);
   end
end
MAXIT=10;%      
Citystart=[];         %       
tau=ones(NC,NC); %              1
rho=0.5;         %     
alpha=1;         %          
beta=5;          %          
Q=10;          %     
NumAnt=20;         %     
routelength=inf;        %                
for n=1:MAXIT
    for k=1:NumAnt       %   K   
        deltatau=zeros(NC,NC); %  K                
        %[routek,lengthk]=path(distance,tau,alpha,beta,[]);      %        
        [routek,lengthk]=path(distance,tau,alpha,beta,Citystart);   %      
       
        if lengthk 
  
 2.          ：path.m
 
  
%            routek,lengthk
function [routek,lengthk]=path(distance,tau,alpha,beta,Citystart) 
[m,n]=size(distance);
if isempty(Citystart)        %        
    p=fix(m*rand)+1;         %          ，    
else
   p=Citystart;            %         
end
lengthk=0;        %          0
routek=[p];        %        ，            ，      
for i=1:m-1
   np=routek(end);  %         ，           
    np_sum=0;      %         0
   for j=1:m
       if inroute(j,routek)        %       j    tabuk，      
           continue;
       else                    % j       ， 
           ada=1/distance(np,j);  %     
           np_sum=np_sum+tau(np,j)^alpha*ada^beta;   %    ：    、   
       end
   end
   cp=zeros(1,m);  %     ，          
   for j=1:m
       if inroute(j,routek)
           continue;
       else
           ada=1/distance(np,j);       %    
           cp(j)=tau(np,j)^alpha*ada^beta/np_sum;   % np j     
       end
   end
   NextCity=nextcitychoose2(cp); %              ,
   %    ，            ，          
   routek=[routek,NextCity]; %     
   lengthk=lengthk+distance(np,NextCity);    %        
end
  
  アルゴリズムシミュレーション  
              ，              。