简介面向本硕博教研学习这套Matlab资源以ACO蚁群算法为核心完整覆盖TSP、二维/三维路径规划和栅格地图避障等典型场景能够帮助读者从组合优化到空间规划全面理解蚁群算法的建模思路与实际实现。压缩包为rar格式内部共17个文件以m脚本为主体12个包含各场景的入口Runme文件、子函数与搜索逻辑另有3个txt文件提供障碍物与地图参数1个mat文件保存三维高度图以及1个avi操作录像辅助复现整体仅1.16MB结构清晰易查。目前已有1531人学习下载。资源不仅给出可运行的完整方案还通过分模块代码和配套录屏细致演示了在Matlab 2021a及以上版本中的运行流程便于快速定位路径规划、栅格构建、适应度计算等关键环节同时也能帮助读者熟悉蚁群算法参数设置与调试方法适合用于课程设计、毕业设计或算法对比研究。1. 用ACO蚁群算法同时打通TSP和路径规划关键是信息素建模如果你只把蚁群算法当做一个解决TSP旅行商问题的玩具那会错过它在路径规划领域最实用的那部分价值。TSP要求的是“访问所有城市一次并回到起点”的最短环而二维和三维路径规划要求的是“从起点到终点避开障碍且代价最小”的连续轨迹这两类问题在ACO蚁群算法框架下其实共用同一套底层机制用信息素浓度引导解构造用启发信息修正搜索方向。遇到栅格地图避障规划时很多时候不是算法不收敛而是你把TSP里那套“城市坐标编码”直接搬到了栅格图上导致蚂蚁在障碍区反复试探收敛曲线毛刺严重。这篇内容面向已经会写基础Python、想用ACO同时覆盖TSP、二维/三维路径规划和栅格地图避障仿真的工程师。我会从ACO的数学表达入手给出可直接运行的Python实现并把参数调整、栅格碰撞检测、三维高度代价这些Real工程问题讲透。无论你是做机器人路径规划、无人机航迹规划还是仿真课程设计这套代码都能让你在半小时内跑出第一版结果并且知道为什么某些参数会让蚂蚁“原地打转”。2. ACO蚁群算法的核心机制与TSP基准实现2.1 从蚂蚁找食到信息素更新ACO的四个基本动作ACO蚁群算法模拟的是蚂蚁在觅食路径上释放信息素、后续蚂蚁按信息素浓度选择路径的行为。工程化之后每一轮迭代包含四个基本动作路径构造、信息素局部更新、路径评估、信息素全局更新。路径构造时一只蚂蚁从一个城市出发按照状态转移概率选择下一个未访问城市。这个概率由两部分加权信息素浓度 tau 和启发信息 eta通常取城市间距离的倒数。状态转移公式是P_ij (tau_ij^alpha) * (eta_ij^beta) / sum(...)alpha 和 beta 分别控制信息素和启发信息的权重。alpha 过大蚂蚁会过早集中在某条次优路径上beta 过大算法退化为贪心搜索。信息素更新分局部和全局。局部更新发生在蚂蚁每一步转移后让刚经过的路径信息素小幅挥发避免所有蚂蚁都走同一条边保持探索性。全局更新发生在所有蚂蚁完成路径构造后只给当前最优路径或迭代最优路径增加信息素公式是tau_ij (1 - rho) * tau_ij delta_tau_ijrho 是蒸发系数控制信息素衰减速度。delta_tau_ij 通常是 Q / L_bestQ 为常数L_best 为最优路径长度。这个设计的直觉是短路径获得更多信息素下一轮蚂蚁更倾向选择它但 rho 不能太大否则历史经验丢得太快算法会像随机搜索。2.2 用Python实现ACO-TSP的最小可运行代码我先给出一个纯Python、无第三方依赖的ACO-TSP实现城市坐标随机生成。这段代码也是后续二维路径规划的基础区别只在节点定义和启发信息计算方式。import numpy as np import random class ACO_TSP: def __init__(self, coords, n_ants50, alpha1.0, beta2.0, rho0.5, Q100, max_iter200): self.coords np.array(coords) self.n len(coords) self.dist self._calc_dist_matrix() self.n_ants n_ants self.alpha alpha self.beta beta self.rho rho self.Q Q self.max_iter max_iter self.pheromone np.ones((self.n, self.n)) / self.n def _calc_dist_matrix(self): diff self.coords[:, None, :] - self.coords[None, :, :] return np.sqrt((diff ** 2).sum(axis2)) def _choose_next(self, current, visited): mask np.ones(self.n, dtypebool) mask[visited] False tau self.pheromone[current, mask] ** self.alpha eta (1.0 / (self.dist[current, mask] 1e-10)) ** self.beta prob tau * eta prob / prob.sum() return np.random.choice(np.where(mask)[0], pprob) def _construct_solution(self): start random.randint(0, self.n - 1) route [start] visited {start} while len(route) self.n: nxt self._choose_next(route[-1], visited) route.append(nxt) visited.add(nxt) # 局部信息素更新边走边挥发 for i in range(len(route) - 1): a, b route[i], route[i 1] self.pheromone[a, b] (1 - self.rho) * self.pheromone[a, b] self.rho * 0.01 return route def run(self): best_route None best_len float(inf) for it in range(self.max_iter): routes [self._construct_solution() for _ in range(self.n_ants)] lengths [] for route in routes: l sum(self.dist[route[i], route[i 1]] for i in range(self.n - 1)) l self.dist[route[-1], route[0]] lengths.append(l) # 全局信息素更新只加强最优路径 idx np.argmin(lengths) if lengths[idx] best_len: best_len lengths[idx] best_route routes[idx] for i in range(self.n - 1): a, b best_route[i], best_route[i 1] self.pheromone[a, b] self.Q / best_len self.pheromone * (self.rho) return best_route, best_len这个实现里有几个关键点。_choose_next中用了np.random.choice按概率抽样而不是直接取最大值保留了随机性避免每一只蚂蚁构造完全相同的解。局部更新放在路径构造过程中对每一条走过的边都做小幅挥发系数固定为 0.01不至于把信息素抹除太多。全局更新放在迭代末尾只对当前已知最优路径加Q / best_len长度越短增量越大。整个run流程结束后返回最优路径和长度。如果你跑这个代码可能会发现前几十轮解的长度下降很快后面趋于平缓。这是ACO的正常现象前期信息素分布比较均匀蚂蚁在探索整个解空间后期最优路径上的信息素越来越强搜索集中在最优路径附近。如果迭代结束后长度还在明显下降说明max_iter不够或者rho太大信息素收益覆盖不了挥发。2.3 参数怎么设alpha、beta、rho、Q的典型取值与影响ACO的参数不像深度学习那样有严格的调参规律但工程上有一组经过大量实验验证的基准区间。下面是TSP场景下我常用的取值范围以及对收敛行为的影响参数典型范围影响alpha0.5 ~ 2.0控制信息素说服力。alpha过小蚂蚁容易忽略历史经验alpha过大容易陷入局部最优beta1.0 ~ 5.0控制启发信息权重。beta适当增大可以让蚂蚁倾向选择距离近的节点加速收敛rho0.3 ~ 0.7蒸发系数。rho大信息素衰减快算法探索性强rho小历史信息保留久收敛快但可能早熟Q10 ~ 1000全局更新增量系数。Q只影响信息素绝对水平和rho配合决定信息素累积速度n_ants20 ~ 60蚂蚁数量。太少则采样不足太多则每轮计算量大收敛速度不一定更快我一般会先用 alpha1.0、beta2.0、rho0.5、Q100 跑一版观察收敛曲线。如果曲线下降斜率一直很大说明迭代数不够如果曲线在较高水平上抖动说明探索过强可以增大 alpha 或减小 rho。如果直接卡在某个次优解尝试增大 beta 并配合略微降低 alpha让蚂蚁更依赖距离启发而不是信息素惯性。栅格地图规划场景下这些参数要重新缩放。因为栅格图上的启发信息不再是“距离的倒数”而是“到目标点欧氏距离的倒数”数值范围比TSP小得多alpha 和 beta 的敏感度也会变化。我会在下一章具体说明。3. 二维路径规划从TSP点序列到连续栅格路径3.1 二维路径规划的ACO建模网格节点与启发信息二维路径规划的目标是在一个平面区域内找一条从起点到终点、不穿越障碍且总长度最短的路径。常见做法是把连续平面离散成栅格地图每个栅格要么是自由格要么是障碍格。ACO在这个场景下的节点不再是城市而是栅格的中心点。和TSP最大的区别在于TSP的蚂蚁要访问所有城市路径规划里的蚂蚁只需要从起点走到终点中间经过哪些栅格是自由的。信息素记录在“从栅格i到相邻栅格j”的方向上而不是全局的任意两点之间。这意味着信息素矩阵的维度是n*n而不再是n*n的完整对称矩阵但存储上依然可以用二维数组只是只更新相邻节点的信息素。启发信息 eta_ij 的标准设计是eta_ij 1 / (dist_to_target_j 1)其中dist_to_target_j是节点 j 到终点的欧氏距离。加 1 是为了避免除零并且压缩数值范围。这个启发信息让蚂蚁在未受信息素干扰时优先朝终点方向移动相当于给蚁群一个“方向感”。如果不加这个启发信息蚂蚁会像无头苍蝇一样在自由区域来回游荡收敛速度极慢。3.2 路径平滑与最短路径约束栅格路径天然是折线蚂蚁每一步只能从当前格移动到八邻域或四邻域中的自由格所以生成的路径会带有大量锯齿。有两个层级的做法第一层是在ACO构造路径时允许八邻域移动这样路径比四邻域平滑但也更靠近障碍。第二层是在ACO结束后做路径平滑处理比如用拉普拉斯平滑或者线段简化去掉冗余的中间节点。工程上我倾向于先做八邻域ACO再用Douglas-Peucker算法简化路径点最后做碰撞检测确认简化后的线段不穿越障碍。如果简化后的线段穿越障碍则保留原始节点不做过度简化。这样既保证了路径长度接近最短又符合避障要求。最短路径约束本质上是通过全局信息素更新实现的。每轮迭代后选择这轮蚂蚁里路径最短的解给它增加信息素增量Q / L_best。这个机制和TSP完全一样只是L_best不再是环的总长而是从起点到终点的累计路径长度。如果某只蚂蚁走了回头路或者绕远路它的路径长度就会变大信息素增量变小下一轮被模仿的概率降低。3.3 二维路径规划的Python实现与结果输出下面给出二维栅格地图ACO路径规划的Python实现。地图用 0 表示自由1 表示障碍。蚂蚁从起点出发每一步在当前位置的八邻域中选择可通行的下一步。import numpy as np import heapq def heuristic(a, b): return np.hypot(a[0]-b[0], a[1]-b[1]) class ACO_Grid2D: def __init__(self, grid, start, goal, n_ants40, alpha1.0, beta3.0, rho0.3, Q100, max_iter100): self.grid np.array(grid) self.h, self.w self.grid.shape self.start start self.goal goal self.n_ants n_ants self.alpha alpha self.beta beta self.rho rho self.Q Q self.max_iter max_iter # 信息素矩阵只对自由格之间存在连接时有用 self.pheromone np.ones((self.h, self.w)) self.dir8 [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] def _valid(self, x, y): return 0 x self.h and 0 y self.w and self.grid[x][y] 0 def _neighbors(self, x, y): nbs [] for dx, dy in self.dir8: nx, ny x dx, y dy if self._valid(nx, ny): # 对角移动时避免穿墙角 if dx ! 0 and dy ! 0: if not self._valid(xdx, y) or not self._valid(x, ydy): continue nbs.append((nx, ny)) return nbs def _construct_path(self): x, y self.start path [(x, y)] while (x, y) ! self.goal: nbs self._neighbors(x, y) if not nbs: return None # 死路 # 计算每个邻居的转移概率 tau np.array([self.pheromone[nx][ny] ** self.alpha for nx, ny in nbs]) eta np.array([1.0 / (heuristic((nx, ny), self.goal) 1.0) ** self.beta for nx, ny in nbs]) prob tau * eta prob / prob.sum() nxt nbs[np.random.choice(len(nbs), pprob)] # 局部信息素更新 self.pheromone[nxt[0]][nxt[1]] (1 - self.rho) * self.pheromone[nxt[0]][nxt[1]] self.rho * 0.05 path.append(nxt) x, y nxt return path def run(self): best_path None best_len float(inf) for it in range(self.max_iter): paths [] for _ in range(self.n_ants): p self._construct_path() if p is not None: paths.append(p) if not paths: continue lens [] for p in paths: l sum(heuristic(p[i], p[i1]) for i in range(len(p)-1)) lens.append(l) idx np.argmin(lens) if lens[idx] best_len: best_len lens[idx] best_path paths[idx] # 全局只更新最优路径 for p in best_path: self.pheromone[p[0]][p[1]] self.Q / best_len self.pheromone * self.rho return best_path, best_len这段代码和TSP版本有四处关键改动。第一信息素存储从(n,n)矩阵变成了(h,w)矩阵数值挂在栅格上而不是边上。这意味着信息素表示“这个栅格值得走”的程度而不是“这条边值得走”。第二启发信息用当前邻居到终点的距离而不是当前节点到邻居的距离这是方向指引的差异。第三加入了障碍碰撞和对角穿越检测如果从(x,y)走到(xdx, ydy)时水平或垂直方向有一个是障碍就禁止这种对角移动防止路径斜穿墙体。第四局部更新系数调整为 0.05比TSP版本略大因为栅格地图的状态空间小信息素容易饱和。跑完后best_path是一个从起点到终点的栅格坐标序列best_len是累计欧氏距离。如果你用的是 Jupyter Notebook可以用 matplotlib 画栅格图在起点和终点处用不同颜色标记然后用折线把best_path画出来。我一般还会把每轮最优长度记录下来画收敛曲线确认算法没有发散。4. 三维路径规划与栅格地图避障同一套框架扩展4.1 三维空间中的节点编码与高度代价三维路径规划常见于无人机航迹规划、水下机器人路径规划。将二维栅格扩展为三维体素网格每个节点成为(x, y, z)的坐标。和二维相比路径规划除了要考虑水平避障还要考虑高度变化带来的代价比如飞行器爬升和下降的燃油消耗或者水下潜航器的深度限制带来的风险。ACO在三维空间里的节点编码有两种形式。一种是直接在三维体素网格上运行蚂蚁每一步可以从当前体素移动到其26个邻居中的自由体素。信息素矩阵需要一个三维数组(X, Y, Z)启发信息依然是当前邻居到终点的欧氏距离的倒数但额外增加高度代价项eta_ij 1 / (dist_to_target_j 1 height_penalty)height_penalty 可以设计成lambda * abs(z_j - z_i)lambda 是高度敏感系数。这样蚂蚁在选择下一步时如果终点的 z 值和当前邻居的 z 值相差很大启发信息就会被削弱促使蚂蚁尽量选择高度平缓的路径。对于固定翼无人机这个设计非常关键因为剧烈的高度变化意味着额外的能量消耗。另一种做法是先将三维路径投影到水平栅格上用ACO确定水平路径再在每一段之间用高度曲线插值比如用三次样条平滑高度变化。这种做法计算量小但如果地形带垂直障碍如悬崖、建筑物投影法容易丢失高度层的碰撞信息。因此我倾向于直接用三维体素网格做ACO只在最终路径上做平滑后处理。4.2 栅格地图避障规划的安全距离与碰撞检测栅格地图避障规划的核心问题不只是“有没有碰到障碍”而是“路径离障碍有多远”。仿真里如果机器人半径较大路径贴着障碍走会导致实际执行时碰撞。所以在ACO的路径构造阶段就要把安全距离约束加进去。一种常见做法是提前对栅格地图做膨胀处理把每个障碍格向周围扩展若干格扩展半径等于机器人半径/栅格分辨率向上取整。膨胀后的栅格地图中原本贴近障碍的自由格变成障碍格蚂蚁自然无法靠近。这个操作叫做Dilation也叫障碍膨胀。下面的代码展示了如何对二维栅格做简单膨胀三维栅格可以按同样逻辑扩展维度from scipy.ndimage import binary_dilation def inflate_grid(grid, radius): structure np.ones((2*radius1, 2*radius1)) return binary_dilation(grid, structurestructure)grid是布尔数组True表示障碍。膨胀后每个障碍周围半径格内的区域都被标记为障碍。这个预处理让ACO不需要在每一步都做半径碰撞检测显著加快收敛速度。三维场景用binary_dilation时把structure改成(2*r1, 2*r1, 2*r1)的全1三维结构即可。碰撞检测还需要注意一种边界情况当膨胀半径大于两个相邻障碍之间的距离时原本可通行的狭窄通道会被膨胀完全堵死导致路径无法找到。遇到这种情况要么缩小膨胀半径要么在ACO结果生成后单独做线段的逐点碰撞检测只禁止真正会碰到障碍的线段而不是完全依赖膨胀。4.3 代码实现三维ACO路径规划与避障三维ACO的代码结构可以和二维完全对齐只需要把邻居生成从8邻域扩展为26邻域并加入高度代价。下面给出核心的邻居选择和信息素更新部分省略了与二维重复的运行框架。class ACO_Grid3D: def __init__(self, voxel_grid, start, goal, n_ants40, alpha1.0, beta3.0, rho0.4, Q100, max_iter80, lambda_h2.0): self.grid voxel_grid # 0自由, 1障碍 self.start start self.goal goal self.lambda_h lambda_h self.pheromone np.ones_like(voxel_grid, dtypefloat) self.dir26 [(dx,dy,dz) for dx in (-1,0,1) for dy in (-1,0,1) for dz in (-1,0,1)] self.dir26.remove((0,0,0)) def _valid(self, x, y, z): return (0 x self.grid.shape[0] and 0 y self.grid.shape[1] and 0 z self.grid.shape[2] and self.grid[x][y][z] 0) def _neighbors(self, x, y, z): nbs [] for dx, dy, dz in self.dir26: nx, ny, nz xdx, ydy, zdz if not self._valid(nx, ny, nz): continue if abs(dx) abs(dy) abs(dz) 3: # 对角穿墙检测 if not self._valid(xdx, y, z) or not self._valid(x, ydy, z) or not self._valid(x, y, zdz): continue nbs.append((nx, ny, nz)) return nbs def _transition_probs(self, current, nbs): x, y, z current tau np.array([self.pheromone[nx][ny][nz] ** self.alpha for nx, ny, nz in nbs]) dist_term np.array([np.hypot(nx-self.goal[0], ny-self.goal[1], nz-self.goal[2]) 1 for nx, ny, nz in nbs]) height_term np.array([1.0 self.lambda_h * abs(nz - z) for nx, ny, nz in nbs]) eta 1.0 / (dist_term * height_term) ** self.beta prob tau * eta prob / prob.sum() return prob def _construct_path(self): x, y, z self.start path [(x, y, z)] while (x, y, z) ! self.goal: nbs self._neighbors(x, y, z) if not nbs: return None prob self._transition_probs((x, y, z), nbs) nxt nbs[np.random.choice(len(nbs), pprob)] path.append(nxt) x, y, z nxt return path这段代码在三维邻居生成上增加了一个重要的碰撞规则当一步移动同时改变 x、y、z 三个坐标时需要检查三个中间位置是否都自由只有都自由时才允许走这个对角步否则路径可能穿越体素的角点。_transition_probs里把启发信息拆成两项dist_term是到目标的距离height_term是高度变化惩罚。lambda_h越大路径越倾向保持当前高度但也可能导致绕路。实际仿真中lambda 需要配合地形起伏程度调整如果地图本身就是平坦地形lambda 设为 0 与二维没有区别。4.4 仿真可视化建议仿真可视化是验证路径规划结果最直接的手段。二维地图可以用 matplotlib 的imshow显示栅格用plot画路径。三维地图建议用 mayavi 或者 plotly 绘制体素和路径也能用 matplotlib 的scatter或plot_surface输出静态图。做三维体素可视化时不要把每个障碍体素都画成方块渲染量太大通常用ax.voxels显示障碍子集或者只画出障碍表面。如果你要做成可交互的仿真推荐使用 matplotlib 的 animation 模块把每轮迭代的最优路径逐帧绘制这样能看到路径逐渐优化、信息素分布变化的过程。代码操作视频的录制可以用屏幕录制工具直接录制 Jupyter 运行过程。录制前先把地图和路径配色调整好路径颜色用高饱和度的亮色障碍用深色起点和终点用不同尺寸的标记这样视频里信息素浓度变化和路径优化过程会非常直观。5. 仿真结果验证与调参技巧怎么确认你的ACO没跑偏5.1 收敛曲线与解质量评估ACO跑完不是终点判断算法有没有正常工作需要看两个指标收敛曲线形态和最终解与已知最优解的差距。收敛曲线横轴是迭代次数纵轴是每轮最优路径长度。正常的ACO曲线应该呈快速下降然后趋于平缓的指数饱和形态。如果曲线呈锯齿状剧烈波动说明 rho 太大或 alpha 太小蚂蚁每轮都在重新探索如果曲线从头到尾只有微小变化说明信息素初始化太久没有收敛可以降低 Q 或增大 rho。解质量评估有两种方式。对于TSP可以用标准库或启发式算法如 LKH、Google OR-Tools得到参考最优解把ACO结果和最优解对比。对于二维/三维路径规划没有绝对最优解但可以用A* 搜索在同一张栅格地图上跑一遍把A* 的路径长度作为下界参考。ACO路径长度通常比A* 长 5%~15%因为ACO没有利用全局一致性启发是在分布式搜索中逼近最优。如果差距超过 30%说明参数设置有问题。5.2 三种工程调参技巧自适应蒸发系数、精英策略、局部搜索第一种技巧是自适应蒸发系数。固定 rho 的问题在于迭代前期需要强探索rho 应该大一些后期需要加强历史信息利用rho 应该小一些。常见做法是把 rho 设计成随迭代次数线性衰减rho_t rho_max - (rho_max - rho_min) * (it / max_iter)我一般用 rho_max0.6、rho_min0.2。这能显著改善三维路径规划在这种小地图上的收敛稳定性。第二种技巧是精英策略。在全局更新时不只更新本轮最优路径还额外保留一个全局历史最优路径每轮给它额外增加信息素加权。实现上就是维护两个路径列表历史最优路径的信息素增量乘以一个系数e比如 2.0。这个技巧能防止最优解的信息素被后续较差路径稀释。第三种技巧是局部搜索。ACO找到的解通常已经不错但可能在某几个节点间出现微幅绕路。对栅格路径可以在每一步检查如果从当前节点直接跳到两步后的节点不碰撞障碍并且距离更短就删掉中间节点。这个贪婪简化操作对路径长度优化的效果非常明显而且不会破坏避障约束。下面是实现def simplify_path(path, grid): simplified [path[0]] i 0 while i len(path) - 1: for j in range(len(path)-1, i, -1): if is_collision_free(path[i], path[j], grid): simplified.append(path[j]) i j break return simplifiedis_collision_free需要逐点采样两个节点之间的直线检查路径上是否有障碍体素。这种方法可以把原路径的冗余点压缩 20%~40%在TSP结果和后处理中同样适用。5.3 仿真视频录制与复现要点如果你要输出“代码操作视频”录制时最容易出的问题是信息素矩阵和路径坐标没有对齐导致动画里路径穿越障碍。我在录制前会用一套固定的随机种子例如在 Python 里设置np.random.seed(42)保证多次运行结果一致。视频内容建议分成四段第一段展示TSP求解过程城市点标记清楚第二段展示二维栅格地图上的路径搜索把每轮最优路径叠加显示第三段展示三维空间中的路径旋转视角展示避障效果第四段展示障碍膨胀前后的地图对比并标注安全距离效果。录制完视频后还要在视频里同步标注关键参数比如 alpha、rho、地图尺寸、障碍膨胀半径。观感最流畅的方案是把每轮迭代的路径长度打印在右上角把收敛曲线放在右下角小窗口这样可以同时展示算法收敛过程和路径变化。如果仿真中遇到路径卡在死胡同或蚂蚁数突然不下降的情况优先检查膨胀后的地图是否仍然连通再检查_neighbors函数里对角碰撞检测是否误杀了合法路径这两处是ACO路径规划仿真最常见的“跑偏”源头。本文还有配套的精品资源点击获取 ACO蚁群算法实战：从TSP到二维三维路径规划与栅格避障
简介面向本硕博教研学习这套Matlab资源以ACO蚁群算法为核心完整覆盖TSP、二维/三维路径规划和栅格地图避障等典型场景能够帮助读者从组合优化到空间规划全面理解蚁群算法的建模思路与实际实现。压缩包为rar格式内部共17个文件以m脚本为主体12个包含各场景的入口Runme文件、子函数与搜索逻辑另有3个txt文件提供障碍物与地图参数1个mat文件保存三维高度图以及1个avi操作录像辅助复现整体仅1.16MB结构清晰易查。目前已有1531人学习下载。资源不仅给出可运行的完整方案还通过分模块代码和配套录屏细致演示了在Matlab 2021a及以上版本中的运行流程便于快速定位路径规划、栅格构建、适应度计算等关键环节同时也能帮助读者熟悉蚁群算法参数设置与调试方法适合用于课程设计、毕业设计或算法对比研究。1. 用ACO蚁群算法同时打通TSP和路径规划关键是信息素建模如果你只把蚁群算法当做一个解决TSP旅行商问题的玩具那会错过它在路径规划领域最实用的那部分价值。TSP要求的是“访问所有城市一次并回到起点”的最短环而二维和三维路径规划要求的是“从起点到终点避开障碍且代价最小”的连续轨迹这两类问题在ACO蚁群算法框架下其实共用同一套底层机制用信息素浓度引导解构造用启发信息修正搜索方向。遇到栅格地图避障规划时很多时候不是算法不收敛而是你把TSP里那套“城市坐标编码”直接搬到了栅格图上导致蚂蚁在障碍区反复试探收敛曲线毛刺严重。这篇内容面向已经会写基础Python、想用ACO同时覆盖TSP、二维/三维路径规划和栅格地图避障仿真的工程师。我会从ACO的数学表达入手给出可直接运行的Python实现并把参数调整、栅格碰撞检测、三维高度代价这些Real工程问题讲透。无论你是做机器人路径规划、无人机航迹规划还是仿真课程设计这套代码都能让你在半小时内跑出第一版结果并且知道为什么某些参数会让蚂蚁“原地打转”。2. ACO蚁群算法的核心机制与TSP基准实现2.1 从蚂蚁找食到信息素更新ACO的四个基本动作ACO蚁群算法模拟的是蚂蚁在觅食路径上释放信息素、后续蚂蚁按信息素浓度选择路径的行为。工程化之后每一轮迭代包含四个基本动作路径构造、信息素局部更新、路径评估、信息素全局更新。路径构造时一只蚂蚁从一个城市出发按照状态转移概率选择下一个未访问城市。这个概率由两部分加权信息素浓度 tau 和启发信息 eta通常取城市间距离的倒数。状态转移公式是P_ij (tau_ij^alpha) * (eta_ij^beta) / sum(...)alpha 和 beta 分别控制信息素和启发信息的权重。alpha 过大蚂蚁会过早集中在某条次优路径上beta 过大算法退化为贪心搜索。信息素更新分局部和全局。局部更新发生在蚂蚁每一步转移后让刚经过的路径信息素小幅挥发避免所有蚂蚁都走同一条边保持探索性。全局更新发生在所有蚂蚁完成路径构造后只给当前最优路径或迭代最优路径增加信息素公式是tau_ij (1 - rho) * tau_ij delta_tau_ijrho 是蒸发系数控制信息素衰减速度。delta_tau_ij 通常是 Q / L_bestQ 为常数L_best 为最优路径长度。这个设计的直觉是短路径获得更多信息素下一轮蚂蚁更倾向选择它但 rho 不能太大否则历史经验丢得太快算法会像随机搜索。2.2 用Python实现ACO-TSP的最小可运行代码我先给出一个纯Python、无第三方依赖的ACO-TSP实现城市坐标随机生成。这段代码也是后续二维路径规划的基础区别只在节点定义和启发信息计算方式。import numpy as np import random class ACO_TSP: def __init__(self, coords, n_ants50, alpha1.0, beta2.0, rho0.5, Q100, max_iter200): self.coords np.array(coords) self.n len(coords) self.dist self._calc_dist_matrix() self.n_ants n_ants self.alpha alpha self.beta beta self.rho rho self.Q Q self.max_iter max_iter self.pheromone np.ones((self.n, self.n)) / self.n def _calc_dist_matrix(self): diff self.coords[:, None, :] - self.coords[None, :, :] return np.sqrt((diff ** 2).sum(axis2)) def _choose_next(self, current, visited): mask np.ones(self.n, dtypebool) mask[visited] False tau self.pheromone[current, mask] ** self.alpha eta (1.0 / (self.dist[current, mask] 1e-10)) ** self.beta prob tau * eta prob / prob.sum() return np.random.choice(np.where(mask)[0], pprob) def _construct_solution(self): start random.randint(0, self.n - 1) route [start] visited {start} while len(route) self.n: nxt self._choose_next(route[-1], visited) route.append(nxt) visited.add(nxt) # 局部信息素更新边走边挥发 for i in range(len(route) - 1): a, b route[i], route[i 1] self.pheromone[a, b] (1 - self.rho) * self.pheromone[a, b] self.rho * 0.01 return route def run(self): best_route None best_len float(inf) for it in range(self.max_iter): routes [self._construct_solution() for _ in range(self.n_ants)] lengths [] for route in routes: l sum(self.dist[route[i], route[i 1]] for i in range(self.n - 1)) l self.dist[route[-1], route[0]] lengths.append(l) # 全局信息素更新只加强最优路径 idx np.argmin(lengths) if lengths[idx] best_len: best_len lengths[idx] best_route routes[idx] for i in range(self.n - 1): a, b best_route[i], best_route[i 1] self.pheromone[a, b] self.Q / best_len self.pheromone * (self.rho) return best_route, best_len这个实现里有几个关键点。_choose_next中用了np.random.choice按概率抽样而不是直接取最大值保留了随机性避免每一只蚂蚁构造完全相同的解。局部更新放在路径构造过程中对每一条走过的边都做小幅挥发系数固定为 0.01不至于把信息素抹除太多。全局更新放在迭代末尾只对当前已知最优路径加Q / best_len长度越短增量越大。整个run流程结束后返回最优路径和长度。如果你跑这个代码可能会发现前几十轮解的长度下降很快后面趋于平缓。这是ACO的正常现象前期信息素分布比较均匀蚂蚁在探索整个解空间后期最优路径上的信息素越来越强搜索集中在最优路径附近。如果迭代结束后长度还在明显下降说明max_iter不够或者rho太大信息素收益覆盖不了挥发。2.3 参数怎么设alpha、beta、rho、Q的典型取值与影响ACO的参数不像深度学习那样有严格的调参规律但工程上有一组经过大量实验验证的基准区间。下面是TSP场景下我常用的取值范围以及对收敛行为的影响参数典型范围影响alpha0.5 ~ 2.0控制信息素说服力。alpha过小蚂蚁容易忽略历史经验alpha过大容易陷入局部最优beta1.0 ~ 5.0控制启发信息权重。beta适当增大可以让蚂蚁倾向选择距离近的节点加速收敛rho0.3 ~ 0.7蒸发系数。rho大信息素衰减快算法探索性强rho小历史信息保留久收敛快但可能早熟Q10 ~ 1000全局更新增量系数。Q只影响信息素绝对水平和rho配合决定信息素累积速度n_ants20 ~ 60蚂蚁数量。太少则采样不足太多则每轮计算量大收敛速度不一定更快我一般会先用 alpha1.0、beta2.0、rho0.5、Q100 跑一版观察收敛曲线。如果曲线下降斜率一直很大说明迭代数不够如果曲线在较高水平上抖动说明探索过强可以增大 alpha 或减小 rho。如果直接卡在某个次优解尝试增大 beta 并配合略微降低 alpha让蚂蚁更依赖距离启发而不是信息素惯性。栅格地图规划场景下这些参数要重新缩放。因为栅格图上的启发信息不再是“距离的倒数”而是“到目标点欧氏距离的倒数”数值范围比TSP小得多alpha 和 beta 的敏感度也会变化。我会在下一章具体说明。3. 二维路径规划从TSP点序列到连续栅格路径3.1 二维路径规划的ACO建模网格节点与启发信息二维路径规划的目标是在一个平面区域内找一条从起点到终点、不穿越障碍且总长度最短的路径。常见做法是把连续平面离散成栅格地图每个栅格要么是自由格要么是障碍格。ACO在这个场景下的节点不再是城市而是栅格的中心点。和TSP最大的区别在于TSP的蚂蚁要访问所有城市路径规划里的蚂蚁只需要从起点走到终点中间经过哪些栅格是自由的。信息素记录在“从栅格i到相邻栅格j”的方向上而不是全局的任意两点之间。这意味着信息素矩阵的维度是n*n而不再是n*n的完整对称矩阵但存储上依然可以用二维数组只是只更新相邻节点的信息素。启发信息 eta_ij 的标准设计是eta_ij 1 / (dist_to_target_j 1)其中dist_to_target_j是节点 j 到终点的欧氏距离。加 1 是为了避免除零并且压缩数值范围。这个启发信息让蚂蚁在未受信息素干扰时优先朝终点方向移动相当于给蚁群一个“方向感”。如果不加这个启发信息蚂蚁会像无头苍蝇一样在自由区域来回游荡收敛速度极慢。3.2 路径平滑与最短路径约束栅格路径天然是折线蚂蚁每一步只能从当前格移动到八邻域或四邻域中的自由格所以生成的路径会带有大量锯齿。有两个层级的做法第一层是在ACO构造路径时允许八邻域移动这样路径比四邻域平滑但也更靠近障碍。第二层是在ACO结束后做路径平滑处理比如用拉普拉斯平滑或者线段简化去掉冗余的中间节点。工程上我倾向于先做八邻域ACO再用Douglas-Peucker算法简化路径点最后做碰撞检测确认简化后的线段不穿越障碍。如果简化后的线段穿越障碍则保留原始节点不做过度简化。这样既保证了路径长度接近最短又符合避障要求。最短路径约束本质上是通过全局信息素更新实现的。每轮迭代后选择这轮蚂蚁里路径最短的解给它增加信息素增量Q / L_best。这个机制和TSP完全一样只是L_best不再是环的总长而是从起点到终点的累计路径长度。如果某只蚂蚁走了回头路或者绕远路它的路径长度就会变大信息素增量变小下一轮被模仿的概率降低。3.3 二维路径规划的Python实现与结果输出下面给出二维栅格地图ACO路径规划的Python实现。地图用 0 表示自由1 表示障碍。蚂蚁从起点出发每一步在当前位置的八邻域中选择可通行的下一步。import numpy as np import heapq def heuristic(a, b): return np.hypot(a[0]-b[0], a[1]-b[1]) class ACO_Grid2D: def __init__(self, grid, start, goal, n_ants40, alpha1.0, beta3.0, rho0.3, Q100, max_iter100): self.grid np.array(grid) self.h, self.w self.grid.shape self.start start self.goal goal self.n_ants n_ants self.alpha alpha self.beta beta self.rho rho self.Q Q self.max_iter max_iter # 信息素矩阵只对自由格之间存在连接时有用 self.pheromone np.ones((self.h, self.w)) self.dir8 [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] def _valid(self, x, y): return 0 x self.h and 0 y self.w and self.grid[x][y] 0 def _neighbors(self, x, y): nbs [] for dx, dy in self.dir8: nx, ny x dx, y dy if self._valid(nx, ny): # 对角移动时避免穿墙角 if dx ! 0 and dy ! 0: if not self._valid(xdx, y) or not self._valid(x, ydy): continue nbs.append((nx, ny)) return nbs def _construct_path(self): x, y self.start path [(x, y)] while (x, y) ! self.goal: nbs self._neighbors(x, y) if not nbs: return None # 死路 # 计算每个邻居的转移概率 tau np.array([self.pheromone[nx][ny] ** self.alpha for nx, ny in nbs]) eta np.array([1.0 / (heuristic((nx, ny), self.goal) 1.0) ** self.beta for nx, ny in nbs]) prob tau * eta prob / prob.sum() nxt nbs[np.random.choice(len(nbs), pprob)] # 局部信息素更新 self.pheromone[nxt[0]][nxt[1]] (1 - self.rho) * self.pheromone[nxt[0]][nxt[1]] self.rho * 0.05 path.append(nxt) x, y nxt return path def run(self): best_path None best_len float(inf) for it in range(self.max_iter): paths [] for _ in range(self.n_ants): p self._construct_path() if p is not None: paths.append(p) if not paths: continue lens [] for p in paths: l sum(heuristic(p[i], p[i1]) for i in range(len(p)-1)) lens.append(l) idx np.argmin(lens) if lens[idx] best_len: best_len lens[idx] best_path paths[idx] # 全局只更新最优路径 for p in best_path: self.pheromone[p[0]][p[1]] self.Q / best_len self.pheromone * self.rho return best_path, best_len这段代码和TSP版本有四处关键改动。第一信息素存储从(n,n)矩阵变成了(h,w)矩阵数值挂在栅格上而不是边上。这意味着信息素表示“这个栅格值得走”的程度而不是“这条边值得走”。第二启发信息用当前邻居到终点的距离而不是当前节点到邻居的距离这是方向指引的差异。第三加入了障碍碰撞和对角穿越检测如果从(x,y)走到(xdx, ydy)时水平或垂直方向有一个是障碍就禁止这种对角移动防止路径斜穿墙体。第四局部更新系数调整为 0.05比TSP版本略大因为栅格地图的状态空间小信息素容易饱和。跑完后best_path是一个从起点到终点的栅格坐标序列best_len是累计欧氏距离。如果你用的是 Jupyter Notebook可以用 matplotlib 画栅格图在起点和终点处用不同颜色标记然后用折线把best_path画出来。我一般还会把每轮最优长度记录下来画收敛曲线确认算法没有发散。4. 三维路径规划与栅格地图避障同一套框架扩展4.1 三维空间中的节点编码与高度代价三维路径规划常见于无人机航迹规划、水下机器人路径规划。将二维栅格扩展为三维体素网格每个节点成为(x, y, z)的坐标。和二维相比路径规划除了要考虑水平避障还要考虑高度变化带来的代价比如飞行器爬升和下降的燃油消耗或者水下潜航器的深度限制带来的风险。ACO在三维空间里的节点编码有两种形式。一种是直接在三维体素网格上运行蚂蚁每一步可以从当前体素移动到其26个邻居中的自由体素。信息素矩阵需要一个三维数组(X, Y, Z)启发信息依然是当前邻居到终点的欧氏距离的倒数但额外增加高度代价项eta_ij 1 / (dist_to_target_j 1 height_penalty)height_penalty 可以设计成lambda * abs(z_j - z_i)lambda 是高度敏感系数。这样蚂蚁在选择下一步时如果终点的 z 值和当前邻居的 z 值相差很大启发信息就会被削弱促使蚂蚁尽量选择高度平缓的路径。对于固定翼无人机这个设计非常关键因为剧烈的高度变化意味着额外的能量消耗。另一种做法是先将三维路径投影到水平栅格上用ACO确定水平路径再在每一段之间用高度曲线插值比如用三次样条平滑高度变化。这种做法计算量小但如果地形带垂直障碍如悬崖、建筑物投影法容易丢失高度层的碰撞信息。因此我倾向于直接用三维体素网格做ACO只在最终路径上做平滑后处理。4.2 栅格地图避障规划的安全距离与碰撞检测栅格地图避障规划的核心问题不只是“有没有碰到障碍”而是“路径离障碍有多远”。仿真里如果机器人半径较大路径贴着障碍走会导致实际执行时碰撞。所以在ACO的路径构造阶段就要把安全距离约束加进去。一种常见做法是提前对栅格地图做膨胀处理把每个障碍格向周围扩展若干格扩展半径等于机器人半径/栅格分辨率向上取整。膨胀后的栅格地图中原本贴近障碍的自由格变成障碍格蚂蚁自然无法靠近。这个操作叫做Dilation也叫障碍膨胀。下面的代码展示了如何对二维栅格做简单膨胀三维栅格可以按同样逻辑扩展维度from scipy.ndimage import binary_dilation def inflate_grid(grid, radius): structure np.ones((2*radius1, 2*radius1)) return binary_dilation(grid, structurestructure)grid是布尔数组True表示障碍。膨胀后每个障碍周围半径格内的区域都被标记为障碍。这个预处理让ACO不需要在每一步都做半径碰撞检测显著加快收敛速度。三维场景用binary_dilation时把structure改成(2*r1, 2*r1, 2*r1)的全1三维结构即可。碰撞检测还需要注意一种边界情况当膨胀半径大于两个相邻障碍之间的距离时原本可通行的狭窄通道会被膨胀完全堵死导致路径无法找到。遇到这种情况要么缩小膨胀半径要么在ACO结果生成后单独做线段的逐点碰撞检测只禁止真正会碰到障碍的线段而不是完全依赖膨胀。4.3 代码实现三维ACO路径规划与避障三维ACO的代码结构可以和二维完全对齐只需要把邻居生成从8邻域扩展为26邻域并加入高度代价。下面给出核心的邻居选择和信息素更新部分省略了与二维重复的运行框架。class ACO_Grid3D: def __init__(self, voxel_grid, start, goal, n_ants40, alpha1.0, beta3.0, rho0.4, Q100, max_iter80, lambda_h2.0): self.grid voxel_grid # 0自由, 1障碍 self.start start self.goal goal self.lambda_h lambda_h self.pheromone np.ones_like(voxel_grid, dtypefloat) self.dir26 [(dx,dy,dz) for dx in (-1,0,1) for dy in (-1,0,1) for dz in (-1,0,1)] self.dir26.remove((0,0,0)) def _valid(self, x, y, z): return (0 x self.grid.shape[0] and 0 y self.grid.shape[1] and 0 z self.grid.shape[2] and self.grid[x][y][z] 0) def _neighbors(self, x, y, z): nbs [] for dx, dy, dz in self.dir26: nx, ny, nz xdx, ydy, zdz if not self._valid(nx, ny, nz): continue if abs(dx) abs(dy) abs(dz) 3: # 对角穿墙检测 if not self._valid(xdx, y, z) or not self._valid(x, ydy, z) or not self._valid(x, y, zdz): continue nbs.append((nx, ny, nz)) return nbs def _transition_probs(self, current, nbs): x, y, z current tau np.array([self.pheromone[nx][ny][nz] ** self.alpha for nx, ny, nz in nbs]) dist_term np.array([np.hypot(nx-self.goal[0], ny-self.goal[1], nz-self.goal[2]) 1 for nx, ny, nz in nbs]) height_term np.array([1.0 self.lambda_h * abs(nz - z) for nx, ny, nz in nbs]) eta 1.0 / (dist_term * height_term) ** self.beta prob tau * eta prob / prob.sum() return prob def _construct_path(self): x, y, z self.start path [(x, y, z)] while (x, y, z) ! self.goal: nbs self._neighbors(x, y, z) if not nbs: return None prob self._transition_probs((x, y, z), nbs) nxt nbs[np.random.choice(len(nbs), pprob)] path.append(nxt) x, y, z nxt return path这段代码在三维邻居生成上增加了一个重要的碰撞规则当一步移动同时改变 x、y、z 三个坐标时需要检查三个中间位置是否都自由只有都自由时才允许走这个对角步否则路径可能穿越体素的角点。_transition_probs里把启发信息拆成两项dist_term是到目标的距离height_term是高度变化惩罚。lambda_h越大路径越倾向保持当前高度但也可能导致绕路。实际仿真中lambda 需要配合地形起伏程度调整如果地图本身就是平坦地形lambda 设为 0 与二维没有区别。4.4 仿真可视化建议仿真可视化是验证路径规划结果最直接的手段。二维地图可以用 matplotlib 的imshow显示栅格用plot画路径。三维地图建议用 mayavi 或者 plotly 绘制体素和路径也能用 matplotlib 的scatter或plot_surface输出静态图。做三维体素可视化时不要把每个障碍体素都画成方块渲染量太大通常用ax.voxels显示障碍子集或者只画出障碍表面。如果你要做成可交互的仿真推荐使用 matplotlib 的 animation 模块把每轮迭代的最优路径逐帧绘制这样能看到路径逐渐优化、信息素分布变化的过程。代码操作视频的录制可以用屏幕录制工具直接录制 Jupyter 运行过程。录制前先把地图和路径配色调整好路径颜色用高饱和度的亮色障碍用深色起点和终点用不同尺寸的标记这样视频里信息素浓度变化和路径优化过程会非常直观。5. 仿真结果验证与调参技巧怎么确认你的ACO没跑偏5.1 收敛曲线与解质量评估ACO跑完不是终点判断算法有没有正常工作需要看两个指标收敛曲线形态和最终解与已知最优解的差距。收敛曲线横轴是迭代次数纵轴是每轮最优路径长度。正常的ACO曲线应该呈快速下降然后趋于平缓的指数饱和形态。如果曲线呈锯齿状剧烈波动说明 rho 太大或 alpha 太小蚂蚁每轮都在重新探索如果曲线从头到尾只有微小变化说明信息素初始化太久没有收敛可以降低 Q 或增大 rho。解质量评估有两种方式。对于TSP可以用标准库或启发式算法如 LKH、Google OR-Tools得到参考最优解把ACO结果和最优解对比。对于二维/三维路径规划没有绝对最优解但可以用A* 搜索在同一张栅格地图上跑一遍把A* 的路径长度作为下界参考。ACO路径长度通常比A* 长 5%~15%因为ACO没有利用全局一致性启发是在分布式搜索中逼近最优。如果差距超过 30%说明参数设置有问题。5.2 三种工程调参技巧自适应蒸发系数、精英策略、局部搜索第一种技巧是自适应蒸发系数。固定 rho 的问题在于迭代前期需要强探索rho 应该大一些后期需要加强历史信息利用rho 应该小一些。常见做法是把 rho 设计成随迭代次数线性衰减rho_t rho_max - (rho_max - rho_min) * (it / max_iter)我一般用 rho_max0.6、rho_min0.2。这能显著改善三维路径规划在这种小地图上的收敛稳定性。第二种技巧是精英策略。在全局更新时不只更新本轮最优路径还额外保留一个全局历史最优路径每轮给它额外增加信息素加权。实现上就是维护两个路径列表历史最优路径的信息素增量乘以一个系数e比如 2.0。这个技巧能防止最优解的信息素被后续较差路径稀释。第三种技巧是局部搜索。ACO找到的解通常已经不错但可能在某几个节点间出现微幅绕路。对栅格路径可以在每一步检查如果从当前节点直接跳到两步后的节点不碰撞障碍并且距离更短就删掉中间节点。这个贪婪简化操作对路径长度优化的效果非常明显而且不会破坏避障约束。下面是实现def simplify_path(path, grid): simplified [path[0]] i 0 while i len(path) - 1: for j in range(len(path)-1, i, -1): if is_collision_free(path[i], path[j], grid): simplified.append(path[j]) i j break return simplifiedis_collision_free需要逐点采样两个节点之间的直线检查路径上是否有障碍体素。这种方法可以把原路径的冗余点压缩 20%~40%在TSP结果和后处理中同样适用。5.3 仿真视频录制与复现要点如果你要输出“代码操作视频”录制时最容易出的问题是信息素矩阵和路径坐标没有对齐导致动画里路径穿越障碍。我在录制前会用一套固定的随机种子例如在 Python 里设置np.random.seed(42)保证多次运行结果一致。视频内容建议分成四段第一段展示TSP求解过程城市点标记清楚第二段展示二维栅格地图上的路径搜索把每轮最优路径叠加显示第三段展示三维空间中的路径旋转视角展示避障效果第四段展示障碍膨胀前后的地图对比并标注安全距离效果。录制完视频后还要在视频里同步标注关键参数比如 alpha、rho、地图尺寸、障碍膨胀半径。观感最流畅的方案是把每轮迭代的路径长度打印在右上角把收敛曲线放在右下角小窗口这样可以同时展示算法收敛过程和路径变化。如果仿真中遇到路径卡在死胡同或蚂蚁数突然不下降的情况优先检查膨胀后的地图是否仍然连通再检查_neighbors函数里对角碰撞检测是否误杀了合法路径这两处是ACO路径规划仿真最常见的“跑偏”源头。本文还有配套的精品资源点击获取