（计算机软件与理论专业论文）多agent系统中联盟形成问题的研究.pdf

兰州大学硕上研究生毕业论文 摘要 在大规模复杂的多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 系统的另一个重要的组成部分，利用合理的分配策略 来划分联盟效用具有重要的意义。本论文主要研究了计算资源受限环境下联盟生 成和联盟效用分配问题。 本文研究的主要内容及创新之处： 联盟生成主要研究如何在多a g e n t 系统中动态生成面向任务的最优a g e n t 联 盟。粒子群算法相对于遗传算法、蚁群算法等其他优化算法具有更好的鲁棒性、 并行性和分布性。本文提出了一种基于改进任务匹配计算方法的联盟生成策略， 能充分发挥a g e n t 的学习能力，准确计算出在m a s 系统中任务间的相似度，更 加快速地决定出如何借鉴积累的经验，从而提高了联盟值的起点和最优解收敛的 速度。对比实验表明本策略有效地增大了联盟值和减少了联盟生成时间。 联盟效用如何分配是a g e n t 在决策时更愿意形成全局更优联盟的关键问题， 本文从信用度的角度提出了划分联盟效用的分配方案，并给出了分配方法。通过 实例验证和结果分析，可以看出这种方法较好地满足了合理性、有效性和时效性 的要求，并且有利于提高联盟的稳定性。 关键词：多a g e n t 系统( m a s ) ，联盟生成，任务匹配，效用分配，信用度 兰州大学硕上研究生毕业论文 a b s t r a c t t h ec o o r d i n a t i o na n dc o o p e r a t i o na m o n ga g e n t si nl a r g e - s c a l ec o m p l i c a t e d m u l t i - a g e n ts y s t e mi sv e r yi m p o r t a n ta n dc o a l i t i o nm e c h a n i s mi s ak i n do f c o o p e r a t i o nf o ra g e n t s c o a l i t i o ng e n e r a t i o ni sak e yt o p i ci nm u l t i a g e n ts y s t e m u s i n gi n t e l l i g e n to p t i m i z a t i o na l g o r i t h m st os o l v et h ea g e n tc o a l i t i o ng e n e r a t i o ni sa n i m p o r t a n tr e s e a r c hd i r e c t i o n t h ec o a l i t i o nu t i l i t ya l l o c a t i o ni s a n o t h e ri m p o r t a n t c o m p o n e n to fm u l t i - a g e n ts y s t e ma n du s i n gt h er e a s o n a b l ea l l o c a t i o ns t r a t e g yi so f g r e a ts i g n i f i c a n c e t h i st h e s i sm a i n l ys t u d i e st h ec o a l i t i o ng e n e r a t i o nu n d e rt h e c o n d i t i o no fc o n s t r a i n e dc o m p u t a t i o nr e s o u r c e sa n dt h ea l l o c a t i o no fc o a l i t i o nu t i l i t y t h em a i nr e s e a r c hc o n t e n t sa n dc o n t r i b u t i o n si nt h i st h e s i sa r ea sf o l l o w s ： c o a l i t i o ng e n e r a t i o nm a i n l yf o c u s e so nh o wt og e n e r a t et h eo p t i m a lt a s k o r i e n t e d c o a l i t i o ni nad y n a m i cm a n n e r c o m p a r e dw i t hg aa n da c a , t h ef e a t u r e so fp s o a l g o r i t h m a r ep a r a l l e l ，d i s t r i b u t e da n dr o b u s t t h i sp a p e ri m p r o v e so na b o v e a l g o r i t h m s ，p r e s e n t sac o a l i t i o ng e n e r a t i o ns t r a t e g yb a s e do ni m p r o v e dt a s k - m a t c h i n g c a l c u l a t i o nm e t h o dw h i c hc a ng i v ef u l lp l a yt ot h ea g e n tl e a r n i n ga b i l i t y ，c a l c u l a t et h e s i m i l a r i t ym o r ea c c u r a t e l yb e t w e e nt a s k si nm a s ，a n dd e c i d em o r eq u i c k l yh o wt o l e a r nf r o me x p e r i e n c e b yu s i n gt h i ss t r a t e g yt h ev a l u eo ft h ec o a l i t i o na n dt h es p e e d o ft h eo p t i m a ls o l u t i o nc o n v e r g e n c ea r ei m p r o v e d t h ee x p e r i m e n t ss h o wt h a tt h i s s t r a t e g yc a n d e c r e a s et h er e t r i e v i n gt i m ea n dc o m p u t a t i o ne f f e c t i v e l y h o wt oa l l o c a t eu t i l i t yi sak e yp r o b l e mi no r d e rt om a k et h ea g e n t sm o r ew i l l i n g t of o r mc o a l i t i o n b a s e do nc r e d i t d e g r e e ，t h i sp a p e rp r o p o s e sac o a l i t i o nu t i l i t y a l l o c a t i o ns c h e m ea n dt h em e t h o d t h r o u g he x a m p l e sa n dt h er e s u l t so fa n a l y s i s ，w e c a ns e et h a tt h i sa p p r o a c hb e t t e rm e e t st h er e q u e s to ft h er e a s o n a b l e n e s s ，e f f e c t i v e n e s s a n dt i m e l i n e s s ，a n di sc o n d u c i v et oi m p r o v et h es t a b i l i t yo fc o a l i t i o n k e yw o r d s ：m u l t i - a g e n ts y s t e m ( m a s ) ，c o a l i t i o ng e n e r a t i o n ，t a s k - m a t c h i n g ，u t i l i t y a l l o c a t i o n ，c r e d i t d e g r e e 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下 独立进行研究所取得的成果。学位论文中凡引用他人已经发表或 未发表的成果、数据、观点等，均已明确注明出处。除文中已经 注明引用的内容外，不包含任何其他个人或集体已经发表或撰写 过的科研成果。对本文的研究成果做出重要贡献的个人和集体， 均己在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：f 旦翌揖 e l期：2 丝曼鱼：2 墨 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产 权归属兰州大学。本人完全了解兰州大学有关保存、使用学位论 文的规定，同意学校保存或向国家有关部门或机构送交论文的纸 质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以 采用任何复制手段保存和汇编本学位论文。本人离校后发表、使 用学位论文或与该论文直接相关的学术论文或成果时，第一署名 单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：凹翌篮 导师签名： 主：! 茎1 日期：出影 兰州大学硕上研究生毕业论文 第一章绪论 a g e n t 理论与技术的研究最早源于分布式人工智能( d i s t r i b u t e da r t i f i c i a l i n t e l l i g e n c e ，n a t ) ，但从5 0 年代末开始，a g e n t 理论、技术的研究从d a i 领域 中拓展开来，并与许多其他领域相互借鉴和融合，在许多不同于最初d a i 应用 的领域得到了更为广泛的应用。a g e n t 理论、技术，特别是多a g e n t 理论、技术， 为分布开放系统的分析、设计和实现提供了一个崭新的途径，被誉为“软件开发 的又一重大突破”1 1 1 。 1 1 研究背景 对于许多复杂的、分布式的问题，单个智能a g e n t 并不合适，甚至无法胜任。 有些问题即便可以由单个智能a g e n t 解决，也可能在速度、可靠性、灵活性和可 维护性等方面受到制约。多a g e n t 系统( m u l t i a g e n ts y s t e mm a s ) 为解决上述问 题提供了一种有效的方法。 简单来说，多a g e n t 系统可以被这样定义：由多个问题解决者( a g e n o 组成的 网络系统( m u l t i a g e n ts y s t e m ) ，其中的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 系统体系结构及其合作机制的研究是其核心问题。 关于m a s 产生的原因【3 j ，不同的角度有不同的观点，其基本思路可归纳为： 实际系统的分布性、复杂性、动态性，有望通过对单个个体能力的有效分工、协 调、组织而达到系统整体优化的目的。其中m a s 产生的最直接的原因是m a s 的协作求解问题的能力超过单个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 之间可以通过协商形成a g e n t 组，我们称之为联盟。 a g e n t 联盟形成机制是m a s 理论研究的一个重要的组成部分，其中a g e n t 兰州大学硕： ：研究生毕业论文 联盟生成问题是需要解决的首要问题。a g e n t 联盟生成问题就是面向任务，寻找 最优的联盟c ，使联盟值v ( c ) 尽可能大。由于在m a s 中，不同a g e n t 之间几乎 都存在彼此合作形成联盟的可能，可能的联盟总数为2 “( 以为m a s 中a g e n t 的数 目) 。从理论上考虑，对整个优化空间2 “进行完全搜索，可以得到这个最优联盟。 但是随着n 的增大，将出现组合爆炸问题，因此a g e n t 联盟生成问题是一个复杂 的组合优化问题。由于a g e n t 计算资源有限，所以研究计算资源受限环境下有效 的联盟生成算法具有重要意义，这就是本文的研究内容之一。 a g e n t 间通过组成联盟来提高求解问题的能力以获得更多的效用，a g e n t 之 间通过联盟共同承担任务，共享目标，共同构造优化求解方案，并划分联盟的额 外效用。自1 9 9 3 年提出联盟以来，r o s e n s c h e i n 、z o l t k i n 等人作了大量研究工作 【5 】【6 1 。目前联盟形成已成为多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 2 相关概念 1 2 1 多a g e n t 系统( m a s ) f r a n k l i n 按照协作类型对m a s 进行了分类1 7 j 文献【8 】在其基础上对m a s 又 做了重新分类，并加入了竞争型和非零和型m a s ，见图1 1 。 如果m a s 中的a g e n t 有各自的目标，不相互通讯，也不相互依赖，那么就 属于独立型的m a s 。这种m a s 又可以分为三类：离散型、协作涌现型和竞争型。 离散型的m a s 中的a g e n t 不但相互独立的完成任务，而且任务之间没有任何关 系。比如一个a g e n t 整理电子邮件，而另一个a g e n t 在网上搜集信息。因此，离 散型的m a s 中不存在任何意义上的协作。但是a g e n t 之间很可能在无意识之中 实现协作。例如，一群a g e n t 相互独立地完成同一个目标，这时对于没有参与其 中的观察者会觉得它们在相互协作，这类m a s 则属于协作涌现型。如果独立型 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 。如果 每个a g e n t 基于其它a g e n t 可能采取的行为来选择自己的最佳行为，此时a g e n t 2 兰州大学硕士研究生毕业论文 所得到的并不完全是其它a g e n t 所失去的，这称为非零和型m a s 。 图1 1 多a g e n t 系统分类 与独立型m a s 相对的是协作型m a s ，也就是说其中的a g e n t 相互间存在某 种形式的协作。根据a g e n t 间是否通讯，协作型m a s 又可分为有通信型和无通 信型。后者a g e n t 问的协调是通过对环境和相互动作的观察做出相应的反应来实 现的。 1 2 1 1m a s 的组织结构 m a s 是模仿人类社会的组织形式而形成的一个求解问题的团队，所以其内 部也具有一定的组织结构，组织结构决定了a g e n t 间的协商、联盟的形成等问题。 m a s 主要有三种组织结构，分别是： ( 1 ) 分层结构：a g e n t 间具有固定的层次关系，上层为控制a g e n t a ，中间 为协调a g e n tb ，下层为两个具有平等关系的a g e n tc 和d ，形成一种多层关系。 如下图1 2 所示： 图1 2 分层结构 ( 2 ) 联邦结构：系统由多个不同的联邦组成，每个联邦又由多个a g e n t 组 3 兰州大学硕上研究生毕业论文 成。如图1 3 所示，不同联邦中的a g e n t 间不能直接通信，而需要通过一个称作 f a c i l i t a t o r 的a g e n t 来中转，即联邦与联邦间的交互都是通过f a c i l i t a t o r 进行的， 屏蔽了各联邦中的a g e n t 。该结构可有效的减少系统中的通信开销，但增加了 a g e n t 间合作过程中的中间层次。 图1 3 联邦结构 ( 3 ) 分布自治结构：系统中所有a g e n t 都是独立自治的，彼此间是完全平 等的关系，如图1 4 所示。需要时各a g e n t 间可直接进行通信并交互和合作，形 成一种水平式的分布自治结构。分布自治结构最能体现m a s 的特点，是m a s 应用的一种最有潜力的结构形式。 本文所研究的系统正是具有这种分布自治结构m a s 。不同a g e n t 之间几乎 都存在彼此合作形成联盟的可能，可能的联盟总数为2 “( 以为m a s 中a g e n t 的数 目) ，这对m a s 联盟生成问题提出了更高要求，而这正是本文所要努力解决的问 题。 图1 4 分布自治结构 1 2 2a g e n t 联盟机制 a g e n t 联盟不仅可以求解那些单个a g e n t 不能完成的任务，而且可以调整目 4 兰州人学硕士研究生毕业论文 标、消解冲突、共享资源，共同构造优化求解方案，从而使得整个m a s 系统能 够以最优的配置、最高的效率来求解既定任务，并获得最大效用【9 1 【l o l 。因此联盟 是m a s 的重要协作方法。 1 2 2 1 典型的a g e n t 联盟的例子 人类社会生产活动中广泛存在通过结盟来获取更多效用的现象。例如三个邮 递员的p o s t m a n 问题：现有一批邮件需要投递，同时有三个邮递员p l 、p 2 和p 3 可以参加工作。那么该如何完成这批邮件的投递工作? 有多种可供选择的方案： ( 1 ) 由一个邮递员完成，如完全由p 1 只完成； ( 2 ) 由任意两个邮递员合作完成，如由p 2 和p 3 共同完成； ( 3 ) 由三个邮递员共同完成。 那么可能存在这样的现象：如果由p 1 单独完成，由于其能力有限，将无法 在规定时间内完成任务，获得效用为0 ；如果由两个邮递员以某种联盟形式共同 承担该任务，则可以完成任务，获得效用为3 ；如果由三个邮递员结盟完成该任 务，获得效用将为4 。但是这并不意味着联盟的规模越大越好，因为联盟扩张同 样会带来成本的增加，只有针对任务选择合适的联盟才能使系统整体效用最大， 这样的联盟就称为全局最优联盟。 1 2 2 2a g e n t 联盟形成机制 由上面的典型例子可以知道，当单个a g e n t 无法独立完成某一任务或者通过 多个a g e n t 协作能提高求解效率时，a g e n t 之间可以通过协商形成联盟( c o a l i t i o n ) 来共同承担该任务。 a g e n t 联盟c 形成过程包括以下三个方面： ( 1 ) 联盟生成：针对问题求解出特征函数值k ( c ) 对应的最优联盟； ( 2 ) 联盟成员间协商：由任务发起者根据求得的最优联盟在a g e n t 间协商， 说服最优联盟候选a g e n t 加入联盟； ( 3 ) 联盟的效用分配：完成任务后在a g e n t 间分配所获得的效用。 联盟形成机制应该满足以下要求1 1 1 】： 有效性：各方分享所有共同效用，则有罗“；= v ( c ) 。 稿 稳定性：包括个体、群体、联盟三种理性要求： ( 1 ) 个体：形成联盟后不会有a g e n t 单独退出联盟而获得更大效用。 5 兰州大学硕卜研究生毕业论文 ( 2 ) 群体：增大联盟内某些a g e n t 的效用就会损害其它a g e n t 的效用。 ( 3 ) 联盟：部分a g e n t 退出联盟去组成新的联盟时不会获得更大的效用。 简单性：交互过程的计算、通信开销应该比较小。 分布性：计算和通信的分布，不需要中央决策，防止通信瓶颈和瘫痪点现象 的发生。 时效性：a g e n t 有与其它a g e n t 形成联盟的可能时，越早加入联盟，其效用 越高。 非减性：每个a g e n t 在联盟形成与调整过程中，不能减少已获得效用或联盟 协议中所分配效用。 1 3 研究目的和意义 m a s 中联盟生成是一个复杂的组合优化问题，属于n p 问题，使用传统方 法寻找一个最优联盟需要花费大量的时间，如何快速有效的找到一个较优联盟是 值得研究的问题。通常情况下，要获取此类问题的最优解是相当困难的，所以更 多情况下都是利用各种优化方法探求问题的近似最优解。因此，优化技术作为一 个重要的学科分支一直受到人们的广泛重视，并在诸多工程领域得到迅速推广和 应用，如：系统控制、人工智能、模式识别、生产调度、v l s i 技术、计算机工 程等。工程过程的最优化对提高效率和效益，节省资源具有重要作用。优化方法 的理论研究对改进算法性能、拓宽算法应用领域、完善算法体系同样具有重要作 用。 粒子群优化算法是由k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出的一种进化计算算 法，作为一种新兴的演化计算技术己成为越来越多研究者的焦点。粒子群算法概 念简明、实现方便，因此自从提出以来便在短期内迅速得到了国际进化计算研究 领域的认可，并在算法实现模式及应用领域得到了很大的发展。粒子群优化算法 在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案 提供了基础，十分适合求解m a s 的联盟形成问题。 多个a g e n t 在形成联盟时，联盟效用如何分配是a g e n t 在决策时更愿意形成 全局更优联盟的关键问题。本文提出了一种把信用度参与效用分配的方案，并取 得了较好的效果。 6 兰州大学硕士研究生毕业论文 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 联盟效用分配策略，并给出了分配方法，通过实例分析了该算法的优越性。 第五章：对论文工作进行了总结，指出了今后进一步研究的方向。 7 兰州大学硕上研究生毕业论文 第二章相关研究工作 a g e n t 问通过组成联盟，可以提高求解问题的能力，获得更多的效用，因此 联盟是m a s 的重要合作方法。从1 9 9 3 年提出联盟方法以来，s h e h o r y ；f l l k r a u s 1 2 1 ， 以及s a n d h o l m 和l e s s e r 作了大量工作【1 3 , 1 4 1 。近年来，联盟生成已成为多a g e n t 系统 研究的一个重要方面。多任务联盟生成问题就是对于任务序列t i , t ：，f ，寻找m 个联盟，使得联盟值总和尽可能大。这是一个复杂的组合优化问题。 2 1 联盟生成问题描述 联盟的生成问题可以形式化描述1 1 5 】如下： 设a g e n t 集n 一 ，资源集q - - - - ，其中 吼一( 口，1 ，口? ，q ) ，q 表示4 的第j 个资源的数量；任务集t = ， 其中正一 是4 的任务集，t 是4 的第个任务。对于每个任务有对 应的资源需求说明，每一个a g e n t 开始都持有一定的资源。一个联盟c 可以用 来描述，其中。是的子集，吼是c 拥有的资源，碰 是资源分配的结果，巧是任务分配的结果，y ( c ) 是联盟的值， u 。一 是每个a g e n t 所得的效用的描述。联盟问题是求一个满足稳 定性要求的( u 。，c s ) ，( u 。，c s ) 是问题求解的一个中间状态或最后结果，其中联盟 结构c s = 为的一个划分。任意4 都有一个能力向量： b ，= ，彰芑0 , 0s fsn , 1sj s 厂) ，用于定量描述4 执行某种动作 的能力大小。例如第3 个a g e n t 具有计算、通信、执行和学习能力，那么厂= 4 ， 可以用b ；至l j b 4 分别描述此a g e n t 的各维能力。假设任务集t = i t 。，t ：，t 。 ，每个 f f 务- t ，均有一定的能力需求口，一 ，彰k2 0 ，( 1s _ s 优，1s 七s 厂) ， 联盟在完成任务t ，之后可以获得相应的效用u ，。一个联盟c 是的一个非空子 集，c 有一个能力向量b c 一 ，b c 是联盟中所有a g e n t 能力向量 的总和， 即b c 一罗垦，联盟c 要完成任务t ，的必要条件是： 互盈 v i ，1 s fs 厂，有6 ；s b c 。 我们作以下假设：( 1 ) 和惯例一样【1 砚1 1 ，在特征函数对策( c h a r a c t e rf u n c t i o n 8 兰州大学硕士研究生毕业论文 g a m e s ，c f g s ) 中研究联盟形成。每个联盟c 的值用一个特征函数f ( c ) 给出。假 定y ( c ) 之0 ，v ( c ) = u 。一f ( c ) - c ( c ) 。式中( ，。指完成任务t 所获得的效用，f ( c ) 指联盟成员总能力折合的成本，c ( c ) 指联盟协作求解t 过程中的额外开销，主要 是通信开销。如果联盟c 不满足上述必要条件，则v ( c ) 为o ，否则v ( c ) 为正数。 ( 2 ) 在非超加性环境中研究联盟形成【1 7 】( 超加性是指v c 。，c ：n ，c 。n c 2 = 中， ：f f v ( c 1uc ：) 苫v ( c 。) + y ( c 2 ) ，在这样的环境中，最大的联盟将是最有益的。 2 2 联盟生成相关的工作分析 一个联盟结构c s 是a g e n t 集的一个划分，从而同一个联盟结构中的联盟是不 相交的。联盟结构c s 一 c 。，c ：，c 。 中的每个c ，对应一个，若对应于任务t ， n n n c ,存在，则联盟结构不包含任何成员。联盟结构的值是该结构中所有 联盟值的总和，且0v ( c s ) 一罗矿( c ) 。所有联盟结构的集合为m 。 c 宅芒s 把多任务联盟问题看作是在联盟结构图中搜索，寻找能极大化联盟值总和的 联盟结构岱，即寻找最优的a g e n t 集合划分形式。大多算法通过部分搜索找到 一个能保证其联盟结构值与最优的联盟结构值相距在一个有限的界限内的联盟 结构。 s a n d h o l m 【1 3 1 4 、s e n 2 2 1 、胡山立【2 3 1 、骆正虎【2 4 】均基于“联盟结构，解决多任务 联盟问题，并对这些算法的性能进行分析： ( 1 ) 方法的及时性、有效性 当曰a l l _ a 霉e a t 8 。暑b t 巩础，对j ：v c se m ，因为 f ( c s ) 和c ( c s ) 一定且极大，所以y f c 跚甚小。 ( 2 ) 计算的可实现性 因为此类算法没有考虑联盟形成的经验学习，在任务完成后联盟解体，每当 新的任务加入任务集时，需要依生成算法重新结盟，这样势必有大量的计算和通 信开销。这对计算资源受限的多a g e n t 系统是难以实现的。 针对这些问题，已有学者提出联盟演化机制【1 5 】，在求解等价联盟问题时计算 量明显减少，但在匹配不成功的情况下调整方法复杂，易失效。 在参考这些成果的基础上，胡娟【2 5 j 将遗传算法应用于a g e n t 联盟生成中，可 9 兰州大学硕上研究生毕业论文 以有效减少联盟生成的搜索时间和计算量，可实现性较好，但是对于小规模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 联盟中具有较广的应用前景。 蒋建国【2 6 l 、夏娜f 2 7 1 提出一种基于蚁群算法的多任务联盟串行生成算法，对 于任务序列可以依次生成全局最优联盟，同时算法基于蚁群系统的学习能力比基 于等价的联盟演化机制灵活、有效、有更高的鲁棒性；可以有效减少联盟生成的 搜索时间和计算量。 粒子群优化算法作为一种新颖的优化搜索算法，自从1 9 9 5 年k e n n e y 和 e b e d l a n 【2 8 】提出以来逐步引起广大学者的关注，研究者们在改善其性能和算法结 构方面做了大量的工作，主要包括：参数设置、粒子多样性、种群结构和算法融 合。y u h u is h i t 2 9 】提出带有惯性权重的改进粒子群算法，李建勇【3 0 l 提出粒子群优 化算法研究，曾建潮【3 1 j 提出微粒子群算法，这些相关算法的研究表明了粒子群智 能优化算法求解a g e n t 联盟问题具有天然的优势。 2 3 典型的联盟生成算法 2 3 1 遗传算法 遗传算法1 2 5 l ( g e n e t i c 触g o f i t h m ，g a ) 是一种基于自然选择和基因遗传学原理 的群体寻优搜索方法。遗传算法首先随机产生一些由个体组成的初始个体群，构 成问题的一群候选解，根据目标函数确定的适应度函数，计算各个个体对于问题 环境的适应度，再根据个体适应度对个体进行选择，留下适应度高的个体，然后 进行交叉、变异等遗传操作产生进化了的群体。如此反复操作，一代一代不断向 最优解方向进化，最后得到满足某种收敛条件的最适应问题环境的个体，从而获 得问题的最优解，遗传算法在解决t s p 问题中有其独特的特点和魅力。近年来， 遗传算法在解决连续变量的函数最优化问题和离散变量的组合最优化问题时所 表现出的鲁棒性、全局最优性、隐含并行性和自适应性，特别适用于大规模非线 性复杂组合优化问题。该算法是以一组解而不仅仅是某一个解为起点，搜索效率 较高，适于复杂问题的求解。 基于遗传算法的多a g e n t 联盟的生成f 2 5 l 利用遗传算法对a g e n t 联盟的求解进 1 0 兰州大学硕七研究生毕业论文 行了研究分析，并将遗传算法应用- 于a g e n t 联盟形成中，使用了面向a g e n t 联盟的 可变长编码方式。 ( 1 ) 基因编码：因为系统中a g e n t 的个数是n ，a g e n t 的集合为 n 一 ，而在某个时刻系统中空闲的a g e n t 的个数为 m ( 0 s m 墨n ) ，所以采用可变染色体长度编码，编码符号集采用二值符号集。定 义一个个体c ( c 一 口。，口：，a 。 ) 是一个联盟结果，一个基因代表a g e n t 是否在联 盟中( 口产1 表示在联盟中，口产0 表示不在联盟中) 。 ( 2 ) 初始化：选择一个整数p 作为群体的规模，然后随机产生p 个位数为n 的二进制编码串作为初始群种。定义适应度函数为 f ( c ) 一v a l u e 。1p r o f i t ，c 0 s f 。当联盟不能完成任务丁时，p r o f i t 。= o 。 ( 3 ) 选择：群体中每一个个体都有被选择的可能。为了使遗传算法对适应 值较高的个体有更多的生存机会，一般使用最常用的策略( 赌轮法) 和最佳保留 法。 ( 4 ) 交叉：交叉就是依概率在两个体间进行随机配对，一般采用优优配对、 随机一点交叉方法，将适应值最高的个体与适应值次高的个体配对交叉。这样产 生的后代个体一般能保证优于父代个体。另外，在配对后要保证种群的规模( 不 应小于n ) 。 ( 5 ) 变异：变异是按照概率改变染色体中某个基因位，可动态改变变异概 率。算法开始阶段，变异概率取较小值；随着算法的执行，变异概率逐渐增大。 这样既能使算法具有局部的随机搜索能力，又能防止未成熟收敛。 ( 6 ) 替换：为找到更好的解，可采用最佳保留法，即将形成的子群体中适 应度最小的个体用所有代的最优个体代替。 2 3 2 蚁群算法 蚁群算法【2 6 ( a n tc o l o n ya l g o r i t h m ，a c a ) 是一种新型的模拟进化算法：它 是在对自然界中真实蚁群的集体行为的研究基础上，由意大利学者m d o r i 9 0 1 3 2 】 等首先提出的。蚁群算法模拟真实蚁群的协作过程，算法由许多蚂蚁共同完成。 每只蚂蚁在候选解的空间中独立地搜索解，并在所寻得的解上留下一定的信息 量。解的性能越好，蚂蚁留在其上的信息量越大，信息量越大的解被选择的可能 性也越大。在算法的最初阶段所有解上的信息量是相同的，随着算法的推进较优 兰州大学硕一卜研究生毕业论文 解上的信息量增加，算法渐渐收敛。蚁群算法已成功解决了一系列问题，如t s p 问题、分配问题、j o b 2 s h o p i h - 题，研究表明蚁群算法在求解复杂组合优化问题方 面具有并行化、正反馈、鲁棒性强等先天优越性。 2 3 2 1 基于基本蚁群算法求解单任务联盟 在含有玎个a g e n t 的m a s 中，寻找能够完成任务f ，且联盟值最大的a g e n t 联盟 c 。我们借助蚁群算法，让蚂蚁选择以前合作过且合作效果较好( 联盟值较 大) a g e n t 再次结成联盟，并以正反馈的方式，逐渐形成联盟值最大或近似最大 的联盟c 。设m 是蚁群中蚂蚁的数量，d o o ，j 一1 ，2 ，1 ) 表示a g e n t 和a g e n t j 之 间的距离，即通信开销；o ) 表示t 时刻在ij 连线上残留的信息素量，物理意 义为“熟悉度”或“友好度 。初始时刻，各条边上的信息素量相等，设( 0 ) n 。 蚂蚁k ( k 一1 , 2 ，朋) 在运动过程中，根据各条边上的信息素量决定转移方向，每 到一个节点就将该a g e n t i j 1 为盟友，p ：表示在t 时刻蚂蚁k 由位置i 转移到位置j 的概率， i j t 时刻蚂蚁k 选择a g e n t 力口入联盟的概率， p ；拱黠胙 泣1 ， 0 ，其它 其中，j 。为蚂蚁七目前尚未访问过的a g e n t 集合。参数口、分别用来控制 熟悉度和通信开销的相对重要程度。当蚂蚁到达某个节点发现当前的a g e n t 联盟 已可以完成任务t ；时，即停止寻径。这就要求蚂蚁每到一个节点就累加该a g e n t 能力向量，计算出当前联盟能力向量，并判断是否已达到任务的能力需求，若是， 则停止寻径，否则继续寻径。当最后一只蚂蚁形成任务求解联盟并停止寻径时一 次循环结束。随着时间的推移，以f i l i a g e n t 之间的熟悉度逐渐降低( 熟人渐忘) ， 用参数口表示熟悉度的降低程度，蚂蚁们完成一次循环，各条边上的熟悉度根据 下式进行调整： z ( f + 1 ) _ p o ) + 荟z ； ( 2 2 a 1 - ；表示第忌只蚂蚁在本次循环中对a g e n t f 、之间熟悉度的增量。 1 2 兰州人学硕士研究生毕业论文 a i - ；一 掣，如果蚂蚍形成的联盟包翻g 绷ff 、j 荟y ( c t ) ( 2 3 ) 0 ，其它 其中，y f 。) 是蚂蚍形成的联盟的值。这里对熟悉度的调整利用的是整体 信息，在求解a g e n t 联盟问题时性能较好。基本蚁群算法中参数口、p 用实 验方法确定其最优组合。停止条件用固定进化代数或者当进化趋势不明显时便停 止计算。算法复杂度为o ( n c n 3 ) ，其中，n c 表示循环次数。 2 3 2 2 求解多任务联盟 首先根据紧迫度u ( t ，) 对丁中的任务进行排序，然后依次求解。当算法求得任 务，的最优a g e n t 联盟开始求解下一个任务+ l 的最优联盟时，a g e n t 之间的信息 素不再是初始值，而是上次求解结束时残留的信息素o ) 。它作为一种非常 宝贵的经验知识，将有效指导蚁群算法后面的求解过程，减少搜索时间和计算量。 可能出现的情况是：在算法生成前两个任务的联盟时，计算量较大，但随着 联盟历史的积累，后面联盟的生成速度越来越快，计算量越来越小。因为系统待 求解任务的性质、类型不会发生根本性的变化，这就意味着系统经过一段时间的 运行后，很多a g c n t 可能会形成相对稳定的并且是成功的联盟。在任务发生重大 变化的情况下，算法仍然可以找到最优解，不过搜索时间要长一些，因为此时的 先验知识失去了指导意义。用蚁群算法求解最优a g e n t 联盟时，同样存在着收敛 慢、易于陷入局部最小等缺陷。文献【2 6 j 引入信息素“内激素”，在出现局部极小情 况时，通过内激素的作用使解跳出局部极小，从而向最优解方向继续进化。 定义1 ：内激素r ：0 9 暑是对蚂蚁自身的思维状态、价值取向进行调整，其 作用形式为： p ； 蓑器胤罗p 血o ) 】积【1 d 诅】芦一。 l 氲 o ，其它 ( 2 4 ) f o ，算法求得最优解仍在进化 g = g + 1 ，最优解在次循环内没有明显改进，如+ 1sg 一 ( 2 5 ) i g 一，其它 1 3 兰州大学硕上研究生毕业论文 g 是内激素的代数，每次循环结束，根据求得的最优解的情况对g 进行调整。 2 3 3 粒子群算法 自然界中一些生物的行为特征呈现群体特征，可以用简单的几条规则将这种 群体行为( s w a r mb e h a v i o r ) 在计算机中建模。r e y n o l d s 使用了下列三条规则作 为简单的行为规则f 3 3 j ： ( 1 ) 向背离最近的同伴的方向运动； ( 2 ) 向目的运动； ( 3 ) 向群体的中心运动。 这即是著名的b o i d ( b i r d o i d ) 模型。在这个群体中每个个体的运动都遵循 这三条规则，通过这个模型来模拟整个群体的运动。粒子群优化算法p s o 的基 本概念也是如此，每个粒子( p a r t i c l e ) 的运动可以用几条规则来描述，因此p s o 算法简单，容易实现，越来越多地引起人们的注意。 p s o 算法最早是由k e n n e y l 2 8 l 和e b e r h a r t 于1 9 9 5 年提出的。p s o 是模拟鸟群 的捕食行为。在p s o 中，每个优化问题的解看作搜索空间中的一只鸟，我们称 之为“粒子”。粒子在搜索空间以一定的速度飞行，这个速度根据它本身的飞行 经验和同伴的飞行经验来动态调整。所有的粒子都有一个由被优化的函数决定的 适应值( f i t n e s sv a l u e ) ，并且知道自己到目前为止发现的最好位_ 置( p a r t i c l eb e s t ，记 为p b e s t ) 和当前的位置。这个可以看作是粒子自己的飞行经验。除此之外，每个 粒子还知道到目前为止整个群体中所有粒子发现的最好位置( g l o b a lb e s t ，记为 g b e s t ) 。g b e s t 是在p b e s t 中的最好值，这个可以看作是粒子同伴的经验。 优化搜索正是在这样一群随机初始化形成的粒子所组成的种群中，以迭代的 方式进行。 2 3 3 1 粒子群算法数学描述 粒子群优化算法中，使用下列信息改变自己的当前位置： ( 1 ) 当前位置；( 2 ) 当前速度；( 3 ) 当前自己最好位置；( 4 ) 当前群体最好位置。 粒子群算法的数学描述如下： 设粒子群规模为，其中每个粒子在d 维空间中的坐标位置可以表示为 x ，= ( x j l ，x ，x 甜，x ) ，粒子i ( i = 1 h 的速度定义为每次迭代粒 子移动的距离，用k = ( 吩。，q ：，) 表示；粒子f ( i = l - n ) 在第d ( d = i - d ) 1 4 兰州大学硕士研究生毕业论文 维子空间的飞行速度根据下式进行调整： = v u + c lr a n d l ( ) ( p b e s t 甜一) + c 2r a n d 2 ( ) ( g b e s t 讨一x 讨) ( 2 6 a ) 。r 一 y 一 ( 2 6 b ) 【一 ，一，f 一l ，嗍 式( 2 6 a ) q h ，p