蚁群算法 ACO · 深度手册

分类：优化类 ｜难度：★★★ 高阶｜编号：aco

一、这是什么（一句话用途）

路径 / 组合优化(TSP / 网络路由 / 调度)

二、核心思想

蚁群算法（ACO）模拟蚂蚁觅食：真实蚂蚁在路径上释放信息素，后续蚂蚁倾向于走信息素更浓的路径，形成正反馈——短路径被更多蚂蚁走、沉积更多信息素，最终整群收敛到最短路径。算法把这种机制抽象为：构造解时按"信息素浓度×启发式能见度"的概率选边，每轮结束后按路径质量更新信息素（同时有蒸发机制防止过早停滞）。它是求解 TSP、车辆路径、调度等组合优化问题的强有力元启发式。

三、数学原理与推导

蚂蚁 $k$ 在节点 $i$ 选择下一节点 $j$ 的概率：

$p_{ij}^k=\frac{[\tau_{ij}]^\alpha[\eta_{ij}]^\beta}{\sum_{l\in\mathcal{N}_i^k}[\tau_{il}]^\alpha[\eta_{il}]^\beta}$

$\tau_{ij}$ 为边 $(i,j)$ 信息素， $\eta_{ij}=1/d_{ij}$ 为启发式能见度（距离越短越有吸引力）， $\alpha,\beta$ 控制二者权重， $\mathcal{N}_i^k$ 为蚂蚁 $k$ 可选邻域。

信息素更新（一轮后）：

$\tau_{ij}\leftarrow(1-\rho)\tau_{ij}+\sum_k\Delta\tau_{ij}^k,\qquad \Delta\tau_{ij}^k=\begin{cases}Q/L_k, & (i,j)\in\text{蚂蚁}k\text{路径}\\ 0, & \text{否则}\end{cases}$

$\rho\in(0,1)$ 为蒸发率（防止信息素无限累积导致早熟）， $L_k$ 为该蚂蚁路径总长， $Q$ 为常数。蒸发+沉积的平衡保证算法既利用已有好解又保留探索能力。

四、建模 / 求解步骤

初始化信息素
构造路径(概率选边)
计算路径长度
更新信息素(蒸发 + 沉积)
迭代得最短路径

五、关键公式速查

p_ij∝[τ_ij]^α·[η_ij]^β；τ←(1−ρ)τ+ΣΔτ

六、典型示例

TSP 城市最短巡回、物流配送路径。

完整算例（数字演示，照着算一遍）

场景：4 城 TSP，距离矩阵已知，蚂蚁 10 只，迭代 50。

信息素收敛：最优回路 1→3→2→4→1，总长 28。

结论：蚁群正反馈找到最短环游。

七、Python 实现示例

import os, numpy as np
import pandas as pd
HERE = os.path.dirname(os.path.abspath(__file__))
df = pd.read_csv(os.path.join(HERE,"..","datasets","aco.csv"))
cities=df[["x","y"]].to_numpy(dtype=float)
D=np.linalg.norm(cities[:,None]-cities[None,:],axis=2)
tau=np.ones_like(D)
rng=np.random.default_rng(4)
best=None; bestL=1e9
for it in range(60):
    for ant in range(10):
        un=[0]; path=[0]
        while len(path)<len(cities):
            last=path[-1]
            probs=(tau[last,un]**1)*( (1/(D[last,un]+1e-9))**2 )
            probs/=probs.sum()
            nx=un[rng.choice(len(un),p=probs)]
            path.append(nx); un.remove(nx)
        L=sum(D[path[i],path[(i+1)%len(path)]] for i in range(len(path)))
        if L<bestL: best, bestL=path[:], L
    for i in range(len(path)-1):
        tau[best[i],best[i+1]]+=1/L
    tau*=0.9
print("蚁群最短巡回=%.2f"%bestL)

配套文件：py_aco.py（需 numpy / pandas；与下方数据集配套练习）

八、MATLAB 实现示例

%% 蚁群算法 TSP 示例（MATLAB/Octave）
df = readtable('..\datasets\aco.csv');
cities=table2array(df(:,2:3)); D=pdist2(cities,cities);
tau=ones(size(D)); bestL=inf;
for it=1:60
  for a=1:10
    un=1:height(cities); path=1; last=1;
    while length(path)<height(cities)
      probs=(tau(last,un).^1).*((1./(D(last,un)+1e-9)).^2);
      probs=probs/sum(probs); nx=un(randsample(length(un),1,true,probs));
      path=[path,nx]; un(un==nx)=[]; last=nx;
    end
    L=sum(diag(D(path,path([2:end,1]))));
    if L<bestL, bestL=L; end
  end
  tau=tau*0.9;
end
fprintf('蚁群最短巡回=%.2f\n', bestL);

配套文件：m_aco.m（基础 MATLAB / Octave 即可运行）

九、练手数据集（可下载）

12 个城市平面坐标。用于蚁群算法求解 TSP。

字段：city, x, y
行数：12 行
下载：aco.csv

十、常见误区与避坑清单

参数 α/β/ρ 敏感
早期信息素少易随机
大规模慢

十一、结果怎么解读

最短路径长度即结果。

十二、常与谁搭配

与 SA / GA 同类。

十三、论文写作技巧（怎么把它写进论文）

把 蚁群算法 ACO 写进论文，核心不是堆公式，而是讲清「为什么用它、结果怎么呈现、如何对比」三件事。

1. 动机怎么写（为什么用它而不是别的）

先把问题「数学化」：决策变量、目标函数、约束条件——这一步写清楚比算法本身更重要。再说明为何用蚁群算法 ACO 求解：连续可导用梯度 / 解析法，组合 / 非凸 / 黑箱用启发式（GA / PSO / SA）。

2. 结果怎么写（图表与指标）

放「收敛曲线（迭代 vs 目标值）」+「最优解参数表」+「约束是否满足」三件套。若是多目标，放 Pareto 前沿散点图。

3. 可直接套用的写作话术

中文模板：针对<问题>，本文采用 蚁群算法 ACO 进行路径 / 组合优化(TSP / 网络路由 / 调度)。该方法能够自动刻画<优势>，在处理<场景>时相较<对比方法>更具<特点>。
英文模板：To address , we adopt 蚁群算法 ACO to 路径 / 组合优化(TSP / 网络路由 / 调度). Benefiting from its ability to , it outperforms on .

4. 同类易踩的写作坑

务必说明约束是否全部满足、是否陷入局部最优（可多次随机初始化对比）；别把无约束结果当约束最优报。

5. 典型论文段落范例（可直接参考 / 改写）

下面是一段可直接套用的论文表述，已按本算法定制，填空处（…）替换成你的真实数值即可。

将配送中心选址建模为带容量约束的总成本最小化问题，本文采用蚁群算法 ACO 求解，得到 5 个选址及其服务分配方案，目标值较贪婪启发式降低 12.4%，且全部约束满足。

We formulate the distribution center location as a total-cost minimization problem with capacity constraints and solve it via 蚁群算法 ACO, yielding 5 sites and their service assignments. The objective is 12.4% lower than a greedy heuristic while satisfying all constraints.

十四、相关手册（延伸阅读）

模拟退火 SA · 优化类
遗传算法 GA · 优化类

十五、本手册导航

上一篇：多目标规划 · 优化类
下一篇：支持向量机 SVM · 聚类分类
返回：算法深度手册库｜资料站首页

本手册由「算法深度手册生成器」自动产出，配套提供 Python / MATLAB 双版本示例与可下载练手数据集。