www.pudn.com > anttsp.rar > AIA_AS_main.m, change:2009-05-23,size:8774b


clear; 
%clc; 
tic; 
%读取城市数据 
%data=load('ulysses16.txt'); 
%data=load('ulysses22.txt'); 
%data=load('oliver30.txt'); 
data=load('att48.txt'); 
%data=load('eil51.txt'); 
%data=load('eil76.txt'); 
%data=load('eil101.txt'); 
%data=load('ch130.txt'); 
%data=load('ch150.txt'); 
%data=load('rat195.txt'); 
X=data(:,2);                                    %城市横坐标 
Y=data(:,3);                                    %城市纵坐标 
[dist,city_num]=dist_cand(X,Y);                  %计算城市之间的距离 
%------------------------------人工免疫算法-------------------------------- 
antitrope_num=30;                               %产生的抗体数目 
AIA_iter=100;                                   %抗体免疫迭代次数 
pc=0.2;                                         %免疫算子1的免疫概率 
uc=4;                                           %免疫算子1的免疫次数 
ps=0.4;                                         %免疫算子1的免疫概率 
us=6;                                           %免疫算子1的免疫次数 
pi=0.6;                                         %免疫算子1的免疫概率 
ui=4;                                           %免疫算子1的免疫次数 
%产生初始抗体并进行预处理 
for i=1:antitrope_num 
   % antitrope(i).tour=randperm(city_num); 
    temp_anti=cat(2,1,randperm(city_num-1)+1); 
    antitrope(i).tour=preproccess(city_num,dist,temp_anti); 
end 
%计算抗体的长度并返回当前最优抗体 
[antitrope,best_antitrope]=anti_length(city_num,dist,antitrope_num,antitrope); 
for k=1:AIA_iter 
     %通过构造免疫算子产生新抗体群 
    for i=1:antitrope_num                       %产生2倍于原抗体数的新抗体 
        new_antitrope(i).tour=immune_operator(city_num,antitrope(i).tour,pc,uc,ps,us,pi,ui); 
        new_antitrope(i+antitrope_num).tour=immune_operator(city_num,antitrope(i).tour,pc,uc,ps,us,pi,ui); 
    end 
    %计算新抗体的长度及新抗体中的最优抗体 
    [new_antitrope,new_best_antitrope]=anti_length(city_num,dist,2*antitrope_num,new_antitrope); 
    %在原有抗体群和新抗体群中产生下一次免疫迭代的抗体群 
    anti1_length=[antitrope.length];            %保存20个原最优抗体在下一次免疫的抗体群中 
    [no_use,index]=sort(anti1_length); 
    for i=1:20                                 
        temp(i)=antitrope(index(i)); 
    end 
    anti2_length=[new_antitrope.length];        %保存10个新最优抗体在下一次免疫的抗体群中 
    [no_use,index]=sort(anti1_length); 
    for i=21:30                             
        temp(i)=new_antitrope(index(i)); 
    end 
    antitrope=temp;   
end 
result_length=[antitrope.length]; 
[no_use,index]=sort(result_length); 
for i=1:30                                      %人工免疫算法后的30个最优抗体 
    AIA(i)=antitrope(index(i)); 
    AIA(i).tour(city_num+1)=AIA(i).tour(1); 
end 
disp(['人工免疫最优路径长度为:' num2str(AIA(1).length) ]); 
disp(['人工免疫运行时间为:' num2str(toc) '秒']); 
%--------------------------------免疫初始化、免疫局部搜索、蚁群算法-------------------------------------- 
tic; 
aia_num=15;                                     %信息素初始化时使用的人工免疫抗体个数([0,30]) 
pher_evap_rate=0.5;                             %信息素蒸发速率                                      
pher_effe_rate=1;                               %信息素系数                                       
heur_effe_rate=3;                               %启发式信息系数                                
tau=0.02;                                       %正常信息素初始化量                                                 
ant_num=15;                                     %蚂蚁数目   
iter_num=300;                                   %基本蚂蚁算法迭代次数 
imu_num=100;                                    %使用免疫算子局部优化次数 
%根据AIA算法进行信息素初始化 
pher=(ones(city_num)-eye(city_num))*tau*0.1; 
for i=1:aia_num 
    for j=1:city_num 
        pres=AIA(i).tour(j); 
        next=AIA(i).tour(j+1); 
        pher(pres,next)=pher(pres,next)+tau*0.2; 
        pher(next,pres)=pher(pres,next); 
    end 
end 
%计算信息素与启发式信息联合矩阵 
choice_info=calc_info(pher_effe_rate,heur_effe_rate,pher,dist); 
%蚂蚁构建路径 
for order=1:iter_num 
    %每一次迭代开始时清楚蚂蚁记录并随机初始化蚂蚁起点城市 
    ant=clear_fisttour(ant_num,city_num); 
    %采用并行方式构建蚂蚁剩余部分路径 
    for step=2:city_num 
        for i=1:ant_num 
            pres_city =ant(i).tour(step-1); 
            next_city=as_next_tour(city_num,choice_info,pres_city,ant(i));     
            %将下一访问城市添加到路径和记录表中 
            ant(i).tour(step)=next_city;                   
            ant(i).visited(next_city)=1;                    
        end 
    end 
    %计算每一只蚂蚁的路径长度和当前迭代最优路径 
    [iter_best,ant]=tourlength_iterbest(ant_num,city_num,dist,ant); 
    %求得迭代至今最优路径 
    if order==1 
        glob_best.tour=iter_best.tour; 
        glob_best.length=iter_best.length; 
        glob_best.found=1; 
        glob_best.time=toc; 
    elseif   iter_best.length<glob_best.length 
        glob_best.tour=iter_best.tour; 
        glob_best.length=iter_best.length; 
        glob_best.found=order; 
        glob_best.time=toc; 
    end 
    %对至今最优路径引入免疫算子进行局部优化 
