蚁群算法–以解决TSP问题为例
先插条题外话，好久没有更新这个系列的博客了。最近应老大的要求，给北大数院出了一道数模题目。中间提示了他们可以用这些算法。最后看论文的时候，看到他们用了这个算法。这才想起来，我好像还没补充这个“蚁群算法”的博客。这里因此补充一下。
关联文章
- 模拟退火算法解决TSP（python实现 110+行代码）【gif生成】
- 模拟退火算法理论+Python解决函数极值+C++实现解决TSP问题
- 遗传算法解决TSP问题 Python实现【160行以内代码】
蚁群算法
算法本身想法是很trival的。
模拟蚂蚁运动规律，在行走的过程中，在轨迹上会留下信息素。后来的蚂蚁会有更大的概率走信息素浓度更高的路径。
映射到TSP问题上，具体分析。
- n只蚂蚁在图上爬。在第i个节点上时候，转移到其他的节点的概率是
信息素浓度 ** alpha * (DistanceAdjusted)。其中的DistanceAdjusted是基于局部的选择，而信息素浓度则是全局的选择。 - 在所有蚂蚁都爬完之后，用
Q/路径总长度表示路径上的平均信息浓度。显然可以，得到一个信息浓度变化矩阵。 - 在考虑到历史信息浓度的挥发，补充一个decay的系数，用于避免陷入局部最优解。
注意： 为了避免陷入到局部最优解，其实应该控制挥发率跟蚁群规模，两者都比较高时，可以一定程度上避免这个问题。
效果
代码
import numpy as np
import random
import matplotlib.pyplot as plt
import os
import shutil
import imageio
def create_data(N, xu=25, yu=25, xd=-25, yd=-25):
fx = lambda: random.random() * (xu - xd) + xd
fy = lambda: random.random() * (yu - yd) + yd
calDistance = lambda x, y: np.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2)
points = [(0, 0)] * N
for i in range(N):
points[i] = (fx(), fy())
Mat = np.zeros((N, N))
for i in range(N):
for j in range(i + 1, N):
dv = calDistance(points[i], points[j])
Mat[i][j], Mat[j][i] = dv, dv
return points, Mat
def calpathValue(path):
global Mat
temp = Mat[0][path[0]]
for i in range(len(path) - 1):
temp += Mat[path[i]][path[i + 1]]
temp += Mat[path[-1]][0]
return temp
def generatePath():
global pheromone_value, N
node = 0
path = []
for _ in range(N - 1):
pv_tmp = pheromone_value[node]
pv_p = pv_tmp / pv_tmp.sum()
seq = [i for i in range(1, N) if i not in path]
pv_p = [pv_p[i] for i in seq]
node = random.choices(seq, weights=pv_p)[0]
path.append(node)
return path
def update_pheromone():
global paths, paths_value, pheromone_mat, Q, volatilize_rate
delta_pheromone = np.zeros(pheromone_mat.shape)
for path, path_value in zip(paths, paths_value):
node = 0
# Ant Cycle Algorithm
pv = Q / path_value
for p_n in path:
delta_pheromone[node][p_n] += pv
node = p_n
pheromone_mat = pheromone_mat * volatilize_rate + delta_pheromone
def draw(path, pv):
global points, N, TIMESIT, PNGFILE, PNGLIST
plt.cla()
plt.title('cross=%.4f' % pv)
xs = [p[0] for p in points]
ys = [p[1] for p in points]
plt.scatter(xs, ys, color='b')
xs = np.array(xs)
ys = np.array(ys)
plt.plot(xs[[0, path[0]]], ys[[0, path[0]]], color='r')
for i in range(N - 2):
plt.plot(xs[[path[i], path[i + 1]]], ys[[path[i], path[i + 1]]], color='r')
plt.plot(xs[[path[N - 2], 0]], ys[[path[N - 2], 0]], color='r')
plt.scatter(xs[0], ys[0], color='k', linewidth=10)
for i, p in enumerate(points):
plt.text(*p, '%d' % i)
plt.savefig('%s/%d.png' % (PNGFILE, TIMESIT))
PNGLIST.append('%s/%d.png' % (PNGFILE, TIMESIT))
TIMESIT += 1
if __name__ == '__main__':
TIMESIT = 0
PNGFILE = './png/'
PNGLIST = []
if not os.path.exists(PNGFILE):
os.mkdir(PNGFILE)
else:
shutil.rmtree(PNGFILE)
os.mkdir(PNGFILE)
N = 30
points, Mat = create_data(N)
alpha = 2
beta = 0.5
Q = 1 # information intensity
volatilize_rate = 0.5
AntNum = 200
# Time = 10000
NOTMORETHANstayINGV = 500
stayINGV = 0
DistanceAdjust = 1. / Mat
DistanceAdjust[DistanceAdjust == np.inf] = 0
pheromone_mat = DistanceAdjust
DistanceAdjust = DistanceAdjust ** beta
global_value, global_path = 0, None
'''
val = (pheromone ** alpha) * ( 1/distance ** beta)
Transport Probability: p = val_i / sum(val_i)
TSP Problem: assume The Path will start and end with node 0.
'''
while True:
pheromone_value = pheromone_mat ** alpha * DistanceAdjust
paths = [generatePath() for _ in range(AntNum)]
paths_value = [calpathValue(path) for path in paths]
if (global_path is None) or (min(paths_value) < global_value):
global_path = paths[np.argmin(paths_value)]
global_value = min(paths_value)
draw(global_path, global_value)
stayINGV = 0
else:
stayINGV += 1
update_pheromone()
if stayINGV >= NOTMORETHANstayINGV:
break
generated_images = []
for png_path in PNGLIST:
generated_images.append(imageio.imread(png_path))
shutil.rmtree(PNGFILE) # 可删掉
generated_images = generated_images + [generated_images[-1]] * 5
imageio.mimsave('TSP-ACO.gif', generated_images, 'GIF', duration=0.5)
