第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 ·