www.pudn.com > anttsp.rar > optACS_main.m, change:2008-04-20,size:4518b


clear all; 
 
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'); 
%data=load('tsp225.txt'); 
X=data(:,2);                                               %城市横坐标 
Y=data(:,3);                                               %城市纵坐标 
%AS算法参数 
tau=1.5e-5;                                                %初始信息素量 
ant_num=15;                                                %蚂蚁数目 
iter_num=400;                                              %算法迭代次数 
pher_evap_rate=0.5;                                        %信息素蒸发速率 
pher_effe_rate=1;                                          %信息素系数 
heur_effe_rate=3;                                          %启发式信息系数 
cand_length=30;                                            %最近邻列表长度 
para_q=0.85;                                                %伪随机比例参数 
psi=0.1;                                                   %局部信息素更新参数 
local_iter_num=100;                                        %局部搜索次数 
%计算城市之间的距离和最近邻列表 
if cand_length==0 
   [dist,city_num]=dist_cand(X,Y); 
else 
   [dist,city_num,cand_list]=dist_cand(X,Y,cand_length); 
end 
%初始化信息素矩阵和计算信息素与启发式信息联合矩阵 
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);                 
            rand_q=rand;      
            if cand_length==0                               %未使用候选列表 
                if rand_q<=para_q 
                    next_city=acs_next_tour(pres_city,city_num,choice_info,ant(i)); 
                else 
                    next_city=as_next_tour(city_num,choice_info,pres_city,ant(i)); 
                end    
            else                                            %使用候选列表 
                if rand_q<=para_q 
                    next_city=acs_next_tour(pres_city,city_num,choice_info,ant(i)); 
                    %next_city=acs_cand_next_tour(pres_city,city_num,choice_info,cand_length,cand_list,ant(i)); 
                else 
                    next_city=as_cand_next_tour(cand_list,cand_length,city_num,pres_city,choice_info,ant(i)); 
                end 
            end 
            %将下一访问城市添加到路径和记录表中 
            ant(i).tour(step)=next_city;                   
            ant(i).visited(next_city)=1;                    
            %局部信息素更新并更改信息素与启发式信息联合矩阵 
            pher(pres_city,next_city)=(1-psi)*pher(pres_city,next_city)+psi*tau; 
            pher(next_city,pres_city)=pher(pres_city,next_city);     
            choice_info(pres_city,next_city)=pher(pres_city,next_city)*(1/dist(pres_city,next_city))^heur_effe_rate; 
            choice_info(next_city,pres_city)=choice_info(pres_city,next_city); 
       end 
    end 
    %对每一只蚂蚁的路径进行3-opt局部搜索 
   % for i=1:ant_num 
   %     ant(i).tour=local_search(city_num,dist,ant(i).tour,local_iter_num); 
   % 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 
    %全局信息素更新 
    pher=acs_glob_pher_update(glob_best,pher_evap_rate,city_num,pher);  
    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)]);