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