,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 的 MMAS‚ACS 和 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 A‚Dorigo M‚Maniezzo V．Distributed optimization by ant colonies ∥ Proc of the First European Conf on Artificial Life．Paris：France Elsevier publishing‚1992：134 ［2］ Dorigo M‚Maniezzo V‚Colorni A．Ant system：optimization by a colony of cooperating agents．IEEE Trans Syst Man Cy￾bern B‚1996‚26（1）：29 ［3］ Bonabeau E‚Dorigo M‚Theraulaz G．Inspiration for opti￾mization from social insect behaviour．Nature‚2000‚406（6）： 39 ［4］ Gravel M‚Price W L‚Gagne C．Scheduling continuous cast￾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 resource-constrained project scheduling．IEEE Trans Evol Comput‚2002‚6（4）：333 ［6］ Gutjah．ACO algorithms with guaranteed convergence to the optimal solution．Inf Process Lett‚2002‚82（3）：145 ［7］ Stützle T‚Hoos H H．MAX-MIN ant system．Future Gener Comput Syst‚2000‚16：889 ［8］ Dorigo M‚Gambardella L M．Ant colony system：a coopera￾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‚LÜZhimin‚XU Jinw u National Engineering Research Center for Advanced Rolling Technology‚University of Science and Technology Beijing‚Beijing100083‚China ABSTRACT 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 globa-l 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 ·798· 北 京 科 技 大 学 学 报 2006年第8期