蚁群优化（Ant Colony Optimization, ACO）
蚁群优化以「信息素 + 概率构造」为骨架：在图中（常为有向图、TSP 完全图等）令蚂蚁按与信息素浓度及启发式（如边权倒数）相关的概率逐步构造可行解，再用所得解质量反馈更新信息素；挥发项避免无界累积。属边协作学习式群体方法。见 元启发式总览。
概念与机制要点
图、弧与解：
- 弧 上存非负信息素 ，可理解为「该弧被历史好解选中的证据」强弱。
- 另设与实例有关的可见度 （如取距离的倒数，使短边更醒目）。
- 蚂蚁在「下一步允许选的弧」上逐步选边，每步对 、 的依赖见下节 与 ，直至得到可行解 并求 。
随机成比例（与 、）：选下一弧时，常使未归一化权重与 成正比；在全体可行候选上归一后，才得到条件概率。参数直观：
- 大：更信长期积累在弧上的信息素。
- 大：更信局部启发式（如距离倒数等可见度）。与蚂蚁条数、挥发率一起调节探索与利用。
转移概率（显式式）：设蚂蚁当前位于状态（或结点），下一步允许选择的弧记为以 为起点的候选集 （满足「尚未访问、容量/时间窗等约束」的全体下一弧，依问题定义）。在经典随机比例（random proportional）规则下，选弧 的概率为
若 不在 中则上式不直接给出（概率为 ）。对号边 写时即 AS 中常见的
其中 为当前步下从 可一步到达的可行城市集合。TSP 中常设 （ 为距离）。
注：蚁群系统（ACS）的伪随机比例规则是：在位于 时，以概率 选使 的下一城 ；以概率 仍按上式 做随机成比例抽样。 控制「贪心一步」与「随分布探索」的混合。具体细节以所采用文献/代码版本为准。
挥发与加量（每外轮/每步的抽象）：
- 先对维护到的 做乘性挥发，如 （），淡化旧信息。
- 再按本轮或历史最优解所经弧，对相应 加量 （与 等单调形式见各文献）。
- MMAS 等常对 设上下界，防垄断与停滞。AS、MMAS、ACS 在谁加、局部/全局何时加上不同，实现里择一写清。
主循环（以弧上信息素、单轮为示意单位）
用边 上信息素 与可见度 （如 TSP 中 ， 为距离）。下框是单轮迭代的抽象：外层在「多轮单轮」上重复。各 ACO 变体在 、上下界、局部/全局更新上不同，在实现中定稿。构造步内抽样分布见上节 与 。
▶ 蚁群优化 一轮（多蚂蚁构造 + 信息素更新）
1. 初始化
若首轮，按问题设定 初值（常数或小随机）； 由实例预计算。准备 只蚂蚁，自源点或 TSP 中规定起点出发（多起点策略依实现定稿）。
2. 蚂蚁构造解
对每只蚂蚁在约束下按随机成比例规则逐步延长路径：在下一步可选弧集合中，以正比于 的概率选取下一弧，直至得到完整可行解 ；评价 。对每只蚂蚁的个体极值、群体极值 按实现更新。
3. 信息素挥发
对全体相关弧 ，，标量 为挥发率；若某变体对 有上/下界，在挥发后截断到允许区间（如 MMAS）。
4. 信息素增量
Ant System（多蚂蚁、全局更新）的常用显式写法是：设第 只蚂蚁在本轮走闭合回路，路径长为 。挥发之后，对弧 有
其中常取
为常数（多取 或与规模相关）。精英 AS 仅对本轮或历史最优路径加量；ACS 等则另设局部（蚂蚁每走一步）与全局（回合末按最优或迭代最优）两种 的施加时机与公式，上式是其中「全局、全体蚂蚁」一式的代表；MMAS 等再对 作上下界截断（见上节第 3 步）。
5. 终止
若已满足外轮总迭代、时间、无改进等则停，输出 ；否则回到步骤 2 进入下一轮（蚂蚁重新构造时可共用更新后的 ）。