蚁群算法的Matlab实现

作者:神秘网友 发布时间:2020-09-14 09:34:17

蚁群算法的Matlab实现

蚁群算法的Matlab实现

为了学习蚁群算法的解决过程,结合一个实际问题,使用Matlab进行编程实现,并解决该问题

已知敌方 100 个目标的经度、纬度数据在文件sj.txt中

53.7121    15.3046    51.1758    0.0322    46.3253    28.2753   30.3313    6.9348 
56.5432    21.4188    10.8198    16.2529   22.7891    23.1045   10.1584    12.4819 
20.1050    15.4562    1.9451     0.2057    26.4951    22.1221   31.4847    8.9640 
26.2418    18.1760    44.0356    13.5401   28.9836    25.9879   38.4722    20.1731 
28.2694    29.0011    32.1910    5.8699    36.4863    29.7284   0.9718     28.1477 
8.9586     24.6635    16.5618    23.6143   10.5597    15.1178   50.2111    10.2944 
8.1519     9.5325     22.1075    18.5569   0.1215     18.8726   48.2077    16.8889 
31.9499    17.6309    0.7732     0.4656    47.4134    23.7783   41.8671    3.5667 
43.5474    3.9061     53.3524    26.7256   30.8165    13.4595   27.7133    5.0706 
23.9222    7.6306     51.9612    22.8511   12.7938    15.7307   4.9568     8.3669 
21.5051    24.0909    15.2548    27.2111   6.2070     5.1442    49.2430    16.7044 
17.1168    20.0354    34.1688    22.7571   9.4402     3.9200    11.5812    14.5677 
52.1181    0.4088     9.5559     11.4219   24.4509    6.5634    26.7213    28.5667 
37.5848    16.8474    35.6619    9.9333    24.4654    3.1644    0.7775     6.9576 
14.4703    13.6368    19.8660    15.1224   3.1616     4.2428    18.5245    14.3598 
58.6849    27.1485    39.5168    16.9371   56.5089    13.7090   52.5211    15.7957 
38.4300    8.4648     51.8181    23.0159   8.9983     23.6440   50.1156    23.7816 
13.7909    1.9510     34.0574    23.3960   23.0624    8.4319    19.9857    5.7902 
40.8801    14.2978    58.8289    14.5229   18.6635    6.7436    52.8423    27.2880 
39.9494    29.5114    47.5099    24.0664   10.1121    27.2662   28.7812    27.6659 
8.0831     27.6705    9.1556     14.1304   53.7989    0.2199    33.6490    0.3980 
1.3496     16.8359    49.9816    6.0828    19.3635    17.6622   36.9545    23.0265 
15.7320    19.5697    11.5118    17.3884   44.0398    16.2635   39.7139    28.4203 
6.9909     23.1804    38.3392    19.9950   24.6543    19.6057   36.9980    24.3992 
4.1591     3.1853     40.1400    20.3030   23.9876    9.4030    41.1084    27.7149 

我方有一个基地,经度和纬度为(70,40)。假设我方飞机的速度为 1000 公里/小时。我方派一架飞机从基地出发,侦察完敌方所有目标,再返回原来的基地。在敌方每一目标点的侦察时间不计,求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长)。 

蚁群算法解决如下:

%% 蚁群算法及Matlab实现—侦查路线问题
% 文件名:example1.m
% 时间:2020年9月13日
% 来源:https://blog.csdn.net/lishan132/article/details/108568242
% 参考:卓金武,王鸿钧编著. MATLAB 数学建模方法与实践 第 3 版. 北京航空航天大学出版社, 2018.07.
% 功能:利用蚁群算法计算侦察机从基地出发侦查完100个目标耗费的最短时间

%% 数据准备
% 清空环境变量
clear close clc
% 程序运行计时开始
t0 = clock;
%导入数据
load sj.txt        %加载敌方 100 个目标的数据 

%% 计算侦查目标间相互距离
x=sj(:,1:2:8); x=x(:); 
y=sj(:,2:2:8); y=y(:); 
sj=[x y]; d1=[70,40];  
sj0=[d1;sj;d1]; sj=sj0*pi/180; 

%生成距离矩阵
d=zeros(102); %距离矩阵 d 
for i=1:101 
     for j=i+1:102 
         temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)); 
         d(i,j)=6370*acos(temp); 
     end 
end 
d=d+d';

n = size(sj0,1);
D = d;
%% 初始化参数
m = 120;                             % 蚂蚁数量
alpha = 1;                           % 信息素重要程度因子
beta = 5;                            % 启发函数重要程度因子
vol = 0.2;                           % 信息素挥发(volatilization)因子
Q = 10;                              % 常系数
Heu_F = 1./D;                        % 启发函数(heuristic function)
Tau = ones(n,n);                     % 信息素矩阵
Table = zeros(m,n);                  % 路径记录表
iter = 1;                            % 迭代次数初值
iter_max = 50;                      % 最大迭代次数 
Route_best = zeros(iter_max,n);      % 各代最佳路径       
Length_best = zeros(iter_max,1);     % 各代最佳路径的长度  
Length_ave = zeros(iter_max,1);      % 各代路径的平均长度  
Limit_iter = 0;                      % 程序收敛时迭代次数

