·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=<6,h,lm1>,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 = < l0 , l1 , …, ln - 1 > , 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 卷