蚁群优化算法——最优解搜索利器

ACS算法得到了进一步发展，成为一个多智能体系统（multi-agent system，MAS），形成了一般化的蚁群优化（ant colony optimization，ACO）算法（Dorigo and Di Caro，1999；Dorigo et al.，1999）。蚁群优化算法的伪代码如下。

蚁群优化算法为求解优化问题提供了一个一般化的算法框架。其中主要包括三个组成部分：（1）人工蚂蚁的产生和活动；（2）信息素挥发机制；（3）守护作业。蚁群优化算法的框架并不限定这三个部分的具体执行方式，可以并行计算独立执行，也可以有信息交互。算法设计者可以针对具体的优化问题进行调整。

人工蚂蚁依据给定的状态转移规则，基于信息素和启发式信息，在顶点间并行移动，逐步构造问题的可行解。例如，在简单蚁群优化（simple ant colony optimization，S-ACO）算法中，蚂蚁k在顶点a选择后续顶点b的概率为（Dorigo and Di Caro，1999）：

在构造解的过程中，或者在完成解的构造后，蚂蚁根据解的质量更新回路上的信息素浓度。在S-ACO算法中，蚂蚁每次释放固定量的信息素：(www.xing528.com)

人工蚂蚁行为机制的详细描述可参见文献（Dorigo and Di Caro，1999）。

信息素挥发机制是为了避免算法过快收敛于局部最优解。信息素挥发可以看成一种遗忘机制，有助于鼓励蚂蚁探索新的解空间。在S-ACO中，采用如下的更新机制：

守护作业（daemon activity）是指单个蚂蚁无法完成的作业。例如一些局部搜索策略，针对最好解的信息素全局更新等。由守护作业执行的信息素更新也被称为离线信息素更新（offline pheromone update）。在ACO算法中，守护作业不是必需的。