%% 迭代寻找最佳路径
while iter <= iter_max
    % 随机产生各个蚂蚁的起点城市
      start = zeros(m,1);
      for i = 1:m
          temp = randperm(n);
          start(i) = temp(1);
      end
      Table(:,1) = start; 
      % 构建解空间
      citys_index = 1:n;
      % 逐个蚂蚁路径选择
      for i = 1:m
          % 逐个城市路径选择
         for j = 2:n
             tabu = Table(i,1:(j - 1));           % 已访问的城市集合(禁忌表)
             allow_index = ~ismember(citys_index,tabu);    % 参加说明1(程序底部)
             allow = citys_index(allow_index);  % 待访问的城市集合
             P = allow;
             % 计算城市间转移概率
             for k = 1:length(allow)
                 P(k) = Tau(tabu(end),allow(k))^alpha * Heu_F(tabu(end),allow(k))^beta;
             end
             P = P/sum(P);
             % 轮盘赌法选择下一个访问城市
            Pc = cumsum(P);     %参加说明2(程序底部)
            target_index = find(Pc >= rand); 
            target = allow(target_index(1));
            Table(i,j) = target;
         end
      end
      % 计算各个蚂蚁的路径距离
      Length = zeros(m,1);
      for i = 1:m
          Route = Table(i,:);
          for j = 1:(n - 1)
              Length(i) = Length(i) + D(Route(j),Route(j + 1));
          end
          Length(i) = Length(i) + D(Route(n),Route(1));
      end
      % 计算最短路径距离及平均距离
      if iter == 1
          [min_Length,min_index] = min(Length);
          Length_best(iter) = min_Length;  
          Length_ave(iter) = mean(Length);
          Route_best(iter,:) = Table(min_index,:);
          Limit_iter = 1; 
          
      else
          [min_Length,min_index] = min(Length);
          Length_best(iter) = min(Length_best(iter - 1),min_Length);
          Length_ave(iter) = mean(Length);
          if Length_best(iter) == min_Length
              Route_best(iter,:) = Table(min_index,:);
              Limit_iter = iter; 
          else
              Route_best(iter,:) = Route_best((iter-1),:);
          end
      end
      % 更新信息素
      Delta_Tau = zeros(n,n);
      % 逐个蚂蚁计算
      for i = 1:m
          % 逐个城市计算
          for j = 1:(n - 1)
              Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i);
          end
          Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);
      end
      Tau = (1-vol) * Tau + Delta_Tau;
    % 迭代次数加1,清空路径记录表
    iter = iter + 1;
    Table = zeros(m,n);
end

%% 结果显示
[Shortest_Length,index] = min(Length_best);
Shortest_Route = Route_best(index,:);
Time_Cost=etime(clock,t0);
disp(['最短距离:' num2str(Shortest_Length)]);
disp(['最短时间:' num2str(Shortest_Length/1000) '小时']);
disp(['收敛迭代次数:' num2str(Limit_iter)]);
disp(['程序执行时间:' num2str(Time_Cost) '秒']);

%% 绘图
figure(1)
%绘制坐标图
plot(x,y,'bO')      %目标坐标
hold on
plot(70,40,'p',...  %基地坐标
    'MarkerSize',10,...
    'MarkerEdgeColor','b',...
    'MarkerFaceColor','r')
hold on
%绘制路线图
plot([sj0(Shortest_Route,1);sj0(Shortest_Route(1),1)],...  %三点省略符为Matlab续行符
     [sj0(Shortest_Route,2);sj0(Shortest_Route(1),2)],'o-');
grid on
hold off
xlabel('经度')
ylabel('纬度')
title(['ACA最优化侦查路线(侦查时间:' num2str(Shortest_Length/1000) '小时)'])
figure(2)
%绘制算法收敛图
plot(1:iter_max,Length_best/1000,'b')
legend('侦查最短时间')
xlabel('迭代次数')
ylabel('时间')
title('算法收敛轨迹')

蚁群算法的Matlab实现

说明:

文中代码是在卓金武,王鸿钧编著. MATLAB 数学建模方法与实践一书中修改而来,只根据本文要解决的问题修改了前面距离矩阵的求法,调整了一下蚂蚁数量,并调整了绘图的相关代码,核心代码并未修改,仅作学习之用。

参考

[1] 卓金武,王鸿钧编著. MATLAB 数学建模方法与实践 第 3 版. 北京航空航天大学出版社, 2018.07.

蚁群算法的Matlab实现相关教程

  1. K-Core算法
  2. 分布式系统-3-同步网络算法
  3. 聚类算法——最大最小距离算法
  4. 算法篇:位运算基本操作
  5. java对称加密算法
  6. 斐波那契查找算法(黄金分割查找算法)
  7. DES算法代码实现
  8. Matlab配置export_fig,可进行去白边、处理保存矢量图像、保存PD