ACO-蚁群算法

1. 方法概述

ACO-蚁群算法 的真实核心位于：

• core/calculator.py
• utils/aco_exporter.py
• ui/aco_params_widget.py
• ui/aco_results_widget.py

这份实现不是连续优化版 ACO，而是经典 TSP 路径规划版 ACO。输入是一张城市坐标表，至少包含 x_column 与 y_column；输出是最优回路、最短路径长度以及收敛历史。

设城市坐标为

$$ c_i=(x_i,y_i),\qquad i=1,\dots,n \tag{1} $$

两城市间距离矩阵由欧氏距离给出：

$$ d_{ij}=\|c_i-c_j\|_2 \tag{2} $$

算法的优化目标是求解一条闭合巡回路径 \(\pi\)，使总路长最小。

2. 路径表示与状态转移

2.1 路径长度

若一只蚂蚁构造出的路径为

$$ \pi=(\pi_1,\pi_2,\dots,\pi_n) \tag{3} $$

则代码中的 _tour_length() 按闭环方式计算长度：

$$ L(\pi)=\sum_{k=1}^{n-1} d_{\pi_k,\pi_{k+1}}+d_{\pi_n,\pi_1} \tag{4} $$

因此它明确是 Hamilton 回路，而不是开放路径。

2.2 启发式信息与选择概率

启发式信息定义为

$$ \eta_{ij}=\frac{1}{d_{ij}+\varepsilon} \tag{5} $$

其中 \(\varepsilon=10^{-12}\) 用于避免除零。对当前城市 \(i\) 的未访问候选集合 \(\mathcal{N}_i\)，转移概率为

$$ p_{ij}= \frac{\tau_{ij}^{\alpha}\eta_{ij}^{\beta}} {\sum_{k\in\mathcal{N}_i}\tau_{ik}^{\alpha}\eta_{ik}^{\beta}}, \qquad j\in\mathcal{N}_i \tag{6} $$

这里的 \(\tau_{ij}\) 是信息素矩阵，\(\alpha,\beta\) 来自 UI 参数页。

2.3 起点机制

实现允许两种起点：

$$ \pi_1= \begin{cases} \text{随机城市}, & \texttt{start\_mode=random}\\ \texttt{start\_index}, & \texttt{start\_mode=fixed} \end{cases} \tag{7} $$

若候选权重全为零或非有限，代码会退化成“在未访问城市中随机选一个”，而不会报错。

3. 信息素更新

3.1 蒸发与增量

每轮迭代结束后，信息素先蒸发：

$$ \tau_{ij}\leftarrow (1-\rho)\tau_{ij} \tag{8} $$

然后对每只蚂蚁的回路边做增量更新。若第 \(k\) 只蚂蚁路径长度为 \(L_k\)，则经过边 \((i,j)\) 时增加

$$ \Delta\tau_{ij}^{(k)}=\frac{q}{L_k} \tag{9} $$

总代入后得到

$$ \tau_{ij}\leftarrow (1-\rho)\tau_{ij}+\sum_k \Delta\tau_{ij}^{(k)} \tag{10} $$

代码按无向边处理，所以会同时更新 \(\tau_{ij}\) 与 \(\tau_{ji}\)。

3.2 精英增强

若 elitist_weight>0，则还会对当前全局最优路径额外追加一次信息素：

$$ \tau_{ij}\leftarrow \tau_{ij}+\texttt{elitist\_weight}\cdot \frac{q}{L_{\mathrm{best}}} \tag{11} $$

这一步不是所有 ACO 教材默认都带，但当前实现是支持的。

3.3 信息素裁剪

更新后代码还会执行

$$ \tau_{ij}\in[\tau_{\min},\tau_{\max}] \tag{12} $$

其中 tau_max 可以为空；若为空，只做下界保护 tau_min。

4. 输出结果与导出

export_aco_results() 的真实 Excel 工作表为：

• 参数
• 处理信息
• 原始数据预览
• 原始数据
• 城市坐标
• 最优摘要
• 最优路径
• 收敛历史
• 信息素矩阵
• 图表清单

并额外导出两张图片：

• charts/convergence.png
• charts/best_tour.png

其中 信息素矩阵 只有在城市数不太大时才导出；若矩阵边长超过 60，代码会主动跳过，避免 Excel 过大。

5. 实现说明与注意事项

从真实实现出发，这个模块应写清以下细节：

