Table of Contents

一、蚁群算法概念

1. 基本思想

蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径问题。根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化(如原有路径上有了障碍物)后，自适应地搜索新的最佳路径。蚂蚁是如何做到这一点的呢？

原来，蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物一信息激素一也可称之为信息素，使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，以致信息素强度增大(当然，随时间的推移会逐渐减弱)，所以蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，这种选择过程被称之为蚂蚁的自催化行为。由于其原理是一种正反馈机制.因此，也可将蚂蚁王国理解为所谓的增强型学习系统。

在自然界中，蚁群的这种寻找路径的过程表现为一种正反馈过程，“蚁群算法”就是模仿生物学蚂蚁群觅食寻找最优路径原理衍生出来的。

2. 算法特点

这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。在数字时代背景下，蚁群算法在网络路由中的应用受到越来越多学者的关注，并提出了一些新的基于蚂蚁算法的路由算法。

二、蚁群算法流程

1. 算法思路

  1. 根据具体问题设置多只蚂蚁，分头并行搜索。

  2. 每只蚂蚁完成一次周游后，在行进的路上释放信息素，信息素量与解的质量成正比。

  3. 蚂蚁路径的选择根据信息素强度大小（初始信息素量设为相等），同时考虑两点之间的距离，采用随机的局部搜索策略。这使得距离较短的边，其上的信息素量较大，后来的蚂蚁选择该边的概率也较大。

  4. 每只蚂蚁只能走合法路线（经过每个城市1次且仅1次），为此设置禁忌表来控制。

  5. 所有蚂蚁都搜索完一次就是迭代一次，每迭代一次就对所有的边做一次信息素更新，原来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。

  6. 更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。

  7. 达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的最优解。

2. 以TSP 问题为例， 算法流程如下：

  • 步骤1：对相关参数进行初始化，包括蚁群规模、信息素因子、启发函数因子、信息素挥发因子、信息素常数、最大迭代次数等，以及将数据读入程序，并进行预处理：比如将城市的坐标信息转换为城市间的距离矩阵。
  • 步骤2：随机将蚂蚁放于不同出发点，对每个蚂蚁计算其下个访问城市，直到有蚂蚁访问完所有城市。
  • 步骤3：计算各蚂蚁经过的路径长度Lk，记录当前迭代次数最优解，同时对路径上的信息素浓度进行更新。
  • 步骤4：判断是否达到最大迭代次数，若否，返回步骤2；是，结束程序。
  • 步骤5：输出结果，并根据需要输出寻优过程中的相关指标，如运行时间、收敛迭代次数等。

image-20211008215146874

3. 关键参数

蚁群算法主要有5个关键参数。

  • 蚂蚁数量

    m 表示蚂蚁数量，m数目越多，得到的最优解就越精确，但是会产生不少重复解，随着算法接近最优值的收敛，信息正反馈作用降低，大量重复工作，消耗了资源，增加了时间复杂度。一般上，在时间等资源条件紧迫的情况下，蚂蚁数设定为城市数的1.5倍较稳妥。

  • 信息素因子

    image-20211009131705181

    信息素因子 $\alpha$ 反映了蚂蚁在移动过程中所积累的信息量在指导蚁群搜索中的相对重要程度，其值过大，蚂蚁选择以前走过的路径概率大，搜索随机性减弱；值过小，等同于贪婪算法，使搜索过早陷入局部最优。实验发现，信息素因子选择[1,4]区间，性能较好。

  • 启发函数因子（适应度的重要程度）

    启发函数因子 $\beta$ 反映了启发式信息在指导蚁群搜索过程中的相对重要程度，其大小反映的是蚁群寻优过程中先验性和确定性因素的作用强度。过大时，虽然收敛速度会加快，但容易陷入局部最优；过小时，容易陷入随机搜索，找不到最优解。实验研究发现，当启发函数因子为[3,4.5]时，综合求解性能较好。

  • 信息素挥发因子

    过小时，各路径信息素过多，导致无效的路径继续被搜索，影响算法收敛速率；过大，无效的路径虽然可以被排除搜索，但是不能保证有效路径不会被放弃搜索，影响到最优值的搜索。当属于[0.2，0.5]时,综合性能较好。

  • 最大迭代次数

    大小直接影响求解的速度和收敛与否。一般取100至500 次，可以先用200尝试。

三、蚁群算法工具箱

只提供了蚁群算法(ACA, Ant Colony Algorithm)解决TSP问题

 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

import numpy as np
from scipy import spatial
import pandas as pd
import matplotlib.pyplot as plt

num_points = 25

points_coordinate = np.random.rand(num_points, 2)  # generate coordinate of points
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')


def cal_total_distance(routine):
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])


# %% Do ACA
from sko.ACA import ACA_TSP

aca = ACA_TSP(func=cal_total_distance, n_dim=num_points,
              size_pop=50, max_iter=200,
              distance_matrix=distance_matrix)

best_x, best_y = aca.run()

# %% Plot
fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_x, [best_x[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
pd.DataFrame(aca.y_best_history).cummin().plot(ax=ax[1])
plt.show()

image-20211008220003745