1.定义
蚁群算法(Ant Colony Optimization, ACO)是由Marco Dorigo于1992年在他的博士论文“Ant system: optimization by a colony of cooperating agents”中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
2.原理简述
蚂蚁在寻找食物或者运动过程中，会在移动的行进的路径上留下一种称之为信息素(pheromone)的物质。该物质有两种比较重要的特性：
- 会随着时间逐渐挥发；
- 信息素对蚂蚁有吸引力。
而蚂蚁在选择路径的时候也会有一定的特性:
- 蚂蚁往往倾向于选择信息素浓度更高的方向行进，但也会有蚂蚁特立独行；
- 在没有信息素作为参考的地方，蚂蚁一般随机选择行进方向，并带有一定惯性。
因此受信息素机制的影响，并在正反馈的作用下，蚁群觅食往往会形成一条长长的队伍。
如图1所示，在两点AB之间有两条路径。蚁群准备在AB之间来回搬运食物，由于刚开始路径1和路径2上都没有信息素，因此蚁群随机选择路径，两条路径各占50%。然后由于路径1比路径2短，因此单位时间内，经过路径1的蚂蚁更多(假如，那么路径1上的蚂蚁一个来回后，路径2上的蚂蚁才刚到B)，因此路径1上的信息素也相对更浓。在这种正反馈机制的作用下，最终大部分蚂蚁都会选择走更短的路径1。
3.蚁群算法简析
原理
受蚁群觅食等行为的启发，有学者将其引入到算法中用于解决类似问题，并提出了蚁群算法。下面，我们针对一个具体的有个城市的TSP问题，构建一个基础的ACS蚁群算法来求解。
首先设定一个启发值
并给他初始化一个常数，这里我们另
，其中
为城市i与j之间的距离。然后再设置一个参数
，该参数表示城市i和j之间的路径信息素浓度，算法一开始将其初始化为一个较小常数。
对于
个城市的TSP问题，蚁群算法的基本框架就是将
(
，一般可设为
)只蚂蚁随机分配到
次，求得最终所需的最优路径。对于第k只蚂蚁，它下一个选择去往哪个城市由如下公式决定：
这里，表示第
只蚂蚁
从城市
运动到到城市
的概率，
表示第
分别代表信息浓度
与启发因子
。
信息素的更新。蚁群算法的核心之一在于信息素的更新策略，有部分改进的蚁群算法就是针对其信息素更新策略做了优化。这里，当
该公式表示信息素的挥发机制，其中
为N个城市的链接集合，
表示信息素的挥发率。其中
的定义为：
即每只蚂蚁在城市i和j之间残留的信息素之和。
ACS - Python实现
- 首先实现一个函数用于生成TSP问题所需的城市集合。
import numpy as np
import matplotlib.pyplot as plt
def creat_city(num, scale):
"""
input:
num: 城市数量
scale: 城市坐标范围x,y in (0, scale)
return:
V：城市的坐标集合
E：城市的邻接矩阵
"""
x = np.random.choice(scale, num)
y = np.random.choice(scale, num)
V = np.stack((x,y), axis=1)
inner = -2 * V.dot(V.T)
xx = np.sum(V**2, axis=1, keepdims=True)
E = xx + inner + xx.T
E = E**0.5
index = [i for i in range(num)]
#为了防止蚂蚁出现自旋，邻接矩阵上的对角线取值尽量大一点。
E[index,index] = 9999999
return V,E
我们使用下面的代码在400*400的范围内生成20个城市，其生成的的效果如图2所示：
V, E = creat_city(20, 400)
plt.scatter(V[:,0], V[:,1], alpha=0.6, c = "r") # 绘制散点图，透明度为0.6（这样颜色浅一点，比较好看）
plt.show()
- 算法所需的其他必备函数
- 依概率采样函数
import heapq
import random
def a_res(samples, m):
"""
:samples: [(item, weight), ...]
:k: number of selected items
:returns: [(item, weight), ...]
"""
heap = [] # [(new_weight, item), ...]
for sample in samples:
wi = sample[1]
if wi==0:
continue
ui = random.uniform(0, 1)
ki = ui ** (1/wi)
if len(heap) < m:
heapq.heappush(heap, (ki, sample))
elif ki > heap[0][0]:
heapq.heappush(heap, (ki, sample))
if len(heap) > m:
heapq.heappop(heap)
return [item[1] for item in heap]
- 由信息素浓度获得蚂蚁去往下一个城市的概率。
def possibility(eta, gamma, other_city, cur_city):
"""
返回候选城市集合中，从start到各候选城市的概率，只返回有路径的
"""
alpha = 1
beta = 5
start_city = cur_city[-1]
t_i = gamma[start_city]
n_i = eta[start_city]
temp = (t_i**alpha * n_i**beta)
temp[cur_city] = 0
add = temp.sum()
p_ij = temp/add
return p_ij
- 其他函数
def rotate(l, n):
'''
旋转列表。
'''
return l[n:] + l[:n]
def get_path_dis(root, E):
"""
获取该路径距离。
"""
dis = E[root[:-1], root[1:]].sum()
return dis + E[root[0],root[-1]]
- 蚁群算法实现
def ACS(V, E, M, num):
"""
Ant system
V : 点集
E: 邻接矩阵，点之间的连接性，
M: 蚂蚁数量
num：迭代次数
"""
#相关参数
global_best_path=None #当前最优路径
global_best_dis = 99999999
cur_city = None
other_city = [i for i in range(len(V))]
lo = 0.5 #信息素挥发率
#信息素启发值
eta = 1/E
eta[np.isinf(eta)] = 0
#信息素浓度
E_mean = E[E>0].mean()
gamma = np.full(E.shape, 1/len(V))
V_index = [i for i in range(len(V))]
for i in range(num):
epoch_gamma = np.zeros_like(gamma) #保存每一轮的各路径信息素累积量
local_best_path=None #每一次迭代当前最优路径
local_best_dis = 99999999
for j in range(M):
cur_city = [j%len(V)]
other_city = [i for i in range(len(V))]
other_city.remove(cur_city[-1])
while(other_city):
p_ij = possibility(eta, gamma, other_city, cur_city)
next_city = int(a_res(np.stack((V_index,p_ij),axis=1), 1)[0][0])
epoch_gamma[cur_city[-1],next_city] += gamma[cur_city[-1],next_city]
cur_city.append(next_city)
other_city.remove(next_city)
epoch_dis = get_path_dis(cur_city, E)
if epoch_dis < local_best_dis:
local_best_dis = epoch_dis
local_best_path = cur_city
if local_best_dis < global_best_dis:
global_best_dis = local_best_dis
global_best_path = local_best_path
gamma = (1 - lo) * gamma + epoch_gamma
print("The shortest distance is {}m and the best path is: ".format(global_best_dis), end="")
best_path = rotate(global_best_path, global_best_path.index(0))
for index in best_path:
print(" city_" + str(index) + " ->", end="")
print("city_0\n")
return best_path
- 算法计算结果
root = ACS(V, E, 20, 50)
path = V[root]
path = np.append(path, [path[0]], axis=0)
plt.plot(path[:,0], path[:,1], marker="o", mfc="r")
plt.show()
MMAS(最大-最小蚁群系统)
- MMAS算法简介
我们从图3中可以看到，ACS算法对于20个城市的TSP问题已经能够得到相对较优的结果了。但是ACS仍然有一些缺点，比如收敛速度比较慢，获取容易陷入局部最小值等等。针对这些缺陷有学者又提出了最大-最小蚁群系统。该改进算法与基本的蚁群算法有以下几点不同
-
，这也正是该算法名字的由来。通常该最大 最小值有我们自己设定。
- 算法开始将城市之间的信息素浓度都初始化为
。
- 每次迭代信息素更新时只针对最优路径进行更新，而不考虑其他路径。其中最优路径可为局部最优路径(本次迭代最优)或全局最优路径(所有迭代最优)。具体更新公式如下：
其中，
指本次迭代最优路径，
为本次迭代最优路径中从城市
,其中
为一个自己设置的常数，
是本次迭代最优路径的长度。
- MMAS算法python实现
def MMAS(V, E, M, num, islocal=True):
"""
最大最小蚁群算法
V : 点集
E: 邻接矩阵，点之间的连接性，
M: 蚂蚁数量
num：迭代次数
"""
#相关参数
global_best_path=None #当前最优路径
global_best_dis = 99999999
cur_city = None
other_city = [i for i in range(len(V))]
lo = 0.8 #信息素挥发率
e = num #精英路径权重
tao_min = 0.1 / num
tao_max = 1
#信息素启发值
eta = 1/E
eta[np.isinf(eta)] = 0
#信息素浓度
E_mean = E[E>0].mean()
gamma = np.full(E.shape,tao_max)
V_index = [i for i in range(len(V))]
for i in range(num):
epoch_gamma = np.zeros_like(gamma) #保存每一轮的各路径信息素累积量
local_best_path=None #每一次迭代当前最优路径
local_best_dis = 99999999
for j in range(M):
cur_city = [j%len(V)]
other_city = [i for i in range(len(V))]
other_city.remove(cur_city[-1])
while(other_city):
p_ij = possibility(eta, gamma, other_city, cur_city)
next_city = int(a_res(np.stack((V_index,p_ij),axis=1), 1)[0][0])
if next_city not in other_city:
next_city = int(a_res(np.stack((V_index,p_ij),axis=1), 1)[0][0])
epoch_gamma[cur_city[-1],next_city] += gamma[cur_city[-1],next_city]
cur_city.append(next_city)
other_city.remove(next_city)
epoch_dis = get_path_dis(cur_city, E)
if epoch_dis < local_best_dis:
local_best_dis = epoch_dis
local_best_path = cur_city
if local_best_dis < global_best_dis:
global_best_dis = local_best_dis
global_best_path = local_best_path
#信息素更新
gamma = (1 - lo) * gamma
if islocal:
for i,j in np.stack((local_best_path[1:] + local_best_path[:1], local_best_path), axis=1):
gamma[i,j] += e / local_best_dis
else:
for i,j in np.stack((global_best_path[1:] + global_best_path[:1], global_best_path), axis=1):
gamma[i,j] += e / global_best_dis
gamma[gamma>tao_max] = tao_max
gamma[gamma<tao_min] = tao_min
print("The shortest distance is {}m and the best path is: ".format(global_best_dis), end="")
best_path = rotate(global_best_path, global_best_path.index(0))
for index in best_path:
print(" city_" + str(index) + " ->", end="")
print("city_0.\n")
return best_path
-
MMAS算法运行结果
从图4可以看到，MMAS对于TSP问题能得到很好的解，并且收敛速度也比较快。因此一般对于TSP类问题使用MMAS来求解是比较合适的。
图4. MMAS结果
蚁群算法的其他优化版本
这里我们限于篇幅仅仅简单介绍了ACS和MMAS，其实对于蚁群算法还有精英系统(EAS)、排序蚁群(ASrank)、连续正交蚁群(COAC)等等。此外，我们这里仅仅是用TSP算法来举例，实际上，蚁群算法可以被应用到许多问题上，比如调度问题、设置问题、分配问题、车辆路径问题等等。读者朋友如果有兴趣可以去扩展这些知识，相信会很有收获的！
4.参考资料
https://zh.wikipedia.org/wiki/%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95
https://www.voidking.com/dev-aco/
https://zhuanlan.zhihu.com/p/45985636
https://blog.csdn.net/zuochao_2013/article/details/71872950
https://blog.csdn.net/acsunqi/article/details/76060669
https://cloud.tencent.com/developer/article/1369213