1. 它只解决 TSP/路径规划，不支持连续变量函数优化，也没有上传 surrogate 模式。
2. 若原始文件里存在 id 列，但用户没有把它指定为 id_column，导出的城市编号会退化成行号 0,1,2,...，不会自动识别原始 ID。
3. 路径长度始终按回路计算，最后一座城市必定回到起点。
4. elitist_weight 是真实生效的额外精英信息素项，不是摆设参数。
5. 结果导出是中文工作表，不同于很多别的目录里的英文 sheet 名。

6. 论文写作模板

可在论文“方法部分”中写为：

“本文采用蚁群算法对旅行商路径规划问题进行求解。首先，将城市节点及其两两距离构造成路径搜索图，并初始化信息素矩阵与启发式信息；其次，每只蚂蚁依据状态转移概率在禁忌表约束下逐步构造完整回路；随后，根据各蚂蚁回路长度对信息素进行挥发、增量更新和精英路径强化；最后，以最优回路长度、最优路径和收敛曲线作为算法输出，用于评价路径规划效果与算法收敛性能。”

7. 单篇终审补充

7.1 表格标题模板

• 最优摘要 表可写为：表X ACO 求得的最优回路长度与关键运行参数。
• 最优路径 表可写为：表X ACO 最优旅行路径节点顺序。
• 收敛历史 表可写为：表X ACO 各迭代最优路径长度变化。
• 信息素矩阵 表可写为：表X 最终信息素矩阵的主要分布特征。

7.2 图表题注模板

• charts/convergence.png 可写为：图X 蚁群算法收敛曲线。
• charts/best_tour.png 可写为：图X 蚁群算法得到的最优旅行回路。

7.3 结果解释模板段落

“由 最优摘要 与 收敛历史 可见，ACO 在迭代过程中能够持续缩短回路长度，并最终收敛到较稳定的最优路径长度。图X 所示 convergence.png 表明算法前期下降较快、后期逐渐趋稳，说明信息素强化已将搜索集中到较优路径附近。图Y 所示 best_tour.png 进一步给出了城市访问顺序及闭合回路结构，可与 最优路径 工作表中的节点序列逐项对应。若 信息素矩阵 已导出，则还可结合其高值边分析算法在最终阶段偏好的主导路径段。”

7.4 全量强化补充

本次全量强化绑定的真实结果目录为 具体的算法3/优化与多目标/ACO-蚁群算法/results/ACO-蚁群算法分析结果_20260329_171836。该目录内主工作簿为 ACO-蚁群算法分析结果_20260329_171836.xlsx，实际工作表为 参数、处理信息、原始数据预览、原始数据、城市坐标、最优摘要、最优路径、收敛历史、信息素矩阵、图表清单。这说明当前单轮结果比正文上方概括更完整，真实还包含 参数、处理信息 和 原始数据预览 等工程页签，论文若介绍结果文件结构，应按这 10 个 sheet 写实。

图件位于 charts/ 目录，真实文件为 convergence.png 与 best_tour.png。同一目录内 repro_inputs/aco_ui.csv 真实存在，且配有 repro_aco.py。该脚本当前真实参数写法为 INPUT_REL_PATH = 'repro_inputs/aco_ui.csv'，并绑定 id_column = None、x_column = 'x'、y_column = 'y'、ants = 30、iters = 200、alpha = 1.0、beta = 2.0、rho = 0.1、elitist_weight = 0.0、random_state = 42。

因此 ACO 当前已经具备“上传城市坐标副本 + 中文主工作簿 + 收敛图与最优路径图 + 相对路径 repro 脚本”的完整单轮证据链。正文可以直接以这轮 20260329_171836 目录作为标准引用，而不需要再混用更早时间戳目录中的结果。

8. 软件实现核查补充（2026-07）

• 当前主结果目录应写作 具体的算法3/优化与多目标/ACO-蚁群算法/results/ACO-蚁群算法分析结果_20260329_171836。
• 正文应围绕 参数、处理信息、原始数据预览、原始数据、城市坐标、最优摘要、最优路径、收敛历史、信息素矩阵、图表清单 来写。
• 图证应对应 charts/convergence.png 与 charts/best_tour.png，并把路径顺序和收敛曲线配套说明。
• 复现脚本应按 repro_aco.py + repro_inputs/aco_ui.csv 的口径说明。