蚁群算法
蚁群算法（Ant Colony Optimization, ACO）是 1991 年由意大利学者 Colorni、Dorigo 和 Maniezzo 提出、1992 年由 Dorigo 在博士论文中系统完善的智能优化算法。它模拟蚂蚁觅食时依靠"信息素"相互协作找到最短路径的行为，特别擅长求解旅行商问题（TSP）、车辆路径问题（VRP）、路径规划等"序列 + 边代价"类组合优化问题，是数学建模竞赛中处理配送路线、旅游路线、巡检路线类题目的王牌算法之一。本文从原理、适用场景、评价指标、可视化诊断到可运行代码（含穷举验证），完整梳理蚁群算法的竞赛实战用法。
一、算法含义
1.1 通俗理解：蚂蚁为什么总能找到最短路径？
真实世界中，蚂蚁外出觅食时起初是随机游走的。但它们有一个关键习性：一边走一边分泌一种化学物质——信息素（pheromone），作为"路标"。
于是发生了一场无声的集体投票：
- 蚂蚁甲找到了食物，沿原路回巢，一路上留下信息素；
- 蚂蚁乙走到岔路口，闻到两条路上信息素浓度不同，更可能选择浓度高的那条；
- 如果乙走的是一条更短的路，它往返一趟花的时间少，单位时间内留下的信息素就更多；
- 信息素越浓 → 吸引更多蚂蚁 → 信息素更浓……形成正反馈，最终几乎所有蚂蚁都汇聚到最短路径上。
这一现象在 1989 年 Goss 等人的"双桥实验"中被证实：起初蚂蚁在长短两座桥上随机分布，一段时间后却几乎全部挤在了短桥上。同时，信息素还会随时间挥发，防止"过时的错误经验"永远占据主导——这正是蚁群算法中挥发率 的生物学来源。
把 TSP 翻译成蚂蚁的语言：
| 蚂蚁世界 | TSP 世界 |
|---|---|
| 食物点 | 城市（节点） |
| 蚂蚁走过的路 | 一条访问顺序（候选解） |
| 路上的信息素 | 边 被历史经验认可的"集体评价" |
| 蚂蚁"看得到"路的长短 | 启发式信息 |
| 每只蚂蚁一次觅食 | 构造一条完整的汉密尔顿回路（每城恰访问一次） |
蚂蚁选择下一座城市时，同时听取两个"声音"：前辈的经验（信息素 ，来自正反馈的积累）和自己的眼睛（启发式 ，距离近的城市更诱人）。二者的权重由参数 、 控制。
1.2 状态转移概率（蚂蚁如何选路）
蚂蚁 当前在城市 ，它选择下一城市 的概率为：
其中：
- ：边 上的信息素浓度，代表"集体的历史经验"；
- ：启发式信息， 为城市 与 的距离——距离越近， 越大，越有吸引力；
- ：信息素重要度（经验权重）， 越大，蚂蚁越"听前辈的话"；
- ：启发式信息重要度（贪心权重）， 越大，蚂蚁越"急功近利"，越像贪心算法；
- ：蚂蚁 尚未访问的城市集合，保证每座城市恰好访问一次。
分母是分子对所有可选城市的求和，作用是归一化，使 成为合法的概率分布。实际实现时，按 用轮盘赌（roulette wheel）抽样选出下一城市：概率大者被选中的机会大，但任何正概率的城市都有机会——这一步的随机性保证了算法既利用经验、又保持探索。
1.3 信息素更新（经验如何积累）
每一代（一次迭代）中， 只蚂蚁各自构造完一条完整路径后，所有边上的信息素先挥发、再增强：
其中增强量来自本代所有蚂蚁的贡献之和：
- ：挥发率。每代所有边上的信息素先按 打折，模拟自然界信息素蒸发。挥发是"遗忘机制"，防止早期偶然找到的次优路径霸占搜索方向；
- ：信息素强度常数，控制每次增强的幅度；
- ：蚂蚁 本代构造的回路总长度。路径越短， 越大——短路径得到更强的信息素奖励，这是正反馈的数学表达。
迭代多次后，最优路径上的边信息素越来越高，被选中的概率越来越大，蚂蚁集体"锁定"优秀解；而挥发机制又不断稀释旧路径的统治力，给新路径留出机会。挥发与增强的平衡，就是探索（exploration）与利用（exploitation）的平衡，这是蚁群算法的灵魂。
1.4 每只蚂蚁构造一条完整路径
蚁群算法属于构造型算法（constructive algorithm）：每只蚂蚁是"一个解构造器"，从随机起点出发，一步步按状态转移概率选择下一城市，走遍全部 个城市后回到起点，得到一条完整回路（Hamiltonian cycle）。这个过程可以用一句话概括：
一只蚂蚁 = 一次"边走边用轮盘赌做决策"的旅行 = 一个完整的候选解。
与遗传算法（种群由交叉变异重组）不同，ACO 的解是增量式逐步构造出来的，这使得它天然适合那些"解的每一部分都是一次选择"的问题（访问顺序、排程、路由）。
1.5 算法流程伪代码
输入：城市坐标，参数 alpha, beta, rho, Q，蚂蚁数 m，最大迭代代数 T
1 计算距离矩阵 d_ij 与启发式信息 eta_ij = 1/d_ij
2 初始化信息素：所有边 tau_ij = tau0（同一初值，公平起点），对角元置 0
3 for t = 1 to T: # 每一代
4 for k = 1 to m: # 每只蚂蚁独立行动
5 随机选择一个起点城市
6 while 存在未访问城市:
7 按概率 p_ij^k 用轮盘赌选择下一城市 j
8 记录该蚂蚁的完整回路 tour_k 及其长度 L_k
9 更新全局最优解（若本代出现更短路径）
10 信息素挥发：tau_ij <- (1 - rho) * tau_ij # 遗忘
11 信息素增强：对每只蚂蚁经过的边增加 Q / L_k # 奖励
12 输出：全局最优路径与长度 L*
1.6 参数建议
竞赛中参数不必死记，但要理解"味道"：
| 参数 | 建议取值 | 作用与直觉 |
|---|---|---|
| 1 | 信息素权重。"经验"与"直觉"的均衡点；太大则蚂蚁盲从老路、过早停滞 | |
| 2~5 | 启发式权重。越大越像最近邻贪心；太小则退化为随机游走 | |
| 0.5 | 挥发率，常用 0.3~0.7。太大信息素来不及积累，太小旧经验赖着不走 | |
| 蚂蚁数 | （城市数） | 太少搜索不充分；太多白白增加计算量、收益递减 |
| 100 | 影响不大，取与路径长度同数量级即可（它只决定信息素的绝对量纲） | |
| 迭代代数 | 100~500 | 视问题规模与时间预算；小规模 100 代足以收敛 |
1.7 优缺点
优点：
- 正反馈机制强：优秀解的信息素自我强化，搜索快速集中到有希望的区域，收敛速度快；
- 天然的并行结构： 只蚂蚁互不干扰地构造解，极易并行化加速；
- 为路径类问题而生：TSP、VRP、网络路由等"序列构造"问题几乎是它的主场；
- 鲁棒性好：不依赖初始解的优劣（信息素均匀初始化即可），对问题规模变化不敏感；
- 易混合：与局部搜索（2-opt）、遗传算法、MMAS 等改进版结合效果更佳。
缺点：
- 计算量大：每代 只蚂蚁各构造 步路径，还要维护 信息素矩阵，比模拟退火等单解算法慢得多；
- 参数敏感：、、 配不好，要么早熟停滞（正反馈锁死局部最优），要么随机游走（收敛不了）；
- 易早熟：正反馈是双刃剑，全体蚂蚁可能集体"锁死"在某个局部最优上；
- 缺乏收敛性理论保证：不像模拟退火有严格的收敛定理，ACO 的解质量主要靠实验验证。
二、何时使用（适用场景与条件）
2.1 适用场景
- 旅行商问题 TSP 及其变体：给定 个城市两两距离，求遍历所有城市的最短回路；多旅行商 MTSP（多名配送员分工巡访）；
- 车辆路径问题 VRP：多辆车从仓库出发服务若干客户，求总里程最短的派车方案，含容量约束 CVRP、时间窗 VRPTW 等变体；
- 路径规划：机器人、无人机、AGV 小车在地图（栅格/路网）上的最短路径与全覆盖巡检路径规划；
- 网络路由：通信网络中寻找时延最短、负载均衡的最优路由（AntNet 即基于 ACO 的路由协议）；
- 调度问题：作业车间调度（JSP）、流水车间调度（FSP）、并行机调度——把"工件加工顺序"当作蚂蚁的访问序列；
- 其他序列构造类问题：二次分配问题（QAP）、装配线平衡、考试排考、PCB 钻孔路径优化（真实工业应用）。
2.2 竞赛典型题目
- 配送路径优化：某生鲜电商从中心仓向 个社区网点配送，求总里程最短的配送顺序（本质 TSP；多车多容量则是 VRP）；
- 旅游路线设计： 个景区、时间与预算约束下设计最优游览路线（TSP + 约束）；
- 无人机/巡检路线：基站巡检、输电线路巡检、园区巡逻的航线规划；
- 公交线路、校车路线规划：站点访问顺序优化。
这些题目的共同特征：把对象当城市、把两两代价（距离/时间/费用）当边、目标是最小化访问序列的总代价——正是蚁群算法的舒适区。国赛历年"旅游路线设计""物流配送方案"类题目，ACO 都是高频获奖解法。
2.3 使用前提
- 问题能建构成**"访问序列 + 边代价 + 总代价求和"**的组合优化模型；
- 任意两个对象之间的代价可以计算（有距离矩阵或代价矩阵即可）；
- 规模适中：基础 ACO 适合 20~200 个节点；更大规模需 MMAS、加入 2-opt 局部搜索等改进；
- 有迭代求解的时间预算（竞赛中 通常取 100~500 代，几十秒到几分钟可接受）。
2.4 不适用情形
- 连续函数优化：如 的参数寻优，蚂蚁的"访问序列"概念用不上，用 PSO（粒子群）、GA、差分进化更合适；
- 超大规模问题：数千个城市的 TSP 用基础 ACO 太慢，需 MMAS + 局部搜索等改进版；
- 实时性要求极高的在线决策：ACO 需要多代迭代，单次决策耗时较长；
- 约束无法自然表达为访问顺序的问题（如连续空间的避障轨迹优化）。
2.5 与其他智能优化算法对比选择表
| 算法 | 最适合的问题 | 优势 | 局限 | 竞赛建议 |
|---|---|---|---|---|
| 蚁群算法 ACO | 路径类组合优化（TSP/VRP/路由） | 正反馈强、收敛快、天然并行、易改进 | 计算量大、参数敏感、易早熟 | 配送、路线、巡检类首选 |
| 遗传算法 GA | 广泛的组合优化与调度 | 全局搜索强、通用性最好 | 编码设计需技巧、收敛较慢 | 通用保底方案 |
| 粒子群 PSO | 连续函数优化、参数寻优 | 实现极简、收敛快 | 易陷入局部最优、不适合序列问题 | 连续变量拟合/寻参 |
| 模拟退火 SA | 小规模组合优化 | 实现简单、有收敛理论保证 | 退火策略难调、效率低 | 小规模 TSP 备选 |
| 禁忌搜索 TS | 局部搜索强化 | 避免重复搜索、局部能力强 | 依赖邻域结构设计 | 常与 ACO 混合使用 |
选择口诀：题目是"排顺序、走路程"→ 蚁群；题目是"连续函数求极值"→ 粒子群；题目是"求稳、什么都行"→ 遗传算法。
三、算法指标
评价一次蚁群算法运行的好坏，竞赛论文中通常报告以下指标（本章公式中的 为蚂蚁 的回路长度， 为回路中第 个访问的城市， 首尾相接）。
3.1 最优路径长度 （Best Tour Length）
含义：整个求解过程中出现的最短回路长度，即算法的最终答案，是评价解质量的第一指标。
解读： 越小越好。应同时报告基线（如最近邻贪心）的长度，计算相对提升；小规模问题还应与穷举最优 对比验证正确性。
3.2 每代平均路径长度 （Mean Tour Length per Generation）
含义：第 代所有蚂蚁路径长度的平均值，反映整个蚂蚁群体的搜索水平，而不是某个幸运个体。
解读：初期 与 差距大（蚂蚁四散探索）；收敛后差距缩小（群体向优秀解聚集）。若平均线始终远离最优线，说明多样性过剩、收敛不足。
3.3 收敛代数 （Convergence Generation）
含义：历史最优长度第一次达到最终最优值 的代数。 为前 代的历史最优长度。
解读： 越小收敛越快，但收敛过快（如 5 代内）要警惕早熟——可能是 过大或 过小，全体蚂蚁过早锁死在同一路径上，此时应结合多次运行和穷举验证判断是否陷入局部最优。
3.4 多次运行的均值 与标准差
含义：ACO 是随机算法，每次运行结果不同。对 次独立运行（换随机种子）的最优长度 求均值 衡量平均求解质量，标准差 衡量稳定性。
解读：变异系数 越小（如 ）说明算法稳定可复现；若 很大，应增大蚂蚁数或迭代代数，或改用带信息素限幅的 MMAS。
3.5 与已知最优解的差距 gap
含义：相对"已知最优解"的相对误差。小规模问题（）可用排列穷举精确求出 ；大规模问题用文献已知最优值或强基线替代。
解读：这是验证算法正确性的硬指标。小规模实例 gap 应为 0% 或接近 0%；若 gap 明显大于 0，说明实现有 bug 或参数严重失衡。竞赛论文中报告"在 10 城市实例上与穷举最优解一致"能大幅增强说服力。
3.6 参数敏感性（//）
含义：固定其余参数，让某一个参数（、 或 ）在合理区间内取值，观察 （或 gap）的变化；可画"参数—性能"曲线，或用 （ 为被考察参数）量化敏感度。
解读：性能对参数变化平缓说明算法鲁棒；若某参数轻微变化导致性能骤降，说明它处于"临界区"，论文中应给出该参数的选值依据（如敏感性实验表格），评审会认为选参有据可依。
3.7 指标汇总表
| 指标 | 公式 | 含义与解读 |
|---|---|---|
| 最优路径长度 | 解的质量，越小越好，第一指标 | |
| 每代平均长度 | 群体平均搜索水平，反映多样性 | |
| 收敛代数 | 收敛速度；过快需警惕早熟 | |
| 多次运行均值 | 平均求解质量 | |
| 多次运行标准差 | 稳定性， 越小越稳 | |
| 与最优解差距 gap | 正确性验证，小规模应 | |
| 参数敏感性 | 固定其余参数变动 // 观察 | 参数选择依据与算法鲁棒性 |
四、可视化图表
4.1 图表清单
| 图名 | 用途 | 关键解读点 |
|---|---|---|
| ① 最优路径长度收敛曲线 | 展示历史最优长度随迭代代数的下降过程；可画多次运行的多条线 | 前期快速下降 = 正反馈起作用；出现平台 = 收敛；多条线重合度 = 算法稳定性；末代仍在下降 = 迭代不足 |
| ② 最终最优路径图 | 城市散点 + 编号 + 按最优访问顺序依次连线 | 连线无交叉、无"跑冤枉路"的长边 = 路径质量高；出现明显交叉可考虑 2-opt 改进 |
| ③ 信息素分布图 | 所有城市对之间连线，粗细/颜色按信息素浓度显示 | 最优路径上的边信息素远高于其他边，形成又粗又亮的"高速公路"，直观展示正反馈的收敛结果 |
| ④ 迭代初期 vs 迭代后期路径对比 | 两个子图：第 1 代最优路径 vs 最后一代最优路径 | 初期路径杂乱、交叉多、总长大；后期路径规整、总长显著缩短，直观展示优化过程 |
4.2 好图与异常图的特征
好图的特征：
- 收敛曲线：前几代快速下降，随后平稳，无剧烈抖动；多次运行曲线基本重合；
- 路径图：连线简洁、无明显交叉、没有"舍近求远"的长边；
- 信息素图：只有少数边（恰好是最终路径上的边）明显又粗又亮，其余边几乎透明——说明群体达成了共识；
- 初期 vs 后期图：后期路径总长显著小于初期，且走向完全不同。
异常图的特征（及其诊断）：
- 收敛曲线在前 5 代内就完全走平 → 早熟停滞： 过大或 过小，正反馈锁死局部最优，应调参或加入随机扰动；
- 收敛曲线持续缓慢下降、100 代还没平稳 → 随机游走： 过小或蚂蚁数不足，搜索缺乏引导；
- 信息素分布几乎均匀、看不到高速公路 → 迭代不足或 过大（信息素来不及积累）；
- 多次运行曲线严重发散 → 算法不稳定，应增加蚂蚁数、迭代代数或改用 MMAS。
五、符号说明
| 符号 | 含义 | 示例/单位 |
|---|---|---|
| 城市（节点）数量 | 25 个 | |
| 每代蚂蚁数量 | 25 只 | |
| 最大迭代代数 | 100 代 | |
| 城市 与 之间的距离 | 35.7（长度单位） | |
| 启发式信息， | 0.028（1/长度） | |
| 边 上的信息素浓度 | 0.5（无量纲） | |
| 信息素初始值（所有边相同） | 1.0 | |
| 蚂蚁 从城市 选择城市 的转移概率 | 0.32（无量纲） | |
| 信息素重要度 | 1 | |
| 启发式信息重要度 | 3 | |
| 信息素挥发率 | 0.5 | |
| 信息素强度常数 | 100 | |
| 蚂蚁 对边 的信息素增量 | ||
| 蚂蚁 的回路长度 | 520.3（长度单位） | |
| 全局最优路径长度 | ||
| 已知最优（穷举/文献）长度 | 小规模验证用 | |
| 收敛代数 | 第 18 代 | |
| 多次运行最优长度的均值、标准差 | 505.2 ± 8.3 | |
| gap | 与已知最优解的相对差距 | 0.5% |
| 蚂蚁 尚未访问的城市集合 | {3, 7, 12} |
六、可运行程序（完整代码）
环境说明：Python 3.12，仅依赖 numpy、matplotlib 与标准库（itertools、os）。scipy 与 scikit-learn 均不提供蚁群算法（scipy.optimize 提供的是确定性优化、dual_annealing 模拟退火等局部/全局搜索器，无 ACO），因此本文完整手写 ACO，并手写最近邻贪心作为基线对照。脚本完全自包含：np.random.seed(42) 生成 25 个城市；另生成 8 个城市的小规模实例，用 itertools.permutations 排列穷举求精确最优，与蚁群结果对比验证正确性。将下列代码块按顺序拼接即为一个完整脚本，可直接运行。
输出内容：控制台打印第三节的全部指标（最优路径长度、平均路径长度、收敛代数、5 次运行均值/标准差、与穷举最优的差距、 敏感性扫描）；在 figures/ 子目录生成第四节要求的 4 张图（文件名前缀 aco_），并弹出显示。脚本运行约半分钟。
6.1 导入库与全局绘图设置
# ========== 0. 导入库与全局绘图设置 ==========
import os
import itertools
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import collections as mc
# 中文字体设置（必须写在所有绘图代码之前，否则图内中文显示为方块）
plt.rcParams["font.sans-serif"] = ["PingFang SC", "Arial Unicode MS", "SimHei"]
plt.rcParams["axes.unicode_minus"] = False
os.makedirs("figures", exist_ok=True) # 图片输出目录，不存在则自动创建
6.2 生成城市坐标与距离矩阵
# ========== 1. 生成 25 个城市的坐标与距离矩阵 ==========
np.random.seed(42) # 固定随机种子，保证结果可复现
N_CITY = 25 # 城市数量
cities = np.random.rand(N_CITY, 2) * 100.0 # 25 个城市均匀分布在 [0,100] x [0,100]
def dist_matrix(pts):
"""欧氏距离矩阵：D[i, j] = 城市 i 与城市 j 的直线距离"""
diff = pts[:, None, :] - pts[None, :, :] # (n, n, 2) 两两坐标差
return np.sqrt((diff ** 2).sum(axis=-1))
D = dist_matrix(cities) # 25 x 25 距离矩阵
print(f"城市数量: {N_CITY}，坐标范围 [0,100] x [0,100]")
6.3 手写蚁群算法核心类
# ========== 2. 手写蚁群算法核心类（不调用任何现成优化库） ==========
class AntColony:
"""手写蚁群算法求解 TSP。
三个核心机制（与第一节公式一一对应）：
(1) 状态转移：蚂蚁 k 在城市 i 时，按概率
p_ij ∝ tau_ij^alpha * eta_ij^beta（eta_ij = 1/d_ij）
选择下一城市 j，用轮盘赌实现按概率抽样；
(2) 信息素更新：每代结束先整体挥发 tau *= (1 - rho)，
再按每只蚂蚁路径长度增强，边 (i,j) 增加 Q / L_k；
(3) 正反馈：路径越短 -> 信息素越多 -> 被选中的概率越大
-> 蚂蚁逐渐聚集到短路径，形成"高速公路"。
"""
def __init__(self, D, n_ants=25, alpha=1.0, beta=3.0, rho=0.5, Q=100.0, seed=0):
self.D = D # 距离矩阵
self.n = D.shape[0] # 城市数
self.n_ants = n_ants # 每代蚂蚁数（建议 = 城市数）
self.alpha = alpha # 信息素重要度
self.beta = beta # 启发式信息重要度
self.rho = rho # 信息素挥发率
self.Q = Q # 信息素强度常数
self.rng = np.random.default_rng(seed) # 独立随机数发生器，保证可复现
# 信息素初始化：所有边取同一初值（公平起点），对角元置 0 防止自环
self.tau = np.ones((self.n, self.n))
np.fill_diagonal(self.tau, 0.0)
self.first_iter_tour = None # 记录第 1 代最优路径（供"初期 vs 后期"对比图用）
self.first_iter_len = np.inf
def run(self, n_iter=100):
"""主循环：迭代 n_iter 代，每代 n_ants 只蚂蚁各自构造一条完整回路"""
best_len, best_tour = np.inf, None
best_hist, mean_hist = [], [] # 历史最优长度序列 / 每代平均长度序列
for it in range(n_iter):
tours, lengths = [], []
for _ in range(self.n_ants):
tour = self._build_tour() # 一只蚂蚁构造完整路径
L = self._tour_len(tour)
tours.append(tour)
lengths.append(L)
if L < best_len: # 更新全局最优
best_len, best_tour = L, tour.copy()
if it == 0: # 记下第 1 代的最优路径
self.first_iter_tour = best_tour.copy()
self.first_iter_len = best_len
# ---- 信息素更新：先挥发，再增强（tau <- (1-rho)*tau + Delta_tau）----
self.tau *= (1.0 - self.rho) # 全局挥发：模拟信息素蒸发
for tour, L in zip(tours, lengths):
delta = self.Q / L # 每只蚂蚁的贡献：Delta_tau = Q / L_k
for i in range(self.n):
a, b = tour[i], tour[(i + 1) % self.n]
self.tau[a, b] += delta # 无向 TSP：对称增强
self.tau[b, a] += delta
best_hist.append(best_len) # 记录第三节指标所需数据
mean_hist.append(float(np.mean(lengths)))
return best_len, best_tour, best_hist, mean_hist
def _build_tour(self):
"""一只蚂蚁的完整旅行：随机起点 + 轮盘赌逐步选择，走遍所有城市成环"""
start = int(self.rng.integers(self.n))
unvisited = list(range(self.n))
unvisited.remove(start)
tour, cur = [start], start
while unvisited:
# 状态转移概率的分子：tau^alpha * eta^beta（eta = 1/d 为启发式信息）
tau = self.tau[cur, unvisited] ** self.alpha
eta = (1.0 / self.D[cur, unvisited]) ** self.beta
p = tau * eta
p = p / p.sum() # 归一化为合法概率分布
# 轮盘赌抽样：生成 U(0,1)，落在累积概率的哪个区间就选哪个城市
idx = int(np.searchsorted(np.cumsum(p), self.rng.random()))
idx = min(idx, len(unvisited) - 1) # 防浮点误差越界
nxt = unvisited[idx]
tour.append(nxt)
unvisited.pop(idx)
cur = nxt
return tour
def _tour_len(self, tour):
"""回路长度：依次累加相邻城市距离，最后回到起点（首尾相接）"""
return sum(self.D[tour[i], tour[(i + 1) % self.n]] for i in range(self.n))
6.4 主实例求解与指标输出
# ========== 3. 主实例：25 城市 TSP 求解与指标输出 ==========
aco = AntColony(D, n_ants=25, alpha=1.0, beta=3.0, rho=0.5, Q=100.0, seed=0)
best_len, best_tour, best_hist, mean_hist = aco.run(n_iter=100)
print("=" * 62)
print("【主实例】25 城市 TSP —— 手写蚁群算法")
print("参数设置：蚂蚁数 m=25，alpha=1.0，beta=3.0，rho=0.5，Q=100，迭代 100 代")
print(f"指标1 最优路径长度 L* = {best_len:.2f}")
print(f"指标2 第 1 代平均路径长度 = {mean_hist[0]:.2f}，"
f"第 100 代平均路径长度 = {mean_hist[-1]:.2f}")
# 收敛代数：历史最优第一次达到最终最优值的代数
conv_gen = next(i for i, v in enumerate(best_hist) if v == best_hist[-1]) + 1
print(f"指标3 收敛代数 t_conv = {conv_gen}"
f"（第 1 次达到最终最优值 {best_hist[-1]:.2f} 的代数）")
# 分阶段观察历史最优的下降过程（供第七节结果解读使用）
for g in [1, 5, 10, 20, 50, 100]:
print(f" 第 {g:3d} 代历史最优长度 = {best_hist[g - 1]:.2f}")
print(f"最优路径（城市访问顺序，从 0 号城市起）: {best_tour}")
# 指标4：多次独立运行统计（随机算法必须报告均值与标准差）
n_runs = 5
run_bests, run_hists = [], []
for r in range(n_runs):
aco_r = AntColony(D, n_ants=25, alpha=1.0, beta=3.0, rho=0.5, Q=100.0,
seed=100 + r)
Lr, _, bh, _ = aco_r.run(n_iter=100)
run_bests.append(Lr)
run_hists.append(bh)
print(f" 第 {r + 1} 次独立运行最优长度: {Lr:.2f}")
run_bests = np.array(run_bests)
mu, sigma = run_bests.mean(), run_bests.std()
print(f"指标4 5 次运行最优长度：均值 mu = {mu:.2f}，标准差 sigma = {sigma:.2f}，"
f"变异系数 sigma/mu = {sigma / mu * 100:.2f}%")
6.5 小规模穷举验证（检验正确性）
# ========== 4. 小规模穷举验证：8 城市求精确最优，检验 ACO 正确性 ==========
N_SMALL = 8
np.random.seed(1)
small_pts = np.random.rand(N_SMALL, 2) * 100.0
D_small = dist_matrix(small_pts)
best_exact, best_perm = np.inf, None
# 固定城市 0 为起点，枚举其余 7 个城市的全排列：7! = 5040 条回路
for perm in itertools.permutations(range(1, N_SMALL)):
tour = (0,) + perm
L = sum(D_small[tour[i], tour[(i + 1) % N_SMALL]] for i in range(N_SMALL))
if L < best_exact:
best_exact, best_perm = L, tour
print("=" * 62)
print("【小规模验证】8 城市 TSP —— 穷举法求精确最优")
print(f"穷举 7! = 5040 条回路，精确最优长度 L_opt = {best_exact:.4f}")
print(f"精确最优路径: {list(best_perm)}")
# 同一实例用蚁群求解，比较与精确最优的差距（指标5）
aco_small = AntColony(D_small, n_ants=8, alpha=1.0, beta=3.0, rho=0.5,
Q=100.0, seed=7)
L_aco_small, tour_aco_small, _, _ = aco_small.run(n_iter=100)
gap_pct = abs(L_aco_small - best_exact) / best_exact * 100.0 # 取绝对差，避免浮点负零
print(f"蚁群算法最优长度 L* = {L_aco_small:.4f}")
print(f"指标5 与穷举最优解的差距 gap = {gap_pct:.4f}%")
print(f"蚁群最优路径: {tour_aco_small}")
6.6 最近邻贪心基线对照
# ========== 5. 基线对照：最近邻贪心启发式 ==========
# 库对照说明：scipy 与 scikit-learn 均不提供蚁群算法，无法做"库调用对照"；
# 因此手写"最近邻贪心"作为简单基线（baseline），
# 用蚁群相对基线的提升幅度证明 ACO 的价值。
def nearest_neighbor(D, start=0):
"""最近邻贪心：从 start 出发，每次都去最近的未访问城市"""
n = D.shape[0]
unvisited = list(range(n))
unvisited.remove(start)
tour, cur = [start], start
while unvisited:
nxt = min(unvisited, key=lambda j: D[cur, j])
tour.append(nxt)
unvisited.remove(nxt)
cur = nxt
L = sum(D[tour[i], tour[(i + 1) % n]] for i in range(n))
return tour, L
nn_tour, nn_len = nearest_neighbor(D, start=0)
_, nn_small_len = nearest_neighbor(D_small, start=0)
print("=" * 62)
print("【基线对照】最近邻贪心 vs 蚁群算法")
print(f"25 城市：最近邻贪心 = {nn_len:.2f}，蚁群 = {best_len:.2f}，"
f"蚁群相对提升 = {(nn_len - best_len) / nn_len * 100:.2f}%")
print(f"8 城市：最近邻贪心 = {nn_small_len:.4f}，蚁群 = {L_aco_small:.4f}，"
f"穷举最优 = {best_exact:.4f}")
6.7 参数敏感性实验（ 扫描）
# ========== 6. 参数敏感性实验：挥发率 rho 的影响（指标6） ==========
# 在 25 城市主实例上扫描：小实例太简单（各 rho 均能找到穷举最优），
# 主实例才能体现出参数对解质量的真实影响
print("=" * 62)
print("【指标6 参数敏感性】固定 alpha=1.0, beta=3.0，变化 rho（25 城市实例）")
rho_scan = {}
for rho_v in [0.1, 0.3, 0.5, 0.7, 0.9]:
aco_v = AntColony(D, n_ants=25, alpha=1.0, beta=3.0, rho=rho_v,
Q=100.0, seed=7)
L_v, _, _, _ = aco_v.run(n_iter=100)
rho_scan[rho_v] = L_v
print(f" rho={rho_v:.1f}: L*={L_v:.2f}")
worst_rho = max(rho_scan, key=rho_scan.get)
print(f" 最优 L* = {min(rho_scan.values()):.2f}（rho={min(rho_scan, key=rho_scan.get)}），"
f"最差 L* = {rho_scan[worst_rho]:.2f}（rho={worst_rho}），"
f"性能波动幅度 = {rho_scan[worst_rho] - min(rho_scan.values()):.2f}")
6.8 可视化：第四节要求的 4 张图
# ========== 7. 可视化：第四节要求的 4 张图 ==========
xs = np.arange(1, len(best_hist) + 1)
# ---- 图 1：最优路径长度收敛曲线（5 次运行多条线 + 平均线） ----
plt.figure(figsize=(9, 5))
for r, bh in enumerate(run_hists):
plt.plot(xs, bh, lw=1.0, alpha=0.55, label=f"第 {r + 1} 次运行")
plt.plot(xs, np.mean(run_hists, axis=0), "k-", lw=2.5, label="5 次运行平均")
plt.xlabel("迭代代数")
plt.ylabel("历史最优路径长度")
plt.title("图1 最优路径长度收敛曲线（25 城市 TSP，5 次独立运行）")
plt.legend()
plt.grid(alpha=0.3)
plt.tight_layout()
plt.savefig("figures/aco_convergence.png", dpi=200)
plt.show()
# ---- 图 2：最终最优路径图（城市散点 + 编号 + 按顺序连线） ----
plt.figure(figsize=(8, 8))
bx, by = cities[best_tour, 0], cities[best_tour, 1]
plt.plot(np.append(bx, bx[0]), np.append(by, by[0]), "r-", lw=1.6, zorder=1)
plt.scatter(cities[:, 0], cities[:, 1], s=90, c="steelblue", edgecolors="k",
zorder=2)
for i, (x, y) in enumerate(cities):
plt.annotate(str(i), (x, y), textcoords="offset points", xytext=(6, 4),
fontsize=9)
plt.xlabel("x 坐标")
plt.ylabel("y 坐标")
plt.title(f"图2 最终最优路径（长度 {best_len:.2f}）")
plt.grid(alpha=0.3)
plt.tight_layout()
plt.savefig("figures/aco_best_route.png", dpi=200)
plt.show()
# ---- 图 3：信息素分布图（连线粗细/颜色 = 信息素浓度，粗线即"高速公路"） ----
plt.figure(figsize=(8, 8))
cmap = plt.get_cmap("viridis")
lines, widths, colors = [], [], []
tau_max = aco.tau.max()
for i in range(N_CITY):
for j in range(i + 1, N_CITY):
t_norm = aco.tau[i, j] / tau_max # 归一化信息素浓度
lines.append([cities[i], cities[j]])
widths.append(0.3 + 4.5 * t_norm) # 浓度越高线越粗
r, g, b, _ = cmap(t_norm) # 浓度越高颜色越亮（黄）
colors.append((r, g, b, 0.12 + 0.88 * t_norm))
lc = mc.LineCollection(lines, linewidths=widths, colors=colors, zorder=1)
plt.gca().add_collection(lc)
plt.scatter(cities[:, 0], cities[:, 1], s=70, c="steelblue", edgecolors="k",
zorder=2)
for i, (x, y) in enumerate(cities):
plt.annotate(str(i), (x, y), textcoords="offset points", xytext=(6, 4),
fontsize=9)
plt.xlim(cities[:, 0].min() - 5, cities[:, 0].max() + 5)
plt.ylim(cities[:, 1].min() - 5, cities[:, 1].max() + 5)
sm = plt.cm.ScalarMappable(cmap=cmap, norm=plt.Normalize(0, tau_max))
sm.set_array([])
plt.colorbar(sm, ax=plt.gca(), label="信息素浓度 tau")
plt.xlabel("x 坐标")
plt.ylabel("y 坐标")
plt.title("图3 信息素分布图（线越粗越亮 = 信息素越浓，粗线为“高速公路”）")
plt.tight_layout()
plt.savefig("figures/aco_pheromone.png", dpi=200)
plt.show()
# ---- 图 4：迭代初期 vs 迭代后期最优路径对比（两个子图） ----
fig, axes = plt.subplots(1, 2, figsize=(14, 6.2))
tours_plot = [
(aco.first_iter_tour, f"迭代初期（第 1 代）\n路径长度 {aco.first_iter_len:.2f}"),
(best_tour, f"迭代后期（第 100 代）\n路径长度 {best_len:.2f}"),
]
for ax, (tour, name) in zip(axes, tours_plot):
px, py = cities[tour, 0], cities[tour, 1]
ax.plot(np.append(px, px[0]), np.append(py, py[0]), "r-", lw=1.6)
ax.scatter(cities[:, 0], cities[:, 1], s=45, c="steelblue", edgecolors="k")
for i, (x, y) in enumerate(cities):
ax.annotate(str(i), (x, y), textcoords="offset points", xytext=(4, 3),
fontsize=8)
ax.set_title(name, fontsize=11)
ax.set_xlabel("x 坐标")
ax.set_ylabel("y 坐标")
ax.grid(alpha=0.3)
fig.suptitle("图4 迭代初期 vs 迭代后期最优路径对比（正反馈优化过程）", fontsize=13)
plt.tight_layout()
plt.savefig("figures/aco_evolution.png", dpi=200)
plt.show()
print(f"图4 数据：第 1 代最优路径长度 = {aco.first_iter_len:.2f}，"
f"第 100 代最优路径长度 = {best_len:.2f}")
print("=" * 62)
print("4 张图片已保存至 figures/ 目录：")
for f in ["aco_convergence.png", "aco_best_route.png",
"aco_pheromone.png", "aco_evolution.png"]:
print(" figures/" + f)
七、结果解读与注意事项
7.1 本次实例结果解读（数值均为第六节脚本的真实运行输出）
主实例（25 城市，m=25，α=1，β=3，ρ=0.5，Q=100，迭代 100 代）：
- 指标1 最优路径长度 。最近邻贪心为 531.63，蚁群相对提升 22.77%——这正是"正反馈 + 全局搜索"相对"局部贪心"的价值；
- 收敛过程：历史最优长度 第 1 代 526.72 → 第 5 代 430.62 → 第 10 代 418.20 → 第 50 代 411.17 → 第 100 代 410.60。前 5 代下降近 100，是正反馈"快车道"的直观体现；第 10~20 代出现平台（蚂蚁聚集在局部最优上），随后继续小幅改进，说明挥发机制给新路径留了机会；
- 指标3 收敛代数 ：第 80 代才锁定最终最优，前期（第 5 代）已逼近、后期缓慢微调。若论文要求更快的收敛，可增大蚂蚁数或改用精英蚁群；
- 指标2 平均路径长度：第 1 代 643.81 → 第 100 代 544.14。平均线始终高于最优线约 130，说明群体并未完全同质化、仍保留探索能力——这是健康的状态，不必追求"平均 = 最优"；
- 指标4 多次运行：5 次独立运行最优长度分别为 416.92、412.27、407.33、410.60、410.60，均值 ，标准差 ，变异系数 （远小于 2%），说明算法稳定可复现。注意第 3 次运行得到 407.33，优于主实例的 410.60——随机算法的特点，竞赛中可"多次运行取最优"报告；
- 指标5 正确性验证（8 城市小实例）：排列穷举 7! = 5040 条回路得精确最优 ；蚁群同样得到 ，gap = 0.0000%。蚁群路径 [1,7,6,0,5,4,3,2] 与穷举路径 [0,5,4,3,2,1,7,6] 是同一回路的旋转/反转，证明实现完全正确；
- 指标6 参数敏感性（ρ 扫描）：ρ 从 0.1 到 0.9， 分别为 413.19、411.17、410.60、412.27、411.17，最差（ρ=0.1）与最优（ρ=0.5）仅差 2.59（约 0.63%）。说明算法对 ρ 较为鲁棒，论文中 ρ 取 0.5 有实验依据；ρ=0.1 偏差的原因正是第一节所说：挥发太慢，旧经验残留、稍许抑制了新路径的探索。
四张图的解读：
- 收敛曲线（图1）：5 条运行曲线几乎重合、均呈"先陡降后平台"形态——收敛快且稳定；若曲线前期就走平，则是早熟的警报；
- 最终路径图（图2）：25 个城市按编号依次连成一条总长 410.60 的回路，连线整体规整、无明显交叉与"舍近求远"的长边；
- 信息素分布图（图3）：少数边又粗又亮（信息素浓度高）、其余边几乎透明——最优路径上的边形成了清晰的"高速公路"，直观展示正反馈的收敛结果；
- 初期 vs 后期对比（图4）：第 1 代最优路径长度 526.72，第 100 代 410.60，缩短约 22%。初期路径多处交叉绕行，后期路径明显规整——优化过程一目了然，非常适合放进竞赛论文。
7.2 常见坑
- α/β 失衡：α 过大（如 α=5、β=1）→ 信息素统治决策，全体蚂蚁盲从老路，5 代内锁死局部最优（早熟）；β 过大（如 α=1、β=10）→ 退化成最近邻贪心，失去全局性；α、β 都过小 → 随机游走，100 代也收敛不了。建议 β/α 在 2~5 之间；
- 蚂蚁数太少：m=5 只蚂蚁每代只产生 5 个候选解，信息素统计意义差，收敛慢且不稳定；m 取城市数即可，收益递减后不必再加；
- 信息素初始化不当： 过大 → 初期转移概率被信息素"抹平"，启发式信息形同虚设，前期等于纯随机游走； 过小 → 前期信息素无法积累。统一初值 + 与 同数量级是稳妥做法；
- 挥发率过大：ρ=0.9 时信息素每代只保留 10%，来不及积累，正反馈失效（本例 ρ=0.9 尚可，但配合更大问题或更少迭代就会退化）；
- 实现细节错误：忘了对称更新信息素（无向 TSP 需 ）；距离矩阵对角元未处理；轮盘赌累积概率浮点误差越界（用
min(idx, len-1)兜底）； - 不固定随机种子：论文里的数字与复现结果对不上，是竞赛翻车的高发原因；
np.random.seed(42)一行的事； - 不验证正确性：直接在大问题上调参、连实现对不对都不知道。先用 8~10 城市穷举对照（本文 6.5 节模板），gap≈0 再上规模。
7.3 竞赛论文写作建议
模型部分话术模板：
针对配送路线优化问题，建立以总里程最小为目标的旅行商模型。采用蚁群算法求解：蚂蚁数取城市数 ，信息素重要度 ，启发式重要度 ，挥发率 ，信息素强度 ，迭代 100 代。求解得到最优路径长度为 410.60，较最近邻贪心基线（531.63）缩短 22.77%。为验证算法正确性，在 8 城市小规模实例上与排列穷举法对比：蚁群解 与穷举最优 完全一致（gap=0.0000%），验证了算法的正确性。此外，对挥发率 ρ 在 0.1~0.9 内做敏感性分析，最优长度波动仅 0.63%，表明算法鲁棒、参数选择合理。
指标报告清单（评审老师爱看的数据）：最优路径长度、与基线的相对提升、收敛代数、5 次运行均值±标准差、小规模穷举 gap、敏感性实验表。
图表建议：论文正文放 图1（收敛曲线）+ 图2（最优路径图）即可；图4（初期 vs 后期对比）放"算法原理"小节作为机理展示；图3（信息素分布）放"算法机理分析"或附录，直观论证正反馈机制。
八、延伸阅读
8.1 最大最小蚂蚁系统（MMAS）
MMAS（Max-Min Ant System）是针对基础 ACO"早熟停滞"问题的经典改进：①把每条边上的信息素限制在区间 内，防止某些边信息素趋于 0 或无限膨胀；②只允许最优蚂蚁（本代最优或全局最优）更新信息素；③信息素初始化为 ，让前期充分探索、后期逐渐收敛。MMAS 在 TSP/VRP 上常能得到比基础 ACO 更好的解，是实现最"划算"的改进。
8.2 精英蚁群（Elitist Ant System）
每代结束后，除各蚂蚁按 增强外，对全局历史最优路径额外奖励 （ 为精英权重， 为全局最优长度）。相当于给"目前最好的历史经验"开小灶，加快向优秀解聚集的速度，但 过大同样会加剧早熟。
8.3 连续域蚁群算法（）
基础 ACO 的离散信息素无法直接处理连续变量。Socha 与 Dorigo 提出的 用高斯核概率密度函数（由每个解维度的多个高斯分布加权叠加而成）替代离散信息素矩阵，蚂蚁从核中抽样构造解，信息素更新即调整各高斯分布。它把 ACO 扩展到了连续优化领域，常用于控制器参数整定、连续函数寻优。
8.4 与遗传算法等混合
- ACO + GA：用 ACO 的结果作为 GA 初始种群的一部分（好起点），或反过来用 GA 进化 ACO 的参数 ；
- ACO + 2-opt 局部搜索：每只蚂蚁构造完路径后做一遍 2-opt（翻转任意子段），大幅提升解质量，是 TSP 求解的标配组合；
- ACO + 模拟退火：用 SA 的接受准则决定信息素更新强度，缓解早熟。
8.5 参考文献
- Dorigo M, Stützle T. Ant Colony Optimization. MIT Press, 2004.（ACO 领域的标准教材）
- Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, 1996.
- Goss S, et al. Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 1989.（双桥实验）