智能系统学报 第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 卷