### 蚁群算法的 Python 实现案例 以下是一个基于蚁群算法的简单实现案例，用于解决旅行商问题（TSP）。该实现参考了蚁群算法的核心思想[^1]，即通过模拟蚂蚁寻找食物时的信息素更新机制来优化路径。 ```python import numpy as np # 参数设置 class AntColony: def __init__(self, distances, n_ants, n_best, n_iterations, decay, alpha=1, beta=1): """ 初始化蚁群算法参数 :param distances: 城市间的距离矩阵 :param n_ants: 蚂蚁数量 :param n_best: 每次迭代中最佳蚂蚁的数量 :param n_iterations: 迭代次数 :param decay: 信息素衰减系数 :param alpha: 信息素重要程度因子 :param beta: 启发式因子 """ self.distances = np.array(distances) self.pheromone = np.ones(self.distances.shape) / len(distances) self.all_inds = range(len(distances)) self.n_ants = n_ants self.n_best = n_best self.n_iterations = n_iterations self.decay = decay self.alpha = alpha self.beta = beta def run(self): shortest_path = None all_time_shortest_path = ("placeholder", np.inf) for i in range(self.n_iterations): all_paths = self.gen_all_paths() self.spread_pheronome(all_paths, self.n_best) current_shortest_path = min(all_paths, key=lambda x: x[1]) if current_shortest_path[1] < all_time_shortest_path[1]: all_time_shortest_path = current_shortest_path self.pheromone *= self.decay return all_time_shortest_path def spread_pheronome(self, all_paths, n_best): sorted_paths = sorted(all_paths, key=lambda x: x[1]) for path, dist in sorted_paths[:n_best]: for move in path: self.pheromone[move] += 1.0 / self.distances[move] def gen_path_dist(self, path): total_dist = 0 for ele in path: total_dist += self.distances[ele] return total_dist def gen_all_paths(self): all_paths = [] for i in range(self.n_ants): path = self.gen_path(0) all_paths.append((path, self.gen_path_dist(path))) return all_paths def gen_path(self, start): path = [] visited = set() visited.add(start) prev = start for i in range(len(self.distances) - 1): move = self.pick_move(self.pheromone[prev], self.distances[prev], visited) path.append((prev, move)) prev = move visited.add(move) path.append((prev, start)) # 回到起点 return path def pick_move(self, pheromone, dist, visited): pheromone = np.copy(pheromone) pheromone[list(visited)] = 0 row = pheromone ** self.alpha * ((1.0 / dist) ** self.beta) norm_row = row / row.sum() move = np_choice(self.all_inds, 1, p=norm_row)[0] return move # 示例：城市间的距离矩阵 distances = [ [0, 2, 9, 10], [1, 0, 6, 4], [15, 7, 0, 8], [6, 3, 12, 0] ] ant_colony = AntColony(distances=distances, n_ants=20, n_best=5, n_iterations=100, decay=0.95, alpha=1, beta=1) shortest_path = ant_colony.run() print("最短路径:", shortest_path) ``` 上述代码实现了蚁群算法的基本框架，并通过一个简单的距离矩阵来测试算法性能。程序中的关键点包括信息素的初始化、路径生成规则以及信息素的更新机制[^2]。 ### 关键点解析 - **信息素更新**：每次迭代后，根据当前最优路径对信息素进行更新，确保路径的选择逐渐向最优解靠拢。 - **启发式因子**：通过结合路径长度的倒数作为启发式因子，增强了算法的收敛能力[^3]。 - **随机性与确定性结合**：在路径选择过程中引入随机性，避免陷入局部最优解。