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 system）．该算法具有很强的通用性、鲁棒性、分布式 计算、易于与其他方法相结合等优点．近年来在 离散型组合优化问题中有突出的表现［45］引起 了学者们的普遍关注． 2002年 Gutjah 证明了 ACO（ant colony optimization）类算法的收敛性［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 subgroupASSS）从几个方面对蚁群算法进行了 改进并从 TSPLIB 库中选取三个有代表性的实 例对算法的性能进行了验证． 1 AS 和 MMAS AS 基 本 思 想 是 模 仿 蚂 蚁 依 赖 信 息 素 （pheromone）进行通信而显示出的社会性行为在 智能体定义的基础上由一个贪心法指导下的自 催化过程引导每个智能体的行动它是一种随机 的通用试探法． 假设 n 个城市m 个蚂蚁任意两城市 ij 之间的距离为 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 访问过边弧（ ij） 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
Vol.28 No.8 许剑等：带有侦察子群的蚁群系统 .795. 式中，心为一个常数，表示蚂蚁完成一次完整的 同时在迭代进程中，若出现停滞现象，可加大Q0 路径搜索后释放的信息素的总量；Lk(t)表示第k 或mg 只蚂蚁环游路径长度， 确定性选择保证大部分蚂蚁会走“主干道”， MMAS与AS的主要区别是：(I)每次迭代中 而侦察子群保证始终有一部分蚂蚁游历在外，在 只允许表现最好的蚂蚁更新路径上的信息素：(2) 搜索过程中动态的调整确定性选择概率、侦察子 为了防止过早的停滞现象，限定了痕迹浓度允许 群的大小和侦察子群随机概率，正是它们的共同 值的上下限[tmin,mm]:(3)在算法启动时将所有 作用才使ASSS具有更强的全局搜索能力， 支路上的痕迹浓度初始化为最大值ax;(4)采用 为了衡量解的多样性，特引入分散度Y,其定 了平滑机制(PTS),痕迹浓度的增加正比于max 义为某一代中每个解到其均值的绝对偏差的平均 和当前浓度(t)之差. 值.第t代解的分散度Y(t)计算公式为： 2带有侦察子群的蚁群系统(ASSS) ()g(! (5) 2.1带有侦察子群的状态转移规则 式中，Lk为第k只蚂蚁的周游长度，avg(t)为第t 现有的蚁群算法都是整个蚁群采用同一个转 代所有蚂蚁周游长度的均值.很明显分散度Y越 移规则，而实际上真实世界的蚁群是有明确分工 大，则说明解的分布越分散，解的多样性越好，反 的，总是有一小部分蚂蚁游历在大部队之外，他们 之亦然 的任务就是探询新的食物源或更好的路径，受此 2.2信息素更新策略 启发，本文提出一种与真实蚁群更加相符的带有 AS是对所有的蚂蚁进行全局更新，MMAS 侦察子群的状态转移规则，也就是说在整个蚁群 是仅对最优的蚂蚁进行更新，最优的蚂蚁可以是 中分出一个探路子群，这个子群以一定概率脱离 一次循环中最优的蚂蚁S,也可以是所有循环中 “主干道”去开辟新的路径，这样在保证算法收敛 最好的蚂蚁S中，只能选择其中之一，选择S有 的同时，增加了解的多样性，有利于算法跳出局部 助于跳出局部最优但降低了收敛速度，选择S中 最优，修改后的状态转移公式如下： 可以提高收敛速度却容易陷入局部最优.鉴于上 P(t)= 述分析，本文提出信息素更新策略为：同时选择 y/∑ k∈S,Q≤Q0,jZ S中和S的路径进行全局信息素更新，且相同的 1任z 边弧只更新一次，修改后的信息素更新公式如 arg max[奇()]”.[专， 0>01.jz 下： 、喻()， 其他 (4) +1)=()+a= 式中，Q是一个[0,1]随机变量，在蚂蚁k选择下 (t)十L驰 (Lh)2 (6) 一个城市之前由随机实验获得，Q0和Q1是事先 设定的阈值且Q0Q1,则 局部最优的风险， 无论蚂蚁k是否属于侦察子群，选择城市时都按 2.3采用LK变异算子 取最大值的情况转移，Q1称为确定概率；其他情 Lin&Kernighan算法是l971年由Lin和 况，则按式(1)的转移概率转移. Kernighan提出的一种解决TSP问题的有效的启 Q0,Q1和m。并不是一成不变，可以随着迭 发式方法，它是在k一opt局部搜索算法(local 代的进程动态调整：在迭代的开始阶段，为了增加 search)的基础上通过改变k来实现的， 解的多样性，可适当增大Q0、减小Q1;随着迭代 由于新的算法引入了侦察子群，增加了每一 的深入，为了加速收敛可适当减小Q0、增大Q1; 代解的多样性，使算法很容易跳出局部最优，但跳
式中w 为一个常数表示蚂蚁完成一次完整的 路径搜索后释放的信息素的总量；Lk（ t）表示第 k 只蚂蚁环游路径长度． MMAS 与 AS 的主要区别是：（1）每次迭代中 只允许表现最好的蚂蚁更新路径上的信息素；（2） 为了防止过早的停滞现象限定了痕迹浓度允许 值的上下限［τminτmax ］；（3）在算法启动时将所有 支路上的痕迹浓度初始化为最大值 τmax；（4）采用 了平滑机制（PTS）痕迹浓度的增加正比于 τmax 和当前浓度 τij（ t）之差． 2 带有侦察子群的蚁群系统（ASSS） 2∙1 带有侦察子群的状态转移规则 现有的蚁群算法都是整个蚁群采用同一个转 移规则而实际上真实世界的蚁群是有明确分工 的总是有一小部分蚂蚁游历在大部队之外他们 的任务就是探询新的食物源或更好的路径．受此 启发本文提出一种与真实蚁群更加相符的带有 侦察子群的状态转移规则也就是说在整个蚁群 中分出一个探路子群这个子群以一定概率脱离 “主干道”去开辟新的路径．这样在保证算法收敛 的同时增加了解的多样性有利于算法跳出局部 最优．修改后的状态转移公式如下： P k ij（ t）＝ ηij／∑l∈／z ηil k ∈ SQ ≤ Q0j ∈／Z arg max｛［τ k ij（ t）］ α·［η k ij ］ β｝ Q ＞ Q1j ∈／Z P k ij（ t） 其他 （4） 式中Q 是一个［01］随机变量在蚂蚁 k 选择下 一个城市之前由随机实验获得Q0 和 Q1 是事先 设定的阈值且 Q0＜ Q1Q0Q1∈［01］．S 是侦 察子群子群中蚂蚁可以随机选定或指定子群大 小 ms 根据整个蚁群规模而定并可适当改变．蚂 蚁 k 在选择下一个城市之前先进行一次随机实 验获得 Q如果蚂蚁 k 属于侦察子群且 Q≤ Q0 则依式中第一项计算出的概率随机选择下一个城 市Q0 称为侦察子群随机概率；如果 Q＞ Q1则 无论蚂蚁 k 是否属于侦察子群选择城市时都按 取最大值的情况转移Q1 称为确定概率；其他情 况则按式（1）的转移概率转移． Q0Q1 和 ms 并不是一成不变可以随着迭 代的进程动态调整：在迭代的开始阶段为了增加 解的多样性可适当增大 Q0、减小 Q1；随着迭代 的深入为了加速收敛可适当减小 Q0、增大 Q1； 同时在迭代进程中若出现停滞现象可加大 Q0 或 ms． 确定性选择保证大部分蚂蚁会走“主干道” 而侦察子群保证始终有一部分蚂蚁游历在外在 搜索过程中动态的调整确定性选择概率、侦察子 群的大小和侦察子群随机概率正是它们的共同 作用才使 ASSS 具有更强的全局搜索能力． 为了衡量解的多样性特引入分散度 γ其定 义为某一代中每个解到其均值的绝对偏差的平均 值．第 t 代解的分散度γ（ t）计算公式为： γ（ t）＝ 1 m ∑ m k＝1 ｜Lk—avg（ t）｜ （5） 式中Lk 为第 k 只蚂蚁的周游长度avg（ t）为第 t 代所有蚂蚁周游长度的均值．很明显分散度 γ越 大则说明解的分布越分散解的多样性越好反 之亦然． 2∙2 信息素更新策略 AS 是对所有的蚂蚁进行全局更新MMAS 是仅对最优的蚂蚁进行更新最优的蚂蚁可以是 一次循环中最优的蚂蚁 S ib也可以是所有循环中 最好的蚂蚁 S gb只能选择其中之一选择 S ib有 助于跳出局部最优但降低了收敛速度选择 S gb 可以提高收敛速度却容易陷入局部最优．鉴于上 述分析本文提出信息素更新策略为：同时选择 S gb和 S ib的路径进行全局信息素更新且相同的 边弧只更新一次．修改后的信息素更新公式如 下： τij（ t＋1）＝ρτij（ t）＋ L gb L bestΔτbest ij ＝ ρτij（ t）＋ L gb （ L best ） 2 （6） L best＝ L gb （ ij）∈ T gb L ib （ ij）∈／T gb（ ij）∈ T ib （7） 式中T gb和 T ib分别对应着 S gb和 S ib的环游路 径长度分别为 L gb和 L ib．信息素更新浓度与 L gb成正比与（ L best ） 2 成反比这样即保留了前面 循环的成果提高了收敛速度同时又降低了陷入 局部最优的风险． 2∙3 采用 LK 变异算子 Lin＆Kernighan 算 法 是 1971 年 由 Lin 和 Kernighan 提出的一种解决 TSP 问题的有效的启 发式方法它是在 k—opt 局部搜索算法（local search）的基础上通过改变 k 来实现的． 由于新的算法引入了侦察子群增加了每一 代解的多样性使算法很容易跳出局部最优但跳 Vol．28No．8 许剑等： 带有侦察子群的蚁群系统 ·795·
.796 北京科技大学学报 2006年第8期 出局部最优后到寻找全局最优又要化费大量的时 最短的环游路径T中=T山；否则，L中，T中保持 间.因此引入LK变异算子，充分利用LK算法超 不变 强的局部搜索能力，在收敛到一定代数时，选择一 Step7以式(6)和式(7)更新信息素浓度， 定数量的解进行变异，从而进一步缩短解路线的 Step8判断是否出现停滞：若出现停滞，则 长度，以加快蚁群算法的收敛速度， 增大Qo或me;否则，转到Step9. 2.4ASSS算法一般步骤 Step9判断是否满足迭代终止条件：若nc Step1初始化：从m只蚂蚁中随机选择m <ncmax,tabu[k]复位，转到Step2,否则转到Step 个蚂蚁组成侦察子群S,ms=int[m/h],h∈[l, 10. m]然后确定Q0,Q1的初值，其余初始化与 Step 10输出最优解 MMAS算法相同(a,B,P,D,最大迭代次数 3 实验结果及效果分析 ncmx,禁忌表tabu[k],Tma,Tmin) Step2开始迭代：迭代次数nc十1. 由于TSP问题曾被许多文献用于检验蚁群 Step3蚂蚁环游： 算法，而且TSP问题又可以推广到许多组合优化 (1)根据迭代进程，确定ms,Qo,Q1的值； 领域，因此从TSPLIB库中选取中等规模的三个 (2)随机实验获得Q; TSP实例进行测试，来检验本文的改进算法，分 (3)蚂蚁k以式(4)和式(1)计算的转移概 别为eil51,kroal00和dl98,后面的数字为城 率，从当前城市i转移到下一个城市 市数. (4)循环进行(1)一(3)，直到所有的蚂蚁都 除非特别注明，以下实验默认参数设置为： 完成环游. a=1,B=5,p=0.9,0=1,m=20.Tmx和 Step4计算本代最短的环游长度Lb及对 tmm的值采用文献[7]中的公式动态计算，迭代次 应的最短路径T. 数为城市数的2倍 Step5LK变异运算：根据事先设定的开始 3.1Qo,Q1和m的影响 变异界限值，若满足则继续，否则转到Step7. 因Q0,Q1和m。组合实验数据较多，在此只 设允许最大交换边数为kmr,LK最大循环 能列出部分实验结果，实验中Q0,Q1和m,确定 次数为n“,选择T并按一定比例接收其他解 规则为：1ncma/5次迭代，Q0,Q1和me不变； 组成变异集C,从C中依次选择各解作为变异初 ncm/5~ncmx次选代，Q0=Q0-0.2,Q1= 始路径To(其长度为L0)·LK变异运算伪代码 Q1一0.2：若出现停滞则Q0=2Q0,m,=2m,否 如下： 则保持原值，为了检验侦察子群对算法的影响， for (j=0;j<nj) 本实验不使用LK变异算子，信息素更新与 被选用过的边集合X=NULL; MMAS一样选用Sb,每个实例独立运算10次取 for(k=l;k<kmax;k十+) 平均值，结果见表1，黑体数字表示每个实例最 {选择边：随机选择xk=(t2k-1,t2k)∈ 好解. T且足X与y%=(t2k,t2k+1)足T,把xk记录到 从表1中可以看出，Q0=0.3,Q1=0.9, Y; m=int[m/4]组合和Q0=0.25,Q1=0.95, 替换边：用y1,…,y来代替x1,…,xk me=int[m/2]组合较好，这是因为若Q0,ms取 得到新的路径TLk及其长度LLK; 值较大，则随机性太强，不利于算法收敛；反过来， 评价解：if（LLk<L0){To=TLK,L0= 若Q0,m,取值太小，侦察子群的作用表现不明 LLK,终止变异} 显，算法容易陷入局部最优 为了与MMAS和AS算法对比，表2给出了 MMAS和AS算法实验结果，该结果是分别采用 当C中所有解都完成变异后，重新计算本代 文献[7]和[2的算法，每个实例独立运算10次的 最短的环游长度L及对应的最短路径T山 平均值。对照表1和表2可以看出，表1中的解 Step6把Lb与历史循环中最短环游长度 大部分好于表2，这说明引入侦察子群后的蚁群 L中相比较：若Lb<L中，则L中=Lb,历史循环中 算法具有更好的全局搜索能力
出局部最优后到寻找全局最优又要化费大量的时 间．因此引入 LK 变异算子充分利用 LK 算法超 强的局部搜索能力在收敛到一定代数时选择一 定数量的解进行变异从而进一步缩短解路线的 长度以加快蚁群算法的收敛速度． 2∙4 ASSS 算法一般步骤 Step1 初始化：从 m 只蚂蚁中随机选择 ms 个蚂蚁组成侦察子群 Sms＝int ［ m／h ］h∈［1 m］然后确定 Q0Q1 的初值其余初始化与 MMAS 算法相同（αβρw最大迭代次数 ncmax禁忌表 tabu［ k］τmaxτmin）． Step2 开始迭代：迭代次数 nc＋1． Step3 蚂蚁环游： （1） 根据迭代进程确定 msQ0Q1 的值； （2） 随机实验获得 Q； （3） 蚂蚁 k 以式（4）和式（1）计算的转移概 率从当前城市 i 转移到下一个城市 j； （4） 循环进行（1）～（3）直到所有的蚂蚁都 完成环游． Step4 计算本代最短的环游长度 L ib及对 应的最短路径 T ib． Step5 LK 变异运算：根据事先设定的开始 变异界限值若满足则继续否则转到 Step7． 设允许最大交换边数为 kmaxLK 最大循环 次数为 n LK max选择 T ib并按一定比例接收其他解 组成变异集 C从 C 中依次选择各解作为变异初 始路径 T0（其长度为 L0）．LK 变异运算伪代码 如下： for （ j＝0；j＜ n LK max；j＋＋） ｛被选用过的边集合 X＝NULL； for （ k＝1；k＜kmax；k＋＋） ｛选择边：随机选择 xk＝（ t2k—1t2k）∈ T 且∈／X 与 yk ＝（ t2kt2k＋1）∈／T把 xk 记录到 X； 替换边：用 y1…yk 来代替 x1…xk 得到新的路径 TLK及其长度 L LK； 评价解：if （ L LK＜ L0）｛T0＝ TLKL0＝ L LK终止变异｝ ｝ ｝ 当 C 中所有解都完成变异后重新计算本代 最短的环游长度 L ib及对应的最短路径 T ib． Step6 把 L ib与历史循环中最短环游长度 L gb相比较：若 L ib＜ L gb则 L gb＝ L ib历史循环中 最短的环游路径 T gb＝ T ib；否则L gbT gb 保持 不变． Step7 以式（6）和式（7）更新信息素浓度． Step8 判断是否出现停滞：若出现停滞则 增大 Q0 或 ms；否则转到 Step9． Step9 判断是否满足迭代终止条件：若 nc ＜ncmaxtabu［ k］复位转到 Step2否则转到 Step 10． Step10 输出最优解． 3 实验结果及效果分析 由于 TSP 问题曾被许多文献用于检验蚁群 算法而且 TSP 问题又可以推广到许多组合优化 领域因此从 TSPLIB 库中选取中等规模的三个 TSP 实例进行测试来检验本文的改进算法分 别为 eil51kroa100 和 d198后面的 数 字 为 城 市数． 除非特别注明以下实验默认参数设置为： α＝1β＝5ρ＝0∙9w ＝1m ＝20．τmax 和 τmin的值采用文献［7］中的公式动态计算迭代次 数为城市数的2倍． 3∙1 Q0Q1 和 ms 的影响 因 Q0Q1 和 ms 组合实验数据较多在此只 能列出部分实验结果．实验中 Q0Q1 和 ms 确定 规则为：1～ncmax／5次迭代Q0Q1 和 ms 不变； ncmax／5～ ncmax 次 迭 代Q0 ＝ Q0—0∙2Q1 ＝ Q1—0∙2；若出现停滞则 Q0＝2Q0ms＝2ms否 则保持原值．为了检验侦察子群对算法的影响 本实验不使 用 LK 变 异 算 子信 息 素 更 新 与 MMAS 一样选用 S ib每个实例独立运算10次取 平均值结果见表1黑体数字表示每个实例最 好解． 从表 1 中可以看出Q0＝0∙3Q1＝0∙9 ms＝int ［ m／4］ 组 合 和 Q0＝0∙25Q1＝0∙95 ms＝int ［ m／2］组合较好．这是因为若 Q0ms 取 值较大则随机性太强不利于算法收敛；反过来 若 Q0ms 取值太小侦察子群的作用表现不明 显算法容易陷入局部最优． 为了与 MMAS 和 AS 算法对比表2给出了 MMAS 和 AS 算法实验结果该结果是分别采用 文献［7］和［2］的算法每个实例独立运算10次的 平均值．对照表1和表2可以看出表1中的解 大部分好于表2这说明引入侦察子群后的蚁群 算法具有更好的全局搜索能力． ·796· 北 京 科 技 大 学 学 报 2006年第8期
Vol.28 No.8 许剑等：带有侦察子群的蚁群系统 797. 表1Qu,Q1和m,的影响 Table 1 Influence of Qo,Qi and m, 最好解 m.=int[m/4] m.=int[m/2] 实例 Q0=0.25 Q0=0.4 Q0=0.25 Q0=0.3 Q0=0.4 (TSPLIB) Q0=0.3 01=0.95 01=0.9 01=0.8 01=0.95 01=0.9 01=0.8 Eil51 426 456.2 455.9 457 455.7 456.3 467.2 Kroal00 21282 23100.3 23074.5 23150.2 23090.8 23099.5 23557 D198 15780 17214.5 17202 17262.4 17205.2 17308.7 17482.3 表2MMAS和AS算法实验结果 表3三种更新策略的比较 Table 2 Test results of MMAS and AS Table 3 Comparison of three kinds of update strategies 实例 MMAS AS 实例 S中+sh sa s中 El51 456.2 486.6 Eli51 455.2 455.9 462.6 Kroa100 23073.0 24650.2 Kroal00 23057.0 23074.5 23834.0 D198 17208.4 18762.4 D198 17192.3 17202.0 17464.5 图1为ASSS和MMAS算法优化eil51解的 表中黑体数字表示每个实例最好解，实验结 分散度比较，其中横坐标为迭代次数，纵坐标为分 果表明，采用S中十s更新策略优于其他两个 散度y.Qo=0.3,Q1=0.9,m=int[m/4],实 策略 验结果表明本算法解的分散度明显大于MMAS 3.3ASSS与其他算法的比较 算法，解的多样性更好 本节实验中ASSS采用上述的Q0=0.3,Q1 40.217 35217 I-ASSS =0.9,m。=int[m/4]组合，信息素更新采用S中 30.217 MMAS 十s山，同时使用LK变异算子，独立运算10次取 25217 世20217 平均值，其结果见图2和表4.表4中MMAS和 15217 AS结果来自文献[7]，ACS结果来自文献[8]， 10.217 5.217 MMAS+Ik结果是文献[7]中MMAS算法采用 50 LK局部优化后的计算结果 迭代次数 508.68m 498.68 I-MMAS 图1ASSS和MMAS算法优化eil51解的分散度比较 蜘488.68 2-ASSS Fig.I Comparison between the data dispersal degrees of ASSS g478.68 and MMAS during optimizing eil51 458.68 448.68 3,2不同信息素更新策略实验结果比较 438.68 428.68 信息素更新策略根据所选用的精英蚂蚁不同 50 100 迭代次数 分三种，分别为S中，S山，s+Sb.表3给出了这 三种更新策略的结果比较，采用上述的Q0=0.3, 图2ASSS和MMAS算法优化eil51收敛特性 Q1=0.9,m,=int[m/4]组合，且不使用LK变异 Fig.2 Convergence characteristic of ASSS and MMAS during 算子，每种策略独立运算10次取平均值 optimizing eil51 表4不同算法计算结果比较 Table 4 Comparison of results of different algorithm 最好解 迭代次数为2n 迭代次数为10000n 实例 (TSPLIB) ASSS MMAS十LK MMAS ACS AS E151 426 426.9(0.21%) 428.1(0.49%) 427.6(0.387%) 428.1(0.49%) 437.3(2.65%) Kroal00 21282 21320.8(0.18%) 21932.1(3.05%) 21320.3(0.18%) 21420.0(0.65%) 22471.4(5.59%) D198 15780 15944.0(1.04%) 16923.2(7.24%) 15972.5(1.22%) 16054.0(1.72%) 16702.1(5.84%)
表1 Q0Q1 和 ms 的影响 Table1 Influence of Q0Q1and ms 实例 最好解 （TSPLIB） ms＝int ［ m／4］ ms＝int ［ m／2］ Q0＝0∙25 Q1＝0∙95 Q0＝0∙3 Q1＝0∙9 Q0＝0∙4 Q1＝0∙8 Q0＝0∙25 Q1＝0∙95 Q0＝0∙3 Q1＝0∙9 Q0＝0∙4 Q1＝0∙8 Eil51 426 456∙2 455∙9 457 455∙7 456∙3 467∙2 Kroa100 21282 23100∙3 23074∙5 23150∙2 23090∙8 23099∙5 23557 D198 15780 17214∙5 17202 17262∙4 17205∙2 17308∙7 17482∙3 表2 MMAS 和 AS 算法实验结果 Table2 Test results of MMAS and AS 实例 MMAS AS Eli51 456∙2 486∙6 Kroa100 23073∙0 24650∙2 D198 17208∙4 18762∙4 图1为 ASSS 和 MMAS 算法优化 eil51解的 分散度比较其中横坐标为迭代次数纵坐标为分 散度 γ．Q0＝0∙3Q1＝0∙9ms＝int ［ m／4］．实 验结果表明本算法解的分散度明显大于 MMAS 算法解的多样性更好． 图1 ASSS 和 MMAS 算法优化 eil51解的分散度比较 Fig．1 Comparison between the data dispersal degrees of ASSS and MMAS during optimizing eil51 3∙2 不同信息素更新策略实验结果比较 信息素更新策略根据所选用的精英蚂蚁不同 分三种分别为 S gbS ibS gb＋S ib．表3给出了这 三种更新策略的结果比较采用上述的 Q0＝0∙3 Q1＝0∙9ms＝int ［ m／4］组合且不使用 LK 变异 算子每种策略独立运算10次取平均值． 表3 三种更新策略的比较 Table3 Comparison of three kinds of update strategies 实例 S gb＋ S ib S ib S gb Eli51 455∙2 455∙9 462∙6 Kroa100 23057∙0 23074∙5 23834∙0 D198 17192∙3 17202∙0 17464∙5 表中黑体数字表示每个实例最好解．实验结 果表明采用 S gb ＋ S ib 更新策略优于其他两个 策略． 3∙3 ASSS 与其他算法的比较 本节实验中 ASSS 采用上述的 Q0＝0∙3Q1 ＝0∙9ms＝int ［ m／4］组合信息素更新采用 S gb ＋S ib同时使用 LK 变异算子独立运算10次取 平均值其结果见图2和表4．表4中 MMAS 和 AS 结果来自文献 ［7］ACS 结果来自文献 ［8］ MMAS＋lk 结果是文献［7］中 MMAS 算法采用 LK 局部优化后的计算结果． 图2 ASSS 和 MMAS 算法优化 eil51收敛特性 Fig．2 Convergence characteristic of ASSS and MMAS during optimizing eil51 表4 不同算法计算结果比较 Table4 Comparison of results of different algorithm 实例 最好解 （TSPLIB） 迭代次数为2n 迭代次数为10000n ASSS MMAS＋LK MMAS ACS AS Eil51 426 426∙9（0∙21％） 428∙1（0∙49％） 427∙6（0∙38％） 428∙1（0∙49％） 437∙3（2∙65％） Kroa100 21282 21320∙8（0∙18％） 21932∙1（3∙05％） 21320∙3（0∙18％） 21420∙0（0∙65％） 22471∙4（5∙59％） D198 15780 15944∙0（1∙04％） 16923∙2（7∙24％） 15972∙5（1∙22％） 16054∙0（1∙72％） 16702∙1（5∙84％） Vol．28No．8 许剑等： 带有侦察子群的蚁群系统 ·797·
,798 北京科技大学学报 2006年第8期 表中括号中的数值是偏离目前公布的最好解 敛速度，能较快地得到全局最优解的较好近似解， 的百分比，黑体数字为每个实例最好解，从表4 是解决组合优化问题特别是大规模优化问题的一 中可以看出：(1)迭代次数为2n的ASSS算法与 种有效算法 迭代次数为10000n的MMAS,ACS和AS相 比，除了kroal1000解的质量稍稍低于MMAS解的 参考文献 质量外，其他实例的解明显优于MMAS和ACS, [1]Colorni A.Dorigo M.Maniezzo V.Distributed optimization 远远胜过AS,(2)在相同的迭代次数内，ASSS算 by ant coloniesProc of the First European Conf on Artificial 法解的质量明显优于MMAS十LK.另外，对于每 Life.Paris:France Elsevier publishing.1992:134 个实例ASSS算法都成功找到了TSPLIB公布的 [2]Dorigo M.Maniezzo V,Colorni A.Ant system:optimization 最好解 by a colony of cooperating agents.IEEE Trans Syst Man Cy- bemB,1996,26(1):29 图2为ASSS和MMAS算法优化Eil51的收 [3]Bonabeau E.Dorigo M.Theraulaz G.Inspiration for opti- 敛特性，其中横坐标为迭代次数，纵坐标为最佳路 mization from social insect behaviour.Nature.2000.406(6): 径长度，从图中可以看出，ASSS算法具有更快的 39 收敛特性 [4]Gravel M.Price W L.Gagne C.Scheduling continuous cast- 结果表明，由于采用上述的改进策略，ASSS ing of aluminum using a multiple objective ant colony optimiza- 算法具有更强的搜索更好解的能力和更快的收敛 tion metaheuristic.Eur J Oper Res,2002.143:218 [5]Merkle D.Middendorf M,Schmeck H.Ant colony optimiza- 速度 tion for resourceconstrained project scheduling.IEEE Trans 4结论 Evol Comput.2002.6(4):333 [6]Gutjah.ACO algorithms with guaranteed convergence to the 本文在MMAS算法的基础上，提出一种带有 optimal solution.Inf Process Lett.2002.82(3):145 侦察子群的蚁群系统(ASSS),在保留MMAS算 [7]St itzle T.Hoos HH.MAX-MIN ant system.Future Gener Comput Syst.2000.16:889 法中最大最小信息素限制的基础上对状态转移规 [8]Dorigo M.Gambardella L M.Ant colony system:a coopera 则和信息素更新策略进行了改进，同时采用LK tive learning approach to the traveling salesman problem. 变异算子，对构造的解进行局部优化，实验表明， IEEE Trans Evol Comput.1997.1(1):53 本文提出的算法不仅增加了解的多样性，有效克 [9]吴斌，史忠植.一种基于蚁群算法的TSP问题分段求解算 服了停滞行为的过早出现，而且能够大大加快收 法.计算机学报，2001,24(12)：1328 An ant system with scouting subgroup XU Jian,LUZhimin,XU Jinwu National Engineering Research Center for Advanced Rolling Technology.University of Science and Technology Beijing.Beijing 100083.China ABSTRACI To solve the disadvantages of the basic ant colony algorithm including slow convergent speed and incidental stagnation behavior,a new ant colony optimization algorithm,named the ant system with scouting subgroup(ASSS),was proposed.In the algorithm a small part of ants were separated and formed a scouting subgroup that random moved at a certain probability to increase results diversity.The pheromone update strategy used the iteration-best -ant and global-best -ant at the same time to make use of both itera- tion fruit and history fruit.LK mutation factor was employed to locally optimize the search results of each step.Three typical traveling salesman problems(TSP)were tested,and the results show that this proposed algorithm can avoid prematurity and speed up convergence. KEY WORDS ant system;ant colony algorithm;ant colony optimization;random search;mutation fac- tor
表中括号中的数值是偏离目前公布的最好解 的百分比黑体数字为每个实例最好解．从表4 中可以看出：（1） 迭代次数为2n 的 ASSS 算法与 迭代次数为10000n 的 MMASACS 和 AS 相 比除了 kroal100解的质量稍稍低于 MMAS 解的 质量外其他实例的解明显优于 MMAS 和 ACS 远远胜过 AS．（2）在相同的迭代次数内ASSS 算 法解的质量明显优于 MMAS＋LK．另外对于每 个实例 ASSS 算法都成功找到了 TSPLIB 公布的 最好解． 图2为 ASSS 和 MMAS 算法优化 Eil51的收 敛特性其中横坐标为迭代次数纵坐标为最佳路 径长度．从图中可以看出ASSS 算法具有更快的 收敛特性． 结果表明由于采用上述的改进策略ASSS 算法具有更强的搜索更好解的能力和更快的收敛 速度． 4 结论 本文在 MMAS 算法的基础上提出一种带有 侦察子群的蚁群系统（ASSS）在保留 MMAS 算 法中最大最小信息素限制的基础上对状态转移规 则和信息素更新策略进行了改进同时采用 LK 变异算子对构造的解进行局部优化．实验表明 本文提出的算法不仅增加了解的多样性有效克 服了停滞行为的过早出现而且能够大大加快收 敛速度能较快地得到全局最优解的较好近似解 是解决组合优化问题特别是大规模优化问题的一 种有效算法． 参 考 文 献 ［1］ Colorni ADorigo MManiezzo V．Distributed optimization by ant colonies ∥ Proc of the First European Conf on Artificial Life．Paris：France Elsevier publishing1992：134 ［2］ Dorigo MManiezzo VColorni A．Ant system：optimization by a colony of cooperating agents．IEEE Trans Syst Man Cybern B199626（1）：29 ［3］ Bonabeau EDorigo MTheraulaz G．Inspiration for optimization from social insect behaviour．Nature2000406（6）： 39 ［4］ Gravel MPrice W LGagne C．Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic．Eur J Oper Res2002143：218 ［5］ Merkle DMiddendorf MSchmeck H．Ant colony optimization for resource-constrained project scheduling．IEEE Trans Evol Comput20026（4）：333 ［6］ Gutjah．ACO algorithms with guaranteed convergence to the optimal solution．Inf Process Lett200282（3）：145 ［7］ Stützle THoos H H．MAX-MIN ant system．Future Gener Comput Syst200016：889 ［8］ Dorigo MGambardella L M．Ant colony system：a cooperative learning approach to the traveling salesman problem． IEEE Trans Evol Comput19971（1）：53 ［9］ 吴斌史忠植．一种基于蚁群算法的 TSP 问题分段求解算 法．计算机学报200124（12）：1328 An ant system with scouting subgroup XU JianLÜZhiminXU Jinw u National Engineering Research Center for Advanced Rolling TechnologyUniversity of Science and Technology BeijingBeijing100083China ABSTRACT To solve the disadvantages of the basic ant colony algorithm including slow convergent speed and incidental stagnation behaviora new ant colony optimization algorithmnamed the ant system with scouting subgroup （ASSS）was proposed．In the algorithm a small part of ants were separated and formed a scouting subgroup that random moved at a certain probability to increase results diversity．The pheromone update strategy used the iteration-best-ant and globa-l best-ant at the same time to make use of both iteration-fruit and history-fruit．LK mutation factor was employed to locally optimize the search results of each step．Three typical traveling salesman problems （TSP） were testedand the results show that this proposed algorithm can avoid prematurity and speed up convergence． KEY WORDS ant system；ant colony algorithm；ant colony optimization；random search；mutation factor ·798· 北 京 科 技 大 学 学 报 2006年第8期