%    for i=1:imu_num 
%        vairiation_tour=immune_operator(city_num,glob_best.tour(1:city_num),pc,uc,ps,us,pi,ui); 
%        vairiation_tour=[vairiation_tour vairiation_tour(1)]; 
%        vairiation_length=0; 
%        for j=1:city_num 
%            vairiation_length=vairiation_length+dist(vairiation_tour(j),vairiation_tour(j+1)); 
%        end 
%        if  vairiation_length<glob_best.length 
%            glob_best.tour=vairiation_tour; 
%            glob_best.length=vairiation_length; 
%            glob_best.found=order; 
%            glob_best.time=toc; 
%        end 
%    end 
    %进行信息素更新 
    pher=as_pher_update(pher_evap_rate,city_num,ant_num,dist,'ant_cycle',pher,ant); 
    %更新信息素与启发式信息素联合矩阵 
    choice_info=calc_info(pher_effe_rate,heur_effe_rate,pher,dist); 
 %   figure(1) 
 %   for i=1:city_num+1 
 %       m=glob_best.tour(i); 
 %       p(i)=X(m); 
 %       q(i)=Y(m); 
 %   end 
 %   scatter(X,Y,'.');box on;hold on;plot(p,q); 
 %   title(num2str(glob_best.length));hold off; 
end 
disp(['人工免疫与蚂蚁系统运行时间为:' num2str(toc) '秒']); 
disp(['人工免疫与蚂蚁系统融合最优路径长度为:' num2str(glob_best.length)]); 
disp(['人工免疫与蚂蚁系统最优解时间为' num2str(glob_best.time)]); 
disp(['人工免疫与蚂蚁系统最优解迭代次数为' num2str(glob_best.found)]); 
 
%-------------------------------------蚂蚁算法--------------------------------- 
tic; 
pher_evap_rate=0.5;                                        
pher_effe_rate=1;                                          
heur_effe_rate=3;                                          
tau=0.02;                                                  
ant_num=15;                                                
iter_num=300;    
%初始化信息素矩阵和计算信息素与启发式信息联合矩阵 
pher=(ones(city_num)-eye(city_num))*tau; 
choice_info=calc_info(pher_effe_rate,heur_effe_rate,pher,dist); 
%蚂蚁构建路径 
for order=1:iter_num 
    %每一次迭代开始时清楚蚂蚁记录并随机初始化蚂蚁起点城市 
    ant=clear_fisttour(ant_num,city_num); 
    %采用并行方式构建蚂蚁剩余部分路径 
    for step=2:city_num 
        for i=1:ant_num 
            pres_city =ant(i).tour(step-1); 
            next_city=as_next_tour(city_num,choice_info,pres_city,ant(i));     
            %将下一访问城市添加到路径和记录表中 
            ant(i).tour(step)=next_city;                   
            ant(i).visited(next_city)=1;                    
        end 
    end 
    %计算每一只蚂蚁的路径长度和当前迭代最优路径 
    [iter_best,ant]=tourlength_iterbest(ant_num,city_num,dist,ant); 
    %求得迭代至今最优路径 
    if order==1 
        glob_best.tour=iter_best.tour; 
        glob_best.length=iter_best.length; 
        glob_best.found=1; 
        glob_best.time=toc; 
    elseif   iter_best.length<glob_best.length 
        glob_best.tour=iter_best.tour; 
        glob_best.length=iter_best.length; 
        glob_best.found=order; 
        glob_best.time=toc; 
    end 
    %作图 
 %   figure(2) 
 %   for i=1:city_num+1 
 %       m=glob_best.tour(i); 
 %       p(i)=X(m); 
 %       q(i)=Y(m); 
 %   end 
 %   scatter(X,Y,'.');box on; 
 %   hold on; 
 %   plot(p,q); 
 %   title(num2str(glob_best.length)); 
 %   hold off; 
    %进行信息素更新 
    pher=as_pher_update(pher_evap_rate,city_num,ant_num,dist,'ant_cycle',pher,ant); 
    %更新信息素与启发式信息素联合矩阵 
    choice_info=calc_info(pher_effe_rate,heur_effe_rate,pher,dist); 
end 
disp(['蚂蚁系统运行时间为:' num2str(toc) '秒']); 
disp(['蚂蚁系统最优路径长度为:' num2str(glob_best.length)]); 
disp(['蚂蚁系统求得最优路径时间为:' num2str(glob_best.time) '秒']); 
disp(['蚂蚁系统最优路径的迭代次数为:' num2str(glob_best.found)]);