as_tsp.m

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

%%
%蚁群算法仿真
%% 张伟（1070329014）算法讲解 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 张德平（107029015）算法仿真 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 随机生成n个城市，由m只蚂蚁首先随机搜索一次，再按简便蚁群算法进行搜索。
% 也是方便看出蚁群算法的优化性。
%% x，y分别代表城市横、纵坐标。
% n代表城市数量，m代表蚂蚁数量，默认蚂蚁数量不超过城市数量。
% NC代表程序的迭代次数，作为算法的停止条件,可以改变。
% aa代表蚁群算法中的α,反映信息素在下一个前往城市选择中的重要性，。
% bb代表蚁群算法中的β,反映启发因子（程序中设为距离）在下一个前往城市选择中的重要性。
% laaa(m) 最后一次搜寻的m只蚂蚁路程长度记录。
% akaa(m×n)最后一次搜寻的m只蚂蚁行程记录。


% 初始化系统 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear;
NC=30;% NC 循环搜寻次数，即蚁群算法搜索次数
C=1; % 信息素初始浓度
n=30; % 城市数目，可以自由设定
m=8; % 蚂蚁数目，这里保证蚂蚁数目不能大于城市数目

% 初始化算法处理因子
aa=1; % 初始化信息量受重视程度
bb=1; % 初始化启发式信息量受重视程度（启发式基于路径长度）
p=0.5;% 初始化转移概率，表示过去信息素对当前路径影响，1-p反映信息素的衰减程度（挥发掉）
Q=50; % 初始化概率设计值

% 初始化信息素等变量矩阵
for i=1:1:n
    for j=1:1:n
        inf(i,j)=C; % 信息素浓度
        dinf(i,j)=0; % 初始信息素增量
%         ptrans(i,j)=0; % 转移概率矩阵，好像没用上
    end
end
inf=inf-eye(n); % 不可能在本地，把本地转移概率置零

% 随机生成城市地图 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ,前面1，2表示矩阵每个元素1行2列向量，矩阵个数按列排。
% 在N*N个坐标点中随机取n点构成城市，城市坐标矩阵四维
%
cmap=zeros(1,2,n,n); %城市坐标矩阵，前两维反映x,y信息，后两维表示城市序号（行列）
for a=1:1:n
    for b=1:1:n
        cmap(:,:,a,b)=[a b];
    end
end
% 随机选择n个城市从N*N中,并且绘制图形。
hold off;  % 把以前图形去掉
ranc=randperm(n*n); % n*n个城市随机排列
ct=zeros(n);% n个城市向量初始化

% 先绘制n个城市地图再说
%%%%%%%%%%%%%%%图形1 单独显示随机生成的30个城市 %%%%%%%%%%%%%%%%

figure(1); % 单独画图n个城市
for i=1:1:n
    x(i)=cmap(:,1,ranc(i)); %从N*N中选择第i个城市的横坐标
    y(i)=cmap(:,2,ranc(i)); %从N*N中选择第i个城市的纵坐标
    plot(x(i),y(i),'b*')
    str=num2str(i);
    text(x(i) +0.5,y(i) +0.5,str)
    hold on
    
end
xlabel ('城市横坐标')
    ylabel ('城市纵坐标')
    title(strcat(num2str(n),'城市随机分布图'))
grid;
hold off;

%
% 选择蚂蚁开始随机搜索
% X(i),Y(i)为城市的横纵坐标
% 初始化距离矩阵
%
for i=1:1:n
    for j=1:1:n
        d(i,j)=((x(i)-x(j))^2+(y(i)-y(j))^2)^0.5;
    end
end
% 绘制随机搜索效果图
%%%%%%%%%%%%%%%% 图形2 8只蚂蚁的随机搜索城市路线图 %%%%%%%%%%%%%%%%%%%%
figure(2); % 绘制随机搜索图，先单独画图n个城市，用于算法对比
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;
%
% k蚂蚁禁忌表 table()
% 把m只蚂蚁随机放到m个城市
% 因为城市编号随机，把m个蚂蚁依次放上1,2,...m城市
% 把k只蚂蚁的禁忌表初始化，路程初始化
% for i=1:1:n  % 要经过n步才能完成
% for k=1:1:m  % m只蚂蚁完成一步
% m只蚂蚁完成一次周游后再进行信息素更新
% 初始化统计数据
%
     lmax=0; % 最长距离初始化
     lmin=30*n; % 最短距离初始化
     index_max=1; % 最长蚂蚁编号
     index_min=1; % 最短蚂蚁编号
%% 蚂蚁开始依次搜索     
for k=1:1:m
     ck(1)=k;% 第一个出发城市，ck()矩阵每次更新
     table=[1:n]; % 允许城市先任意共n个
     old=k;% 第一个旧城市即出发城市
     nleft=n-1; % 共循环n-1步，第n步为首尾相连
     lk=0; % 初始路程长
     index=k; % 城市坐标，类似提出者的s
