第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 ] 提 出 的
·2 智能系统学报 第2卷 MMAS(max-min ant system)蚁群系统，朱庆保 选择的城市列表，Uk=N一禁忌列表Tabue/:几，为 等)提出的基于变异和动态信息素更新的NDMA- 路径αg的能见度，可理解为该路径的启发信息（先 CO算法(ACO algorithm based on the nearest 验)，一般取几=1/d;是初始设定的参数，q是 neighbor node choosing,dynamic pheromone upda- 一个随机采样的数，且，q∈0,1：J是由式2)确 ting and mutation),黄国锐等提出的基于信息素 定的随机变量.若g<,将按式1)选择下一城市， 扩散模型的PDACO算法(ACO algorithm based on 否则，按式2)的转移概率确定下一城市： pheromone diffusion)等都是通过对信息素生成和 I工·a j∈Uk, 更新策略的改进及优化来提高蚁群算法的寻优能 pa (1) ∑It(w…fnmP' w (2) 力，并改善解的全局收敛性.虽然许多算法都具有发 现较优解的能力，但迭代次数多、收敛速度慢仍是制 0 其他 约大多数算法在实际组合优化问题中应用的瓶颈. 式中：a、B分别表示路径ag上的信息素和先验结构 针对这一问题，本文结合信息素扩散的耦合特征，提 信息对蚂蚁选择转移方向时的影响权重，在原始的 出一种基于信息素扩散模型解耦控制策略的蚁群算 ACS算法中a=1 蚁群在觅食过程中，一方面通过蚂蚁的行走会 法.首先，对信息素扩散模型进行改善，建立以蚂蚁 经过的路径（直线段）为信源的信息素扩散模型，细 在路径上留下新的信息素，另一方面随着时间的推 化了信息素扩散机制：然后，通过分析信息素扩散浓 移己有的信息素会逐渐挥发，所以各条路径上的信 度场的耦合性，引入去耦控制策略来修正信息素的 息素会根据蚁群的行动和时间变化不断更新.信息 素的更新体现了可行解空间的后验信息积累的变 更新公式，强化了蚂蚁间的协作和交流.大量TSP 问题的实验结果表明：该算法不仅能获得更好的解， 化.ACS算法在每次迭代中，要进行局部和全局2 次信息素的更新 而且能加快算法的收敛速度 首先在构造解时，每只蚂蚁对其走过的路径用 1蚁群算法及信息素扩散模型 式3)来进行局部信息素的更新 1.1ACS蚁群算法 (t+1)=1-g·g()+p·△鸢.3) 蚁群优化算法是一类基于模型的搜索算法] 式中：参数P表示信息素的挥发程度，且0<P<1, 该类算法实现的基本思想是通过模拟自然界中真实 表示△在本次周游中蚂蚁k留在路径a)上的信息 蚁群的觅食行为而获得所求问题的解，但不同的求 素，如果采用ant quantity system模型(Q为常数)， 解模型使用不同的状态转移方法和信息素的更新策 有 略，从而形成了不同的蚁群算法.ACS算法是其中 Q 当第k只蚂蚁在本次周游中 最成熟且应用最广的蚁群算法之一.下面以n个城 (1→1+1时段)经过路径a时， 0 其他， 市的旅行商问题为例，介绍该算法的求解过程.设m 4) 是蚁群中蚂蚁的数量，d表示城市1与城市j之间 其次，当每次循环所有的蚂蚁都完成了一次周游后， 的欧氏距离，叫表示城市i与城市j之间的路径， ACS算法对最优解的每条路径上的信息素按式(4) ()表示1时刻在a上残留的信息素浓度，并设初始 进行全局更新： 时刻各条路径上的信息素浓度均为C(常数).蚂蚁 "=(1-A)·g+A△g, (5 k(1≤k≤m在自己周游的过程中，将根据目前可行 Q7(Le),当全局最优解包含路径a时， 候选路径的结构信息先验知识)与其上残留的信息 △Tg 0, 其他 素浓度（后验信息，来选择自己前进的方向.ACS算 法中，每只蚂蚁从城市1走向城市j的过程分2步 同样，A是挥发系数，且0<A<1;Q'为常数 且在原始的ACS算法中Q取1；Le是到目前为止 进行：首先通过随机采样和比较，然后再确定状态变 迁的规则，其实现的公式为 蚁群寻优得到的全局最优解的路线长度.ACS蚁群 算法一方面通过强化状态变迁规则，增强了解的多 arax[a(0]几f, 9<利用) 样性，可以避免早熟现象；另一方面，通过全局信息 otherwise开发). 素的更新，强化正反馈的过程，加速收敛过程.所以 (1) 在求解TSP问题时，ACS算法具有良好的求解能 式中：Uk表示妈蚁k在本次周游中在当前位置允许 力 @1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
MMAS( max2min ant system) 蚁群系统 , 朱庆保 等[7 ]提出的基于变异和动态信息素更新的 NDMA2 CO 算 法 ( ACO algorithm based on t he nearest neighbor node choosing , dynamic p heromone upda2 ting and mutation) , 黄国锐等[8 ]提出的基于信息素 扩散模型的 PDACO 算法(ACO algorithm based on p heromone diff usion) 等都是通过对信息素生成和 更新策略的改进及优化来提高蚁群算法的寻优能 力 ,并改善解的全局收敛性. 虽然许多算法都具有发 现较优解的能力 ,但迭代次数多、收敛速度慢仍是制 约大多数算法在实际组合优化问题中应用的瓶颈. 针对这一问题 ,本文结合信息素扩散的耦合特征 ,提 出一种基于信息素扩散模型解耦控制策略的蚁群算 法. 首先 ,对信息素扩散模型进行改善 ,建立以蚂蚁 经过的路径(直线段) 为信源的信息素扩散模型 ,细 化了信息素扩散机制 ;然后 ,通过分析信息素扩散浓 度场的耦合性 ,引入去耦控制策略来修正信息素的 更新公式 ,强化了蚂蚁间的协作和交流. 大量 TSP 问题的实验结果表明 :该算法不仅能获得更好的解 , 而且能加快算法的收敛速度. 1 蚁群算法及信息素扩散模型 111 ACS 蚁群算法 蚁群优化算法是一类基于模型的搜索算法[9 ] . 该类算法实现的基本思想是通过模拟自然界中真实 蚁群的觅食行为而获得所求问题的解 ,但不同的求 解模型使用不同的状态转移方法和信息素的更新策 略 ,从而形成了不同的蚁群算法. ACS 算法是其中 最成熟且应用最广的蚁群算法之一. 下面以 n 个城 市的旅行商问题为例 ,介绍该算法的求解过程. 设 m 是蚁群中蚂蚁的数量 , dij 表示城市 i 与城市 j 之间 的欧氏距离 , aij表示城市 i 与城市 j 之间的路径 ,τij ( t) 表示 t 时刻在 aij上残留的信息素浓度 ,并设初始 时刻各条路径上的信息素浓度均为 C(常数) . 蚂蚁 k (1 ≤k ≤m) 在自己周游的过程中 ,将根据目前可行 候选路径的结构信息(先验知识) 与其上残留的信息 素浓度(后验信息) 来选择自己前进的方向. ACS 算 法中 ,每只蚂蚁从城市 i 走向城市 j 的过程分 2 步 进行 :首先通过随机采样和比较 ,然后再确定状态变 迁的规则 ,其实现的公式为 j = argmax u∈Uk {[τiu (t) ] ·[ηiu ] β } , q < q0 (利用) , J , otherwise(开发) . (1) 式中 :Uk 表示蚂蚁 k 在本次周游中在当前位置允许 选择的城市列表 ,Uk = { N —禁忌列表 Tabuk } ;ηij 为 路径 aij的能见度 ,可理解为该路径的启发信息 (先 验) ,一般取ηij = 1/ dij ; q0 是初始设定的参数 , q 是 一个随机采样的数 ,且 q0 , q ∈[0 ,1 ]; J 是由式(2) 确 定的随机变量. 若 q < q0 ,将按式(1) 选择下一城市 , 否则 ,按式(2) 的转移概率确定下一城市 : p k ij ( t) = [τij ( t) ] α ·[ηij ] β u∑∈U k [τiu ( t) ] α ·[ηiu ] β , j ∈Uk , 0 , 其他. (2) 式中 :α、β分别表示路径 aij 上的信息素和先验结构 信息对蚂蚁选择转移方向时的影响权重 ,在原始的 ACS 算法中α= 1. 蚁群在觅食过程中 ,一方面通过蚂蚁的行走会 在路径上留下新的信息素 ,另一方面随着时间的推 移已有的信息素会逐渐挥发 ,所以各条路径上的信 息素会根据蚁群的行动和时间变化不断更新. 信息 素的更新体现了可行解空间的后验信息积累的变 化. ACS 算法在每次迭代中 ,要进行局部和全局 2 次信息素的更新. 首先在构造解时 ,每只蚂蚁对其走过的路径用 式(3) 来进行局部信息素的更新. τij ( t + 1) = (1 - ρ) ·τij ( t) +ρ·Δτk ij . (3) 式中 :参数ρ表示信息素的挥发程度 ,且 0 <ρ< 1 , 表示Δτk ij在本次周游中蚂蚁 k 留在路径 aij上的信息 素 ,如果采用 ant quantity system 模型( Q 为常数) , 有 Δτk ij = Q d ij , 当第 k 只蚂蚁在本次周游中 ( t →t + 1 时段) 经过路径 aij 时 , 0 , 其他. (4) 其次 ,当每次循环所有的蚂蚁都完成了一次周游后 , ACS 算法对最优解的每条路径上的信息素按式(4) 进行全局更新 : τnew ij = (1 - ρ1 ) ·τold ij +ρ1 ·Δτij , (5) Δτij = Q′/ (Lbest) , 当全局最优解包含路径 aij 时 , 0 , 其他. 同样 ,ρ1 是挥发系数 ,且 0 <ρ1 < 1 ; Q′为常数 , 且在原始的 ACS 算法中 Q′取 1 ; Lbest是到目前为止 蚁群寻优得到的全局最优解的路线长度. ACS 蚁群 算法一方面通过强化状态变迁规则 ,增强了解的多 样性 ,可以避免早熟现象;另一方面 ,通过全局信息 素的更新 ,强化正反馈的过程 ,加速收敛过程. 所以 在求解 TSP 问题时 ,ACS 算法具有良好的求解能 力. ·2 · 智 能 系 统 学 报 第 2 卷
第4期 冀俊忠，等：基于信息素扩散模型解耦控制策略的蚁群算法 1.2基于城市信源的信息素扩散模型 了蚂蚁群中个体之间的合作效果，增强蚁群算法的 文献[8]在蚁群优化中提出了信息素扩散模型， 有效性，更凸现了群集智能的思想 其基本思想是：在蚂蚁进行路径选择时，适当考虑相 2 基于信息素扩散模型解耦控制的 近路径上信息素的相互作用.即一只蚂蚁在某条路 径上留下的信息素，一方面会直接影响连接该路径 蚁群算法 的2个城市上的其他蚂蚁选择下一个城市的行为； 2.1基于路径信源的信息素扩散模型 另一方面，它会以这2个城市为中心向外扩散，影响 从蚁群算法的状态变迁可以看出，蚂蚁选路总 该城市附近的其他城市上蚂蚁的选路行为. 是偏向于长度短且信息素浓度高的边.由于路径长 该信息素扩散模型用于模拟以城市信源为中 度是固定不变的先验信息，故信息素浓度就成为衡 心，近似服从正态分布的扩散浓度场，模型较客观地 量某段路径优劣的一个重要的评价标准.在蚁群算 反映了信息素浓度与到信源之间距离的反比关系， 法中，信息素是蚁群个体之间进行信息交流的载体 如城市C与信源O相邻，则位于城市C上的蚂蚁能 信息素浓度体现了蚁群群体后验信息的积累，所以 够感受到信源O所扩散的信息素浓度Dc 对信息素浓度更新策略的合理设计是关系到能否产 Dc Dmax((htan 0-/(h tan )(6) 生高质量解的关键 式中：Dx为信源O处的信息素浓度，h为简化的圆 基于城市信源的信息素扩散模型就是考虑了信 锥体模型高度，0为圆锥体锥面与中心轴的夹角（为 息素向周遍路径扩散的事实，对蚁群算法中相邻路 一设定的固定参数)，htan0为扩散范围的半径r, 径上信息素的更新进行修正来提高算法求解能力 σ为位于扩散范围中的城市C与信源O的距离。 的.不过该算法中对信息素扩散浓度场的模拟过于 基于信息素扩散模型，蚁群算法进行相邻路径 简化，存在一定的缺陷.例如当d>2r时，按照原扩 信息素的更新.假设蚂蚁k刚走过的2个城市i和了 散模型，信息素扩散的浓度场及扩散范围可如图1 之间的距离为d,该蚂蚁所留的信息素将以i和j ()中灰色区域所示，图中小圆点表示城市位置，黑 为信源向周围扩散，即以i和j为中心形成扩散的 色圆点表示受扩散影响的城市，圆圈表示不同位置 浓度场，并按简化的扩散模型向周围扩散.这种扩散 浓度场强的等势线.从图可见，城市信源作为信息素 不仅影响城市ⅰ和j上的其他蚂蚁选择下一段路 扩散浓度场的中心，离信源越近，浓度场的场强越强 径，也会影响位于扩散范围内其他城市上蚂蚁的选 等势线越密).除所经过的城市1和j外，蚂蚁k在 择路径.若任一城市I满足da≤r或dn≤r,则该城 本次行走中还会影响位于城市C、CG、G、C上蚂 市上的蚂蚁在进行下一城市的选择时将受到城市1 蚁选路的行为.但信息素是依附在可行路径上的，所 或j信源的影响，即蚂蚁k的本次行动不仅会导致 以不失一般性，本文假设信息素随蚂蚁的行走均匀 路径ag上信息素的变化：△专=O/d山(Q为常数)， 分布在路径上，那么信息素应以所依附的路径为中 而且也会影响一些相邻路径的信息素浓度变化，如 心向外扩散，所以图1(d中的扩散模型存在一定的 路径au或au上信息素浓度的变化可表示为：△专= 局限.为此，本文对其进行改进，将扩散模型改为以 D,△克=D唬：令h=d1(d山)“，ω为大于1的可调 路径为信源向周边扩散，如图16)所示，此时，蚂蚁 常数，d为各城市间的平均距离，则 k在从城市了走到ⅰ的过程中留下的信息素将形成 r=tan0·df/(d)“;以i为中心扩散时o,=da: 更大范围的浓度场，受其影响的城市集合也扩大为 以j为中心扩散时a=d;并设Dmx=Y·△奇，Y为 G、G、G、C、C、G、C、C.从图可见，处于扩散的 小于1的可调常数，则 范围内的城市，无论是到信源城市，还是到信源路 Y01- 径，只要处于信源扩散浓度场内同一等势线上的点 dg≤r D d (7) 都受到相同的信息素浓度的影响，这更符合自然界 0 其他 信源扩散的现象.所以这种变化能更真实地反映信 息素扩散的浓度场，并扩大了信息素扩散的作用范 d≤r, D dy 8) 围 0. 其他 2.2扩散模型的耦合性分析及解耦控制策略 依据这种扩散模型，每只蚂蚁每走一步，不仅会 信息素的扩散说明了相邻路径上信息素的浓度 改变其所经过的那段路径上的信息素浓度，而且可 是非独立的，相互之间具有耦合作用，即扩散浓度场 能会改变多条路径上的信息素浓度，这种改进提高 内相邻路径上信息素的浓度具有耦合性.在相邻路 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
112 基于城市信源的信息素扩散模型 文献[8 ]在蚁群优化中提出了信息素扩散模型 , 其基本思想是 :在蚂蚁进行路径选择时 ,适当考虑相 近路径上信息素的相互作用. 即一只蚂蚁在某条路 径上留下的信息素 ,一方面会直接影响连接该路径 的 2 个城市上的其他蚂蚁选择下一个城市的行为 ; 另一方面 ,它会以这 2 个城市为中心向外扩散 ,影响 该城市附近的其他城市上蚂蚁的选路行为. 该信息素扩散模型用于模拟以城市信源为中 心 ,近似服从正态分布的扩散浓度场 ,模型较客观地 反映了信息素浓度与到信源之间距离的反比关系 , 如城市 C 与信源 O 相邻 ,则位于城市 C 上的蚂蚁能 够感受到信源 O 所扩散的信息素浓度 D C : DC = Dmax ·( ( h ·tanθ- σ) / ( h ·tanθ) ) . (6) 式中 : Dmax为信源 O 处的信息素浓度 , h 为简化的圆 锥体模型高度 ,θ为圆锥体锥面与中心轴的夹角 (为 一设定的固定参数) , h ·tanθ为扩散范围的半径 r , σ为位于扩散范围中的城市 C 与信源 O 的距离. 基于信息素扩散模型 ,蚁群算法进行相邻路径 信息素的更新. 假设蚂蚁 k 刚走过的 2 个城市 i 和 j 之间的距离为 dij ,该蚂蚁所留的信息素将以 i 和 j 为信源向周围扩散 ,即以 i 和 j 为中心形成扩散的 浓度场 ,并按简化的扩散模型向周围扩散. 这种扩散 不仅影响城市 i 和 j 上的其他蚂蚁选择下一段路 径 ,也会影响位于扩散范围内其他城市上蚂蚁的选 择路径. 若任一城市 l 满足 d il ≤r 或 d jl ≤r,则该城 市上的蚂蚁在进行下一城市的选择时将受到城市 i 或 j 信源的影响 ,即蚂蚁 k 的本次行动不仅会导致 路径 aij上信息素的变化 :Δτk ij = Q/ dij ( Q 为常数) , 而且也会影响一些相邻路径的信息素浓度变化 ,如 路径 ail或 ajl 上信息素浓度的变化可表示为 :Δτk il = D k il ,Δτk jl = D k jl ;令 h = d ω+ 1 ( dij ) ω ,ω为大于 1 的可调 常 数 , d 为 各 城 市 间 的 平 均 距 离 , 则 r = tanθ·d ω+ 1 / ( dij ) ω ;以 i 为中心扩散时σi = dil ; 以 j 为中心扩散时σj = djl ;并设 Dmax =γ·Δτk ij ,γ为 小于 1 的可调常数 ,则 D k il = γ·Q d ij (1 - dil r ) , dil ≤r, 0 , 其他. (7) D k jl = γ·Q d ij (1 - djl r ) , djl ≤r, 0 , 其他. (8) 依据这种扩散模型 ,每只蚂蚁每走一步 ,不仅会 改变其所经过的那段路径上的信息素浓度 ,而且可 能会改变多条路径上的信息素浓度 ,这种改进提高 了蚂蚁群中个体之间的合作效果 ,增强蚁群算法的 有效性 ,更凸现了群集智能的思想. 2 基于信息素扩散模型解耦控制的 蚁群算法 211 基于路径信源的信息素扩散模型 从蚁群算法的状态变迁可以看出 ,蚂蚁选路总 是偏向于长度短且信息素浓度高的边. 由于路径长 度是固定不变的先验信息 ,故信息素浓度就成为衡 量某段路径优劣的一个重要的评价标准. 在蚁群算 法中 ,信息素是蚁群个体之间进行信息交流的载体 , 信息素浓度体现了蚁群群体后验信息的积累 ,所以 对信息素浓度更新策略的合理设计是关系到能否产 生高质量解的关键. 基于城市信源的信息素扩散模型就是考虑了信 息素向周遍路径扩散的事实 ,对蚁群算法中相邻路 径上信息素的更新进行修正来提高算法求解能力 的. 不过该算法中对信息素扩散浓度场的模拟过于 简化 ,存在一定的缺陷. 例如当 dij > 2 r 时 ,按照原扩 散模型 ,信息素扩散的浓度场及扩散范围可如图 1 (a) 中灰色区域所示 ,图中小圆点表示城市位置 ,黑 色圆点表示受扩散影响的城市 ,圆圈表示不同位置 浓度场强的等势线. 从图可见 ,城市信源作为信息素 扩散浓度场的中心 ,离信源越近 ,浓度场的场强越强 (等势线越密) . 除所经过的城市 i 和 j 外 ,蚂蚁 k 在 本次行走中还会影响位于城市 C1 、C2 、C3 、C4 上蚂 蚁选路的行为. 但信息素是依附在可行路径上的 ,所 以不失一般性 ,本文假设信息素随蚂蚁的行走均匀 分布在路径上 ,那么信息素应以所依附的路径为中 心向外扩散 ,所以图 1 ( a) 中的扩散模型存在一定的 局限. 为此 ,本文对其进行改进 ,将扩散模型改为以 路径为信源向周边扩散 ,如图 1 ( b) 所示 ,此时 ,蚂蚁 k 在从城市 j 走到 i 的过程中留下的信息素将形成 更大范围的浓度场 ,受其影响的城市集合也扩大为 C1 、C2 、C3 、C4 、C5 、C6 、C7 、C8 . 从图可见 ,处于扩散的 范围内的城市 ,无论是到信源城市 , 还是到信源路 径 ,只要处于信源扩散浓度场内同一等势线上的点 都受到相同的信息素浓度的影响 ,这更符合自然界 信源扩散的现象. 所以这种变化能更真实地反映信 息素扩散的浓度场 ,并扩大了信息素扩散的作用范 围. 212 扩散模型的耦合性分析及解耦控制策略 信息素的扩散说明了相邻路径上信息素的浓度 是非独立的 ,相互之间具有耦合作用 ,即扩散浓度场 内相邻路径上信息素的浓度具有耦合性. 在相邻路 第 4 期 冀俊忠 ,等 :基于信息素扩散模型解耦控制策略的蚁群算法 ·3 ·
智能系统学报 第2卷 为t(ab=t+△t(ahl,ag路径上信息素的浓度为 t(ag=t+△t(ahl,式中：△t()表示相应路径· 对位于其扩散浓度场内相邻路径的耦合补偿：可见 此时路径ah上信息素的浓度将大于其他2条路径 ab、ag上信息素的浓度，当大到一定程度时将足以 (a)以城市为信源 影响第4只蚂蚁的选路行为，即它将以更大的概率 选择h作为下一步要到达的位置，从而使该蚂蚁选 择了一条通向目标最短的道路，点到路径信源扩散 距离求解的示意如图3 B区 C区 (b)以路径为信源 (片） 图1信息素扩散的浓度场场强示意图 图3点到路径信源扩散距离求解的示意图 Fig 3 The sketch map of distance form a point Fig 1 The intensity fields of pheromone diffusion to info fountain of path 径上信息素的这种耦合特性，使得一条路径上信息 针对这种耦合特性，本文的解耦控制策略是利 素的改变往往会引起其周边其他路径信息素的变 用耦合补偿原理来消除耦合关系，使蚁群算法能够 化，从而间接地影响蚂蚁的选路行为.传统的蚁群算 对每条路径上的信息素浓度进行单独的控制.下面 法没有考虑这一特性，将路径上信息素的更新独立 推导耦合补偿的计算公式.如图3所示，假设蚂蚁k 地进行，这可能会误导蚂蚁选路的方向，增加算法的 刚走过路径ag,为了求城市I到路径a,的垂直距离 迭代次数.为解决这一问题，本文引入解耦控制策 d,对此分2种情况讨论 略，通过耦合补偿将彼此相互影响的多路径信息素 1)当TSP问题中的城市位置用坐标给出时，城 浓度问题解耦为相对独立的单路径信息素浓度问题 市i寸和1的坐标分别为(x1,)、(x2,2)和(0， 来处理，从而克服蚂蚁选路的干扰，增强算法的鲁棒 ),这时计算过程如下： 性，扩散耦合补偿的原理示意图如图2所示 当x1=2时，由i寸两点形成的直线L垂直于 x轴，L的方程为：x=x1; 当x1≠x2时，由iy两点形成的直线L的方程 为y-”=2出(x·x):将直线L的表达式化为 x2-x1 形如ax+by+c=0的标准形式，然后依据点到直线 图2扩散耦合补偿的原理示意图 的距离公式，可以得到1点到直线L的距离：d= ig 2 Principle map of coupled compensation for diffusion l axo byo +d 如图2所示，蚂蚁从a到d存在3条可行通路， d+b 2)当TSP问题中城市间的距离己知时，即在图 在3条通路中分别包含路径ab、ah和ag,其中，路 径ab的长度稍小于ah和ag的长度，h到ab、ag的 2中己知a叫、am、a,此时，可以利用海伦公式求垂 距离小于扩散半径.假设有3只蚂蚁刚刚从a出发， 直距离d,方法如下：令s=(a叫+a+a/2,则三角 分别经过ab、ah和ag3条路径向d前进，并且在3 形jl的面积为△=s(s-ag)(s-a(s-aa),又 条路径上留下了相同浓度的信息素x当第4只蚂 因为△=(d·a画)/2，所以d=2△/a则. 蚁出发时，如果不考虑信息素的扩散，无疑它将以更 得到城市1离路径信源的距离d后，就可判断 大的概率选择b作为下一步要到达的位置.但如果 城市！是否位于蚂蚁k在本次行走中所形成的信息 考虑路径信息素的扩散影响，由于距离远近的不同， 素浓度场的扩散范围内，如果在扩散半径内，就根据 h处在ab和ag的扩散浓度场内，故ah路径上信息 它的值，计算扩散到相应路径上的信息素： 素的浓度为t(ahW=t+△t(ab+△t(ag;而b、g处 1)当城市1位于图1b)中的A区，且da(扩 在ah的扩散浓度场内，故ab路径上信息素的浓度 散半径)时，城市i对路径aa的影响D可按式9)计 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 1 信息素扩散的浓度场场强示意图 Fig11 The intensity fields of pheromone diffusion 径上信息素的这种耦合特性 ,使得一条路径上信息 素的改变往往会引起其周边其他路径信息素的变 化 ,从而间接地影响蚂蚁的选路行为. 传统的蚁群算 法没有考虑这一特性 ,将路径上信息素的更新独立 地进行 ,这可能会误导蚂蚁选路的方向 ,增加算法的 迭代次数. 为解决这一问题 , 本文引入解耦控制策 略 ,通过耦合补偿将彼此相互影响的多路径信息素 浓度问题解耦为相对独立的单路径信息素浓度问题 来处理 ,从而克服蚂蚁选路的干扰 ,增强算法的鲁棒 性 ,扩散耦合补偿的原理示意图如图 2 所示. 图 2 扩散耦合补偿的原理示意图 F ig12 Principle map of coupled compensation for diffusion 如图 2 所示 ,蚂蚁从 a 到 d 存在 3 条可行通路 , 在 3 条通路中分别包含路径 ab、ah 和 ag ,其中 ,路 径 ab的长度稍小于 ah 和 ag 的长度 , h 到 ab、ag 的 距离小于扩散半径. 假设有 3 只蚂蚁刚刚从 a 出发 , 分别经过 ab、ah 和 ag 3 条路径向 d 前进 ,并且在 3 条路径上留下了相同浓度的信息素τ. 当第 4 只蚂 蚁出发时 ,如果不考虑信息素的扩散 ,无疑它将以更 大的概率选择 b 作为下一步要到达的位置. 但如果 考虑路径信息素的扩散影响 ,由于距离远近的不同 , h 处在 ab 和 ag 的扩散浓度场内 ,故 ah 路径上信息 素的浓度为τ( ah) =τ+Δτ( ab) +Δτ( ag) ;而 b、g 处 在 ah 的扩散浓度场内 ,故 ab 路径上信息素的浓度 为τ( ab) =τ+Δτ( ah) , a g 路径上信息素的浓度为 τ( ag) =τ+Δτ( ah) ,式中 :Δτ( ·) 表示相应路径 · 对位于其扩散浓度场内相邻路径的耦合补偿;可见 , 此时路径 ah 上信息素的浓度将大于其他 2 条路径 ab、ag 上信息素的浓度 ,当大到一定程度时将足以 影响第 4 只蚂蚁的选路行为 ,即它将以更大的概率 选择 h 作为下一步要到达的位置 ,从而使该蚂蚁选 择了一条通向目标最短的道路 ,点到路径信源扩散 距离求解的示意如图 3. 图 3 点到路径信源扩散距离求解的示意图 Fig13 The sketch map of distance form a point to info fountain of path 针对这种耦合特性 ,本文的解耦控制策略是利 用耦合补偿原理来消除耦合关系 ,使蚁群算法能够 对每条路径上的信息素浓度进行单独的控制. 下面 推导耦合补偿的计算公式. 如图 3 所示 ,假设蚂蚁 k 刚走过路径 aij ,为了求城市 l 到路径 aij的垂直距离 d ,对此分 2 种情况讨论. 1) 当 TSP 问题中的城市位置用坐标给出时 ,城 市 i、j 和 l 的坐标分别为 ( x1 , y1 ) 、( x2 , y2 ) 和 ( x0 , y0 ) ,这时计算过程如下 : 当 x1 = x2 时 ,由 i、j 两点形成的直线 L 垂直于 x 轴 , L 的方程为 : x = x1 ; 当 x1 ≠x2 时 ,由 i、j 两点形成的直线 L 的方程 为 y - y1 = y2 - y1 x2 - x1 ( x - x1 ) ;将直线 L 的表达式化为 形如 ax + by + c = 0 的标准形式 ,然后依据点到直线 的距离公式 , 可以得到 l 点到直线 L 的距离 : d = | ax0 + by0 + c| a 2 + b 2 . 2) 当 TSP 问题中城市间的距离已知时 ,即在图 2 中已知 aij 、ajl 、ali ,此时 ,可以利用海伦公式求垂 直距离 d ,方法如下 :令 s = ( aij + ajl + ali) / 2 ,则三角 形 i j l 的面积为Δ = s(s - aij ) (s - ajl ) (s - ali) ,又 因为Δ= ( d ·aij ) / 2 ,所以 d = 2Δ/ aij . 得到城市 l 离路径信源的距离 d 后 ,就可判断 城市 l 是否位于蚂蚁 k 在本次行走中所形成的信息 素浓度场的扩散范围内 ,如果在扩散半径内 ,就根据 它的值 ,计算扩散到相应路径上的信息素 : 1) 当城市 l 位于图 1 ( b) 中的 A 区 ,且 dil ≤r(扩 散半径) 时 ,城市 i 对路径 ail的影响 D k il可按式(9) 计 ·4 · 智 能 系 统 学 报 第 2 卷
第4期 冀俊忠，等：基于信息素扩散模型解耦控制策略的蚁群算法 5 算得到： 按式4)计算路径可上新产生的信息素浓 Yd0.),d≤r 度： D 9) 以为信源，判断位于该扩散浓度场内的城市 0. 其他 点，并根据不同的情况，依据式9)、(10)或11)计算 2当城市1位于图1b)中的C区，且d≤（扩 该信源扩散到相邻其他路径上的信息素浓度： 散半径)时，城市j对路径au的影响D可按式(I0) 综合上面各式计算结果，利用式3)进行局部信 计算得到： 息素的更新： dn≤r, }信息素扩散、耦合补偿及局部更新 D 10 其他， 3)本次迭代信息素的全局更新 0. 3)当城市1位于图1b)中的B区，且d≤r FOR k=1 TO m 时，D,为直线段ag对路径a和路径au上信息素的 计算L:}计算每只蚂蚁在本次迭代中的旅 影响，其计算公式为 行长度 y·h0a.业)， FOR每个a西∈Lbet.ir du≤r, Lk (11) 利用式5)进行全局信息素的更新(P=A); 0 其他 佺局信息素的更新 通过上面的推导，就可计算出蚂蚁的每次行走 4)判断算法是否结束 对其所形成的扩散范围内相邻路径的影响，从而对 IF(结束条件满足)THEN 这些路径上的信息素做耦合补偿的修正更新 输出多次迭代后的最优解Le·山； 2.3算法描述 ELSE 基于信息素扩散模型解耦控制策略的蚁群算法 迭代次数增1：初始化始点各城市可访问的 首先以路径代替城市作为扩散模型的信源，优化了 城市列表： 信息素扩散模型，扩大了浓度场的作用范围：然后通 G0TO2)/继续进行下一次迭代 过解耦控制策略，在信息素的更新中引入了耦合补 偿，更真实、准确地反映了每条路径上信息素的浓 2.4算法复杂度分析 度.此外，新算法采用ACS算法的基本框架，即信息 在这一部分，对基本流程给出算法进行计算复 素得进行2次更新.新算法的基本流程可以描述如 杂度分析.在初始化阶段，主要的花费是为每条路径 下： 指定初始的信息素浓度，故O(C)=O():在构造 ETPDACO alg orithm 解的第2阶段，在循环体内主要的计算花费包括城 市转移：O(C.)=O(W,以及判断其他城市是否落 1)初始化阶段 在本扩散浓度场内的计算花费：30(C.2)=O(m, 初始化参数，赋各条路径相同的信息浓度，并将 m只蚂蚁随机放到n个城市节点上； 所以这阶段总的计算复杂度为：O(n·m·(n+ 为每只蚂蚁设置起点5k和允许访问的城市列 W)=O(·m:在第3阶段，计算蚂蚁的旅行长度 表Uk; 复杂度为O(m),对最佳路径进行全局信息素更新 2)蚁群的一次周游过程（一次迭代） 的复杂度为O(W,由于m≤，所以该部分总的计算 FORp=1TOn遍历所有城市，最后回到出 复杂度为O(W;而第4阶段计算复杂度为01)：所 发点 以，如果经过NC次迭代，算法成功结束，这时总的 FORk=1TOm/蚁群的一步转移 计算复杂度为NC·(0()+O(·m+O(+ 设蚂蚁当前位置为i O1))=O(NC··m,与基本的ACS蚁群算法 IFp<n THEN没有遍历完所有城市 具有相同的计算复杂度.可见，尽管在信息素扩散和 按状态转移公式1)和2)选择下一城市j 耦合补偿过程中，算法增加了一些计算量，但并没有 完成一步行走可，并变更允许访问的城市列表 引起复杂度阶次的变化，而且由于耦合补偿可以克 U(》: 服相邻路径间彼此的干扰，更客观、正确地引导蚂蚁 ELSE/遍历完所有城市 的选路，减少算法运行的迭代次数，所以总的计算性 行走一步可，回到出发的城市} 能会得到提高 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
算得到 : D k il = γ·dij ·Q L k (1 - dil r ) , dil ≤r, 0 , 其他. (9) 2) 当城市 l 位于图 1 (b) 中的 C区 ,且 djl ≤r(扩 散半径) 时 ,城市 j 对路径 ajl的影响 D k jl可按式(10) 计算得到 : D k jl = γ·dij ·Q L k (1 - djl r ) , djl ≤r, 0 , 其他. (10) 3) 当城市 l 位于图 1 ( b) 中的 B 区 ,且 dLl ≤r 时 , D k L I为直线段 aij 对路径 ail和路径 ajl上信息素的 影响 ,其计算公式为 D k Ll = γ·dij ·Q L k (1 - dLl r ) , dLl ≤r, 0 , 其他. (11) 通过上面的推导 ,就可计算出蚂蚁的每次行走 对其所形成的扩散范围内相邻路径的影响 ,从而对 这些路径上的信息素做耦合补偿的修正更新. 213 算法描述 基于信息素扩散模型解耦控制策略的蚁群算法 首先以路径代替城市作为扩散模型的信源 ,优化了 信息素扩散模型 ,扩大了浓度场的作用范围 ;然后通 过解耦控制策略 ,在信息素的更新中引入了耦合补 偿 ,更真实、准确地反映了每条路径上信息素的浓 度. 此外 ,新算法采用 ACS 算法的基本框架 ,即信息 素得进行 2 次更新. 新算法的基本流程可以描述如 下 : ETPDACO a lg orithm { 1) 初始化阶段 初始化参数 ,赋各条路径相同的信息浓度 ,并将 m 只蚂蚁随机放到 n 个城市节点上 ; 为每只蚂蚁设置起点 sk 和允许访问的城市列 表 Uk ; 2) 蚁群的一次周游过程(一次迭代) FOR p = 1 TO n ∥遍历所有城市 ,最后回到出 发点 FOR k = 1 TO m ∥蚁群的一步转移 {设蚂蚁当前位置为 i IF p < n TH EN ∥没有遍历完所有城市 {按状态转移公式(1) 和(2) 选择下一城市 j 完成一步行走 i j , 并变更允许访问的城市列表 Uk ( j) ;} EL SE ∥遍历完所有城市 {行走一步 i j ,回到出发的城市} 按式 (4) 计算路径 i j 上新产生的信息素浓 度; 以 aij为信源 ,判断位于该扩散浓度场内的城市 点 ,并根据不同的情况 ,依据式(9) 、(10) 或(11) 计算 该信源扩散到相邻其他路径上的信息素浓度; 综合上面各式计算结果 ,利用式(3) 进行局部信 息素的更新; } ∥信息素扩散、耦合补偿及局部更新 3) 本次迭代信息素的全局更新 FOR k = 1 TO m {计算 L k ;} ∥计算每只蚂蚁在本次迭代中的旅 行长度 FOR 每个 aij ∈Lbest - ittr {利用式(5) 进行全局信息素的更新 (ρ=ρ1 ) ;} ∥全局信息素的更新 4) 判断算法是否结束 IF(结束条件满足) TH EN 输出多次迭代后的最优解 Lbest - all ; ELSE {迭代次数增 1 ;初始化始点各城市可访问的 城市列表; GO TO 2) ∥继续进行下一次迭代} } 214 算法复杂度分析 在这一部分 ,对基本流程给出算法进行计算复 杂度分析. 在初始化阶段 ,主要的花费是为每条路径 指定初始的信息素浓度 ,故 O( C 2 n ) = O( n 2 ) ;在构造 解的第 2 阶段 ,在循环体内主要的计算花费包括城 市转移 :O( C 1 n - 1 ) = O( n) ,以及判断其他城市是否落 在本扩散浓度场内的计算花费 :3O ( C 1 n - 2 ) = O ( n) , 所以这阶段总的计算复杂度为 : O ( n ·m ·( n + n) ) = O( n 2 ·m) ;在第 3 阶段 ,计算蚂蚁的旅行长度 复杂度为 O ( m) ,对最佳路径进行全局信息素更新 的复杂度为 O( n) ,由于 m ≤n ,所以该部分总的计算 复杂度为 O( n) ;而第 4 阶段计算复杂度为 O(1) ;所 以 ,如果经过 N C 次迭代 ,算法成功结束 ,这时总的 计算复杂度为 N C ·( O( n 2 ) ) + O( n 2 ·m) + O( n) + O(1) ) = O( N C ·n 2 ·m) ,与基本的 ACS 蚁群算法 具有相同的计算复杂度. 可见 ,尽管在信息素扩散和 耦合补偿过程中 ,算法增加了一些计算量 ,但并没有 引起复杂度阶次的变化 ,而且由于耦合补偿可以克 服相邻路径间彼此的干扰 ,更客观、正确地引导蚂蚁 的选路 ,减少算法运行的迭代次数 ,所以总的计算性 能会得到提高. 第 4 期 冀俊忠 ,等 :基于信息素扩散模型解耦控制策略的蚁群算法 ·5 ·
智能系统学报 第2卷 为了进一步验证本文算法的有效性，在TSP问 3 实验结果 题典型范例上进行了大量的实验.表2是不同算法 本节对新算法的性能进行测试，并将测试结果 运行得到的实验结果.在表2中，最优解是指获得的 与基本的ACS算法及PDACO算法进行了比较.实 最短路径长度，进化代数是指当得到表2中的结果 验中所使用的多个TSP问题的数据来源于 时，蚂蚁的周游代数(10次实验的平均取整).从结 TSPLIB标准库(http://elib.zib.de/pub/mp 果可见，对于oliver30问题，3种算法都能得到最优 testdata/tsp/.tsplib/tsplib.html).算法用 解，但所需要的迭代次数和运行时间各不相同，ACS Visual C++语言编程实现，实验的参数均通过实 算法的迭代次数和运行时间最大，PDACO算法的 验确定，表1为获得下面实验结果所使用的参数表. 迭代次数和运行时间较ACS算法有明显改进，而本 文算法在迭代次数和运行时间上又有进一步的改 表1不同TSP范例所使用的参数配置 进.类似地，在其他3个问题上本文算法在迭代次数 Table 1 Para meter deployments used in experiments 和运行时间上都有显著的改进.而且，在较少的进化 for several TSP problems 代数和较短的运行时间内，本文算法在oliver.30、 TSP问题的 实验时使用的参数 bays29、dantzig42问题上都得到了各自的最优解， 典型范例1.pQQ' a B 在berlin52问题上也得到了更接近于最优解的结 oliver.300.856001.5305510.4/8 果 表3为不同算法在各种TSP问题上的单次运 bays290.856002.030.5510.4w8 行时间比较，从实验结果可以看出：正如在算法计算 复杂度中所分析的那样，由于PDACO算法和本文 dantzig420.854502.040.510.48 算法都包含扩散模型的建立与计算，故单次迭代的 berlin52 0.8 57002.54055 1 0.4四8 运行时间都较ACS算法有所增加，而本文算法与 PDACO算法相比，由于具有相当的单次计算复杂 度，故在单次迭代的运行时间上非常接近， 表2 各种ISP问题上不同算法的结果比较 Table 2 Comparison of results among different algorithms for several TSP problems ACS算法 PDACO算法 本文算法 问题的 典型范例 最优解 得到的 所需进 运行时 得到的 所需进 运行时 得到的 所需进 运行时 最优解 化代数 间/s 最优解 化代数 间/s 最优解 化代数 间/s oliver30 423.74 423.74 830 1245 423.74 76.00 3.8 423.74 1.68 bays292020.002034.00 955 13.30 2028.00 132.00 5.6 2020.00 46 2.00 dantzig42699.00714.00 896 37.60 712.00 174.00 23.1 699.00 61 8.20 berlin:527542.007681.45 1754 147.307663.59316.00 90.2 7544.37 82 23.80 表3不同算法在各种SP问题上的单次运行时间比较 Table 3 Comparison of time consumption of a single cycle among different algorithms for several TSP problems ACS算法 PDACO算法 本文算法 问题的 典型范例 最优解 每次迭代的 每次迭代的 每次迭代的 得到的最优解 得到的最优解 得到的最优解 运行时间/s 运行时间/s 运行时间/s oliver30 423.74 423.74 0.01500 423.74 0.05000 423.74 0.05100 bays292020.00 2034.00 0.01393 2028.00 0.04242 2020.00 0.04348 dantig42 699.00 714.00 0.04196 712.00 0.13276 699.00 0.13443 berlin527542.00 7681.45 0.08398 7663.59 0.28544 7544.37 0.29024 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
3 实验结果 本节对新算法的性能进行测试 ,并将测试结果 与基本的 ACS 算法及 PDACO 算法进行了比较. 实 验中 所 使 用 的 多 个 TSP 问 题 的 数 据 来 源 于 TSPL IB 标 准 库 ( http :/ / elib. zib. de/ p ub/ mp2 testdata/ tsp/ tsplib/ tsplib. html ) . 算 法 用 Visual C + + 语言编程实现 ,实验的参数均通过实 验确定 ,表 1 为获得下面实验结果所使用的参数表. 表 1 不同 TSP 范例所使用的参数配置 Table 1 Parameter deployments used in experiments for several TSP problems TSP 问题的 典型范例 实验时使用的参数 1 - ρ Q Q′ α β q0 ω γ θ oliver30 018 5 600 115 3 0155 1 014 π/ 8 bays29 018 5 600 210 3 0155 1 014 π/ 8 dantzig42 018 5 450 210 4 015 1 014 π/ 8 berlin52 018 5 700 215 4 0155 1 014 π/ 8 为了进一步验证本文算法的有效性 ,在 TSP 问 题典型范例上进行了大量的实验. 表 2 是不同算法 运行得到的实验结果. 在表 2 中 ,最优解是指获得的 最短路径长度 ,进化代数是指当得到表 2 中的结果 时 ,蚂蚁的周游代数 (10 次实验的平均取整) . 从结 果可见 ,对于 oliver30 问题 ,3 种算法都能得到最优 解 ,但所需要的迭代次数和运行时间各不相同 ,ACS 算法的迭代次数和运行时间最大 ,PDACO 算法的 迭代次数和运行时间较 ACS 算法有明显改进 ,而本 文算法在迭代次数和运行时间上又有进一步的改 进. 类似地 ,在其他 3 个问题上本文算法在迭代次数 和运行时间上都有显著的改进. 而且 ,在较少的进化 代数和较短的运行时间内 ,本文算法在 oliver30、 bays29、dantzig42 问题上都得到了各自的最优解 , 在 berlin52 问题上也得到了更接近于最优解的结 果. 表 3 为不同算法在各种 TSP 问题上的单次运 行时间比较 ,从实验结果可以看出 :正如在算法计算 复杂度中所分析的那样 ,由于 PDACO 算法和本文 算法都包含扩散模型的建立与计算 ,故单次迭代的 运行时间都较 ACS 算法有所增加 ,而本文算法与 PDACO 算法相比 ,由于具有相当的单次计算复杂 度 ,故在单次迭代的运行时间上非常接近. 表 2 各种 TSP 问题上不同算法的结果比较 Table 2 Comparison of results among different algorithms for several TSP problems 典型范例 问题的 最优解 ACS 算法 PDACO 算法 本文算法 得到的 最优解 所需进 化代数 运行时 间/ s 得到的 最优解 所需进 化代数 运行时 间/ s 得到的 最优解 所需进 化代数 运行时 间/ s oliver30 423174 423174 830 12145 423174 76100 318 423174 33 1168 bays29 2 020100 2 034100 955 13130 2 028100 132100 516 2 020100 46 2100 dantzig42 699100 714100 896 37160 712100 174100 2311 699100 61 8120 berlin52 7 542100 7 681145 1 754 147130 7 663159 316100 9012 7544137 82 23180 表 3 不同算法在各种 TSP问题上的单次运行时间比较 Table 3 Comparison of time consumption of a single cycle among different algorithms for several TSP problems 典型范例 问题的 最优解 ACS 算法 PDACO 算法 本文算法 得到的最优解 每次迭代的 运行时间/ s 得到的最优解 每次迭代的 运行时间/ s 得到的最优解 每次迭代的 运行时间/ s oliver30 423174 423174 01015 00 423174 01050 00 423174 01051 00 bays29 2 020100 2 034100 01013 93 2 028100 01042 42 2 020100 01043 48 dantig42 699100 714100 01041 96 712100 01132 76 699100 01134 43 berlin52 7 542100 7 681145 01083 98 7 663159 01285 44 7 544137 01290 24 ·6 · 智 能 系 统 学 报 第 2 卷
第4期 冀俊忠，等：基于信息素扩散模型解耦控制策略的蚁群算法 图4为不同算法在dantzig42问题上的解图，其 有更强的不断获得最优解的能力，因此本文算法更 中图4(a)为ACs算法得到的最优解，图4(b)为 容易克服最优解停滞的现象（陷入局部最优），获得 PDACO算法得到的最优解，而图4(c)为本文算法 问题的全局最优解 得到的最优解.从图可见，不同算法在局部连接的差 110 异（虚线圆框内的连接部分）导致了最后所得到的最 100 90 优解的不同」 炉特 2品 入 4181121161 迭代次数！次 (a)ACS算法的多样性曲线 110 100 90 80 4物 60 (a)ACS算法最优解 0 81121161 迭代次数/次 (b)PDACO算法的多样性曲线 10 100 88 70 60 50 40 41 81121161 (b)PDACO算法最优解 迭代次数/次 (c)本文算法的多样性曲线 图5不同算法在dantzig42问题上的多样性曲线 Fig 5 Diversity curves of several algorithms for dantzig42 总之，本文算法在解的质量、解的多样性、周游 的迭代代数、算法运行时间等方面具有更好的结果 这说明了基于信息素扩散模型的解耦策略利于提高 和改进蚁群算法的求解能力 (c)本文算法最优解 图4不同算法在dantzig42问题上的解图 4 结束语 Fig 4 Tours of several algorithms for dantzig42 蚁群优化算法是目前群集智能理论研究领域中 图5是不同算法在dantzig42问题的求解过程 的一个研究热点，该算法已成功应用于许多复杂组 中得到的多样性曲线比较.其中，横坐标为蚁群旅行 合优化问题的求解.虽然目前的许多算法都具有发 现较优解的能力，但迭代次数多、收敛速度慢仍是制 的迭代数，纵坐标为蚁群在每次迭代所得到的旅行 约大多数算法在实际组合优化问题中应用的瓶颈 长度的标准偏差，其公式见参考文献[8].从图5中 针对这一问题，本文结合信息素扩散的耦合特征，提 曲线的对比（标准偏差的均值和振幅）可以看出，在 出一种基于信息素扩散模型解耦控制策略的蚁群算 整个随机搜索的过程中，PDACO算法、本文算法的 法.大量TSP问题的实验结果表明：该算法不仅能 多样性性能明显优于ACS算法，而且本文算法在多 获得更好的解，而且能加快算法的收敛速度.进一步 样性性能方面也优于PDACO算法，即本文算法具 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 4 为不同算法在 dantzig42 问题上的解图 ,其 中图 4 (a) 为 ACS 算法得到的最优解 ,图 4 ( b) 为 PDACO 算法得到的最优解 ,而图 4 (c) 为本文算法 得到的最优解. 从图可见 ,不同算法在局部连接的差 异(虚线圆框内的连接部分) 导致了最后所得到的最 优解的不同. (a) ACS 算法最优解 (b) PDACO 算法最优解 (c)本文算法最优解 图 4 不同算法在 dantzig42 问题上的解图 Fig14 Tours of several algorithms for dantzig42 图 5 是不同算法在 dantzig42 问题的求解过程 中得到的多样性曲线比较. 其中 ,横坐标为蚁群旅行 的迭代数 ,纵坐标为蚁群在每次迭代所得到的旅行 长度的标准偏差 ,其公式见参考文献[ 8 ]. 从图 5 中 曲线的对比(标准偏差的均值和振幅) 可以看出 ,在 整个随机搜索的过程中 ,PDACO 算法、本文算法的 多样性性能明显优于 ACS 算法 ,而且本文算法在多 样性性能方面也优于 PDACO 算法 ,即本文算法具 有更强的不断获得最优解的能力 ,因此本文算法更 容易克服最优解停滞的现象 (陷入局部最优) ,获得 问题的全局最优解. (a) ACS 算法的多样性曲线 (b) PDACO 算法的多样性曲线 (c) 本文算法的多样性曲线 图 5 不同算法在 dantzig42 问题上的多样性曲线 Fig15 Diversity curves of several algorithms for dantzig42 总之 ,本文算法在解的质量、解的多样性、周游 的迭代代数、算法运行时间等方面具有更好的结果. 这说明了基于信息素扩散模型的解耦策略利于提高 和改进蚁群算法的求解能力. 4 结束语 蚁群优化算法是目前群集智能理论研究领域中 的一个研究热点 ,该算法已成功应用于许多复杂组 合优化问题的求解. 虽然目前的许多算法都具有发 现较优解的能力 ,但迭代次数多、收敛速度慢仍是制 约大多数算法在实际组合优化问题中应用的瓶颈. 针对这一问题 ,本文结合信息素扩散的耦合特征 ,提 出一种基于信息素扩散模型解耦控制策略的蚁群算 法. 大量 TSP 问题的实验结果表明 :该算法不仅能 获得更好的解 ,而且能加快算法的收敛速度. 进一步 第 4 期 冀俊忠 ,等 :基于信息素扩散模型解耦控制策略的蚁群算法 ·7 ·
8 智能系统学报 第2卷 的研究包括借助于相关学科的知识对各种实验参数 [8]黄国锐，曹先彬，王煦法.基于信息素扩散的蚁群算法 的确定进行理论分析，剖析参数的选择与问题最优 [J].电子学报，2004,32(5)：865.868. 解以及解的收敛性的关系 HUANG Guorui,CAO Xianbin,WANG Xufa.An ant colony optimization algorithm based on pheromone diffu- 参考文献： sion [J ]Chinese Journal of Electronics,2004,32(5): [1]彭喜元，彭字，戴毓丰.群智能理论及应用U].电子学 865-868 报，2003,31(12)：1982-1988 [9]BLUM C,DORIGO M.The hyper-cube framework for PEN G Xiyuan,PENG Yu,DAI Yufeng.Swarm intelli- ant colony optimization [J].IEEE Transactions on Sys gence theory and applications[J ]Journal of Electronics, tems,Man,and Cybernetics,2004,34(2):1161-1172. 2003,31(12):1982-1988. 作者简介 [2]DORIGO M,COLORNIA,MANIEZZO V.Distributed 冀俊忠，男，1969年生，博士，副研 optimization by ant colonies [A ]Proc of the First Euro- 究员，中国计算机学会高级会员，主要 pean Conf of Artificial Life [C].Paris:Elsevier,1991. 研究方向为机器学习、Wwcb智能、计算 [3]DORIGO M,MANIEZZO V,COLORNI A.The ant 智能.在国内外学术刊物和重要国际学 system:optimization by a colony of cooperating agents 术会议上发表论文20余篇，其中10余 [J ]IEEE Transactions on Systems,Man,and Cyber- 篇被SCL、EI、ISTP三大检索收录 netics,1996,26(1):29-41. Email jjzol @bjut.edu.cn. [4]DORIGO M,GAMBARDELLA L M.Ant colony sys- tem:a cooperative learning approach to the traveling salesman problem[J ]IEEE Trans Evolutionary Compu tation,1997,1(1):53-66. 刘椿年，男，1944年生，教授，博士 [5]GAMBARDELLA L M,DORIGO M.Solving aymmet- 生导师，主要研究方向为数据挖掘、人 ric and asymmetric TSPs by ant colonies [A].Interna- 工智能、约束逻辑程序设计.主持多项 tional Conference on Evolutionary Computation[C].Na- 国家自然科学基金和863计划课题.在 goya,Japan,1996. 国内外学术刊物和重要国际学术会议 [6]STU TZL E T,HOOS HH.Maxmin ant system and lo- 上发表论文100余篇，出版专著及译著 cal search for the traveling salesman problem[A].IEEE 多部 Intl Conf on Evolutionary Computation[C].Indianapo- lis:IEEE Press,1997. [7]朱庆保，杨志军.基于变异和动态信息素更新的蚁群优化 算法0].软件学报，2004,15(2)：185·192 黄振，男，1981年生，硕士研究 ZHU Qingbao,YANG Zhijun.An ant colony optimiza- 生，主要研究方向为机器学习、Web智 tion algorithm based on mutation and dynamic pheromone 能、计算智能 updating [J ]Journal of Software,2004,15(2):185 192. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
的研究包括借助于相关学科的知识对各种实验参数 的确定进行理论分析 ,剖析参数的选择与问题最优 解以及解的收敛性的关系. 参考文献 : [1 ]彭喜元 , 彭 宇 , 戴毓丰. 群智能理论及应用[J ]. 电子学 报 ,2003 ,31 (12) :1982 - 1988. PEN G Xiyuan , PEN G Yu , DAI Yufeng . Swarm intelli2 gence theory and applications[J ]. Journal of Electronics , 2003 , 31 (12) :1982 - 1988. [2 ]DORIGO M , COLORNI A , MANIEZZO V. Distributed optimization by ant colonies [A ]. Proc of the First Euro2 pean Conf of Artificial Life [C]. Paris: Elsevier , 1991. [3 ] DORIGO M , MANIEZZO V , COLORNI A. The ant system : optimization by a colony of cooperating agents [J ]. IEEE Transactions on Systems , Man , and Cyber2 netics ,1996 , 26 (1) : 29 - 41. [4 ]DORIGO M , GAMBARDELLA L M. Ant colony sys2 tem : a cooperative learning approach to the traveling salesman problem[J ]. IEEE Trans Evolutionary Compu2 tation , 1997 , 1 (1) : 53 - 66. [5 ] GAMBARDELLA L M , DORIGO M. Solving aymmet2 ric and asymmetric TSPs by ant colonies[ A ]. Interna2 tional Conference on Evolutionary Computation [ C]. Na2 goya , J apan , 1996. [6 ]STU TZL E T , HOOS H H. Max2min ant system and lo2 cal search for the traveling salesman problem[ A ]. IEEE Intl Conf on Evolutionary Computation [ C ]. Indianapo2 lis: IEEE Press ,1997. [7 ]朱庆保 ,杨志军. 基于变异和动态信息素更新的蚁群优化 算法[J ]. 软件学报 , 2004 ,15 (2) :185 - 192. ZHU Qingbao , YAN G Zhijun. An ant colony optimiza2 tion algorithm based on mutation and dynamic pheromone updating [J ]. Journal of Software , 2004 , 15 (2) : 185 - 192. [8 ]黄国锐 ,曹先彬 ,王煦法. 基于信息素扩散的蚁群算法 [J ]. 电子学报 ,2004 ,32 (5) :865 - 868. HUAN G Guorui , CAO Xianbin , WAN G Xufa. An ant colony optimization algorithm based on pheromone diffu2 sion[J ]. Chinese Journal of Electronics , 2004 , 32 (5) : 865 - 868. [9 ]BLUM C , DORIGO M. The hyper2cube framework for ant colony optimization [J ]. IEEE Transactions on Sys2 tems , Man , and Cybernetics ,2004 ,34 (2) : 1161 - 1172. 作者简介 : 冀俊忠 ,男 ,1969 年生 ,博士 ,副研 究员 ,中国计算机学会高级会员 ,主要 研究方向为机器学习、Web 智能、计算 智能. 在国内外学术刊物和重要国际学 术会议上发表论文 20 余篇 ,其中 10 余 篇被 SCI、EI、ISTP 三大检索收录. Email : jjz01 @bjut. edu. cn. 刘椿年 ,男 ,1944 年生 ,教授 ,博士 生导师 ,主要研究方向为数据挖掘、人 工智能、约束逻辑程序设计. 主持多项 国家自然科学基金和 863 计划课题. 在 国内外学术刊物和重要国际学术会议 上发表论文 100 余篇 ,出版专著及译著 多部. 黄 振 ,男 , 1981 年生 ,硕士研究 生 ,主要研究方向为机器学习、Web 智 能、计算智能. ·8 · 智 能 系 统 学 报 第 2 卷