第2期 蒋建国，等：自适应粒子群算法求解Agct联盟 ·71· 极值和全局极值分别作交叉操作 环内没有明显进化，即可能陷入局部极小，c开始 算法描述如下： 逐步增大，使解更容易跳出局部极小；另外，为了保 1)设定粒子数m,规定迭代次数NC,随机产生 证算法的收敛速度，引入cmax对c幽进行强度控制. m个初始解L=L8,L,L”}: 一旦解跳出局部极小，算法求得的最优解又开始进 2)根据当前位置计算出每个粒子的适应值V, 化时，ca=o,返回成基本PS0算法 (即粒子对应联盟的联盟值V(C©)，设置当前适应 此外，区别于基本PSO算法，APSO算法中分 值为个体极值Vpe,当前位置为个体极值位置 别随机选择口和？个位置进行相应的赋值，而不 LPe,找出其中最大的作为全局极值V,对应位 是随机选择长度为Q和©的段进行交叉，保证了 置为L; 3)和4)操作的有效性；随机选择c个位置赋值0 While(迭代次数<NCdo 或者1，而不是变异，这样不仅简单易于操作，而且 for (i=0;i<m;i++) 提高了解的多样性.改进后3)~5)就成为简单的赋 3)第i个粒子位置L。与L交叉得到L； 值，花费时间远小于原本的交叉和变异，算法复杂度 4)L与L交叉得到L2; 约为O(mNg,降低为原来的1/3 5)对L2进行变异操作得到L: 2.4算法描述 6)对L计算适应值V: 应用APSO算法求解Agent联盟问题，具体算 7)如果V,>Vpe,则Le4=La,Vpet=V; 法伪代码如下： End 1)设定粒子数m,规定迭代次数NC,随机产生 8)根据个体极值Vp,找出全局极值Ve及 m个初始解L”=L9,Lh,L}: 其位置L; 2)根据当前位置计算出每个粒子的适应值V, End 即粒子对应联盟的联盟值V(),设置当前适应 9)输出全局极值Ve及其位置L 值为个体极值Vp,当前位置为个体极值位置 此算法中交叉和变异操作花费时间最多，里面 LPc,找出其中最大的作为全局极值V,对应位 循环3m次，外面循环NC次，因此算法复杂度大约 置为L; 为O(3mNC) While(迭代次数<NC)do 2.3算法的改进 for(i=0;i<m;i++) PS0算法有3个权重因子31：惯性权重Qo、加 3)对于粒子i随机从LPe和L选择c1和 速常数q和a.惯性权重©使粒子保持运动惯性 Q个位置赋值给L”,保证这些位置不重叠：再从 使其有扩展搜索空间的趋势，有能力探索新的区域， 中随机选择ca个位置随机赋值为0或者1； 具有全局搜索能力.加速常数α使粒子具有认知能 4)对L”计算适应值V: 力，在粒子的相互左右下，有能力到达新的搜索空 5)如果V,>Vpe,则Lp=La,Vpe=V,; 间.Q保证了粒子间的交互，使得社会信息得到共 End 享.基本PSO算法在求解Agent联盟生成问题时没 6)根据个体极值Vpet,找出全局极值Ve及 有考虑©、©和a的关系，研究发现较小的惯性权 其位置L: 重①有利于算法收敛，而较大的m有利于跳出局 f(N次循环V都没有改进) 部极值.为了提高算法的全局搜索能力和搜索速度， then if(cap++≤cmax)then cad中++ 引入自适应惯性权重c,在出现局部极小情况时 else Cadp =Cmax 通过c的作用使解跳出局部极小，从而向最优解 else cdp =a 继续进化，称这种能够自适应调整惯性权重©中的 End PSO算法为自适应粒子群算法(APSO). 7)输出全局极值Vm及其位置L ©，算法求解的最优解仍在进化， 3 实验验证 定义1ca中 c+1,最优解在N次循环内没， 有明显改进，且cat+1≤cmax 为了检验APSO算法性能进行了对比实验.首 可见，在APSO系统运行初期，算法求得的最 先产生实验所需的参数：Agent数n=30、每个A- 优解仍在进化时，自适应惯性权重c=©，仍然运 gent的能力向量A=<ad,ad,:a>,Agent之间 行基本PSO算法：当算法求得的最优解在N次循 的通信开销d、任务t的能力需求N();然后分别 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net极值和全局极值分别作交叉操作. 算法描述如下 : 1) 设定粒子数 m ,规定迭代次数 N C,随机产生 m 个初始解 L m n = { L 0 n ,L 1 n , …,L m - 1 n } ; 2) 根据当前位置计算出每个粒子的适应值 V i (即粒子对应联盟的联盟值 V ( C) ) ,设置当前适应 值为个体极值 V i pbest ,当前位置为个体极值位置 L i pbest n ,找出其中最大的作为全局极值 V gbest ,对应位 置为 L gbest n ; While (迭代次数 < N C) do for (i = 0 ;i < m ;i + + ) 3) 第 i 个粒子位置 L i n 与 L gbest n 交叉得到 L i 1 n ; 4) L i 1 n 与 L i pbest n 交叉得到 L i 2 n ; 5) 对 L i 2 n 进行变异操作得到 L i n ; 6) 对 L i n 计算适应值 V i ; 7) 如果 V i > V i pbest ,则 L i pbest n = L i n ,V i pbest = V i ; End 8) 根据个体极值 V i pbest ,找出全局极值 V gbest 及 其位置 L gbest n ; End 9) 输出全局极值 V gbest及其位置 L gbest n 此算法中交叉和变异操作花费时间最多 ,里面 循环 3 m 次 ,外面循环 N C 次 ,因此算法复杂度大约 为 O(3 m N C) . 213 算法的改进 PSO 算法有 3 个权重因子[13 ] :惯性权重 c0 、加 速常数 c1 和 c2 . 惯性权重 c0 使粒子保持运动惯性 , 使其有扩展搜索空间的趋势 ,有能力探索新的区域 , 具有全局搜索能力. 加速常数 c1 使粒子具有认知能 力 ,在粒子的相互左右下 ,有能力到达新的搜索空 间. c2 保证了粒子间的交互 ,使得社会信息得到共 享. 基本 PSO 算法在求解 Agent 联盟生成问题时没 有考虑 c0 、c1 和 c2 的关系 ,研究发现较小的惯性权 重 c0 有利于算法收敛 ,而较大的 c0 有利于跳出局 部极值. 为了提高算法的全局搜索能力和搜索速度 , 引入自适应惯性权重 cadp ,在出现局部极小情况时 通过 cadp的作用使解跳出局部极小 ,从而向最优解 继续进化 ,称这种能够自适应调整惯性权重 cadp 的 PSO 算法为自适应粒子群算法(APSO) . 定义 1 cadp = c0 ,算法求解的最优解仍在进化 , cadp + 1 ,最优解在 N 次循环内没 , 有明显改进 ,且 cadp + 1 ≤cmax . 可见 ,在 A PSO 系统运行初期 ,算法求得的最 优解仍在进化时 ,自适应惯性权重 ccdp = c0 ,仍然运 行基本 PSO 算法 ;当算法求得的最优解在 N 次循 环内没有明显进化 ,即可能陷入局部极小 , cadp 开始 逐步增大 ,使解更容易跳出局部极小 ;另外 ,为了保 证算法的收敛速度 ,引入 cmax对 cadp 进行强度控制. 一旦解跳出局部极小 ,算法求得的最优解又开始进 化时 ,cadp = c0 ,返回成基本 PSO 算法. 此外 ,区别于基本 PSO 算法 ,A PSO 算法中分 别随机选择 c2 和 c1 个位置进行相应的赋值 ,而不 是随机选择长度为 c2 和 c1 的段进行交叉 ,保证了 3) 和 4) 操作的有效性 ;随机选择 cadp 个位置赋值 0 或者 1 ,而不是变异 ,这样不仅简单易于操作 ,而且 提高了解的多样性. 改进后 3) ～5) 就成为简单的赋 值 ,花费时间远小于原本的交叉和变异. 算法复杂度 约为 O( m N C) ,降低为原来的1/ 3. 214 算法描述 应用 A PSO 算法求解 Agent 联盟问题 ,具体算 法伪代码如下 : 1) 设定粒子数 m ,规定迭代次数 N C ,随机产生 m 个初始解 L m n = { L 0 n ,L 1 n , …,L n - 1 n } ; 2) 根据当前位置计算出每个粒子的适应值 V i (即粒子对应联盟的联盟值 V ( C) ) ,设置当前适应 值为个体极值 V i pbest , 当前位置为个体极值位置 L i pbest n ,找出其中最大的作为全局极值 V gbest ,对应位 置为 L gbest n ; While (迭代次数 < N C) do for (i = 0 ;i < m ;i + + ) 3) 对于粒子 i 随机从 L i pbest n 和 L gbest n 选择 c1 和 c2 个位置赋值给 L i n ,保证这些位置不重叠;再从 L i n 中随机选择 cadp个位置随机赋值为 0 或者 1 ; 4) 对 L i n 计算适应值 V i ; 5) 如果 V i > Vpbest ,则 L i pbest n = L i n ,V i pbest = V i ; End 6) 根据个体极值 V i pbest ,找出全局极值 V gbest 及 其位置 L gbest n ; If ( N 次循环 V gbest都没有改进) then if ( cadp + + ≤cmax ) then cadp + + else cadp = cmax else cadp = c0 End 7) 输出全局极值 V gbest及其位置 L gbest n 3 实验验证 为了检验 APSO 算法性能进行了对比实验. 首 先产生实验所需的参数 : Agent 数 n = 30、每个 A2 gent 的能力向量 Ai = < a 1 i , a 2 i , …, a r i > , Agent 之间 的通信开销 dij 、任务 t 的能力需求 N ( t) ;然后分别 第 2 期 蒋建国 ,等 :自适应粒子群算法求解 Agent 联盟 ·71 ·