4. TSP问题—蚁群算法实现（python版本）
问题背景：
假设有一位邮递员，他从初始城市（任意一城市）出发，途径所有城市并回到初始城市，利用蚁群算法求得最短路径
数据：
以下是10个城市的坐标数据：
城市
X坐标
Y坐标
A
5
10
B
6
15
C
10
15
D
14
14
E
20
10
F
16
5
G
8
5
H
4
8
I
8
12
J
12
12
准备阶段
首先，将数据存储在Graph中，并且计算各个城市之间的距离distances。
```python
class Graph(object):
def init(self, city_location, pheromone=1.0, alpha=1.0, beta=1.0):self.city_location = city_location self.n = len(city_location) # phernmone矩阵 self.pheromone = [[pheromone for _ in range(self.n)] for _ in range(self.n)] self.alpha = alpha self.beta = beta # 城市之间的距离矩阵 self.distances = self._generate_distances()欧式距离作为图的权重
def _generate_distances(self):
distances = [] # 遍历行 # 遍历列 # 如果行值=列，比如（1,1）(2,2)，这样就是相同的城市，则距离为零 # 如果行值<列,比如（1，2）（2，3）,这样就是不同的城市，距离按欧拉距离公式来算 # 否则，将矩阵的斜对称位置上的距离来补（原因：城市之间距离矩阵是一个distances[i][j] = distances[j][i]特点的矩阵,这样的目的就是减少至少一半的计算） for index_i, _i in enumerate(self.city_location): row = [] for index_j, _j in enumerate(self.city_location): if _i == _j: row.append(0) elif _i < _j: x1, y1 = self.city_location[str(_i)] x2, y2 = self.city_location[str(_j)] row.append(np.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)) else: row.append(distances[index_j][index_i]) distances.append(row) return distances
- 属性
- `city_location`: 城市位置的字典
- `n`: 城市的数量
- `pheromone`: 蚂蚁留下的信息素的矩阵
- `alpha`: 信息素强度的影响因子
- `beta`: 启发式因子的影响因子
- `distances`: 城市之间距离的矩阵
- 方法
- `__init__(self, city_location, pheromone=1.0, alpha=1.0, beta=1.0)`: 对象初始化，计算出城市之间的距离矩阵
- `_generate_distances(self)`: 计算城市之间的距离矩阵
2. 那么，我们将各项能力赋予蚂蚁
```python
class Ant(object):
def __init__(self, graph, start_city):
self.graph = graph
self.start_city = start_city
self.curr_city = start_city
self.visited = [False for _ in range(graph.n)]
self.visited[start_city] = True
self.tour_length = 0
self.tour = [start_city]
def choose_next_city(self):
# calculate probabilities of all cities
probs = []
total_prob = 0
for i in range(self.graph.n):
if not self.visited[i]:
prob = self.graph.pheromone[self.curr_city][i] ** self.graph.alpha * \\
(1.0 / self.graph.distances[self.curr_city][i]) ** self.graph.beta
probs.append((i, prob))
total_prob += prob
# select the next city randomly based on the probabilities
r = random.uniform(0, total_prob)
upto = 0
for i, prob in probs:
if upto + prob >= r:
self.curr_city = i
self.visited[i] = True
self.tour.append(i)
self.tour_length += self.graph.distances[self.tour[-2]][i]
return
upto += prob
def tour_complete(self):
return len(self.tour) == self.graph.n
- 属性：
- `graph`: 图对象，表示要在其上运行蚁群算法的图
- `start_city`: 整数，表示蚂蚁的起始城市
- `curr_city`: 整数，表示蚂蚁当前所在城市
- `visited`: 布尔列表，表示城市是否已被访问
- `tour_length`: 浮点数，表示蚂蚁的路径长度
- `tour`: 整数列表，表示蚂蚁的路径
- 方法：
- `choose_next_city()`: 计算所有城市的概率，根据概率随机选择下一个城市
- `tour_complete()`: 检查蚂蚁是否已经遍历完所有城市
算法构造
通过上面的准备，我们现阶段有了蚂蚁和城市图，那么，我们来规划一下算法的流程。把：
- 初始化蚂蚁和信息素矩阵。
- 蚂蚁根据信息素浓度和启发函数选择下一个节点。
- 蚂蚁在路径上释放信息素。
- 重复步骤2和3，直到所有蚂蚁都找到了解。
- 评估每条路径的适应度，并更新信息素矩阵。
- 重复步骤2到5，直到达到预设的迭代次数或者找到最优解。
这里要考虑选择哪一种更新策略、更新时机：
- 静态规则（这里我选的这个）
- 在每个迭代周期结束后进行更新，即在所有蚂蚁完成当前迭代周期后，根据其路径长度和信息素更新信息素浓度。
def ant_colony(graph, num_ants, num_iterations, evaporation_rate=0.5, q=500):
shortest_tour = None # 最短路径
shortest_tour_length = float('inf') # 最短路径长度
for i in range(num_iterations):
ants = [Ant(graph, random.randint(0, graph.n - 1)) for _ in range(num_ants)] # 随机生成蚂蚁
for ant in ants:
while not ant.tour_complete():
ant.choose_next_city() # 选择下一个城市
ant.tour_length += graph.distances[ant.tour[-1]][ant.start_city] # 计算路径长度
if ant.tour_length < shortest_tour_length:
shortest_tour_length = ant.tour_length
shortest_tour = ant.tour[:]
for i in range(graph.n):
for j in range(graph.n):
if i != j:
graph.pheromone[i][j] *= (1 - evaporation_rate) # 更新挥发信息素
for ant in ants:
if (i, j) in zip(ant.tour, ant.tour[1:]):
graph.pheromone[i][j] += q / ant.tour_length # 更新释放信息素
return shortest_tour, shortest_tour_length
- 注释：
- shortest_tour：最短路径，初始化为 None。
- shortest_tour_length：最短路径长度，初始化为正无穷。
- ants：蚂蚁集合，随机生成。
- ant：蚂蚁，从 graph 中随机选择一个起始城市开始走。
- choose_next_city：选择下一个城市。
- tour_length：路径长度，初始化为 0。
- pheromone：信息素。
- evaporation_rate：信息素挥发率。
- q：信息素强度。
- zip(ant.tour, ant.tour[1:])：将 ant.tour 中的相邻两个元素组成一个二元组 (i, j)，便于后续计算。
- 更新信息素时，需要更新挥发信息素和释放信息素。挥发信息素是指信息素随时间的推移而逐渐消失；释放信息素是指蚂蚁在路径上释放信息素，增强这条路径的吸引力。
- 返回最短路径和最短路径长度。
测试：
将数据和流程带入：
city_location = {
'A': (5, 10),
'B': (6, 15),
'C': (10, 15),
'D': (14, 14),
'E': (20, 10),
'F': (16, 5),
'G': (8, 5),
'H': (4, 8),
'I': (8, 12),
'J': (12, 12)
}
# 创建Graph对象
g = Graph(city_location)
shortest_tour, shortest_tour_length = ant_colony(graph=g, num_ants=500, num_iterations=1000)
print(shortest_tour,shortest_tour_length)
# 城市索引
city_index = {
city: i for i, city in enumerate(sorted(city_location))}
# 城市索引
city_index = {
city: i for i, city in enumerate(sorted(city_location))}
# 城市名称列表
shortest_tour = [list(city_index.keys())[i] for i in shortest_tour]
# 打印结果
print(shortest_tour)
g.plot_path(shortest_tour)
参考代码：
import math
import random
class Graph(object):
def __init__(self, n, pheromone=1.0, alpha=1.0, beta=1.0):
self.n = n
self.pheromone = [[pheromone for _ in range(n)] for _ in range(n)]
self.alpha = alpha
self.beta = beta
self.distances = self._generate_distances()
def _generate_distances(self):
# randomly generate distances between cities
distances = []
for i in range(self.n):
row = []
for j in range(self.n):
if i == j:
row.append(0)
elif j > i:
row.append(random.uniform(1, 10))
else:
row.append(distances[j][i])
distances.append(row)
return distances
class Ant(object):
def __init__(self, graph, start_city):
self.graph = graph
self.start_city = start_city
self.curr_city = start_city
self.visited = [False for _ in range(graph.n)]
self.visited[start_city] = True
self.tour_length = 0
self.tour = [start_city]
def choose_next_city(self):
# calculate probabilities of all cities
probs = []
total_prob = 0
for i in range(self.graph.n):
if not self.visited[i]:
prob = self.graph.pheromone[self.curr_city][i] ** self.graph.alpha * \\
(1.0 / self.graph.distances[self.curr_city][i]) ** self.graph.beta
probs.append((i, prob))
total_prob += prob
# select the next city randomly based on the probabilities
r = random.uniform(0, total_prob)
upto = 0
for i, prob in probs:
if upto + prob >= r:
self.curr_city = i
self.visited[i] = True
self.tour.append(i)
self.tour_length += self.graph.distances[self.tour[-2]][i]
return
upto += prob
def tour_complete(self):
return len(self.tour) == self.graph.n
def ant_colony(graph, num_ants, num_iterations, evaporation_rate=0.5, q=500):
shortest_tour = None
shortest_tour_length = float('inf')
for i in range(num_iterations):
# initialize ants
ants = [Ant(graph, random.randint(0, graph.n-1)) for _ in range(num_ants)]
# have each ant choose a path
for ant in ants:
while not ant.tour_complete():
ant.choose_next_city()
ant.tour_length += graph.distances[ant.tour[-1]][ant.start_city]
# check if this ant found a shorter tour
if ant.tour_length < shortest_tour_length:
shortest_tour_length = ant.tour_length
shortest_tour = ant.tour[:]
# update pheromones
for i in range(graph.n):
for j in range(graph.n):
if i != j:
graph.pheromone[i][j] *= (1 - evaporation_rate)
for ant in ants:
if (i, j) in zip(ant.tour, ant.tour[1:]):
graph.pheromone[i][j] += q / ant.tour_length
return shortest_tour, shortest_tour_length
# generate a 11-city TSP problem and solve it using the ant colony algorithm
graph = Graph(11)
shortest_tour, shortest_tour_length = ant_colony(graph, num_ants=10, num_iterations=50)
# print the shortest tour and its length
print("Shortest tour:", shortest_tour)
print("Shortest tour length:", shortest_tour_length)
