（计算机应用技术专业论文）基于群智能的复杂联盟机制研究.pdf

摘要 基于多a g e n t 系统( m u l t i a g e n ts y s t e m s ，m a s ) 的分布式智能控制正在蓬勃兴起，以适应 计算机支持的协同工作等应用需求，因而使得对m a s 中的联盟研究也变得越来越重要。如何 形成一个稳定均衡的联盟，使联盟朝着稳定的方向发展，是控制理论的前沿课题，已经成为 迫切需要解决的关键问题。传统的研究方法仅考虑一个a g e n t 只能加入一个联盟，势必造成 a g e n t 能力和资源的极大浪费，而且在很多应用场合不能满足实际系统的需要。 基于上述背景，本文提出“复杂联盟”的概念，并引入群智能技术，力图在多任务环境 中实现真正意义上的一个a g e n t 可以同时加入多个联盟和一个联盟可以同时承担多个任务，从 而能在一定程度上提高系统的任务求解效率和资源利用率，为解决复杂控制问题提供理论指 导和方法依据。本文的主要内容及创新之处如下： ( 1 ) 提出一种基于多粒子群协同优化的复杂联盟串行生成算法。基于图论的思想，给出 了“虚拟a g e n t ”的概念，旨在转移父联盟的剩余能力，由“虚拟a g e n t ”代表其父联盟参与后 续任务的竞争，在一定程度上解决了a g e n t 资源和能力的浪费问题。实验结果表明，本算法对 于任务较多且较简单的情形特别有效。 ( 2 ) 将离散粒子群算法扩充到二维二进制编码，实现复杂联盟的并行生成。算法中设计 的编码有效性检查、冲突消解策略克服了求解过程中因多个任务求解联盟同时竞争某个能力 有限的a g e n t 而导致的资源冲突和联盟死锁，而且实现了真正意义上的一个a g e n t 可以参加多 个联盟，在一定程度上可以提高系统的资源利用率。 ( 3 ) 提出一种基于按劳分配和效用非减的效用分配策略。针对已有工作无法摆脱搭便车 问题，导致联盟潜在的不稳定，采用拍卖机制对任务进行快速和有效分解，基于合同机制对 联盟效用以及额外效用进行合理分配，并依据联盟机制的数学模型推导出了局部效用非减和 全局效用非减应满足的条件。该策略既严格遵循按劳分配又完全符合效用非减，在具有超加 性的面向任务的领域中可以形成全局最优联盟，并具有n a s h 均衡意义下的稳定性。 ( 4 ) 基于m a r k o v 过程和鞅理论推演了蚁群算法的几乎处处强收敛性，并提出一种基于 蚁群正反馈的动态联盟形成策略。利用蚁群中的信息素浓度表示熟人之间的熟悉度，以信息 素更新规则作为熟悉度调整规则。仿真实验的测试及分析说明了该策略能在一定程度上降低 整个系统的通信代价和资源开销，提高了系统的可靠程度。 关键词：分布式智能控制：多a g e n t 系统；群智能；复杂联盟；联盟生成；二维二进制编码： 冲突消解：效用分配：几乎处处强收敛：正反馈 a b s t r a c t t h ed i s t r i b u t e di n t e l l i g e n tc o n t r o lb a s e do nm u l t i a g e n ts y s t e m s ( m a s ) i ss p r i n g i n gu p v i g o r o u s l yf o ra na p p l i c a t i o nt oc o o p e r a t i v et a s k ss u p p o r t e db yc o m p u t e r s t h e r e f o r e ，r e s e a r c ho n c o a l i t i o ni nt h ef i e l do fm a si sb e c o m i n gm o r ei m p o r t a n t f o r m i n gs t a b l ea n db a l a n c e dc o a l i t i o n si s am a j o r 托= s e a i hc h a l l e n g ei nt h ef i e l do fc o n t r o lt h e o r y e x i s t i n gr e s e a r c h e ss u f f e rf r o ma l l i m p o r t a n td r a w b a c kt h a ta na g e n tc a l ln o tb u tj o i ni no n l yac o a l i t i o na n dac o a l i t i o nc a nn o tb u tb e e n g a g e di no n l yat a s k ，p r o d u c i n gab i gw a s t e o fr e s o u r c e sa n dc a p a b i l i t i e s ，a n dl i m i t i n gt h es c o p eo f t h e i ra p p l i c a t i o n si nr e a l - w o r l ds c e n a r i o s a g a i n s tt h i sb a c k g r o u n d , w ed e v e l o pan o v e l c o m p l i c a t e dc o a l i t i o n a n da d o p ts w a r m i n t e l l i g e n c et oa d d r e s st h ep r o b l e mo fc o a l i t i o nf o r m a t i o ni nm u l t i t a s ke n v i r o n m e n t sw h e r ea l la g e n t m a yj o i ni ns e v e r a ld i f f e r e n tc o a l i t i o n sa n dac o a l i t i o nm a yp e r f o r ms e v e r a ld i f f e r e n tt a s k s s i m u l t a n e o u s l y o u ra i mi st oi m p r o v et h ee f f i c i e n c yo fs o l v i n gt a s k sa n du t i l i z i n gr e s o u r c c sa n d p r o v i d eat h e o r e t i c a la n dm e t h o d o l o g i c a lg u i d a n c ef o rm a n yc o m p l i c a t e dc o n t r o lp r o b l e m s t h em a i nr e s e a r c hc o n t e n t sa n di n n o v a t i v ec o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： ( 1 ) w ed e v e l o pap a r t i c l es w a r m sc o o p e r a t i v eo p t i m i z a t i o nb a s e da l g o r i t h mf o rc o m p l i c a t e d c o a l i t i o ns e r i a lg e n e r a t i o n an o v e l v n t u a la g e n t e n l i g h t e n e db yg r a p ht h e o r yi su s e dt ot r a n s f e r t h er e m a i n d e rc a p a b i l i t i e so faf a t h e rc o a l i t i o n t ot h el a t t e rt a s k s ，t h ef a t h e rc o a l i t i o nw i l ld e l e g a t e i t sp o w e rt ot h ev i r t u a la g e n tt oc o m p e t ef o rt a s k s s p e c i a l l y , o u ra l g o r i t h mr e a l i z e st h ec o n d i t i o nt h a t a na g e n tc a r lt a k ep a r ti ns e v e r a ld i f f e r e n tc o a l i t i o n sa n dac o a l i t i o nc a nt u r ni t sh a n dt os e v e r a l d i f f e r e n tt a s k s ，p a r t l yr e d u c i n gt h ew a s t eo fr e s o u r c e sa n dc a p a b i l i t i e s m o r e o v e r , t h ee x p e r i m e n t a l r e s u l ts h o w st h a to u ra l g o r i t h mi sm o r ee f f i c i e n tf o rm o r et a s k s 、析ms m a l lc a p a b i l i t i e s ( 2 ) w ed e v e l o pd i s c r e t ep a r t i c l es w a r mo p t i m i z a t i o nw i t ht w o - d i m e n s i o n a lb i n a r ye n c o d i n gf o r s o l v i n gc o m p l i c a t e dc o a l i t i o np a r a l l e lg e n e r a t i o n s p e c i a l l y , c h e c k i n go ne n c o d i n gv a l i d i t ya n d s t r a t e g i e sf o rc o n f l i c tr e s o l u t i o na r eb r o u g h ti n t oe f f e c tt os u r m o u n tr e s o u r c ec o n f l i c ta n dc o a l i t i o n l o c kw h e ns e v e r a ld i f f e r e n tc o a l i t i o n sc o m p e t ea g a i n s te a c ho t h e rf o rt h es a m ea g e n t 州ms m a l l c a p a b i l i t i e ss i m u l t a n e o u s l yi nc o u r s eo fp r o b l e ms o l v i n g m o r e o v e r , o u ra l g o r i t h mr e a l i z e st h e c o n d i t i o nt h a ta na g e n tc a nj o i ni ns e v e r a ld i f f e r e n tc o a l i t i o n s ，p a r t l yi m p r o v i n gt h ee f f i c i e n c yo f u t i l i z i n gr e s o u r c e si nm a s ( 3 ) w r ed e v e l o pan o v e ls t r a t e g yf o rc o a l i t i o nu t i l i t yd i s t r i b u t i o nb a s e do nd i s t r i b u t i o na c c o r d i n g t ow o r ka n dn o n - r e d u c i n gu t i l i t y e x i s t i n gs t r a t e g i e sh a v ea ni n e x t r i c a b l ef r e e - r i d e rp r o b l e ma n dc a n n o tc l e a r l yd i s t i n g u i s he a c ha g e n t sc o n t r i b u t i o nf o rm e i rc o a l i t i o n , w h i c hm a yr e s u l ti nt h ep o t e n t i a l i n s t a b i l i t yo fm e i rc o a l i t i o bi no r d e rt ot a c k l et h es h o r t a g ea b o v e ，a u c t i o ni su s e dt oa l l o c a t et a s k s q u i c k l ya n de f f i c i e n t l y , b a r g a i ni ga d o p t e dt od i s t r i b u t bc o a l i t i o nu t i l i t ye s p e c i a l l ya d d i t i o n a lu t i l i t y r e a s o n a b l y , a n da l s ot h en e c e s s a r yc o n d i t i o n so fl o c a ln o n - r e d u c i n gu t i l i t ya n dg l o b a ln o n - r e d u c i n g u t i l i t ya r ed e d u c e dr e s p e c t i v e l y o u rs t r a t e g ys t r i c t l yf o l l o w st h ep r i n c i p l e so fd i s t r i b u t i o na c c o r d i n g t ow o r ka n dn o n - r e d u c i n gu t i l i t y i ns u p e r - a d d i t i v et a s ko r i e n t e dd o m a i n s ，o u rs t r a t e g yc a nr e a c ha g l o b a lo p t i m a lc o a l i t i o nw h i c h i ss t a b l ew i t hn a s he q u i l i b r i u m ( 4 ) w ed e v e l o pa na l m o s te v e r y w h e r es t r o n gc o n v e r g e n c ep r o o ff o ra n tc o l o n yo p t i m i z a t i o nb y u s i n gm a r k o vp r o c e s sa n dm a r t i n g a l et h e o r y , a n dt h e nw ep r e s e n tad y n a m i cc o a l i t i o nf o r m a t i o n s t r a t e g yb a s e do np o s i t i v ef e e d b a c km e c h a n i s mo fa n tc o l o n yo p t i m i z a t i o n s p e c i a l l y , f a m i l i a r i t y i s a d o p t e dt od e s c r i b et h ei n t e r r e l a t i o nb e t w e e na g e n t sa n dp h e r o m o n e t r a i li na n tc o l o n yi sr e u s e dt o d e s c r i b et h ef a m i l i a r i t yb e t w e e na c q u a i n t a n c e s m o r e o v e r , p h e r o m o n eu p d a t i n gr u l e si na n tc o l o n y o p t i m i z a t i o na l ea d o p t e dt oa d j u s tt h ef a m i l i a r i t y t h ee x p e r i m e n t a lr e s u l ts h o w st h a to u rs t r a t e g y c a nr e d u c et h ec o m m u n i c a t i o nc o s ta n dr e s o u r c ec o n s u m p t i o ni nt h ew h o l es y s t e ma n dm a r k e d l y 即h a n c et h ew h o l es y s t e m sr e l i a b i l i t y k e y w o r d s ：d i s t r i b u t e di n t e l l i g e n tc o n l r o l ；m u l t i - a g e n ts y s t e m s ；s w a r mi n t e l l i g e n c e ；c o m p l i c a t e d c o a l i t i o n ；c o a l i t i o ng e n e r a t i o n ；t w o - d i m e n s i o n a lb i n a r ye n c o d i n g ；c o n f l i c tr e s o l u t i o n ； u t i l i t yd i s t r i b u t i o n ；a l m o s te v e r y w h e r es t r o n gc o n v e r g e n c e ；p o s i t i v ef e e d b a c k 插图清单 图1 1 智能a g e n t 2 图1 2a g e n t 联盟3 图1 3 粒子群算法7 图1 4 蚁群算法9 图2 1 复杂联盟1 6 图2 2 通信开销1 7 图2 3 虚拟a g e n t 1 8 图2 4p s c o 算法在环境4 中的联盟生成结果2 2 图2 5p s c o 算法在环境3 中的最优解进化曲线2 3 图3 1 二维二进制染色体编码2 6 图3 2 染色体编码初始化2 8 图3 3 交叉算子2 9 图3 4 变异算子3 0 图3 5 粒子编码3 2 图3 6 冲突消解3 3 图3 7 初始编码3 6 图3 8 冲突消解一3 7 图3 9 冲突消解二3 7 图3 1 0 冲突消解三3 8 图3 1 1 冲突消解四3 8 图3 1 2 冲突消解五3 9 图3 1 3 冲突消解六3 9 图3 1 4 冲突消解七4 0 图3 1 5 冲突消解八0 ooooom o 4 1 图3 1 6 冲突消解九4 l 图3 1 7 冲突消解十4 2 图3 1 8 冲突消解后的编码4 2 图3 1 9c c d p s o 进化曲线( 十个a g e n t ) 4 4 图3 2 0c s g a 算法中的死循环( 十个a g e n t ) 4 5 图3 2 1 两种算法的进化曲线( 十五个a g e n t ) 4 6 图3 2 2c cd p s o 进化曲线( 十维向量) 4 8 图3 2 3c sg a 进化曲线( 十维向量) 4 8 图4 1 三个a g e n t 的p o s t m a n 问题5 3 图5 1 反射壁的构筑7 4 图5 2 实验1 的交互次数7 9 图5 3 实验2 的交互次数7 9 图5 4 实验2 的任务完成数8 0 表格清单 表2 1 三种算法的性能比较2 2 表3 1 四个任务的能力需求3 6 表3 2 十个a g e n t 的能力向量3 6 表3 3 冲突消解的结果4 2 表3 4 各a g e n t 间的通信开销4 4 表3 c c d p s o 算法的联盟值( 十个a g e n t ) 4 4 表3 6c cd p s o 算法的最优联盟( 十个a g e n t ) 4 5 表3 7 两种算法的联盟值( 十五个a g e n t ) 4 5 表3 8c cd p s o 算法的最优联盟( 十五个a g e n t ) 4 6 表3 9c sg a 算法的最优联盟( 十五个a g e n t ) 4 6 表3 1 0 两种算法的联盟值( 十维向量) 4 7 表3 1 1c cd p s o 算法的最优联盟( 十维向量) 4 7 表3 1 2c sg a 算法的最优联盟( 十维向量) 4 7 表4 1 五种方法求解过程比较6 5 表4 2 相关的性能比较6 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金g 垦王些太堂或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 券，虱留 学位论文版权使用授权书 本学位论文作者完全了解金目旦王些太堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金目巴王 些盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位敝作者躲获) 稿 签字嗍埘年川扣 学位论文作者毕业去向： 工作单位： 通讯地址： 导师签名： 毋， d 一 致谢 终于迎来了论文定稿的这一天，心绪久久难平。时光荏苒，天道酬勤，匆匆五年而去， 在宇宙变迁不过长河一瞬，但对于我的人生旅程却是浓墨重彩。回首当初的天真无知，抚思 昔日之韶华，实在包含了太多人的关心和热情，谨以此致谢。 首先，对我的导师蒋建国教授致以深深的谢意。在整整五年的光阴里，我的每一点进步、 每一份成果，无不包含着蒋老师的敦敦教诲和殷殷期望。蒋老师治学之严谨、学识之渊博、 视野之宽阔，置身其间，潜移默化，在学术上和生活上都使我受益匪浅，更让我领悟了“学 高为师、身正为范”的真谛。 感谢d s p 实验室的齐美彬副教授、夏娜副教授两位老师。感谢他们为我的博士论文在思 路上出谋划策，在实验中挽袖襄助，在困扰时指点迷津。两位老师对待学术求真求实，对待 生活朴实无华，每当想起点滴，暖意沁浸全身。 还要由衷的感谢i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 主编，英国伯明翰大学姚 新教授，i e e et e c 主编助理f e l i c i t ys i m o n ，英国南安普敦大学j e n n i n g s 教授及其领导的i a m g r o u p ，浙江大学罗小平博士后等，与他们邮件来往，总是耐心解答我的问题，并承蒙提供很 多有价值的文献。 论文的完成离不开课题组和实验室其他同仁的并肩奋斗。感谢李援、梁立伟、胡嘉凯、 彭兴邦、王德宝、常传文、黄越等在实验上给予的大力帮助。与尹翔、李勇、包先雨等的探 讨总是使我获益良多。还要感谢吴从中老师、李小红老师，感谢他们在低落时给我的勉励， 懈怠时给我的鼓舞，迷茫时给我的警醒。 此外，还有在合工大十年结识的兄弟姐妹们和朋友们，虽然很多时候只是在电脑前的陪 伴和支持，但和他们在一起的时光总是轻松而快乐，为我在求学的道路上又增添了一份力量， 和他们的友情，是我莫大的财富。 最后要把我的谢意留给我的家人。父母无私的关爱与付出，为我的成长含辛茹苦、积劳 成疾，一篇博士论文远非我报答养育之恩的终点，我将继续努力，以更大的成绩回报父母， 以及所有关心过我成长的亲人们。特别感谢我的未婚妻苏兆品，我们一起经历了苦难，又一 起在苦难中得到成长，执子之手，与子偕老，是我论文搁笔之际的最大心愿。 作者：张国富 2 0 0 8 年3 月3 1 日于斛兵塘畔 第一章绪论 第一章绪论 计算机科学的潜能如果能够被全部挖掘和开发出来，它将把我们带到一个更高的关于世 界的知识平台。计算机科学将帮助我们对智能处理有更深入的理解，能增长我们在学习过程、 思考过程和推理过程中的知识。计算机科学能够为认知科学提供模型化和概念化工 具那些将极大改变我们生活的重大进步将会持续不断的出现人们将能够理解 如何去组织和管理知识 j o h ne d w a r dh o p c r o f l ，a c m 图灵奖演说，1 9 8 7 近年来，基于a g e n t 的观点提供了一种强有力的工具、技术和途径来提高人们概念化和实 现许多类型系统的能力，也提供了一种自然和艺术的方式来表述一系列多样化的问题，并且 它提供了很好的机会来处理由于工业正在向更加模块化、分布和开放系统的发展趋势而引起 的一系列新类型应用。特别是随着智能控制和分布式控制两大工业控制技术的不断发展，基 于多a g e n t 系统( m u l t i - a g e n ts y s t e m s ，m a s ) 的分布式智能控制正在蓬勃兴起，以适应计算机 支持的协同工作等应用需求，因而使得对m a s 中的联盟研究也变得越来越重要。联盟形成 ( c o a l i t i o nf o r m a t i o n ) 是联盟一切活动的基础，如何形成一个稳定均衡的联盟，使联盟朝着稳 定的方向发展，是控制理论的前沿课题，已经成为迫切需要解决的关键问题，正被国内外的 众多学者所关注和研究。基于m a s 的分布式智能控制，是按控制应用的要求从功能上划分成 多个a g e n t ，各个a g e n t 相互通信，彼此协调，共同完成大的复杂系统的控制任务。因此，联 盟形成理论中的基础理论和方法为分布式智能控制系统( d i s t r i b u t e di n t e l l i g e n tc o n t r o ls y s t e m ) 提供了良好的解决方案。 基于m a s 的分布式智能控制系统不仅具备一般分布式控制系统所具有的资源共享、易于 扩张及灵活性强的特点，而且各a g e n t 通过相互协调、协作可解决大规模的复杂问题，克服了 建立一个庞大知识库所造成的知识管理和扩展的困难，使系统具有很强的鲁棒性、可靠性和 自组织能力。目前，其应用已涉及到国民经济众多领域，如过程控制、空中交通控制、电子 商务、商业过程管理、娱乐业和医疗看护等【1 。6 】。然而，由于系统本身的计算资源有限，往往 会面临计算瓶颈和信息拥塞，造成资源利用率不高和系统的极不稳定，因此需要借助其他理 论、方法和技术( 如群智能) 来解决这些问题。 2 0 世纪9 0 年代，随着进化计算技术的不断发展，以粒子群算法( p a r t i c l es w a r m o p t i m i z a t i o n ) 和蚁群算法( a n tc o l o n y o p t i m i z a t i o n ) 为主要代表的群智能( s w a r m i n t e l l i g e n c e ) 开始出现，它较好地解决了各种工程优化问题，为寻找复杂的分布式问题的解决方案提供了 基础。群智能中的群体指的是“一组相互之间可以进行通信的a e n t ，这组a g e n t 能够合作进 2 合肥工业大学博士论文 行分布式问题求解”，而群智能则是指“无智能的a g e n t 通过合作表现出智能行为的特性”，可 见群智能恰似一个简单的单工m a s ，因此将群智能引入到m a s 领域中，借以丰富联盟形成 的相关理论和方法具有先天的优势。本论文主要研究群智能应用于联盟形成若干关键问题的 基本理论和技术方法，本章系统地阐述了联盟形成、群智能的相关背景知识，并对全文研究 的主要内容进行了概括。 1 1 联盟形成( c o a l i t i o nf o r m a t i o n ) a g e n t 理论与技术的研究最早源于分布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ，d a d 。 d a i 主要研究参与由人和计算机组成的社会的a g e n t 所必须的知识模型、通讯和推理技术，关 注几个a g e n t 交互作用共同求解一个公共问题。d a i 通过对问题的描述、分解和分配，构成分 散的、面向特定问题相对简单的子系统，并协调各子系统并行和相互协作地进行问题求解。 d a i 代表了一种分析、设计和实现大型、复杂系统的方法途径，其思想十分适合大规模控制 问题的智能求解。因此，d a i 领域中的a g e n t 和m a s 技术已被描述为设计构建分布式复杂工 程应用系统的下一代模型。 1 1 1 智能a g e n t 在本文中，a g e n t 是一类在特定环境下能感知( p e r c e p t s ) 环境( e n v i r o n m e n t ) ，并能自主 运行以实现一系列目标的计算实体 7 1 。这里的“自主”指的是a g e n t 能在没有人类或其他a g e n t 的干涉下持续运行，并能根据要实现的目标控制其内部状态和动作( a c t i o n s ) 【8 】。每个a g e n t 拥有其他a g e n t 的信息和知识，并能通过某种通信方式与其他a g e n t 进行交互和协作。此外， a g e n t 能够感知环境，并能对环境中发生的事件做出反应，即a g e n t 具有一定的智能，所以， 我们也可以称a g e n t 为智能a g e n t ( 如图1 1 所示) 。 图1 1 智能a g e n t 但是对于许多复杂的、分布式的问题，单个a g e n t 并不适合，甚至无法胜任，有些问题即 便可以由单个a g e n t 解决，也可能在速度、可靠性、灵活性和可维护性等方面受到制约，因此 就产生了多a g e n t 系统。 1 1 2 多a g e n t 系统( m a s ) ， 八 露 第一章绪论3 多a g e n t 系统是一个由多个智能a g e n t 组成的松耦合的问题求解器网络，其中的a g e n t 相 互作用、相互合作，从而解决单个a g e n t 由于能力、知识或资源上的不足而无法解决的问题或 即使能解决而效率很低的问题 9 】。m a s 中的每个成员a g e n t 仅拥有不完全的信息和问题求解能 力，不存在全局控制，数据是分散的或分布的，计算过程是异步、并发或并行的，a g e n t 之间 可以交互、动态自组织、协调、合作，从而大大提高求解问题的能力。 在m a s 中，a g e n t 不是孤立存在的，各a g e n t 的能力和资源也是有限的，当单个a g e n t 无 法独立完成目标，需要其它a g e n t 帮助时，就需要协作。协作不仅能提高单个a g e n t 以及相应 m a s 的整体行为的性能和解决问题的能力，而且可使系统具有更好的灵活性。通过协作，可 使m a s 能解决更多的实际问题，拓宽应用。因此，m a s 领域里最集中和关键的问题表现在 系统的协调合作机制上，现有的多数方法是形成一个a g e n t 联盟。 1 1 3 联盟( c o a l i t i o n ) “联盟”的概念源于n 人合作对策论1 0 , 1 1 】，1 9 9 3 年被欧洲学者引入到m a s 领域【1 2 - 1 4 】。在 m a s 中，联盟是为了完成特定任务而建立的a g e n t 组织，联盟内的a g e n t 实行资源共享和任务 分担，相互合作以最佳方式完成任务，使联盟的总资源得到充分利用，使联盟的收益得到最 大化。a g e n t 联盟是一组平等的、协作的、共同承担任务的a g e n t 集合( 如图1 2 所示) 。a g e n t 间通过组成联盟，可以提高求解问题的能力，获得更多的利益，因此a g e n t 联盟是多a g e n t 之 间一个重要的合作方式 1 5 】。总的来说，联盟是一个周期性概念，联盟是有生命周期的，它随 着任务的到来而产生，又会随着任务求解的结束而解体。 图1 2a g e n t 联盟 联盟形成( c o a l i t i o nf o r m a t i o n ) 是联盟一切活动的基础，如何形成一个稳定均衡的联盟， 使联盟朝着稳定的方向发展，从而顺利完成其承担的任务，正受到越来越多的关注和研究， 并已成功应用于信息收集、邮件路由、传感器网络等领域 1 6 - 1 8 】。 一般情况下，联盟形成过程包括联盟生成和效用分配两个方面。 1 1 3 1 联盟生成( c o a l i t i o ng e n e r a t i o n ) 设m a s 中a g e n t 集a = a la 2 ，a 。) ，对应效用分配集u = u lu 2 ，“。) ，u f 为a f 所 获得的效用( 1 f n ) 。v a f a 都有一个能力向量b f = 【6 | ，琏，匆 ( 彰0 ，1 j ，| ， 4 合肥工业大学博士论文 r en ) ，用于表征口f 执行某种特定动作的能力大小。 任务集丁= 瓶，t 2 ，t m ，v t k r 均有一定的能力需求d t = 【计，d 多，彬 ( 砑0 ， l k m ) 。彬对应能力权重向量w ；= 【计，坩，钟】( 嘭o ) ，满足埘= 1 ，表示 | 各维能力在任务“中的相对重要程度。 联盟c a ( co ) 具有一个能力向量b c = 【砰，西，够】，b c 是c 中所有a g e n t 能力 向量的总和， 即够= 彩。联盟c 可以完成任务“的必要条件是： 皿e c w 1 ，2 ，】，盱彬。联盟c 的值用一个特征函数u ( c ) 给出( 不妨设p ( c ) o ) 。 v ( c ) = 矽( “) 一( c ) 一万( c ) 其中，矽( “) 为完成任务如的所获得的报酬；( c ) 指联盟成员总能力折合的成本；万( c ) 指 联盟协作求解“过程中的通信开销。 和惯例一样，在非超加性环境中研究联盟生成。超加性是指对v c , ，c 2 a ，若 qnc 2 = a ，则u ( c lu g ) u ( g ) + 秒( c 2 ) ，显然在超加性环境中最大的联盟将是最优的。 联盟生成问题就是对任务序列矗，t z ，寻找m 个联盟，使得系统总收益o m a s 尽可能大， 这是一个复杂的组合优化问题。 册 = u ( g ) k = l ( 1 2 ) 联盟生成问题是从联盟结构生成演化而来的，起初学者们都是在特征函数对策 ( c h a r a c t e r i s t i cf u n c t i o ng a m e s ，c f g s ) 中搜索最佳联盟结构。一个联盟结构是a g e n t 集合的一 个划分，由若干联盟构成，联盟结构中任意两个联盟都是不相交的，也就是说，一个联盟结 构中，每个a g e n t 恰好仅仅属于一个联盟。为了找到最佳联盟结构，s a n d _ h o l m 等学者相继给出 了一些确定性搜索算法【1 9 - 2 ，但这些算法根本无法穷尽庞大的联盟结构空间，不利于解决实 际问题，而且d a n g 等学者发现联盟结构生成对于面向任务的领域是不适用的 2 2 - 2 4 ，存在巨大 的资源浪费，即使y a n g 和z h c n g 等引入进化计算也摆脱不了联盟结构固有的弊病 2 5 , 2 6 ，所得 到的联盟结构仍然存在一定的冗余。显然在面向任务的领域中，联盟结构是没有实际意义的， 对于给定的几个任务，如何快速的求出几个较优的联盟去执行任务才是我们关心的重点。 因此，研究联盟生成问题具有更大的优势和潜力，夏娜等学者做出了一些有益的尝试 2 7 , 2 8 ， 第一章绪论 5 并取得了一定的成果，但仍然受到联盟结构的影响，只限于讨论一个a g e n t 只能加入一个联盟 的情形，在很多场合不能满足实际应用系统的需要，因此，将联盟生成问题延伸到一个a g e n t 可以加入多个不同的联盟仍是一个值得深入研究的课题。 1 1 3 2 效用分配( u t i l i t yd i s t r i b u t i o n ) 联盟完成任务可以获得一定的效用，当联盟形成后，联盟所得效用如何分配给其中的各 个a g e n t 也是一个核心问题。联盟中a g e n t 所获的效用可以作为m a s 中a g e n t 进化的定量化依 据，a g e n t 根据获得效用多少申请相应的等级进化，从而在不同的等级间迁移，获得效用越多 等级提升越大，例如对于分布式智能控制系统，可以表现为设备中断优先级提高、通信带宽 加大等。 为了鼓励a g e n t 倾向于促进联盟形成，通常将联盟限于超加性环境中，即对vc l ，c 2 互a ， 若c l nc 2 = o ，则口( c l uc 2 ) d ( c 1 ) + 口( c 2 ) 。显然在这样的环境中联盟的形成是平凡的。 牟取效用是各a g e n t 参加联盟的内在驱动力，系统管理者为鼓励a g e n t 结盟，必须指定一 种合适的效用划分规则，效用划分是否合理将直接影响联盟的形成和稳定。因为一旦某些a g e n t 发现自己受到不合理的待遇，已经形成的联盟就有破裂的危险，所以要维持业已形成的联盟 的稳定，效用的分配应满足一定的合理性。早期文献都是借用协作博弈论中的核心、稳定集 等方法1 0 1 ，s h e h o r y 等学者致力于s h a p l e y 值的研究 2 4 , 2 9 】，罗翊等提出效用非减的思想3 0 3 1 1 ， 但已有工作都摆脱不了平均分配的影响，不能明确反映出各a g e n t 对于联盟贡献的差异性，容