第1期 夏小云，等：蚁群优化算法的理论研究进展 ·29. 于NP难解组合优化问题本身结构的复杂性，确定 近似比r为：若为最大化问题，r=max f(D) 性算法（穷举法、分支界定、动态规划等）无法保证 ):若为最 在多项式内获得精确解，转而寻求一些近似算 (。也就是说，算法A能获得 小化问题，r=max A(D 法6。蚁群优化作为随机启发式方法，不能期待其 在多项式时间内找到NP-完全（难）优化问题所有实 r一近似比。若r=1,表明算法找到最优解。 例的精确解。实际上，蚁群算法在很多优化问题上 蚁群算法的启发来自于一个蚂蚁群体对食物源 扮演着近似算法的角色，一般用于获得满意解或者 的搜索，是一种杰出而具有代表性的群智能算法，对 近似解。因此蚁群优化算法的近似性能分析就变得 于其算法描述可以参考相关文献[1。AC0算法有 尤为重要。希望在平均多项式时间内获得近似最优 一些不同的变体，为了分析的方便，在当前理论分析 或者可接受的解，对于理解蚁群算法在NP难优化 方面，还是主要考虑一只蚂蚁的情况。下面给出蚁 问题上的工作原理以及寻求其能获得的近似性能非 群优化算法理论研究中用到的一个简单的ACO算 常关键，并将进一步推进蚁群算法的理论研究及应 法(1+1)蚂蚁算法((1+1)Ant Algorithm, 用进展。对于丰富和发展近似算法和组合优化理 (1+1)AA),其类似于演化算法理论分析中的 论，切实有效地解决一些实际问题具有重要现实意 (1+1)EA。不失一般性，考虑最小化问题。 义。 (1+1)AA算法描述如下 1 蚁群优化算法：模型、描述、变体 Algorithm 1:(1+1)AA Begin 1.1优化问题及算法描述 初始化：参数设置，信息素值，选择一个初始解 蚁群算法是一种随机启发式搜索方法，它具有 s,While(不满足终止条件) 较强的鲁棒性，优良的分布式计算机制并易于与其 使用构造过程构建一个新的解s': 他方法相结合等优，点。目前人们对蚁群算法的研究 选择：如果f(s')<f(s),则s=s';更新信息素值。 已经由当初单一的旅行商问题(TSP)领域渗透到了 End while 多个其他应用领域]，由解决一维、静态优化问题 End 发展到解决多维、动态优化问题，由离散求解空间逐 (1+1)AA算法使用简单的爬山选择策略，如果 渐拓展到连续求解空间，使得该群智能算法在科学 当前蚂蚁解的函数值大于新的蚂蚁解的函数值，则 研究及实际问题求解中表现出了巨大的潜力和 当前蚂蚁解被新蚂蚁解替代。以下两节分别介绍理 优势。 论分析中蚁群算法解的构建以及信息素更新机制。 优化问题可以分为两类：连续的优化问题和离 1.2解的构建 散的优化问题。连续的优化问题是指其具有连续的 对于一个给定的优化问题，其解通过蚂蚁在一 变量、经常需要计算导数、使用牛顿方法或者线性规 个具有信息素值的构造图(construction graph)的边 划技术等。本文关注的是离散的优化问题。离散优 上随机游走获得。另外，蚁群算法也使用启发式信 化问题也称为组合优化问题，是指在有限的或者可 息来指导随机游走的方向。蚂蚁从构造图的任意一 数无限的潜在解集中搜索满足给定约束条件的最优 个初始状态出发，随机游走到下一个邻域结点。这 解。然而，组合优化问题通常包含大量的局部极值 个移动是基于概率规则，依赖于信息素和启发式 点，而且许多组合优化问题为NP完全（难）问题。 信息。 一个组合优化问题P通常可描述为一个三元 令G=(V,E)为一给定问题的构造图。To为 组(S,f,2),其中S为给定的由所有状态构成的搜 边e=(u,u)∈E上的信息素值，nao为启发式信 索空间，f:S→R*为目标函数，一般为最大化或者最 息。假设蚂蚁当前所在位置为顶点“，其允许访问 小化；2为可行解满足的约束条件集合。一个可行 的后续结点为N.。蚂蚁在下一步访问结点v∈N, 解s·∈S,如果对于最小化问题有Hs∈S,f(s·)≤ 的概率由以下公式给出： f代s),对于最大化问题有s∈S,f(s·)≥f(s),则称 (ru)·(ne)B s·为一个全局最优解。定义最优解集合为S·二S, Pu=- 算法的目标是从优化问题的可行解集中找到最优解 ∑(r)·(m)日 回eN. s”eS°。 式中：参数α表示蚂蚁在运动过程中所积累的信息 给定算法A和优化问题P,对于一个给定的P 素在指导蚂蚊搜索路径的相对重要性：参数B表示 的实例I,其最优解为f(I)。如果算法A能在多项 路径能见度的相对重要性，即表示启发式信息， 式时间内获得最优解A(I),则算法A在问题P上的 的重要性。于 ＮＰ 难解组合优化问题本身结构的复杂性，确定 性算法（穷举法、分支界定、动态规划等） 无法保证 在多项 式 内 获 得 精 确 解， 转 而 寻 求 一 些 近 似 算 法［６］ 。 蚁群优化作为随机启发式方法，不能期待其 在多项式时间内找到 ＮＰ⁃完全（难）优化问题所有实 例的精确解。 实际上，蚁群算法在很多优化问题上 扮演着近似算法的角色，一般用于获得满意解或者 近似解。 因此蚁群优化算法的近似性能分析就变得 尤为重要。 希望在平均多项式时间内获得近似最优 或者可接受的解，对于理解蚁群算法在 ＮＰ 难优化 问题上的工作原理以及寻求其能获得的近似性能非 常关键，并将进一步推进蚁群算法的理论研究及应 用进展。 对于丰富和发展近似算法和组合优化理 论，切实有效地解决一些实际问题具有重要现实意 义。 １ 蚁群优化算法：模型、描述、变体 １．１ 优化问题及算法描述 蚁群算法是一种随机启发式搜索方法，它具有 较强的鲁棒性，优良的分布式计算机制并易于与其 他方法相结合等优点。 目前人们对蚁群算法的研究 已经由当初单一的旅行商问题（ＴＳＰ）领域渗透到了 多个其他应用领域［２］ ，由解决一维、静态优化问题 发展到解决多维、动态优化问题，由离散求解空间逐 渐拓展到连续求解空间，使得该群智能算法在科学 研究及实际问题求解中表现出了巨大的潜力和 优势。 优化问题可以分为两类：连续的优化问题和离 散的优化问题。 连续的优化问题是指其具有连续的 变量、经常需要计算导数、使用牛顿方法或者线性规 划技术等。 本文关注的是离散的优化问题。 离散优 化问题也称为组合优化问题，是指在有限的或者可 数无限的潜在解集中搜索满足给定约束条件的最优 解。 然而，组合优化问题通常包含大量的局部极值 点，而且许多组合优化问题为 ＮＰ 完全（难）问题。 一个组合优化问题 Ｐ 通常可描述为一个三元 组（ Ｓ，ｆ，Ω），其中 Ｓ 为给定的由所有状态构成的搜 索空间，ｆ：Ｓ→Ｒ ＋为目标函数，一般为最大化或者最 小化；Ω 为可行解满足的约束条件集合。 一个可行 解 ｓ ∗ ∈Ｓ，如果对于最小化问题有∀ｓ∈Ｓ，ｆ（ ｓ ∗ ）≤ ｆ（ｓ），对于最大化问题有∀ｓ∈Ｓ，ｆ（ｓ ∗ ）≥ｆ（ ｓ），则称 ｓ ∗为一个全局最优解。 定义最优解集合为Ｓ ∗⊆Ｓ， 算法的目标是从优化问题的可行解集中找到最优解 ｓ ∗∈Ｓ ∗ 。 给定算法 Ａ 和优化问题 Ｐ，对于一个给定的 Ｐ 的实例 Ｉ，其最优解为 ｆ ｏｐｔ（Ｉ）。 如果算法 Ａ 能在多项 式时间内获得最优解 Ａ（Ｉ），则算法 Ａ 在问题 Ｐ 上的 近似比 ｒ 为：若为最大化问题，ｒ ＝ ｍａｘ Ｉ∈Ｐ ｆ ｏｐｔ（Ｉ） Ａ（Ｉ） ；若为最 小化问题，ｒ ＝ｍａｘ Ｉ∈Ｐ Ａ（Ｉ） ｆ ｏｐｔ（Ｉ） 。 也就是说，算法 Ａ 能获得 ｒ－近似比。 若 ｒ ＝ １，表明算法找到最优解。 蚁群算法的启发来自于一个蚂蚁群体对食物源 的搜索，是一种杰出而具有代表性的群智能算法，对 于其算法描述可以参考相关文献［１⁃５］ 。 ＡＣＯ 算法有 一些不同的变体，为了分析的方便，在当前理论分析 方面，还是主要考虑一只蚂蚁的情况。 下面给出蚁 群优化算法理论研究中用到的一个简单的 ＡＣＯ 算 法 （ １ ＋ １ ） 蚂 蚁 算 法 （（ １ ＋ １ ） Ａｎｔ Ａｌｇｏｒｉｔｈｍ， （１＋１）ＡＡ）， 其 类 似 于 演 化 算 法 理 论 分 析 中 的 （１＋１） ＥＡ。 不 失 一 般 性， 考 虑 最 小 化 问 题。 （１＋１）ＡＡ算法描述如下 Ａｌｇｏｒｉｔｈｍ １： （１＋１）ＡＡ Ｂｅｇｉｎ 初始化：参数设置，信息素值，选择一个初始解 ｓ，Ｗｈｉｌｅ（不满足终止条件） 使用构造过程构建一个新的解 ｓ′； 选择：如果 ｆ（ｓ′）＜ｆ（ｓ），则 ｓ ＝ ｓ′；更新信息素值。 Ｅｎｄ ｗｈｉｌｅ Ｅｎｄ （１＋１）ＡＡ 算法使用简单的爬山选择策略，如果 当前蚂蚁解的函数值大于新的蚂蚁解的函数值，则 当前蚂蚁解被新蚂蚁解替代。 以下两节分别介绍理 论分析中蚁群算法解的构建以及信息素更新机制。 １．２ 解的构建 对于一个给定的优化问题，其解通过蚂蚁在一 个具有信息素值的构造图（ ｃｏｎｓｔｒｕｃｔｉｏｎ ｇｒａｐｈ）的边 上随机游走获得。 另外，蚁群算法也使用启发式信 息来指导随机游走的方向。 蚂蚁从构造图的任意一 个初始状态出发，随机游走到下一个邻域结点。 这 个移动是基于概率规则，依赖于信息素和启发式 信息。 令 Ｇ ＝ （Ｖ，Ｅ）为一给定问题的构造图。 τ（ｕ，ｖ） 为 边 ｅ ＝ （ ｕ，ｖ） ∈Ｅ 上的信息素值，η（ｕ，ｖ） 为启发式信 息。 假设蚂蚁当前所在位置为顶点 ｕ，其允许访问 的后续结点为 Ｎｕ 。 蚂蚁在下一步访问结点 ｖ∈Ｎｕ 的概率由以下公式给出： ｐｕｖ ＝ τ（ｕ，ｖ） ( ) α· η（ｕ，ｖ） ( ) β ω∑∈Ｎｕ τ（ｕ，ω） ( ) α· η（ｕ，ω） ( ) β 式中：参数 α 表示蚂蚁在运动过程中所积累的信息 素在指导蚂蚁搜索路径的相对重要性；参数 β 表示 路径能见度的相对重要性，即表示启发式信息 η（ｕ，ｖ） 的重要性。 第 １ 期 夏小云，等：蚁群优化算法的理论研究进展 ·２９·