·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.netMMAS( 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 卷