as_tsp.m

蚁群算法 关于城市旅行商问题

     lk=0; % 初始路长
     index=k; % 下一个城市坐标
     cka(1)=k; % 出发城市向量纪录
%  第k只蚂蚁完成搜索一圈，需要n步，但可选城市只有n-1个
     for i=1:1:n-1
         table(index)=[];% 去掉起点城市，形成可行城市集
%  从可行表中选择下一个城市，在可行性表中，已知起点k   
%  先求可行信息素总量即Pij的分子，其实没用.可以看出可行总量为定值，只靠分子决定下一个城市
         infsum=0; % 信息素总量初始化，即分子
         ptmax=0;  % 最初转移概率为零，即分母
%  再求可行城市概率，选择下一步城市
         for ii=1:1:length(table)
%              infsum=infsum+inf(old,table(ii))^aa*d(old,table(ii))^-bb;% 信息素总量集，其实没用
%  蚁群算法转移概率公式，其实概率矩阵在搜索前就已知,下面是公式4
             pt(ii)=inf(old,table(ii))^aa*d(old,table(ii))^(-bb); % 经典概率计算公式，核心。即趋向下一个城市的概率
             if pt(ii)>=ptmax
                ptmax=pt(ii);
                index=ii;  % 选出下一个城市在可行城市中的位置,即pt最大的城市
             end   
         end % 选择出最大概率城市
         new=table(index); % 得出下一个城市的序号
         lk=lk+d(old,new); % 行走路程增加
         hold on 
         line([x(old),x(new)],[y(old),y(new)]); % 路径绘制，
         cka(i+1)=new; % 纪录行走向量，更新一次
         old=new; % 新城变旧城
%          nleft=nleft-1; % 允许表容量下降
         hold off
%%%%%设置断点4
%%%%%%%%%%%在此设置断点 观察蚁群算法的第一次迭代%%%%%%%%%%%%%%%%%%%%%%

     end   % k蚂蚁完成一圈搜索
         line([x(table),x(k)],[y(table),y(k)],'color','r','LineWidth',2); % 绘制最后一条结束之路
         lk=lk+d(table,k); % 第k只蚂蚁本次搜索的总长
         laa(k)=lk; % 纪录蚁群算法蚂蚁的路程长度
         aka(k,:)=cka(:); % 纪录蚁群算法蚂蚁的行程,可以在此设置断点观察绘制

% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%在此设置断点5 观察蚁群算法 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%图形比以前的随机路线干净 清爽 原因是蚂蚁有很多的公共的路线可以走
% 开始更新第k只蚂蚁的信息素
% 信息素增量矩阵更新，只有在蚂蚁走完之后才能更新
%
     for s=1:1:n-1
         dinf(cka(s),cka(s+1))=dinf(cka(s),cka(s+1))+Q/lk; % 更新信息素增量矩阵,经过n城完成一遍
         dinf(cka(s+1),cka(s))=dinf(cka(s),cka(s+1)); % 信息素增量矩阵其实是对称阵
     end    
         dinf(cka(1),cka(n))=dinf(cka(1),cka(n))+Q/lk;  % 首尾城市信息素更新
         dinf(cka(n),cka(1))=dinf(cka(1),cka(n)); % 信息素增量矩阵其实是对称阵
% 第k只蚂蚁对信息素的贡献完成
% 统计第k只蚂蚁的表现
     if laa(k)<=lmin 
           lmin=laa(k);
           index_min=k;
     end
     if laa(k)>=lmax
           lmax=laa(k);
           index_max=k;
     end
% 下一只蚂蚁开始了     
end  % m只蚂蚁完成一次搜索总的信息素变化
         inf=p*inf+dinf; % 信息素矩阵进行优化
         str1=strcat(num2str(m),'只蚂蚁蚁群搜索最长总长是： ', num2str(lmax));
         str2=strcat(num2str(m),'只蚂蚁蚁群搜索最短总长是： ', num2str(lmin));
         text(0.5,0.5,str1,'FontSize',8);
         text(15.5,0.5,str2,'FontSize',8);
hold off;

% 蚁群搜索路线图     

