D0I:10.13374/1.issnl00I53.2006.08.020 第28卷第8期 北京科技大学学报 Vol.28 No.8 2006年8月 Journal of University of Science and Technology Beijing Aug.2006 带有侦察子群的蚁群系统 许剑吕志民徐金梧 北京科技大学高效轧制国家工程研究中心，北京100083 摘要针对基本蚁群算法收敛速度慢，容易出现停滞等缺陷，提出一种新的蚁群优化算法一 带有侦察子群的蚁群系统.该算法从整个蚁群中分离出一部分蚂蚁组成侦察子群，在优化过程中 侦察子群以一定概率做随机搜索，提高了解的多样性：在信息素更新策略上同时使用本代和全局 最优蚂蚁，兼顾了本代和历史的搜索成果：同时还采用LK变异算子，对每次搜索的解进行局部优 化·最后对三个典型T$P实例进行了仿真实验，结果表明新的算法不仅能够克服早熟现象，而且 能够大大加快收敛速度 关键词蚁群系统：蚁群算法：蚁群优化：随机搜索：变异算子 分类号TP18 蚁群算法是20世纪90年代由意大利科学家 Macro Dorigo等人提出一种新型的拟生态系统算 1AS和MMAS 法[1-3]，最初的蚁群算法称为蚁群系统(ant sys- AS基本思想是模仿蚂蚁依赖信息素 tem).该算法具有很强的通用性、鲁棒性、分布式 (pheromone)进行通信而显示出的社会性行为，在 计算、易于与其他方法相结合等优点，近年来在 智能体定义的基础上，由一个贪心法指导下的自 离散型组合优化问题中有突出的表现[4]，引起 催化过程引导每个智能体的行动，它是一种随机 了学者们的普遍关注 的通用试探法， 2002年Gutjah证明了AC0(ant colony opti 假设n个城市，m个蚂蚁，任意两城市i,j mization)类算法的收敛性6]，虽然蚁群算法有许 之间的距离为d,可(t)表示两个城市间信息素 多优点，但也存在着许多缺陷，如与其他方法相 的浓度，t为迭代次数，P(t)表示第t代蚂蚁k 比，该算法一般需要较长的搜索时间，并且容易出 的转移概率： 现停滞现象，即搜索进行到一定程度后，所有个体 [ca(t)][nl2 所发现的解完全一致，因此，针对这些缺点许多 P(t) 3[(t)][]8 (1) 学者对蚁群算法提出了改进，如Stitzle和Hoos 0, 提出的最大最小蚁群系统(max min ant system, j∈z MMAS)[门，Dorigo和Gambardella提出的ACS 式中，j表示未访问过的城市，：表示已经访问过 (ant colony system)8],还有文献[9]提出的一种 城市的集合，=1/dg称为边弧的能见度，a为 信息素浓度的重要程度，3为可见度的相对重要 相遇算法等，这些算法对基本蚁群(A$)的性能都 程度 有了不同程度的提高 信息素浓度更新公式为： 本文在AS和MMAS的基础上提出一种带 有侦察子群的蚁群系统(ant system with scouting (+1)=()十∑△(0) (2) =1 subgroup,ASSS),从几个方面对蚁群算法进行了 式中，△(t)表示第t代蚂蚁k访问过支路(i, 改进，并从TSPLIB库中选取三个有代表性的实 j)后释放的信息浓度，P为信息素挥发因子(O≤P 例对算法的性能进行了验证 ≤1)： △(t)= 收稿日期：2005-04-19修回日期：2005-10-31 w/Lx(), 如果蚂蚁k访问过边弧(i,j) 基金项目：国家自然科学基金资助项目(N。.70371057) 否则 作者简介：许剑(1973一)，男，博士研究生：徐金梧(1949-)， 男，教授，博士 (3)带有侦察子群的蚁群系统 许 剑 吕志民 徐金梧 北京科技大学高效轧制国家工程研究中心‚北京100083 摘 要 针对基本蚁群算法收敛速度慢、容易出现停滞等缺陷‚提出一种新的蚁群优化算法——— 带有侦察子群的蚁群系统．该算法从整个蚁群中分离出一部分蚂蚁组成侦察子群‚在优化过程中 侦察子群以一定概率做随机搜索‚提高了解的多样性；在信息素更新策略上同时使用本代和全局 最优蚂蚁‚兼顾了本代和历史的搜索成果；同时还采用 LK 变异算子‚对每次搜索的解进行局部优 化．最后对三个典型 TSP 实例进行了仿真实验‚结果表明新的算法不仅能够克服早熟现象‚而且 能够大大加快收敛速度． 关键词 蚁群系统；蚁群算法；蚁群优化；随机搜索；变异算子 分类号 TP18 收稿日期：20050419 修回日期：20051031 基金项目：国家自然科学基金资助项目（No．70371057） 作者简介：许 剑（1973—）‚男‚博士研究生；徐金梧（1949—）‚ 男‚教授‚博士 蚁群算法是20世纪90年代由意大利科学家 Macro Dorigo 等人提出一种新型的拟生态系统算 法［13］‚最初的蚁群算法称为蚁群系统（ant sys￾tem）．该算法具有很强的通用性、鲁棒性、分布式 计算、易于与其他方法相结合等优点．近年来在 离散型组合优化问题中有突出的表现［45］‚引起 了学者们的普遍关注． 2002年 Gutjah 证明了 ACO（ant colony opti￾mization）类算法的收敛性［6］．虽然蚁群算法有许 多优点‚但也存在着许多缺陷‚如与其他方法相 比‚该算法一般需要较长的搜索时间‚并且容易出 现停滞现象‚即搜索进行到一定程度后‚所有个体 所发现的解完全一致．因此‚针对这些缺点许多 学者对蚁群算法提出了改进‚如 Stützle 和 Hoos 提出的最大最小蚁群系统（max-min ant system‚ MMAS） ［7］‚Dorigo 和 Gambardella 提出的 ACS （ant colony system） ［8］‚还有文献［9］提出的一种 相遇算法等‚这些算法对基本蚁群（AS）的性能都 有了不同程度的提高． 本文在 AS 和 MMAS 的基础上提出一种带 有侦察子群的蚁群系统（ant system with scouting subgroup‚ASSS）‚从几个方面对蚁群算法进行了 改进‚并从 TSPLIB 库中选取三个有代表性的实 例对算法的性能进行了验证． 1 AS 和 MMAS AS 基 本 思 想 是 模 仿 蚂 蚁 依 赖 信 息 素 （pheromone）进行通信而显示出的社会性行为‚在 智能体定义的基础上‚由一个贪心法指导下的自 催化过程引导每个智能体的行动‚它是一种随机 的通用试探法． 假设 n 个城市‚m 个蚂蚁‚任意两城市 i‚j 之间的距离为 dij‚τij （ t）表示两个城市间信息素 的浓度‚t 为迭代次数．P k ij （ t）表示第 t 代蚂蚁 k 的转移概率： P k ij（ t）＝ ［τij（ t）］ α［ηij ］ β ∑l∈／z ［τil（ t）］ α［ηil］ β‚ j ∈／z 0‚ j ∈ z （1） 式中‚j 表示未访问过的城市‚z 表示已经访问过 城市的集合‚ηij ＝1／dij 称为边弧的能见度‚α为 信息素浓度的重要程度‚β为可见度的相对重要 程度． 信息素浓度更新公式为： τij（ t＋1）＝ρτij（ t）＋ ∑ m k＝1 Δτk ij（ t） （2） 式中‚Δτk ij（ t）表示第 t 代蚂蚁 k 访问过支路（ i‚ j）后释放的信息浓度‚ρ为信息素挥发因子（0≤ρ ≤1）； Δτij（ t）＝ w／Lk（ t）‚ 如果蚂蚁 k 访问过边弧（ i‚j） 0‚ 否则 （3） 第28卷 第8期 2006年 8月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．28No．8 Aug．2006 DOI:10．13374／j．issn1001－053x．2006．08．020