蚁群算法实现 - 全局路径规划算法_蚁群算法路径规划详细步骤

参考博客：
（1）【人工智能】蚁群算法(密恐勿入)
（2）计算智能——蚁群算法
（3）蚁群算法(实例帮助理解)
（4）【数之道 04】解决最优路径问题的妙招-蚁群ACO算法
（5）路径规划与轨迹跟踪系列算法学习_第2讲_蚁群算法

1 蚁群算法讲解

基本原理：模拟蚂蚁觅食行为的启发式算法，广泛应用于优化问题的求解。将一群蚂蚁放在问题的解空间上，让它们通过信息素的传递和挥发，逐渐找到最优解
模拟蚂蚁在简单地形，寻找食物
① 在蚁群算法的初始阶段，我们在地图上不放置任何食物，因为蚂蚁需要在没有任何信息素的情况下开始摸索前进。一开始，蚂蚁们在洞外随机移动，试图找到食物的位置。每只蚂蚁的速度相同，它们会按照随机的方向前进，直到遇到障碍物或者到达了边界。此时，它们会再次随机选择一个方向，并继续前进。这个过程会持续进行

② 当蚂蚁们找到了食物后，它们会将一些信息素沿着它们的路径释放出来，并且在回到蚁巢的路上也会释放信息素。

蚁群之间的规则：

蚂蚁发现食物并将其带回巢穴时，通常会遵循已经标记的路径返回，即原路返回。在返回过程中，蚂蚁会释放归巢素和信息素，这些化学物质可以吸引其他蚂蚁跟随它的路径前往食物源。如果路径上有较多的归巢素或信息素，则越来越多的蚂蚁将会选择这条路径前往食物。

③ 当蚂蚁们回到巢穴时，它们会在原来的路径上释放更多信息素，增强这条路径的吸引力，并且尝试着寻找更短的路径。蚂蚁们会在路径上选择合适的地方停下来，释放信息素，然后返回巢穴。这个过程将持续进行，直到蚂蚁们找到了最优路径。信息素会随着时间的推移而逐渐挥发。

随着时间的推移，蚂蚁终会找到最优路径。有点类似快速搜索随机树算法。

蚁群算法在复杂地形的应用：

蚁群优化算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，比如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域己获得成功的应用，其中最成功的是在组合优化问题中的应用

如果读者还是不理解，请看下面这个例子：

假设1号蚂蚁和2号蚂蚁速度相同，释放的信息素浓度相同，▲ACB为等腰三角形。当1号蚂蚁从A走到C的时候，2号蚂蚁已经走到了食物B。此时AC和AB信息素浓度相同。然后2号蚂蚁找到食物返回，1号蚂蚁从C走到B。此时AB信息素浓度是BC的两倍，当1号蚂蚁想返回到A点，不会沿BCA返回，而是选择信息素浓度高的BA路径返回。这样持续下去，AB路径上的信息素浓度会越来越高，后面的蚂蚁都会选择AB路径来获取食物，从而找到了获取食物的最短路径。

2 算法设计

蚂蚁觅食行为本质可以概括为以下几点：
① 路径概率选择机制信息素踪迹越浓的路径,被选中的概率越大
② 信息素更新机制路径越短,路径上的信息素踪迹增长得越快
③ 协同工作机制蚂蚁个体通过信息素进行信息交流

当蚁群算法陷入局部最优解时，可以使用以下方法进行优化：

（1）增加蚂蚁的数量。增加蚂蚁的数量可以增加搜索的广度，从而有更大的可能性找到全局最优解。
（2）调整信息素挥发速度。通过适当降低信息素挥发速度，可以增加信息素在路径上的积累，从而增加蚂蚁选择该路径的概率。
（3）引入随机因素。在蚁群算法中引入随机因素，可以使蚂蚁更具有探索性，从而有可能跳出局部最优解，进而找到全局最优解。
（4）改变参数。通过改变蚁群算法中的参数，如信息素浓度、信息素挥发速度、启发式因子等，可以使算法更加灵活，从而更容易找到全局最优解。
（5）使用局部搜索算法。在蚁群算法的基础上，可以结合局部搜索算法，如模拟退火算法、遗传算法等，来寻找全局最优解。

算法步骤：

（1）初始化(各个参数): 在计算之初需要对相关的参数进行初始化，如蚂蚁数量m、信息素因子α、启发函数因子β、信息素挥发因子ρ、信息素常数Q、最大迭代次数t等等。
（2）构建解空间： 将各个蚂蚁随机地放置于不同的出发点，对每个蚂蚁k（k=1，2，……，m），计算其下一个待访问的城市，直到所有蚂蚁访问完所有的城市。
（3）更新信息素： 计算各个蚂蚁经过的路径长度L，记录当前迭代次数中的最优解（最短路径）。同时，对各个城市连接路径上的信息素浓度进行更新。
（4）判断是否终止： 若迭代次数小于最大迭代次数则迭代次数加一，清空蚂蚁经过路径的记录表，并返回步骤二；否则终止计算，输出最优解。

1 初始化参数的设置：
参考博客：蚁群算法(实例帮助理解)

