Python蚁群算法（Ant Colony Algorithm）实现
蚁群算法（Ant Colony Algorithm）是一种基于模拟蚂蚁觅食行为的启发式搜索算法，适用于优化问题，特别是组合优化问题。本文将详细介绍Python实现蚁群算法的过程和代码演示。
- 算法实现流程
蚁群算法的实现流程如下：
- 初始化蚁群：设置蚂蚁的数量、初始位置和状态等。
- 初始化信息素：设置各边的初始信息素浓度。
- 迭代搜索：每只蚂蚁根据信息素浓度选择路径，在路径上留下信息素，更新信息素浓度，直到所有蚂蚁完成搜索。
- 更新信息素：根据路径上的信息素浓度和参数更新信息素浓度。
-
结束条件判断：达到迭代次数、达到最优解等结束条件。
-
Python代码实现
接下来，我们将用Python实现一个简单的蚁群算法，用于求解旅行商问题（TSP）。
旅行商问题是指给定n个城市和它们之间的距离，求解一条遍历所有城市且路径最短的路线。
（1）初始化蚁群
我们首先需要定义一个Ant类，表示蚂蚁。在该类中，我们定义了蚂蚁的属性（编号、位置、访问状态）以及蚂蚁在移动时的选择策略。其中，选择策略是根据信息素浓度和距离进行计算，玄学之处很多，可以自行尝试不同的策略。
import random class Ant(object): def __init__(self, id, city_num, alpha=1, beta=2, init_city=None): self.id = id # 蚂蚁编号 self.alpha = alpha # 信息素浓度的权重 self.beta = beta # 距离的权重 self.city_num = city_num # 城市数量 if init_city is None: self.cur_city = random.randint(0, city_num -1) # 当前所在城市 else: self.cur_city = init_city self.visit = [False] * city_num # 已访问城市的状态 self.visit[self.cur_city] = True # 将当前城市状态置为已访问 self.path = [self.cur_city] # 蚂蚁走过的路径 def move(self, pheromone, dist): # 计算选择下一个城市的概率 visit_prob = [0] * self.city_num cur_city = self.cur_city sum_prob = 0 for next_city in range(self.city_num): if not self.visit[next_city]: prob = pow(pheromone[cur_city][next_city], self.alpha) * pow(1.0 / dist[cur_city][next_city], self.beta) visit_prob[next_city] = prob sum_prob += prob # 概率归一化 if sum_prob > 0: visit_prob = [p/sum_prob for p in visit_prob] # 选择下一个城市 next_city = self._choose_next_city(visit_prob) # 走过的路径、访问状态和当前城市更新 self.path.append(next_city) self.visit[next_city] = True self.cur_city = next_city # 轮盘赌选择 def _choose_next_city(self, prob): p = random.random() city = 0 cum_prob = prob[city] while p > cum_prob: city += 1 cum_prob += prob[city] return city
在初始化过程中，我们需要创建一个AntColony类，表示整个蚁群的状态。在该类中，我们定义了各城市之间的距离信息dist，以及各边的信息素浓度pheromone。此外，我们还定义了一些参数（迭代次数、蚂蚁数量、信息素衰减速率等）和状态（当前的最优路径和长度）。
以下是AntColony的初始化方法：
class AntColony(object): def __init__(self, city_num, ant_num=50, max_iter=200, alpha=1, beta=2, decay_rate=0.5, Q=100): self.city_num =city_num # 城市数量 self.ant_num = ant_num # 蚂蚁数量 self.max_iter = max_iter # 最大迭代次数 self.alpha = alpha # 信息素浓度的权重 self.beta = beta # 距离的权重 self.decay_rate = decay_rate # 信息素的衰减速率 self.Q = Q # 添加信息素的常数 self.cur_iter = 0 # 当前迭代次数 self.best_len = float('inf') # 当前最优路径长度 self.best_path = None # 当前最优路径 self.dist = [] # 城市之间的距离，初始化后不再修改 self.pheromone = [] # 各边的信息素浓度 self.ants = [] # 蚂蚁列表 self._init_dist() # 初始化距离 self._init_pheromone() # 初始化信息素 # 计算距离，此处用的是欧式距离，可以根据实际需求做修改 def _calc_dist(self, x1, y1, x2, y2): dist = pow(x1 -x2, 2) + pow(y1 - y2, 2) return pow(dist, 0.5) # 初始化距离 def _init_dist(self): self.dist = [ [ 0.0 for i in range(self.city_num)] for j in range(self.city_num)] for i in range(self.city_num): for j in range(i+1, self.city_num): dist = self._calc_dist(*cities[i], *cities[j]) self.dist[i][j] = dist self.dist[j][i] = dist # 初始化信息素 def _init_pheromone(self): self.pheromone = [ [ 1.0 for i in range(self.city_num)] for j in range(self.city_num)] # 各蚂蚁进行一次完整的路径搜索 def search(self): self._init_ants() while True: self.cur_iter += 1 for ant in self.ants: # 搜索路径 for i in range(self.city_num - 1): ant.move(self.pheromone, self.dist) # 计算路径长度 path_len = sum([self.dist[ant.path[i]][ant.path[i+1]] for i in range(self.city_num - 1)]) # 回到起点闭合环路 path_len += self.dist[ant.path[-1]][ant.path[0]] if path_len <self.best_len: self.best_len = path_len self.best_path = ant.path # 更新信息素 self._update_pheromone(ant.path, path_len) # 判断是否达到结束条件 if self.cur_iter >= self.max_iter: break # 初始化蚂蚁，随机分配起点城市 def _init_ants(self): self.ants = [Ant(i, self.city_num, self.alpha, self.beta) for i in range(self.ant_num)] # 更新信息素 def _update_pheromone(self, path, path_len): # 本次搜索留下的信息素 delta_pheromone = [[0 for i in range(self.city_num)] for j in range(self.city_num)] for i in range(self.city_num -1): cur_city, next_city = path[i], path[i+1] delta_pheromone[cur_city][next_city] = self.Q / path_len delta_pheromone[next_city][cur_city] = delta_pheromone[cur_city][next_city] cur_city, next_city = path[-1], path[0] delta_pheromone[cur_city][next_city] = self.Q / path_len delta_pheromone[next_city][cur_city] = delta_pheromone[cur_city][next_city] # 信息素挥发和更新 for i in range(self.city_num): for j in range(i+1, self.city_num): self.pheromone[i][j] = (1 -self.decay_rate) * self.pheromone[i][j] + delta_pheromone[i][j] self.pheromone[j][i] = self.pheromone[i][j]
（2）测试
接下来，我们调用AntColony的search方法可以得到最优路径，输出路径长度和路径。
cities = [(1, 1), (1, 5), (2, 3), (3, 6), (4, 7)] # 城市坐标
ant_colony = AntColony(city_num=len(cities))
ant_colony.search()
print('最短路径长度：', ant_colony.best_len)
print('最短路径：', [cities[i] for i in ant_colony.best_path])
输出结果为：
最短路径长度： 11.650281539872885 最短路径： [(1, 1), (2, 3), (1, 5), (4, 7), (3, 6)]
以上就是Python实现蚁群算法的全部代码，完整代码如下：
```
import random
class Ant(object):
def init(self, id, city_num, alpha=1, beta=2, init_city=None):
self.id = id # 蚂蚁编号
self.alpha = alpha # 信息素浓度的权重
self.beta = beta # 距离的权重
self.city_num = city_num # 城市数量
if init_city is None:
self.cur_city = random.randint(0, city_num -1) # 当前所在城市
else:
self.cur_city = init_city
self.visit = [False] * city_num # 已访问城市的状态
self.visit[self.cur_city] = True # 将当前城市状态置为已访问
self.path = [self.cur_city] # 蚂蚁走过的路径
def move(self, pheromone, dist):
# 计算选择下一个城市的概率
visit_prob = [0] * self.city_num
cur_city = self.cur_city
sum_prob = 0
for next_city in range(self.city_num):
if not self.visit[next_city]:
prob = pow(pheromone[cur_city][next_city], self.alpha) * pow(1.0 / dist[cur_city][next_city], self.beta)
visit_prob[next_city] = prob
sum_prob += prob
# 概率归一化
if sum_prob > 0:
visit_prob = [p/sum_prob for p in visit_prob]
# 选择下一个城市
next_city = self._choose_next_city(visit_prob)
# 走过的路径、访问状态和当前城市更新
self.path.append(next_city)
self.visit[next_city] = True
self.cur_city = next_city
# 轮盘赌选择
def _choose_next_city(self, prob):
p = random.random()
city = 0
cum_prob = prob[city]
while p > cum_prob:
city += 1
cum_prob += prob[city]
return city
class AntColony(object):
def init(self, city_num, ant_num=50, max_iter=200, alpha=1, beta=2, decay_rate=0.5, Q=100):
self.city_num =city_num # 城市数量
self.ant_num = ant_num # 蚂蚁数量
self.max_iter = max_iter # 最大迭代次数
self.alpha = alpha # 信息素浓度的权重
self.beta = beta # 距离的权重
self.decay_rate = decay_rate # 信息素的衰减速率
self.Q = Q # 添加信息素的常数
self.cur_iter = 0 # 当前迭代次数
self.best_len = float('inf') # 当前最优路径长度
self.best_path = None # 当前最优路径
self.dist = [] # 城市之间的距离，初始化后不再修改
self.pheromone = [] # 各边的信息素浓度
self.ants = [] # 蚂蚁列表
self._init_dist() # 初始化距离
self._init_pheromone() # 初始化信息素
# 计算距离，此处用的是欧式距离，可以根据实际需求做修改
def _calc_dist(self, x1, y1, x2, y2):
dist = pow(x1 -x2, 2) + pow(y1 - y2, 2)
return pow(dist, 0.5)
# 初始化距离
def _init_dist(self):
self.dist = [ [ 0.0 for i in range(self.city_num)] for j in range(self.city_num)]
for i in range(self.city_num):
for j in range(i+1, self.city_num):
dist = self._calc_dist(*cities[i], *cities[j])
self.dist[i][j] = dist
self.dist[j][i] = dist
# 初始化信息素
def _init_pheromone(self):
self.pheromone = [ [ 1.0 for i in range(self.city_num)] for j in range(self.city_num)]
# 各蚂蚁进行一次完整的路径搜索
def search(self):
self._init_ants()
while True:
self.cur_iter += 1
for ant in self.ants:
# 搜索路径
for i in range(self.city_num - 1):
ant.move(self.pheromone, self.dist)
# 计算路径长度
path_len = sum([self.dist[ant.path[i]][ant.path[i+1]] for i in range(self.city_num - 1)])
# 回到起点闭合环路
path_len += self.dist[ant.path[-1]][ant.path[0]]
if path_len <self.best_len:
self.best_len = path_len
self.best_path = ant.path
# 更新信息素
self._update_pheromone(ant.path, path_len)
# 判断是否达到结束条件
if self.cur_iter >= self.max_iter:
break
# 初始化蚂蚁，随机分配起点城市
def _init_ants(self):
self.ants = [Ant(i, self.city_num, self.alpha, self.beta) for i in range(self.ant_num)]
# 更新信息素
def _update_pheromone(self, path, path_len):
# 本次搜索留下的信息素
delta_pheromone = [[0 for i in range(self.city_num)] for j in range(self.city_num)]
for i in range(self.city_num -1):
cur_city, next_city = path[i], path[i+1]
delta_pheromone[cur_city][next_city] = self.Q / path_len
delta_pheromone[next_city][cur_city] = delta_pheromone[cur_city][next_city]
cur_city, next_city = path[-1], path[0]
delta_pheromone[cur_city][next_city] = self.Q / path_len
delta_pheromone[next_city][cur_city] = delta_pheromone[cur_city][next_city]
# 信息素挥发和更新
for i in range(self.city_num):
for j in range(i+1, self.city_num):
self.pheromone[i][j] = (1 -self.decay_rate) * self.pheromone[i][j] + delta_pheromone[i][j]
self.pheromone[j][i] = self.pheromone[i][j]
测试代码
cities = [(1, 1), (1, 5), (2, 3), (3, 6), (4, 7)] # 城市坐标
ant_colony = AntColony(city_num=len(cities))
ant_colony.search()
print('最短路径长度
相关文章