2.2 蚁群算法的基本框架

在文献[4]中，Dorigo和Caro给出了一个针对组合优化问题的蚁群算法基本框架。组合优化问题通常可以由三元组（S, f, Ω）表示，其中S是候选解的集合；f是目标函数，对于任意s∈S有目标函数值f（s）; Ω是约束条件集合。其优化目标是寻找全局最优可行解。

组合优化问题（S, f, Ω）可以映射为具有如下特征的问题：

（1）有限集合ζ= {c1, c2, …, cNC}表示优化问题的组成元素（component）。

（2）根据所有的可能序列x=＜ci, cj, …, ck, …＞定义问题的有限状态集合χ，其中ci, cj, …, ck是ζ的元素。序列的长度定义为|x|，表示序列中元素的个数，序列长度的最大值l＜±∞。

（3）候选解集合S是有限状态集合χ的子集，即S⊆χ。

（4）可行状态集合，由满足约束条件集合Ω的序列x∈χ构成。

（5）非空集合S*是最优解组成的集合，且S*⊆S。

通过以上描述，组合优化问题可以通过图的形式表示为G=（ζ, L），其中，ζ表示结点集合，L表示所有结点的连接弧集合。从而，待求解的问题转化为在一个图中搜索最小代价路径问题。问题的解对应于G上的可行序列（可行路径）。它的最优解即为G上满足约束条件的最短路径，即目标函数的最优解。

蚁群算法是一个迭代算法，在每一次迭代中执行如下操作：一群蚂蚁同步或异步地在问题的相邻状态之间移动，它们利用关联在每个状态中的信息素和启发信息，采用状态转移规则选择移动方向，逐步构造出问题的可行解；在每只蚂蚁构造解时，可以局部地更新信息素；在所有蚂蚁都完成了解的构造之后，依据获得的解对信息素全局更新。这个迭代过程持续到某个停止条件被满足为止。常用的停止条件有最大运行时间或者允许构造解的最大数目等。用不同的方法对蚁群算法总框架的各部分进行具体化，可以产生不同的蚁群算法。图2-3为蚁群算法的标准流程图。

图2-3 蚁群算法的标准流程