第2卷第2期 智能系统学报 Vol.2 Na 2 2007年4月 CAAI Transactions on Intelligent Systems Apr.2007 自适应粒子群算法求解Agent联盟 蒋建国，吴琼，夏娜 (合肥工业大学计算机与信息学院，安徽合肥230009) 摘要：联盟生成是多Agct系统的一个关键问题，主要研究如何在多Agent系统中动态生成面向任务的最优A: gct联盟.引入粒子群算法来解决这一问题，受到惯性权重a在进化过程中所起作用的启发，引入自适应惯性权重 对粒子群算法进行改进，使其不再易于陷入局部极小.对比实验结果表明，该算法在解的性能和收敛速度上均优 于相关算法 关键词：多Aget系统：粒子群优化算法；自适应粒子群算法；联盟 中图分类号：TP18文献标识码：A文章编号：16734785(2007)02006905 Solving Agent coalition using ada ptive particle swarm optimization algorithm JIAN GJiamguo,WU Qiong XIA Na (College of Computer and Information,Hefei University of Technology,Hefei 230009,China) Abstract:Coalition Generation is a key issue in a Multi-Agent System which primarily focuses on generation of an optimal task-oriented coalition in a dynamic manner.A particle swarm optimization (PSO)algorithm is adopted to solve the problem.And a novel "adaptive inertia weight"is proposed to improve PSO by the illumination of function of inertia weight ,so as to avoid falling into local minimum.The results of compar- ison experiments show that this algorithm is superior to other related methods in both performance of solu- tion and convergence rate. Key words:MAS;PSO algorithm;adaptive particle swarm optimization;coalition 在大规模复杂的分布式智能控制系统中，多个研究，包括联盟生成4、成员间协商1以及联盟内 子系统之间的协调、合作尤为重要，基于智能Agent 收益分配？割等方面，其中联盟生成问题是本论文 的MAS系统将是解决这一难题的重要途径.在由 的研究重点 自治Agent构成的多Agent系统(MAS)中，Agent 1联盟生成问题 之间经常需要协作来完成任务求解.假设系统中有 一个Agent集合和一组待求解任务，由于单个A- 1.1问题的描述 gent无法独立完成某一任务或者通过多个Agent 联盟生成问题可形式化描述如下 协作能提高求解效率，Agent之间可以通过协商形 设Agent集N=(A1,A2,Am},任意A都有 成Agent组称之为联盟(coalition)来共同承担 一个能力向量：A=,a0,1≤ 该任务.自Shehoryli和Sandholm2.引提出联盟方 i≤，1≤≤用于定量描述A,执行某种特定动作 法以来，已取得了一定的研究进展.通过联盟可以提 的能力大小.任务t具有一定的能力需求N()= 高Agent求解问题的能力，获得更多的报酬，因而 ,n0,1≤k≤)，Agent完成任 联盟是多Agent系统(MAS)中的重要合作方法，已 务t可获得相应的利益P(). 经有很多学者在Agent联盟这一领域进行了大量 定义一个联盟C是N的一个非空子集.联盟C 有一个能力向量C=,C是联盟中 收稿日期：20061012. 基金项目：国家自然科学基金资助项目(60474035) 所有Agent能力向量的总和，即C-∑A.联盟C 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 2 期 智 能 系 统 学 报 Vol. 2 №. 2 2007 年 4 月 CAA I Transactions on Intelligent Systems Apr. 2007 自适应粒子群算法求解 Agent 联盟 蒋建国 ,吴 琼 ,夏 娜 (合肥工业大学 计算机与信息学院 ,安徽 合肥 230009) 摘 要 :联盟生成是多 Agent 系统的一个关键问题 ,主要研究如何在多 Agent 系统中动态生成面向任务的最优 A2 gent 联盟. 引入粒子群算法来解决这一问题 ,受到惯性权重 c0 在进化过程中所起作用的启发 ,引入自适应惯性权重 cadp对粒子群算法进行改进 ,使其不再易于陷入局部极小. 对比实验结果表明 ,该算法在解的性能和收敛速度上均优 于相关算法. 关键词 :多 Agent 系统 ;粒子群优化算法 ;自适应粒子群算法 ;联盟 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0220069205 Solving Agent coalition using adaptive particle swarm optimization algorithm J IAN G Jian2guo ,WU Qiong ,XIA Na (College of Computer and Information , Hefei University of Technology , Hefei 230009 , China) Abstract :Coalition Generation is a key issue in a Multi2Agent System which p rimarily focuses on generation of an optimal task2oriented coalition in a dynamic manner. A particle swarm optimization (PSO) algorit hm is adopted to solve t he problem. And a novel“adaptive inertia weight”is propo sed to improve PSO by t he illumination of f unction of inertia weight ,so as to avoid falling into local minimum. The results of compar2 ison experiments show that t his algorit hm is superior to other related met hods in both performance of solu2 tion and convergence rate. Keywords :MAS; PSO algorithm ; adaptive particle swarm optimization ;coalition 收稿日期 :2006210212. 基金项目 :国家自然科学基金资助项目(60474035) . 在大规模复杂的分布式智能控制系统中 ,多个 子系统之间的协调、合作尤为重要 ,基于智能 Agent 的 MAS 系统将是解决这一难题的重要途径. 在由 自治 Agent 构成的多 Agent 系统 (MAS) 中 ,Agent 之间经常需要协作来完成任务求解. 假设系统中有 一个 Agent 集合和一组待求解任务 ,由于单个 A2 gent 无法独立完成某一任务或者通过多个 Agent 协作能提高求解效率 ,Agent 之间可以通过协商形 成 Agent 组 ———称之为联盟 (coalition) 来共同承担 该任务. 自 Shehory [1 ] 和 Sandholm [2 - 3 ] 提出联盟方 法以来 ,已取得了一定的研究进展. 通过联盟可以提 高 Agent 求解问题的能力 ,获得更多的报酬 ,因而 联盟是多 Agent 系统(MAS) 中的重要合作方法 ,已 经有很多学者在 Agent 联盟这一领域进行了大量 研究 ,包括联盟生成[4 - 5 ] 、成员间协商[6 ]以及联盟内 收益分配[7 - 8 ]等方面 ,其中联盟生成问题是本论文 的研究重点. 1 联盟生成问题 111 问题的描述 联盟生成问题可形式化描述如下 : 设 Agent 集 N = { A1 , A2 , …, A n } ,任意 Ai 都有 一个能力向量 : Ai = , a k i ≥0 , (1 ≤ i ≤n ,1 ≤k ≤r) 用于定量描述 Ai 执行某种特定动作 的能力大小. 任务 t 具有一定的能力需求 N ( t) = , n k ≥0 , (1 ≤k ≤r) , Agent 完成任 务 t 可获得相应的利益 P ( t) . 定义一个联盟 C是 N 的一个非空子集. 联盟 C 有一个能力向量 C = , C 是联盟中 所有 Agent 能力向量的总和 , 即 C = A∑i ∈C Ai . 联盟 C
·70· 智能系统学报 第2卷 可以完成任务t的必要条件是： 1≤k≤r,n≤c 2算法 作以下假设：(1)和惯例一样23]，在特征函数 2.1粒子群算法 对策(character function games,CFGs)中研究联盟 粒子群算法(PSO)是由Kennedy和Eber 形成.每个联盟C的值用一个特征函数V(C给出. hart.1等于1995年提出的一种进化计算算法 假定vC0,V(C=P()-F(g-C(C.式中 其基本思想来源于对鸟群觅食过程的研究及行为模 P()指完成任务所获得的利益：F(C指联盟成员总 拟.群体中的鸟被抽象为理想“粒子”，这些“粒子”的 能力折合的成本；C(C指联盟协作求解t过程中的 运动受到自身速度、自身和群体的历史最佳位置信 额外开销，主要是通信开销.如果联盟C不满足上 息的影响，能够在复杂的解空间寻找最优解.PSO 述必要条件，则V(C为0，否则V(d为正数.2)在 算法概念简明、实现方便，因此自从提出以来便在短 非超加性环境中研究联盟形成)（超加性是指G, 期内迅速得到了国际进化计算研究领域的认可，并 G∈N,CnC=Φ，有V(CUG)≥V(C)+ 在算法实现模式及应用领域得到了很大的发展】 V(C),在这样的环境中，最大的联盟将是最有益 PS0初始化为一群随机粒子（随机解），然后通 的) 过迭代找到最优解.在每次迭代中，每个粒子根据以 Agent联盟生成问题就是对于任务t寻找最优 下公式更新自己的速度和新的位置： 的联盟C(C三N),使得联盟值V(C尽可能大.由于 V+I a ve c (pbest x)+c(gbest -x) 在MAS中，不同Agent之间几乎都存在彼此合作 1) 形成联盟的可能，可能的联盟总数同MAS中A Xk+I XE Vk+1. 2) gent的数目成指数关系，为了得到一个满意的结 式中pbesta表示粒子本身找到的最优解的位置； 果必须考虑所有或大部分的联盟组合形式，因此联 gbestx表示整个种群目前找到的最优解的位置； 盟问题是一个复杂的组合优化问题 是粒子的速度向量；x是当前粒子的位置；©、a和 1.2相关的工作分析 Q是权重系数.Vg+1是pbeste-x和gbest&-x 目前在MAS中，联盟形成的基本理论是N人 矢量的加权和，其示意图如图121所示： 合作对策论，如Shapley值核、核心等.N人合作对 pbest 策主要考虑如何划分联盟值，检查划分的稳定性和 公平性，使Agent在决策时愿意形成全局最优联 盟，它没有考虑算法，只考虑解的存在性，也不考虑 ●gbest. 计算资源通信开销和计算分布等要求， 随着MAS的发展，研究人员从计算可实现的 角度研究联盟生成，并提出了一些相关算法.Sand holm2.刂、胡山立o1、徐晋晖基于“联盟机构”求 图1粒子运动矢量示意图 解多任务的Agent联盟，联盟的生成过程就是在联 Fig 1 Sketch map of particle's movement vector 盟结构图中进行搜索.这些算法大多通过约束条件 2.2基于基本PS0算法求解Agent联盟 来裁减搜索树，减少搜索空间，在降低了算法复杂度 Agent联盟问题是在含有n个Agent的MAS 的同时也牺牲了对最优解的求解，往往得到一个与 中，寻找能够完成任务t且联盟值最大的Agent联 最优解相距在一个界限内的次优解.Sen]、骆正 盟，属于组合优化问题.在PS0算法中每一个位置 虎]基于遗传算法求解Aget联盟，在可接受的时 对应一个联盟，在单任务联盟中，由于Agent只能 间内求解的质量有所提高.夏娜]等引入改进后的 选择参加或者不参加联盟，因此解可以表示为一个 蚁群算法来求解单任务的Agent联盟，加快了收敛 n维矢量Ln=,1,∈0,1}(1≤ 速度；还有很多学者在MAS联盟的应用方面做了 W,h=1代表Agent:.在L所对应的联盟里.PSO 大量工作，MAS联盟已经被成功应用于项目管 算法的本质是利用个体极值和全局极值2个信息， 理、虚拟企业创建1、智能诊断6]和智能控 来指导粒子下一步的迭代位置).如按照基本PS0 制1等领域。 算法，其速度难以表达，故借鉴遗传算法的思想：式 本文在参考这些成果的基础上，引入粒子群算 (I)中：ovk项可以看作变异操作，q(pbest:-x)+ 法来求解单任务的Agent联盟 a(gbestr-x)可以看作交叉操作，将当前解与个体 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
可以完成任务 t 的必要条件是 : Π1 ≤k ≤r, n k ≤c k . 作以下假设 : (1) 和惯例一样[2 - 3 ,9 ] ,在特征函数 对策(character f unction games , CFGs) 中研究联盟 形成. 每个联盟 C的值用一个特征函数 V ( C) 给出. 假定 V ( C) ≥0 , V ( C) = P ( t) - F( C) - C( C) . 式中 P( t) 指完成任务所获得的利益; F( C) 指联盟成员总 能力折合的成本; C( C) 指联盟协作求解 t 过程中的 额外开销 ,主要是通信开销. 如果联盟 C 不满足上 述必要条件 ,则 V ( C) 为 0 ,否则 V ( C) 为正数. (2) 在 非超加性环境中研究联盟形成[3 ] (超加性是指 ΠC1 , C2 Α N , C1 ∩C2 = Φ, 有 V ( C1 ∪C2 ) ≥V ( C1 ) + V ( C2 ) ,在这样的环境中 , 最大的联盟将是最有益 的) . Agent 联盟生成问题就是对于任务 t 寻找最优 的联盟 C( C Α N) ,使得联盟值 V ( C) 尽可能大. 由于 在 MAS 中 ,不同 Agent 之间几乎都存在彼此合作 形成联盟的可能 , 可能的联盟总数同 MAS 中 A2 gent 的数目成指数关系[ 1 ] ,为了得到一个满意的结 果必须考虑所有或大部分的联盟组合形式 ,因此联 盟问题是一个复杂的组合优化问题. 112 相关的工作分析 目前在 MAS 中 ,联盟形成的基本理论是 N 人 合作对策论 ,如 Shapley 值、核、核心等. N 人合作对 策主要考虑如何划分联盟值 ,检查划分的稳定性和 公平性 ,使 Agent 在决策时愿意形成全局最优联 盟 ;它没有考虑算法 ,只考虑解的存在性 ,也不考虑 计算资源、通信开销和计算分布等要求. 随着 MAS 的发展 ,研究人员从计算可实现的 角度研究联盟生成 ,并提出了一些相关算法. Sand2 holm [2 - 3 ] 、胡山立[10 ] 、徐晋晖[ 11 ] 基于“联盟机构”求 解多任务的 Agent 联盟 ,联盟的生成过程就是在联 盟结构图中进行搜索. 这些算法大多通过约束条件 来裁减搜索树 ,减少搜索空间 ,在降低了算法复杂度 的同时也牺牲了对最优解的求解 ,往往得到一个与 最优解相距在一个界限内的次优解. Sen [12 ] 、骆正 虎[13 ]基于遗传算法求解 Agent 联盟 ,在可接受的时 间内求解的质量有所提高. 夏娜[5 ] 等引入改进后的 蚁群算法来求解单任务的 Agent 联盟 ,加快了收敛 速度 ;还有很多学者在 MAS 联盟的应用方面做了 大量工作 , MAS 联盟已经被成功应用于项目管 理[14 ] 、虚拟企业创建[15 ] 、智能诊断[ 16 ] 和智能 控 制[17 ]等领域. 本文在参考这些成果的基础上 ,引入粒子群算 法来求解单任务的 Agent 联盟. 2 算 法 211 粒子群算法 粒子群算法 ( PSO) 是由 Kennedy 和 Eber2 hart [ 18 - 19 ]等于 1995 年提出的一种进化计算算法 , 其基本思想来源于对鸟群觅食过程的研究及行为模 拟. 群体中的鸟被抽象为理想“粒子”,这些“粒子”的 运动受到自身速度、自身和群体的历史最佳位置信 息的影响 ,能够在复杂的解空间寻找最优解. PSO 算法概念简明、实现方便 ,因此自从提出以来便在短 期内迅速得到了国际进化计算研究领域的认可 ,并 在算法实现模式及应用领域得到了很大的发展. PSO 初始化为一群随机粒子 (随机解) ,然后通 过迭代找到最优解. 在每次迭代中 ,每个粒子根据以 下公式更新自己的速度和新的位置 : vk+1 = c0 vk + c1 (p best k - xk ) + c2 (gbest k - xk ) . (1) xk+1 = xk + vk+1 . (2) 式中 :p best k 表示粒子本身找到的最优解的位置 ; gbest k 表示整个种群目前找到的最优解的位置 ; vk 是粒子的速度向量; xk 是当前粒子的位置; c0 、c1 和 c2 是权重系数. vk + 1 是 vk 、p best k - xk 和 gbest k - xk 矢量的加权和 ,其示意图如图 1 [20 ]所示 : 图 1 粒子运动矢量示意图 Fig11 Sketch map of particle’s movement vector 212 基于基本 PSO 算法求解 Agent 联盟 Agent 联盟问题是在含有 n 个 Agent 的 MAS 中 ,寻找能够完成任务 t 且联盟值最大的 Agent 联 盟 ,属于组合优化问题. 在 PSO 算法中每一个位置 对应一个联盟 ,在单任务联盟中 ,由于 Agent 只能 选择参加或者不参加联盟 ,因此解可以表示为一个 n 维矢量 L n = , li ∈{ 0 , 1} (1 ≤i ≤ n) , li = 1 代表 Agenti 在 L 所对应的联盟里. PSO 算法的本质是利用个体极值和全局极值 2 个信息 , 来指导粒子下一步的迭代位置[13 ] . 如按照基本 PSO 算法 ,其速度难以表达 ,故借鉴遗传算法的思想 :式 (1) 中 : c0 vk 项可以看作变异操作 , c1 (p best k - xk ) + c2 (gbest k - xk ) 可以看作交叉操作 ,将当前解与个体 ·70 · 智 能 系 统 学 报 第 2 卷
第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(迭代次数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(迭代次数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=,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 (迭代次数 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 (迭代次数 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 = , Agent 之间 的通信开销 dij 、任务 t 的能力需求 N ( t) ;然后分别 第 2 期 蒋建国 ,等 :自适应粒子群算法求解 Agent 联盟 ·71 ·
·72 智能系统学报 第2卷 应用文献10]的改进型蚁群算法基本PS0算法和 JIAN GJianguo,XIA Na,QI Meibin,et al.An ant colo- 本文提出的APSO算法求解该Agent联盟问题，并 ny algorithm based multi-task coalition serial generation 对所得结果进行了比较.下图2为最优解进化曲线， algorithm[J ]Acta Electronica Sinica,2005,33(12): 说明了3种算法解的进化过程比较 2178.2182 从图2可以看出，和前2种算法相比，APS0算 [5]夏娜，蒋建国，魏星，等.改进型蚁群算法求解单任 法不仅在解的质量上有所提高，而且收敛速度较快 务Agent联盟[U].计算机研究与发展，2005,42(5)： ×10 734.739 3.82 XIA Na,JIANG Jianguo,WEI Xing,et al.Searching 3.80 for Agent coalition for single task using improved ant col- 3.78 ony algorithm[J].Journal of Computer Research and De- 3.76 velopment,2005,42(5):734.739. 3.74H 一自适应粒子群 [6]陶海军，王亚东，郭茂祖，等.基于熟人联盟及扩充合同 基本粒子群 3.72 网协议的多智能体协商模型[J].计算机研究与发展， 改选型蚁群 2006,43(7):1155.1160. 3.70650100159200.250300350400450500 进化代数 TAO Haijun,WANG Yadong,Guo Maozu,et al.A multi-Agent negotiation model based on acquaintance coa- 图23种算法求解过程最优解进化曲线 lition and extended contract net protocol [J].Journal of Fig 2 The solution evolving curves of 3 algorithms Computer Research and Development,2006,43(7): 1155-1160 4 结束语 [7]蒋建国，夏娜，于春华.基于能力向量发挥率和拍卖 的联盟形成策略U].电子学报，2004,32(12A):215- 本文引入APSO算法来求解单任务Agent联 217 盟问题，保持了PS0算法简单、并行的优点；并且在 JIANG Jianguo,XIA Na,YU Chunhua.The coalition 求解过程中APSO算法对惯性权重a进行了自适 formation strategy based on capability vector contribu 应调整，使V更容易跳出局部极小，具有更强的 tiomrrate and auction [J ]Acta Electronica Sinica,2004, 鲁棒性.实验证明APSO算法有利于求解此类A 32(12A):215-217. gent联盟形成问题.下一步工作是研究多任务并行 [8]李亚东，李从东，张炎亮.动态联盟收益分配问题的博弈 Agent联盟生成算法的构造】 研究[U].工业工程，2006,9(3)：15·18. LI Yadong,LI Congdong,ZHANG Yanliang.Research 参考文献： on the profit-allotting problem of dynamic-alliances [1]SHEHORY O,KRAUS S.Task allocation via coalition through the game theory [J].Industrial Engineering formation among autonomous agents [A].In O Shehory Journal,2006,9(3):15-18. ed.Proc of DCAF95 [C].Los Angeles,CA,USA, [9]SEN S,P DUTTA S.Searching for optimal coalition Morgan Kaufmann Publishers,1995. structures [A].In S Sen ed.Proc.of the 4th ICMAS [2]SANDHOLM T,LARSON K,ANDERSSON M.et al. [C].Boston,USA,2000. Anytime coalition structure generation with worst case [10]胡山立，石纯一.一种任意时间联盟结构生成算法印] guarantees [A].In T Sandholm ed.Proc of the National 软件学报，2001,12(5)：729.734. Conference on Artificial Intelligence [C].Madison,WI, HU Shanli,SHI Chunyi.An anytime coalition struc- 1998 ture generation algorithm [J ]Journal of Software, [3]SAND HOL M T,L ESSER V.Coalition among computa- 2001,12(5):729.734. tionally bounded agents [J ]Artificial Intelligence, [11]徐晋晖，张伟，石纯一，等.面向结构的Agct组织 1997,94(1):99.137. 形成和演化机制[J].计算机研究与发展，2001,38 [4]蒋建国，夏娜，齐美彬，等.一种基于蚁群算法的多任 (8):897-903 务联盟串行生成算法[J].电子学报，2005,33(12)： XU Jinhui,ZHANG Wei,SHI Chunyi,et al.A struc- 2178-2182 ture-oriented mechanism of agent organization formation 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
应用文献[10 ]的改进型蚁群算法、基本 PSO 算法和 本文提出的 APSO 算法求解该 Agent 联盟问题 ,并 对所得结果进行了比较. 下图 2 为最优解进化曲线 , 说明了 3 种算法解的进化过程比较. 从图 2 可以看出 ,和前 2 种算法相比 ,APSO 算 法不仅在解的质量上有所提高 ,而且收敛速度较快. 图 2 3 种算法求解过程最优解进化曲线 Fig12 The solution evolving curves of 3 algorithms 4 结束语 本文引入 A PSO 算法来求解单任务 Agent 联 盟问题 ,保持了 PSO 算法简单、并行的优点 ;并且在 求解过程中 APSO 算法对惯性权重 c0 进行了自适 应调整 ,使 V gbest 更容易跳出局部极小 ,具有更强的 鲁棒性. 实验证明 A PSO 算法有利于求解此类 A2 gent 联盟形成问题. 下一步工作是研究多任务并行 Agent 联盟生成算法的构造. 参考文献 : [1 ]SHEHOR Y O , KRAUS S. Task allocation via coalition formation among autonomous agents [ A ]. In O Shehory ed. Proc of IJCAI295 [ C ]. Los Angeles , CA , USA , Morgan Kaufmann Publishers , 1995. [2 ]SAND HOLM T , LARSON K , ANDERSSON M , et al. Anytime coalition structure generation with worst case guarantees [ A ]. In T Sandholm ed. Proc of the National Conference on Artificial Intelligence [C]. Madison , WI , 1998. [3 ]SAND HOLM T , L ESSER V. Coalition among computa2 tionally bounded agents [ J ]. Artificial Intelligence , 1997 , 94 (1) : 99 - 137. [4 ]蒋建国 ,夏 娜 , 齐美彬 , 等. 一种基于蚁群算法的多任 务联盟串行生成算法 [J ]. 电子学报 , 2005 , 33 (12) : 2178 - 2182. J IAN GJianguo , XIA Na , QI Meibin , et al. An ant colo2 ny algorithm based multi2task coalition serial generation algorithm[J ]. Acta Electronica Sinica , 2005 , 33 (12) : 2178 - 2182. [5 ]夏 娜 , 蒋建国 , 魏 星 ,等. 改进型蚁群算法求解单任 务 Agent 联盟[J ]. 计算机研究与发展 , 2005 , 42 (5) : 734 - 739. XIA Na , J IAN G Jianguo , WEI Xing , et al. Searching for Agent coalition for single task using improved ant col2 ony algorithm[J ]. Journal of Computer Research and De2 velopment , 2005 , 42 (5) : 734 - 739. [6 ]陶海军 , 王亚东 , 郭茂祖 ,等. 基于熟人联盟及扩充合同 网协议的多智能体协商模型[J ]. 计算机研究与发展 , 2006 , 43 (7) :1155 - 1160. TAO Haijun , WAN G Yadong , Guo Maozu , et al. A multi2Agent negotiation model based on acquaintance coa2 lition and extended contract net protocol [J ]. Journal of Computer Research and Development , 2006 , 43 ( 7 ) : 1155 - 1160. [7 ]蒋建国 , 夏 娜 , 于春华. 基于能力向量发挥率和拍卖 的联盟形成策略[J ]. 电子学报 , 2004 , 32 (12A) : 215 - 217. J IAN G Jianguo , XIA Na , YU Chunhua. The coalition formation strategy based on capability vector contribu2 tion2rate and auction [J ]. Acta Electronica Sinica , 2004 , 32 (12A) : 215 - 217. [ 8 ]李亚东 ,李从东 , 张炎亮. 动态联盟收益分配问题的博弈 研究[J ]. 工业工程 , 2006 ,9 (3) :15 - 18. L I Yadong , L I Congdong , ZHAN G Yanliang. Research on the profit2allotting problem of dynamic2alliances through the game theory [J ]. Industrial Engineering Journal , 2006 , 9 (3) : 15 - 18. [9 ] SEN S , P DU TTA S. Searching for optimal coalition structures [ A ]. In S Sen ed. Proc. of the 4th ICMAS [C]. Boston , USA , 2000. [10 ]胡山立 , 石纯一. 一种任意时间联盟结构生成算法[J ]. 软件学报 , 2001 , 12 (5) : 729 - 734. HU Shanli , SHI Chunyi. An anytime coalition struc2 ture generation algorithm [J ]. Journal of Software , 2001 , 12 (5) : 729 - 734. [11 ]徐晋晖 , 张 伟 , 石纯一 , 等. 面向结构的 Agent 组织 形成和演化机制 [J ]. 计算机研究与发展 , 2001 , 38 (8) : 897 - 903. XU Jinhui , ZHAN G Wei , SHI Chunyi , et al. A struc2 ture2oriented mechanism of agent organization formation ·72 · 智 能 系 统 学 报 第 2 卷
第2期 蒋建国，等：自适应粒子群算法求解Agent联盟 ·73 and evolution [J ]Journal of Computer Research and [18]KENNED YJ,EBERHART R C.Particle swarm opti- Development,2001,38(8):897-903. mization[A].In Kennedy J ed.Proc IEEE Int Conf on [12]SEN S,DUTTA P S.Searching for optimal coalition Neural Networks[C].Perth,1995. structures[A].In:Proc the 4th ICMAS[C].Boston, [19]EBERHART R C,KENNEDY J.A new optimizer u MA,USA,2000. sing particle swarm theory [A].In Eberhart R C ed. [13]骆正虎.移动Aget系统若干关键技术问题研究[D]. Proc 6th International Symposium on Micro Machine 合肥：合肥工业大学，2002 and Human Science[C].Nagoya,1995. LUO Zhenghu.Research on several key problems in [20]高尚，杨静宇.群智能算法及其应用[M].北京：中 mobile agent systems[D].Hefei:Hefei University of 国水利水电出版社，2006. Technology,2002. 作者简介： [14]罗东坤，丁治国.石油工程项目管理机制[卫].石油勘探 蒋建国，男，1955年生，教授，博士 与开发，2006,33(2)：242.245. 生导师，合肥工业大学计算机与信息学 LUO Dongkun,DING Zhiguo.Petroleum engineering 院院长，全国信息与电子学科研究生教 project management [J ]Petroleum Expoloration and 有委员会理事，安徽省计算机学会副理 Development,2006,33(2):242-245. 事长，主要研究方向为智能信息处理、 [15]李惠君，王志宇，贾勤，等，Aget技术在虚拟企业 分布式智能系统、数字图像分析与处 创建过程中的应用研究U].计算机工程与设计，2006， 理.发表论文30余篇，出版专著1部 27(15):2805.2807. Email jgjiang @hfut.edu.cn. LI Huijun,WANG Zhiyu,JIA Qin,et al.Application study of agent technology in creating process of virtual enterprise [J ]Computer Engineering and Design, 2006,27(15):2805-2807. [16]李卫宁，基于MAS的智能诊断技术集成方法研究[U] 吴琼，女，1983年生，硕士研究 运筹与管理，2005,14(5)：13-17 生，主要研究方向为智能计算 LI Weinin.Research on the method of expert's evalua- tion in Fault diagnosis system based on MAS [J ]Op- erations Research and Management Science,2005,14 (5):13-17. [I7]蒋建国，夏娜.基于MAS的分布式智能控制初探 0].合肥工业大学学报（自然科学版），2002,28(9)： 夏娜，男，1979年生，副教授， 1085-1088 主要研究方向为分布式人工智能、智 JIAN GJianguo,XIA Na.Research on the MAS based 能控制等。 intelligent distributed control system [J ]Journal of Hefei University of Technology (Natural Science),28 (9):1085.1088. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
理. 发表论文30 余篇 ,出版专著 1 部. and evolution [J ]. Journal of Computer Research and Development , 2001 , 38 (8) : 897 - 903. [12 ] SEN S , DU TTA P S. Searching for optimal coalition structures[A ]. In : Proc the 4th ICMAS[ C]. Boston , MA , USA , 2000. [13 ]骆正虎. 移动 Agent 系统若干关键技术问题研究[D ]. 合肥 :合肥工业大学 , 2002. LUO Zhenghu. Research on several key problems in mobile agent systems [ D ]. Hefei : Hefei University of Technology , 2002. [14 ]罗东坤 ,丁治国. 石油工程项目管理机制[J ]. 石油勘探 与开发 , 2006 , 33 (2) : 242 - 245. LUO Dongkun , DIN G Zhiguo. Petroleum engineering project management [J ]. Petroleum Expoloration and Development , 2006 , 33 (2) : 242 - 245. [15 ]李惠君 , 王志宇 , 贾 勤 ,等. Agent 技术在虚拟企业 创建过程中的应用研究[J ]. 计算机工程与设计 , 2006 , 27 (15) :2805 - 2807. L I Huijun , WAN G Zhiyu , J IA Qin , et al. Application study of agent technology in creating process of virtual enterprise [ J ]. Computer Engineering and Design , 2006 , 27 (15) :2805 - 2807. [16 ]李卫宁. 基于 MAS 的智能诊断技术集成方法研究[J ]. 运筹与管理 , 2005 , 14 (5) : 13 - 17. L I Weinin. Research on the method of expert’s evalua2 tion in Fault diagnosis system based on MAS [J ]. Op2 erations Research and Management Science , 2005 , 14 (5) : 13 - 17. [17 ]蒋建国 , 夏 娜. 基于 MAS 的分布式智能控制初探 [J ]. 合肥工业大学学报 (自然科学版) ,2002 ,28 (9) : 1085 - 1088 J IAN G Jianguo , XIA Na. Research on the MAS based intelligent distributed control system [J ]. Journal of Hefei University of Technology ( Natural Science) , 28 (9) : 1085 - 1088. [18 ] KENNED Y J , EBERHART R C. Particle swarm opti2 mization[ A ]. In Kennedy J ed. Proc IEEE Int Conf on Neural Networks[C]. Perth , 1995. [19 ] EBERHART R C , KENN ED Y J. A new optimizer u2 sing particle swarm theory [ A ]. In Eberhart R C ed. Proc 6th International Symposium on Micro Machine and Human Science[C]. Nagoya , 1995. [20 ]高 尚 , 杨静宇. 群智能算法及其应用[ M ]. 北京 : 中 国水利水电出版社 , 2006. 作者简介 : 蒋建国 ,男 ,1955 年生 ,教授 ,博士 生导师 ,合肥工业大学计算机与信息学 院院长 ,全国信息与电子学科研究生教 育委员会理事 ,安徽省计算机学会副理 事长 ,主要研究方向为智能信息处理、 分布式智能系统、数字图像分析与处 E2mail : jgjiang @hfut. edu. cn. 吴 琼 ,女 , 1983 年生 ,硕士研究 生 ,主要研究方向为智能计算. 夏 娜 ,男 , 1979 年生 ,副教授 , 主要研究方向为分布式人工智能、智 能控制等. 第 2 期 蒋建国 ,等 :自适应粒子群算法求解 Agent 联盟 ·73 ·
