第2卷第4期 智能系统学报 Vol.2№4 2007年8月 CAAI Transactions on Intelligent Systems Aug.2007 基于信息素扩散模型解耦控制策略的蚁群算法 冀俊忠，刘椿年，黄振 (北京工业大学计算机学院，北京100022) 摘要：蚁群优化是一种元启发式的随机搜索技术.信息素是蚁群进行交流并实现群集智能的媒介，所以信息素的 更新策略一直是蚁群算法中的一个研究热点.针对信息素扩散的耦合特征，提出一种基于信息素扩散模型解耦控制 策略的蚁群算法.对信息素扩散模型进行改善，建立以蚂蚁经过的路径（直线段）为信源的信息素扩散模型，通过分 析信息素扩散浓度场的耦合性，引入去耦控制策略来修正信息素的更新公式，大量TSP(traveling salesman prob lm)问题的实验表明：该算法不仅能获得更好的解，而且能加快算法的收敛速度. 关键词：蚁群算法：扩散模型：耦合性：解耦控制策略 中图分类号：TP18文献标识码：A文章编号：1673-4785(2007)04-0001-08 An ant colony optimization algorithm based on a decoupling control strategy of pheromone diffusion model JIJum-zhong,LIU Chumnian,HUANG Zhen (College of Computer Science and Technology,Beijing University of Technology,Beijing 100022,China) Abstract:Ant colony optimization (ACO)is a metaheuristic search technique.Pheromones are an impor- tant media ants use to communicate with each other and implement swarm intelligence.Thus research on pheromone updating strategies is a hotspot in ACO.A new decoupling control strategy model of phero- mone diffusion is proposed based on the coupling characteristic of pheromone diffusion.First,the algo- rithm sets up a new pheromone diffusion model with the path that the ant travels as the pheromone source. Then,according to the coupling degree of the concentration field of pheromone diffusion,a decoupling control strategy is employed to revise the pheromone updating formula.Experimental results for many TSP problems demonstrate that the proposed algorithm can not only generate better solutions but also ac- celerate the speed of convergence. Key words :ant colony optimization;diffusion model;coupling characteristic;decoupling control strategy 仿生学的研究己经为人类自然科学的发展和进 元启发式的随机搜索技术1，！，目前已成为群集智 步提供了许多有益的启迪.其中，群集智能(swarm 能中解决组合优化问题最有效的算法之一，并已在 intelligence)是人们在对生物群落行为的观察和对生产过程、车辆管理、路由寻址、布局规划、资源调配 生物社会性的研究中得到的一种演化计算技术，近 和数据挖掘等领域中获得了成功的应用.ACO进行 年来受到学者们的广泛关注，并为解决复杂组合优 优化的基本特性是：将可行解的先验结构信息与目 化问题提供了一个理论框架.蚁群优化算法(ant 前已得到的较好解的后验信息相融合，用以引导搜 colony optimization,ACO)是Dorigo等人根据蚂蚁 索过程，加速最优解的获取.在这个寻优过程中，信 群体在觅食过程中所体现出的智能行为提出的一种 息素是蚁群进行相互交流、完成信息融合并实现群 集智能的重要媒介.所以，近些年国内外的学者对蚁 收稿日期：200612-28. 群算法的研究，都是围绕信息素的产生和更新策略 基金项目：因家自然科学基金资助项目(60496322)：北京市教育委员 进行的.例如，Gambardella等1提出的ACS(ant 会科技发展资助项目(KM200610005020), colony system)蚁群系统，Stutzle等]提出的 @1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 2 卷第 4 期 智 能 系 统 学 报 Vol. 2 №. 4 2007 年 8 月 CAAI Transactions on Intelligent Systems Aug. 2007 基于信息素扩散模型解耦控制策略的蚁群算法 冀俊忠 ,刘椿年 ,黄 振 (北京工业大学 计算机学院 ,北京 100022) 摘 要 :蚁群优化是一种元启发式的随机搜索技术. 信息素是蚁群进行交流并实现群集智能的媒介 ,所以信息素的 更新策略一直是蚁群算法中的一个研究热点. 针对信息素扩散的耦合特征 ,提出一种基于信息素扩散模型解耦控制 策略的蚁群算法. 对信息素扩散模型进行改善 ,建立以蚂蚁经过的路径 (直线段) 为信源的信息素扩散模型 ,通过分 析信息素扩散浓度场的耦合性 ,引入去耦控制策略来修正信息素的更新公式 ,大量 TSP (traveling salesman prob2 lem) 问题的实验表明 :该算法不仅能获得更好的解 ,而且能加快算法的收敛速度. 关键词 :蚁群算法 ;扩散模型 ;耦合性 ;解耦控制策略 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0420001208 An ant colony optimization algorithm based on a decoupling control strategy of pheromone diffusion model J I J un2zhong , L IU Chun2nian , HUAN G Zhen (College of Computer Science and Technology , Beijing University of Technology , Beijing 100022 , China) Abstract :Ant colony optimization (ACO) is a meta2heuristic search technique. Pheromones are an impor2 tant media ants use to communicate wit h each ot her and implement swarm intelligence. Thus research on p heromone updating strategies is a hotspot in ACO. A new decoupling control strategy model of p hero2 mone diff usion is proposed based on t he coupling characteristic of p heromone diff usion. First , t he algo2 rit hm sets up a new p heromone diff usion model with t he path that t he ant travels as t he p heromone source. Then , according to the coupling degree of the concentration field of p heromone diff usion , a decoupling control strategy is employed to revise t he p heromone updating formula. Experimental results for many TSP problems demonstrate t hat the proposed algorit hm can not only generate better solutions but also ac2 celerate t he speed of convergence. Keywords :ant colony optimization ; diff usion model ; coupling characteristic ; decoupling control strategy 收稿日期 :2006212228. 基金项目 :国家自然科学基金资助项目(60496322) ;北京市教育委员 仿生学的研究已经为人类自然科学的发展和进 步提供了许多有益的启迪. 其中 ,群集智能 (swarm intelligence) 是人们在对生物群落行为的观察和对 生物社会性的研究中得到的一种演化计算技术 ,近 年来受到学者们的广泛关注 ,并为解决复杂组合优 化问题提供了一个理论框架. 蚁群优化算法 ( ant colony optimization ,ACO) 是 Dorigo 等人根据蚂蚁 群体在觅食过程中所体现出的智能行为提出的一 会科技发展资助项目 ( KM200610005020) . 种 元启发式的随机搜索技术[1 - 4 ] ,目前已成为群集智 能中解决组合优化问题最有效的算法之一 ,并已在 生产过程、车辆管理、路由寻址、布局规划、资源调配 和数据挖掘等领域中获得了成功的应用. ACO 进行 优化的基本特性是 :将可行解的先验结构信息与目 前已得到的较好解的后验信息相融合 ,用以引导搜 索过程 ,加速最优解的获取. 在这个寻优过程中 ,信 息素是蚁群进行相互交流、完成信息融合并实现群 集智能的重要媒介. 所以 ,近些年国内外的学者对蚁 群算法的研究 ,都是围绕信息素的产生和更新策略 进行的. 例如 , Gambardella 等[5 ] 提出的 ACS ( ant colony system ) 蚁 群 系 统 , Stutzle 等[6 ] 提 出 的