% 因为首城市已经定下来，现在实际上每只蚂蚁只有n-1个城市可选了          
     for i=1:1:n-1
         table(index)=[];% 去掉出发城市序号，容量逐渐下降，为nleft
         nc=randperm(nleft);% 随机剩余城市排序
         index=nc(1); % 随机选择下一个城市序号
         new=table(index); % 更新可行城市表
         lk=lk+d(old,new); % 行走路程纪录
         hold on 
         line([x(old),x(new)],[y(old),y(new)]); % 向下一个城市路径绘制，暂时不绘
         ck(i+1)=new; % 纪录行走向量
         old=new; % 新城变旧城
         nleft=nleft-1; % 允许表容量下降
         hold off
%%%%%设置断点1 -->>>>>>>>>>>>>>>>>>------>>>>>>>>>>>>>>>>
%%%%%%%%%%%%%%%%%%设置断点1 再次观察一只蚂蚁的一次随机搜索情况%%%%%%%%%%%%%%%%%%%%%%
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     end   
         line([x(table),x(k)],[y(table),y(k)],'color','r','LineWidth',2); % 绘制最后一条结束之路
         lk=lk+d(table,k); % 本次搜索的总长
         la(k)=lk; % 纪录蚂蚁的路程长度，la()表示各蚂蚁的行程
         ak(k,:)=ck(:); % 纪录第k只蚂蚁的行程,至此第k只蚂蚁完成一圈搜索
%         
% 开始更新第k只蚂蚁的信息素，c(k)已经记录完蚂蚁的行程
% 信息素增量矩阵更新，在第k只蚂蚁完成周游城市后。公式1
%
     for s=1:1:n-1
         dinf(ck(s),ck(s+1))=dinf(ck(s),ck(s+1))+Q/lk; % 更新信息素增量矩阵,经过n城完成一遍
         dinf(ck(s+1),ck(s))=dinf(ck(s),ck(s+1)); % 信息素增量矩阵其实是对称阵
     end    
         dinf(ck(1),ck(n))=dinf(ck(1),ck(n))+Q/lk;  % 首尾城市信息素增量更新
         dinf(ck(n),ck(1))=dinf(ck(1),ck(n)); % 信息素增量矩阵其实是对称阵
% 第k只蚂蚁对信息素的贡献完成
% 统计第k只蚂蚁的表现
%%%%%%%%%%%%%%%%%%%%%%%% 找出路径最长和最短的两条路径 %%%%%%%%%%%%%%%%%%%%%%
     if la(k)<=lmin 
           lmin=la(k);
           index_min=k;
     end
     if la(k)>=lmax
           lmax=la(k);
           index_max=k;
     end
end % 至此m只蚂蚁完成搜索

% m只蚂蚁完成一次搜索总的信息素变化
         inf=p*inf+dinf; % 信息素矩阵形成了，公式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);
%%%%%设置断点2
% 绘制随机搜索的最长最短路线图   
%%%%%%%%%%%%%%%%%%%%%%%%% 图形3 随机搜索中最长的 和最短的路线图%%%%%%%%%%
figure(3);
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(ak(index_max,j)),x(ak(index_max,j+1))],[y(ak(index_max,j)),y(ak(index_max,j+1))],'color','r','LineWidth',2); % 绘制最长路径
    line([x(ak(index_min,j)),x(ak(index_min,j+1))],[y(ak(index_min,j)),y(ak(index_min,j+1))],'color','g','LineWidth',3); % 绘制最短路径
end
% 把路程封闭
    line([x(ak(index_max,n)),x(ak(index_max,1))],[y(ak(index_max,n)),y(ak(index_max,1))],'color','r','LineWidth',2); % 绘制最长路径
    line([x(ak(index_min,n)),x(ak(index_min,1))],[y(ak(index_min,n)),y(ak(index_min,1))],'color','g','LineWidth',3); % 绘制最短路径

    text(0.5,0.5,str1,'FontSize',8);
    text(15.5,0.5,str2,'FontSize',8);
hold off;

% % 
% % 蚁群算法搜索开始
% % 准备开始有信息素的仿真了,在路径选择上不是随机的了
% % 重新初始化最短最长距离
% % 绘制蚁群算法搜索路程
% %
%%%%%设置断点3 --------》》》》》》》》》》》》》》》
%%%%%%%%%%%%%%%%%%%图形4 使用蚁群算法 路径选择不再是随机的 %%%%%%%%%
figure(4); % 蚁群算法搜索效果，先画城市
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;
% 初始化距离
     lmax=0;
     lmin=30*n;
for k=1:1:m
% 初始化行走路线
     table=[1:n]; % 可行性城市表
     old=k;% 第一个旧城市
%      nleft=n-1; % 共循环n-1步