%%%%%%%% 图形5 绘制极端的搜索情况 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
figure(5); % 蚁群搜索的极端情况,最初还是画城市坐标，可在此设置断点观察信息素矩阵情况
for i=1:1:n

    plot(x(i),y(i),'b*')
    str=num2str(i);
    text(x(i) +0.5,y(i) +0.5,str)
    hold on
    xlabel ('城市横坐标')
    ylabel ('城市纵坐标')
    title(strcat(num2str(m),'只蚂蚁蚁群搜索城市最好最差路线图'))
end
grid;
hold off;
      
%  绘制蚁群搜索极端搜索路线图
for j=1:1:n-1
    line([x(aka(index_max,j)),x(aka(index_max,j+1))],[y(aka(index_max,j)),y(aka(index_max,j+1))],'color','r','LineWidth',1); % 绘制最长路径
    line([x(aka(index_min,j)),x(aka(index_min,j+1))],[y(aka(index_min,j)),y(aka(index_min,j+1))],'color','g','LineWidth',3); % 绘制最短路径
%     jianyan=jianyan+d(aka(index_min,j),aka(index_min,j+1));
end
    line([x(aka(index_max,n)),x(aka(index_max,1))],[y(aka(index_max,n)),y(aka(index_max,1))],'color','r','LineWidth',1); % 绘制最长路径
    line([x(aka(index_min,n)),x(aka(index_min,1))],[y(aka(index_min,n)),y(aka(index_min,1))],'color','g','LineWidth',3); % 绘制最短路径
%     jianyan=jianyan+ d(aka(index_min,n),aka(index_min,1));   
    
    text(0.5,0.5,str1,'FontSize',8);
    text(15.5,0.5,str2,'FontSize',8);
    

%  现在进行关键的一步了，看蚂蚁究竟好不好，迭代几次看看
%  因为已经2次了，随机1次，蚂蚁一次
%  aka纪录蚁群搜索结果
%%
%%%%%%%%%%%%%%图形6 绘制NC次迭代的蚁群算法效果图 %%%%%%%%%%%%%%%%%%%%%
figure(6); % 绘制迭代NC次蚂蚁算法的效果，照例先把城市地图画出来，在此设置断点观察最优路径
for i=1:1:n

    plot(x(i),y(i),'b*')
    str=num2str(i);
    text(x(i) +0.5,y(i) +0.5,str)
    hold on
    xlabel ('城市横坐标')
    ylabel ('城市纵坐标')
    title(strcat(num2str(m),'只蚂蚁蚁群搜索',num2str(NC),'次城市路线图'))
end
grid;
hold off;
% 开始迭代
     lminrec=lmin;    % 纪录最短路径
     antsrec=aka(index_min,:);% 记录一下最好纪录
for mm=1:1:NC-2
% 初始化距离
     lmax=0;
     lmin=30*n;
% k只蚂蚁依次又开始搜索了，先还是从老地方走，尽管容易陷入局部最优     
  for k=1:1:m
% 初始化行走路线，还是从原来n个城市依次搜索
     table=[1:n]; % 可行性城市表
     old=k;% 第一个旧城市
%     nleft=n-1; % 共循环n-1步
     lk=0; % 初始路长
     index=k; % 下一个城市坐标
     ckaa(1)=k; % 出发城市向量纪录
%  第k只蚂蚁完成搜索一圈，需要n步，但可选城市只有n-1个
      for i=1:1:n-1
          table(index)=[];% 去掉起点城市，形成可行城市集,table表内为城市序号
          infsum=0; % 信息素总量初始化，即分子
          ptmax=0;  % 最初转移概率为零，即分母
%  再求可行城市概率，选择下一步城市
         for ii=1:1:length(table)
%              infsum=infsum+inf(old,table(ii))^aa*d(old,table(ii))^-bb;% 信息素总量集，其实没用
%  蚁群算法转移概率公式，
             pt(ii)=inf(old,table(ii))^aa*d(old,table(ii))^(-bb); % 经典概率计算公式，核心
             if pt(ii)>=ptmax
                ptmax=pt(ii);
                index=ii;  % 选出下一个城市,即分子最大的城市序列号
             end   
         end
         new=table(index); % 下一个城市
         lk=lk+d(old,new); % 行走路程增加
         hold on 
         line([x(old),x(new)],[y(old),y(new)]); % 路径绘制，
         ckaa(i+1)=new; % 纪录行走向量，更新一次
         old=new; % 新城变旧城
