蚁群算法

一、直观理解：蚂蚁用信息素在图上「集体学习」好路

蚁群优化（Ant Colony Optimization, ACO）受真实蚂蚁寻路启发：蚂蚁在经过的路径上留下信息素，短而优的路径被重复走得更多，信息素更浓，后续蚂蚁更倾向选择它们，形成正反馈。

算法中，多只「人工蚁」根据

$$P_{ij}\propto [\tau_{ij}]^{\alpha}[\eta_{ij}]^{\beta}$$

在构造图上逐步选择下一步（$\tau$ 信息素，$\eta$ 启发，如 $1/d_{ij}$），完成解后按质量增浓信息素，并全局挥发避免早熟。

ACO 天然适合路径、指派、在图上构造的组合问题，尤其是 TSP 变体。但它仍是启发式：不保证最优，且对参数与信息素更新敏感。

定位（必读）：仅作兜底。标准最短路用 Dijkstra；标准分配用匈牙利/matchpairs；中小 TSP 可用动态规划或 MILP。ACO 用于大规模、复杂约束的构造型组合优化，并必须报告种子、多次运行与基线（最近邻、2-opt 等）。

二、适用场景与优缺点

类型	说明
适用场景	TSP/VRP 变体、图上带复杂约束的路径构造、调度中的排列构造；启发 $\eta$ 易定义。
核心优点	与图结构契合；正反馈强化好边；可融入问题启发；并行构造解。
局限与缺点	参数多（$\alpha,\beta,\rho$）；易停滞；连续优化不是长项；实现与调参成本高于简单局部搜索；无最优证明。

动用前：问题是否其实是最短路/MST/匹配？有无强力局部搜索基线？

三、核心原理

1. 解的构造

每只蚁从起点（或随机城）出发，按概率选未访问节点，直到构成完备解。禁忌表保证可行性（如 TSP 不重复访问）。

2. 转移概率

$$P_{ij}^{k}=\frac{\tau_{ij}^{\alpha}\eta_{ij}^{\beta}}{\sum_{l\in \mathcal{N}_k}\tau_{il}^{\alpha}\eta_{il}^{\beta}},\quad j\in\mathcal{N}_k$$

$\mathcal{N}_k$ 为蚂蚁 $k$ 的可行邻域。

3. 信息素更新（Ant System 示意）

挥发：$\tau\leftarrow (1-\rho)\tau$。

增浓：对边 $(i,j)$ 若被优解使用，

$$\tau_{ij}\leftarrow\tau_{ij}+\frac{Q}{L}$$

$L$ 为路径长。精英策略、最大最小蚂蚁系统（MMAS）等限制 $\tau$ 上下界，减轻停滞。

4. 与局部搜索杂交

ACO 构造后接 2-opt/3-opt，往往比纯 ACO 强得多。报告时应写清是否杂交。

四、关键决策

1. 基线

最近邻、节约算法、纯 2-opt、随机重启局部搜索。ACO 必须赢过或稳定匹配这些基线才有说服力。

2. 参数起点

$\alpha\approx 1,\ \beta\approx 2\sim 5,\ \rho\approx 0.1\sim 0.5$；蚂蚁数约等于城市数或同量级。

3. 评价预算

公平比较看构造解次数或 2-opt 调用次数。

4. 复现

种子、运行次数、最好/均值/方差、最优已知解 gap（若有）。

5. 停用

一旦问题是最短路或可紧 MILP，不用 ACO 充数。

五、MATLAB 示例

TSP 上的简易 Ant System + 2-opt 抛光，对比最近邻。

rng(1);
n = 25;
XY = rand(n, 2);
D = squareform(pdist(XY));
eta = 1 ./ (D + eye(n));  % 启发，对角不用

tourLength = @(tour) sum(D(sub2ind([n n], tour, tour([2:end,1]))));

% 基线：最近邻 + 2-opt
tour = 1; un = true(1,n); un(1)=false;
for k = 2:n
    last = tour(end);
    cand = find(un);
    [~,j] = min(D(last,cand));
    tour(end+1) = cand(j); un(cand(j))=false; %#ok<SAGROW>
