第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.net112 基于城市信源的信息素扩散模型 文献[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 ·