%          nleft=nleft-1; % 允许表容量下降
%          hold off
     end   % 第k只蚂蚁完成一次全搜索
         line([x(table),x(k)],[y(table),y(k)],'color','r','LineWidth',2); % 绘制最后一条结束之路
         lk=lk+d(table,k); % 第k只蚂蚁本次搜索的总长
         laaa(k)=lk; % 纪录蚁群算法蚂蚁的路程长度
         akaa(k,:)=ckaa(:); % 纪录蚁群算法迭代蚂蚁的行程,设置断点看长度
%         
% 开始更新第k只蚂蚁的信息素
% 信息素增量
      for s=1:1:n-1
         dinf(ckaa(s),ckaa(s+1))=dinf(ckaa(s),ckaa(s+1))+Q/lk; % 更新信息素增量矩阵,经过n城完成一遍
         dinf(ckaa(s+1),ckaa(s))=dinf(ckaa(s),ckaa(s+1)); % 信息素增量矩阵其实是对称阵
      end    
         dinf(ckaa(1),ckaa(n))=dinf(ckaa(1),ckaa(n))+Q/lk;  % 首尾城市信息素更新
         dinf(ckaa(n),ckaa(1))=dinf(ckaa(1),ckaa(n)); % 信息素增量矩阵其实是对称阵
% 第k只蚂蚁对信息素的贡献完成
% 统计第k只蚂蚁的表现
      if laaa(k)<=lmin 
           lmin=laaa(k);
           index_min=k;%记录最短距离
      end
      if laaa(k)>=lmax
           lmax=laaa(k);
           index_max=k; %纪录最长距离
      end
 end
% m只蚂蚁完成一次搜索总的信息素变化
         inf=p*inf+dinf; % 信息素矩阵形成了，可以进行下一次搜索了。
         mydebug=0;
end %  NC-2次搜索后结果       
         
% 多次搜索后进行统计输出吧         
         str1=strcat(num2str(m),'只蚂蚁迭代搜索最长总长是： ', num2str(lmax));
         str2=strcat(num2str(m),'只蚂蚁迭代搜索最短总长是： ', num2str(lmin));
         text(0.5,0.5,str1,'FontSize',8);
         text(15.5,0.5,str2,'FontSize',8);
hold off;

%  绘制蚁群搜索极端搜索路线图
%%%%%%%%%%%%%% 图7 NC次迭代完成之后 最差和最优的线路图 %%%%%%%%%%%%%%%%%%%%%%%
figure(7);
for i=1:1:n

    plot(x(i),y(i),'b*')
    str=num2str(i);
    text(x(i) +0.5,y(i) +0.5,str)
    hold on
    xlabel ('城市横坐标')
    ylabel ('城市纵坐标')
    title(strcat(num2str(m),'只蚂蚁蚁群迭代',num2str(NC),'次搜索城市最好最差路线图'))
end
grid;
hold off;
for j=1:1:n-1
    line([x(akaa(index_max,j)),x(akaa(index_max,j+1))],[y(akaa(index_max,j)),y(akaa(index_max,j+1))],'color','r','LineWidth',1); % 绘制最长路径
    line([x(akaa(index_min,j)),x(akaa(index_min,j+1))],[y(akaa(index_min,j)),y(akaa(index_min,j+1))],'color','g','LineWidth',3); % 绘制最短路径
end
    line([x(akaa(index_max,n)),x(akaa(index_max,1))],[y(akaa(index_max,n)),y(akaa(index_max,1))],'color','r','LineWidth',1); % 绘制最长路径
    line([x(akaa(index_min,n)),x(akaa(index_min,1))],[y(akaa(index_min,n)),y(akaa(index_min,1))],'color','g','LineWidth',3); % 绘制最短路径
        
    text(0.5,0.5,str1,'FontSize',8);
    text(15.5,0.5,str2,'FontSize',8);
%    总结：
% 简便蚁群算法相比纯粹蚁群算法的收敛速度更快，但容易陷入局部最优，
% 不过考虑到效率优先，结果也能接受。
% 该算法在处理对称城市时非常迅速，结果不错。