2 构建路径(解空间)，将各个蚂蚁随机地置于不同的出发点，为每只蚂蚁确定当前候选道路集：
蚂蚁选择城市的概率公式如下：
P i j k = { τ i j α ( t ) ∗ η i j β ( t ) ∑ s ∈  allowed k τ i j α ( t ) ∗ η i j β ( t ) j ∈  allowed k 0  其他  P_{i j}^{k}=\left\{

$$\begin{array}{ll} \frac{\tau_{i j}^{\alpha}(t) * \eta_{i j}^{\beta}(t)}{\sum_{\mathrm{s}_{\mathrm{}\in} \text { allowed}_{k}} \tau_{i j}^{\alpha}(t) * \eta_{i j}^{\beta}(t)} & j \in \text { allowed}_{k} \\ 0 & \text { 其他 } \end{array}$$ \right. Pijk​=⎩ ⎨ ⎧​∑s∈​ allowedk​​τijα​(t)∗ηijβ​(t)τijα​(t)∗ηijβ​(t)​0​j∈ allowedk​ 其他 ​

• i，j为起点和终点，k表示第k只蚂蚁
• ${\eta }_{ij}(t)=1/d_{ij}$为启发函数用于表示蚂蚁从i到j的能见度，其大小是两点i,j路径距离的倒数
• ${\tau }_{ij}(t)$为时间t由i到j的信息素浓度
• $allowe{d}_k$表示蚂蚁k尚未访问过节点的集合
• $\alpha$为信息素重要程度因子，值越大，信息素在转移中的作用越大
• $\beta$为启发函数重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁会以较大的概率转移到距离短的城市。

3 更新信息素浓度:计算每个蚂蚁经过路径长度$L_k$，记录当前迭代次数中的最优解（最短路径）。同时，对各个节点连接路径上信息素浓度进行更新。

蚁群算法分为三种模型：蚁周模型、蚁量模型、蚁密模型。蚁周模型是完成一次路径循环后，蚂蚁才释放信息素，其利用的是全局信息。蚁量模型和蚁密模型蚂蚁完成一步后就更新路径上的信息素，其利用的是局部信息。
蚁周模型公式：
Δ τ i j k = { Q L k ,  如果蚂蚁  k  经过路径城市  i  到  j 0 ,  否则  \Delta \tau_{i j}^{k}=\left\{

$$\begin{array}{l} \frac{Q}{L_{k}}, \text { 如果蚂蚁 } k \text { 经过路径城市 } \mathrm{i} \text { 到 } \mathrm{j} \\ 0, \text { 否则 } \end{array}$$ \right. Δτijk​={Lk​Q​, 如果蚂蚁 k 经过路径城市 i 到 j0, 否则 ​
$Q$为信息素常量，$L_k$表示第$k$只蚂蚁在本次循环中所走路径的长度。

4 判断是否中止:若$iter<itermax$，则令$iter=iter+1$，清空蚂蚁经过路径的记录表，并返回步骤2；否则，终止计算，输出最优解

一次迭代就是指m只蚂蚁都走完所有的城市，即存在m个搜索路径。将所有路径进行比较，选择长度最短的路径，做出这一次迭代的可视化结果，更新信息素。并将当前的最短路径与过往的最短路径长度进行对比，同时迭代次数加1。然后判断当前迭代次数是否等于设置的迭代次数。如果等于则停止迭代，否则进行下一次迭代

3 代码实现

使用蚁群算法解决旅行商问题（TSP）

%% I. 清空环境变量
clear all
clc
%% II. 导入数据
% load citys_data.mat
 citys = [16.4700   96.1000
     16.4700   94.4400
     20.0900   92.5400
     22.3900   93.3700
     25.2300   97.2400
     22.0000   96.0500
     20.4700   97.0200
     17.2000   96.2900
     16.3000   97.3800
     14.0500   98.1200
     16.5300   97.3800
     21.5200   95.5900
     19.4100   97.1300
     20.0900   92.5500];
%% III. 计算城市间相互距离
n = size(citys,1); % 城市数量
D = zeros(n,n);
for i = 1:n
    for j = 1:n
        if i ~= j
            D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));
        else
            D(i,j) = 1e-4;  %如果是0会导致矩阵对角线都是0 导致启发函数无穷大 因此取个很小的值    
        end
    end    
end
 
%% IV. 初始化参数
m = 50;                              % 蚂蚁数量
alpha = 1;                           % 信息素重要程度因子
beta = 5;                            % 启发函数重要程度因子
rho = 0.1;                           % 信息素挥发因子
Q = 1;                               % 常系数
Eta = 1./D;                          % 启发函数
Tau = ones(n,n);                     % 信息素矩阵
Table = zeros(m,n);                  % 路径记录表,每一行代表一个蚂蚁走过的路径
iter = 1;                            % 迭代次数初值
iter_max = 200;                      % 最大迭代次数 
Route_best = zeros(iter_max,n);      % 各代最佳路径       
Length_best = zeros(iter_max,1);     % 各代最佳路径的长度  
Length_ave = zeros(iter_max,1);      % 各代路径的平均长度  
 
%% V. 迭代寻找最佳路径
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);
             allow = citys_index(allow_index);  % 待访问的城市集合
             P = allow;
             % 计算城市间转移概率
             for k = 1:length(allow)
                 P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta;
             end
             P = P/sum(P);
             % 轮盘赌法选择下一个访问城市
             Pc = cumsum(P);     
            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,:);
      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,:);
          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-rho) * Tau + Delta_Tau;
    % 迭代次数加1，清空路径记录表
    iter = iter + 1;
    Table = zeros(m,n);
end
 
%% VI. 结果显示
[Shortest_Length,index] = min(Length_best);
Shortest_Route = Route_best(index,:);
disp(['最短距离:' num2str(Shortest_Length)]);
disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);
%% VII. 绘图
figure(1)
plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
     [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
grid on
for i = 1:size(citys,1)
    text(citys(i,1),citys(i,2),['   ' num2str(i)]);
end
text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'       起点');
text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'       终点');
xlabel('城市位置横坐标')
ylabel('城市位置纵坐标')
title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')'])
figure(2)
plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')
legend('最短距离','平均距离')
xlabel('迭代次数')
ylabel('距离')
title('各代最短距离与平均距离对比')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

最短距离:29.3405
最短路径:6  12   7  13   8  11   9  10   1   2  14   3   4   5   6
1
2

运行结果：