蚁群系统（ACS）
2026/3/21约 1567 字大约 5 分钟
蚁群系统（ACS）
名称
蚁群系统（Ant Colony System, ACS），蚁群优化（Ant Colony Optimization, ACO）
分类
蚁群系统是一种受蚂蚁觅食行为启发的元启发式优化算法，隶属于群体智能领域，而群体智能又是计算智能的一个子领域。它与其他蚁群优化算法密切相关，例如蚁群系统基础模型（Ant System, AS）和最大最小蚁群系统（Max-Min Ant System, MMAS）。
- 计算智能
- 生物启发计算
- 群体智能
- 蚁群优化（ACO）
- 蚁群系统基础模型（AS）
- 蚁群系统（ACS）
- 最大最小蚁群系统（MMAS）
- 蚁群优化（ACO）
- 群体智能
- 生物启发计算
策略
基于信息素的优化
在蚁群系统中，人工蚂蚁通过迭代地依据路径上的信息素强度和启发式信息来选择解的组成部分，从而逐步构造优化问题的候选解。信息素轨迹会随着蚂蚁搜索过程中所获得解的质量而动态更新，从而引导搜索朝向解空间中更有潜力的区域推进。
局部搜索
蚁群系统通常引入局部搜索机制，以进一步改进蚂蚁构造得到的候选解。局部搜索策略一般依赖于具体问题本身，其目的在于通过探索当前解的邻域结构来获得质量更高的解。
信息素更新
蚁群系统中的信息素更新通常包括两种方式：局部更新和全局更新。局部更新由每只蚂蚁在完成解构造后执行，通过适度降低已访问路径上的信息素浓度来增强探索能力；全局更新则由当前最优蚂蚁执行，对历史最优解所对应路径上的信息素进行强化，以提升优质路径被再次选择的概率。
过程
数据结构：
- 信息素矩阵：用于存储问题各组成部分对应的信息素浓度。
- 启发式信息：用于引导蚂蚁决策的、与具体问题相关的信息，通常反映选择某一组成部分的吸引程度。
参数：
- 蚂蚁数量：算法中使用的人工蚂蚁个体数目。
- 阿尔法（Alpha）：信息素对蚂蚁决策影响程度的控制参数。
- 贝塔（Beta）：启发式信息对蚂蚁决策影响程度的控制参数。
- 蒸发率：信息素随时间衰减的速率。
- Q：信息素更新过程中使用的常数。
初始化
- 设定算法参数：蚂蚁数量、alpha、beta、蒸发率以及 Q。
- 以较小的正值初始化信息素矩阵。
- 根据具体问题初始化启发式信息。
解的构造
- 对每只蚂蚁：
- 根据信息素轨迹和启发式信息选择起始组成部分。
- 当解尚未构造完成时：
- 根据信息素轨迹和启发式信息选择下一个组成部分。
- 对所选择的组成部分执行局部信息素更新。
- 对构造完成的解进行局部搜索改进（可选）。
信息素更新
- 从所有蚂蚁构造的解中选出最优解。
- 更新信息素矩阵：
- 按照蒸发率对信息素进行挥发衰减。
- 对最优解对应路径上的信息素进行强化。
终止条件
- 若满足终止条件（例如达到最大迭代次数，或解的质量达到预期要求），则停止算法。
- 否则，返回“解的构造”步骤继续执行。
注意事项
优点：
- 蚁群系统在求解组合优化问题方面表现出较高有效性，尤其适用于具有图结构特征的问题，例如旅行商问题。
- 它能够适应动态优化问题，即当最优解随时间变化时仍具备一定的适应能力。
- 蚁群系统具有较好的可扩展性，并可通过并行化方式处理大规模问题。
缺点：
- 蚁群系统的性能对参数取值较为敏感，因此通常需要进行细致的参数调节。
- 若探索与开发之间的平衡控制不当，算法可能会过早收敛到次优解。
- 对于组成部分数量较多的问题，蚁群系统的计算开销可能较高。
启发式经验
参数设置
- 蚂蚁数量应根据问题规模与复杂度进行设置。常见经验是将蚂蚁数量设为与问题组成部分数量大致相当。
- 阿尔法（Alpha）与 Beta 的取值应当在信息素与启发式信息之间取得平衡。其典型取值范围通常为 1 到 5。
- 蒸发率一般设为较小数值，通常在 0.01 到 0.1 之间，以便逐步遗忘旧的信息素轨迹。
- Q 的取值应结合目标函数值的量级确定；为简化处理，在很多情况下可直接设为 1。
初始化
- 初始信息素浓度应设为较小的正值，以促进算法初期的充分探索。一个常见经验是将其设为问题组成部分数量的倒数。
局部搜索
- 局部搜索策略的具体选取依赖于所求解的问题类型。对于旅行商问题，常用方法包括 2-opt、3-opt 以及最近邻搜索等。
- 局部搜索不宜过于频繁地使用，以避免带来过高的计算代价。常见经验是仅对部分构造解进行局部搜索，例如在每轮迭代中仅对最优解执行局部改进。
终止准则
- 最大迭代次数应结合问题规模与可用计算资源进行设定。常见经验是将迭代次数设置为与问题组成部分数量平方成比例的水平。
- 另一种常用终止准则是：当当前最优解在连续若干次迭代中均未得到改进时，认为算法已趋于收敛并终止运行。