end
nnLen = tourLength(tour);
% 简易 2-opt
improved = true;
while improved
    improved = false;
    for i = 1:n-2
        for k = i+1:n-1
            a=tour(i); b=tour(i+1); c=tour(k); d=tour(mod(k,n)+1);
            if D(a,c)+D(b,d) < D(a,b)+D(c,d) - 1e-12
                tour(i+1:k) = tour(k:-1:i+1); improved = true;
            end
        end
    end
end
baseLen = tourLength(tour);
fprintf("NN=%.4f, NN+2opt=%.4f\n", nnLen, baseLen);

% ACO 多次
nRuns = 10; seeds = 12000+(1:nRuns); bests = zeros(nRuns,1);
for r = 1:nRuns
    rng(seeds(r));
    alpha = 1; beta = 5; rho = 0.3; Q = 1;
    nAnt = n; nIter = 80;
    tau = ones(n); 
    globalBest = inf; globalTour = [];
    for it = 1:nIter
        tours = zeros(nAnt, n); lens = zeros(nAnt,1);
        for a = 1:nAnt
            start = randi(n);
            visited = false(1,n); visited(start)=true;
            seq = zeros(1,n); seq(1)=start; cur=start;
            for step = 2:n
                cand = find(~visited);
                prob = (tau(cur,cand).^alpha) .* (eta(cur,cand).^beta);
                prob = prob / sum(prob);
                next = cand(find(rand <= cumsum(prob), 1, "first"));
                seq(step)=next; visited(next)=true; cur=next;
            end
            tours(a,:)=seq; lens(a)=tourLength(seq);
        end
        % 挥发 + 增浓
        tau = (1-rho)*tau;
        for a = 1:nAnt
            seq = tours(a,:); L = lens(a);
            for k = 1:n
                i = seq(k); j = seq(mod(k,n)+1);
                tau(i,j) = tau(i,j) + Q/L; tau(j,i)=tau(i,j);
            end
        end
        [bL, idx] = min(lens);
        if bL < globalBest
            globalBest = bL; globalTour = tours(idx,:);
        end
    end
    % 抛光
    tour = globalTour; improved = true;
    while improved
        improved = false;
        for i = 1:n-2
            for k = i+1:n-1
                a=tour(i); b=tour(i+1); c=tour(k); d=tour(mod(k,n)+1);
                if D(a,c)+D(b,d) < D(a,b)+D(c,d) - 1e-12
                    tour(i+1:k)=tour(k:-1:i+1); improved=true;
                end
            end
        end
    end
    bests(r) = tourLength(tour);
end
fprintf("ACO+2opt %d次 best/mean/std=%.4f/%.4f/%.4f\n", ...
    nRuns, min(bests), mean(bests), std(bests));
fprintf("种子: "); disp(seeds);
fprintf("相对 NN+2opt 改进 %.2f%%\n", 100*(baseLen-min(bests))/baseLen);

六、如何解释结果

应包含：

1. 问题为何不用精确图算法/MILP；
2. $\alpha,\beta,\rho$、蚂蚁数、迭代、是否 MMAS/精英；
3. 是否接局部搜索；
4. 种子与多次统计；
5. 与 NN、2-opt 等基线对照；
6. 路径图与业务费用；
7. 近优声明。

七、常见误区

1. 最短路问题用蚁群

错误选型。Dijkstra 才是正道。

2. 只调到一次漂亮结果

方差可能巨大。

3. 无启发 $\eta$ 或 $\beta=0$

收敛慢且无差别于盲目随机。

4. 信息素爆炸或归零

缺挥发或 $\rho$ 不当；考虑 $\tau$ 上下界。

5. 与 2-opt 比时 2-opt 预算远小

不公平。

6. 宣称生物启发本身等于先进

评审看的是指标与对照，不是故事。

八、小结

蚁群算法的核心思想可以概括为：

多只蚂蚁在图上按信息素与启发概率构造可行解，并通过信息素挥发与增浓形成对优质边的正反馈，从而启发式搜索组合近优解。

它适合复杂构造型路径问题的兜底，不适合替代经典网络精确算法。规范用法强调：基线、种子、多次运行、与局部搜索结合，以及克制的结果表述。