（计算机应用技术专业论文）多agent系统动态重构及其应用研究.pdf

摘要 多a g e n t 系统动态重构及其应用研究 计算机应用技术专业硕士研究生：陶丽 指导教师：张自力教授 摘要 多a g e n t 系统住探索大规模分布式开放系统和理解、刻画现实世界中的许多复杂问题都 有非常j “泛的戍川。但在基于多a g e n t 的应用中，有一个亟待解决的斟难问题，即在h j 户需 求、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 动态变化的情况f ，构建智能a g e n t 系统的动态重构模璎：开发实现 动态重构和让动态重构有效t 作的一系列算法、技术：改进智能a g e m 系统动态重构的技 术，并将其运用剑供应链管理问题当中。 本文的研究i ：作主要包括以下3 个方面： 1 提出了多a g e m 系统动态重构的抽象建模a d r m 本文采用最新的计算范型面向自治的计算a o c ( a u t o n o m y - o r i e n t e dc o m p u t i n g ) ，在 三个不同层次上设计并刻画a g e n t 的行为；提取出了智能a g e n t 系统动态重构的抽象模硝； 对基于该模璎构建的人i ：系统中的戈键要素进行了定义：构建了自治实体的行为规则库。因 此，本文在为智能a g e n t 系统提供动态重构技术的同时，也为新的计算范例面向自治的 计算做出贡献。 2 ，提出了支持动态重构模型有效l 作的算法a s d r 、i e r a 和h i e r a 本文提出支持动态重构的算法a s d r 用以控制重构的过程。对丁二动态重构中涉及到的建 组和组维持问题，我们改进了算法e r a ，并对改进后的算法i e r a 和启发式h i e r a 的收敛 性、有效性以及参数设置进行了实验。实验证明，两个算法均能收敛，比较适合丁二动态、分 两南j 。筇，i 卞 诊上 布式、实时的建组情形。 3 对实际的动态霞构问题供麻链管理系统的再构进行r 究 存现蛮f i = 界中，存在很多需要动态呕构能力的问题，为探i f 抽蒙的模础如何运用f 具体 l u 】题，本之选择了四际供应链管珲觅赛t a cs c m 为研究鹿川7 f 祭。住此7 f 景f ，改进和扩 展动态五构模剐，提出了支持动态重构的供应链管理系统框架d r _ s c m ：并基y - j a v a 和 t a cs ( m 提供的i ：具包实现了原删系统；最后通过实验，对具霄和不具有动态重构能力的 供应链管理肴进行了比较。实验结果表明。动态重构能够为构建白治智能a g e n t 系统提供很 大的帮助能够让解决实际问题的a g e n t 系统自适应变化，从而更加迅速、高效的解决问 题。 关键词：多a g e n t 系统动态重构面向自治的计算a o c 联盟形成算法供应 链管理 一i i d y n a m i cr e c o n f i g u r a t i o no fm u l t i - a g e n ts y s t e m s a n di t sa p p l i c a t i o n s m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g i e s r e s e a r c hd i r e c t i o n ：a r t i f i c i a li n t e l li g e n c e s u p e r v i s o r ：p r o f z h a n gz i l i m a s t e rc a n d i d a t e ：t a ol i ( $ 2 0 0 3 7 3 7 ) a b s t r a c t m u l t i a g e n ts y s t e m sa r ew e l ls u i t e dt oe n g i n e e r i n gc o m p l e xs o f t w a r es y s t e m sa n dc o n s t r u c t a r t i f i c i a ls y s t e m s b u th o wt od y n a m i c a l l yr e c o n f i g u r ea na g e n ts y s t e mb a s e do nd i f f e r e n tt a s k sa n d c h a n g i n ge n v i r o n m e n t i sak e yi s s u ew h i c hr e m a i n su n s o l v e d t h i si sc r u c i a lf o rc o m p l e xs o f t w a r e s y s t e m sw h i c hs o l v ec o m p l e xp r o b l e m s a c t u a l l y ，d y n a m i cr e c o n f i g n r a t i o ni sl i s t e da so n eo ft h ek e yc h a l l e n g e si ns u p p o r to fa g e n t a d a p t a t i o n t oe n v i r o n m e n t s ，w h i c hi sc a l l e d n l n t i m er e c o n f i g u r a t i o na n dr e d e s i g n f u r t h e r r e s e a r c hi n d i c a t e st h a td y n a m i cr e c o n f i g u r a t i o no rs e l fc o n f i g u r a t i o ni sa l s oak e yi s s u er e q u i r i n g u r g e n ts o l u t i o ni ng r i dc o m p u t i n g w e l l a sa u t o n o m i cc o m p u t i n g i ng r i dc o m p u t i n g s u c ha l l i s s u ei sc a l l e d v i r t u a lo r g a n i z a t i o nf o r m a t i o na n dm a n a g e m e n t a n di na u t o n o m i cc o m p u t i n g , i ti s c a l l e d s e l f - m a n a g e m e n to fc o m p u t i n gs y s t e m t h ee m p h a s i so ft h i sp a p e ri so ut h ed y n a m i c r e c o n f i g u r a t i o nw i t hd i f f e r e n tt a s k sa n de n v i r o n m e n tc h a n g e s t h o u g hal o to f w o r kh a sb e e n d o n eo nt h i si s s u e ，t h e r ei sn oe f f i c i e n ts o l u t i o nr e p o r t e dt od a t e a b o u td y n a m i cr e c o n f i g n m t i o nw i t hd i f f e r e n tt a s k sa n de n v i r o n m e n tc h a n g e s t h i sp a p e rw i l lf o c u s o nt h r e ek e yi s s u e s ：m o d e l l i n gt h ea b s t r a c tc o n c e p to fd y n a m i cr e c o n f i g n m t i o na p p r o p r i a t e l yf o r a g e n t - b a s e ds y s t e m s ，p r o d u c i n gt e c h n i q u e s t o e f f i c i e n t l yw o r k o ut h em o d e lo fd y n a m i c r e e o n f i g n r a t i o n ，a n ds m d y i n gh o wt oa p p l yd y n a m i cr e c o n f i g u r a t i o nt e c h n i q u e sf o ra g e n t - b a s e d s y s t e m st os u p p l yc h a i nm a n a g e m e n t t h ec o n t r i b u t i o n so f t h i sp a p e ra r ei nt h ef o l l o w i n gt h r e ea s p e c t s ： 1 m o d e l l i n gd y n a m i cr e c o n f i g u r a t i o no f a g e n t - b a s e ds y s t e m s a ne m e r g i n gc o m p u t a t i o n a lp a r a d i 毋t 一a u t o n o m yo r i e n t e dc o m p u t i n g ( a o ca ss h o r t ) 1 1 1 两j 日，舢日f7 77 ；i f h a sb e e nu s e dt oc h a r a c t e rd y n a m i cr e c o n f i g u r a t i o no fa g e n t - b a s e ds y s t e m s ；am o d e lo fd y n a m i c r e c o n f i g u r a t i o no fm u l t i a g e n ts y s t e m sh a sb e e np r o p o s e d ；t h ek e ye l e m e n t so ft h i sa r t i f i c i a lm o d e l h a sb e e nc l e a r l yd e f i n e d ；t h eb e h a v i o r a lr u l e so fa u t o n o m o u se n t i t i e s ( h e r ea r ea g e n t s ) h a v eb e e n p r e s e n t e d t h i sr e s e a r c hw i l l ，o no n eh a n d ，p r o d u c en e wd y n a m i cr e c o n f i g u r a t i o nt e c h n i q u e sf o r a g e n ts y s t e m s ；o nt h eo t h e rh a n d ，i tw i l la l s oc o n t r i b u t et o an e wc o m p u t i n gp a r a d i g m a u t o n o m y o r i e n t e dc o m p u t i n g 2 d e s i g n i n ga l g o r i t h m sf o rd y n a m i cn c o n f i g u r a t i o n t h em u l t i a g e n ts y s t e md y n a m i cr e c o n f i g u r m i o n ( a s d r ) a l g o r i t h mw a sd e v e l o p e dt o c o n t r o lt h ed y n a m i cr e c o n f i g u r a t i o np r o c e s s a n do t h e rt w oa l g o r i t h m sc a l l e di e r a ( i m p r o v e de r a ) a n dh i e r a ( h e u r i s t i ci m p r o v e de r a ) w h i c hi m p r o v e du p o ne r a ( e n v i r o n m e n t - r e a c t i v er u l e s - - a g e n t s ) a l g o r i t h mh a v eb e e np r o p o s e dt os u p p o r tt h eo r g a n i z a t i o nf o r m a t i o nb e h a v i o r , w h i c hi s e s s e n t i a li nd y n a m i cr e c o n f i g u r a t i o n w ed os o m ee x p e r i m e n t so nt h ec o n v e r g e n c es p e e da n d p a r a m e t e rs e t t i n g so ft h e t w oa l g o r i t h m s e x p e r i m e n t ss h o wt h a tt h e s et w oa l g o r i t h m sc a n c o n v e r g e n te f f i c i e n t l y ，a n dc a nb eu s e dt os u p p o r tn o to n l yt h ea d r mm o d e l ，b u ta l s ot h eo t h e r s i m i l a rd i s m b u t e ds e a r c hp r o b l e m s ， 3 c o n d u c t i n gr e s e a r c ho n r e a ld y n a m i cr e c o n f i g u r a t i o np r o b l e mi ns u p p l yc h a i n m a n a g e m e n ts y s t e m t h ei n t e m a t i o n a l t r a d i n ga g e n t sc o m p e t i t i o n f o r s u p p l y c h a i nm a n a g e m e n t ( h t t p ：w w w s i c s s e t a c ) ( t a cs c m ) w a ss e l e c t e du st h es c e n a r i oo f t h i sp a p e r t h ea d r mm o d e l h a sb e e ne x t e n d e da n dt a i l o r e dt ot h es c e n a r i o as u p p l yc h a i nn m n a g e m e n ts y s t e mw h i c hn a m e d d r - s c mw i t hd y n a r m cr e c o n f i g u r a t i o na b i l i t yh a sb e e nd e v e l o p e db yj a v aa n dt a c - s c mt o o l k i t t h ee x p e r i m e n to nd r - s c md e m o n s t r a t e st h a to u rr e s e a r c hc a r lb e l l e f i tr e a ld y n a m i c r e c o n f i g u r a t i o np r o b l e mi ns u p p l yc h a i nm a n a g e m e n ts y s t e mal o t i ta l s os h o w st h a tw i t h d y n a m i cr e c o n f i g u r a t i o n ，a g e n t - b a s e ds y s t e m sc a no p tt o d i f f e r e n tt a s k s ，a n db e a d a p t i v et ot h ee n v i r o n m e n tc h a n g e s m a n yc o m p l e xp r o b l e m sc a nb es o l v e d i na s h o r t e rt i m ef l a m ea n dr e s u l t i n gi nh i g h e rq u a l i t ys o l u t i o n s k e y w o r d s ：m u l t i a g e n ts y s t e m s ，d y n a m i cr e c o n f i g u r a t i o n ，a u t o n o m yo r i e n t e d c o m p u t i n g ，c o a l i t i o nf o r m a t i o na l g o r i t h m s ，s u p p l yc h a i nm a n a g e m e n t i v 独创性声明 学位论文题目：量垒g ! 望! 墨丝盘查重塑丛甚廛旦盟塞 本人声明所呈交的学位论文是本人在导师指导f 进行的研究j ：作及取 得的研究成果。据我所知，除了，文中特别加以标注和致谢的地力。外，论义 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得i 巧南大学 或j i 4 , f i 旦教育机构的学啦减证书而使用过的材料。与我一同1 ： 1 ：的1 哥志对本 研究所做l 佝任何贡献均已在沦文巾作了明确的说明并表示谢意。 h 、 一 学位论文作者：悝0 阳 签字日期： 声。年5 月c d 日 学位论文版权使用授权书 _ ：= 小= 。弘位论文作者完全厂解西南大学有关保留、使用学位沦殳的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允i 午论文被 套阅和借阅。本人授权西南大学研究生院可以将学位论文的令部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制r 段保存、 汇编学位论文。 ( 保密的学位论文在解密后适用本授权书， 密期限至年月止) 。 学位论文作者签名：9 匐彳导师签名： 签字目期：多7 年岁月r p 日签字曰期： 学位论文作者毕业后去向： 工作单位：亟直盍堂电话： 通讯地址：酉直盍堂i 土篚扭复焦皇叠堂堂瞳邮编： f 坠! j2i ! 21 1 4 0 07 i5 砾 婴 “瓣 论 鬈h 一豫川 i 争t j f0 1 1 论文研究背景 第1 章引言 a g e n t 是处在某个环境中的计算机系统，该系统有能力在这个环境中自主行动以实现其 设计目标。而多a g e n t 系统则是由多个可以相互交互的a g e n t 计算单元所组成的系统【1 】。白 2 0 世纪8 0 年代以来，人们已酱遍认识剑多a g e n t 系统在探索大规模分布式开放系统方面、 在理解和刻画现实世界中的复杂问题方面，在构造备种人工系统方面都有1 f 常广泛的应用 【1 】 2 】。 但在基f 多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 对环境自适席能力的关键挑战之- - p l 。在网格计算领域和自主计算领域中，也存在类似的困 难问题，分别称为“虚拟组织的形成和管理” 4 1 5 1 和“计算系统的自我管理”【6 】。本文即是立足 丁多a g e n t ，对a g e n t 、网格计算、自主计算等这多个领域共同关心的动态重构问题进行研 究。 同时，这一问题亦来自于对导师研究课题的思考。导师张自力教授一直致力于如何设 计、采用多a g e n t 系统来解决如金融投资规划、大璎数据挖掘等现实世界中存在的复杂问题， 目前己成功地构建了用丁二金融投资规划和数据挖掘的混合智能a g e n t 系统。提出了一个革命性 的构建混合智能系统的通用框架 2 ( 如图卜l 所示) 。 然而，在此框架中，还有一个关键问题尚未解决：即在任务不同或者环境变化的情况 下，p l a n n i n ga g e n t 如何动态重构基t a g e n t 的智能系统。本文的研究能够对这一问题提供有 力支持。 1 2 问题的提出 动态重构问题是在动态、分布式、复杂的网络环境中构建自治多a g e n t 系统的一个关键问 题。比如，在动态变化的环境中，一个a g e n t 系统中的某个a g e n t u - 能会在某个时刻无预期的 消失( 比如因为通信失败) ，这样原来的a g e n t 系统将不再有效，需要重新组织一个适合于当 前环境的新a g e n t 系统。再比如，某个任务的执行过程中，任务的要求和参与解决任务的 a g e i l t 的个体能力发生r 改变那么也需要对腻来的a g e n t 系统进i ，调铬使它适合r 当i j i 的 情形。 图1 - 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 的位置) 、a g e n 【 实现的重构和l a g e n t 交且接口的重构。针对这四个方面，国内外学者探索了多种解决途径。如 a g e n t g 页域s y c a r a 等提出了利川不同种类的中f 司a g e n t ，以实现系统d p a g e n t 的动态增加或删 除【7 】；h a n n e b a u e r 提出了侧蕾丁个体a g e n t ( 微观) 而不是十t 会( 宏观) 级别的两种重配霞操 作“a g e n t 合并”与“a g e n t 分解” 8 】：p a l m a 等探索了修改系统q h a g e n t 地理分布的匝构 技术【9 】；一些研究者借鉴博奔论承l 社会学的方法，对在动态网络中构建健壮、敏捷的a g e n t 动态联盟进行了探索 1 0 1 1 1 l 】。同时，类似的相关研究 作也在网格计算【5 1 2 】、自主计算 【6 j 、计算机通信网络 1 3j 、自适戍软件1 1 4 等领域进行。 动态莛构在不同的应用研究中，有不同的具体含义。在m i c h a e lw o o l d r i d g e 提山的场景l 中 1 】，动态藿构指的是邻近机场的自治航空运输控制系统自主发现并协助其他故障航空运输 控制系统的能力，我们可以把它理解为整个圆家机场自治航空运输控制系统的自我恢复。在 l a nf o s t e r 提出的场景2 中【1 5 】，动态重构则指系统如何根据 h 户需求，动态维持网络营运商综 合服务以最大化用户满意度。 场景l ：r u r i t a n i a 王国一个主要机场的关键航空运输控制系统突然出现故障，使机场附 近的航班失去航空运输控制的支持。幸运的是，邻近机场的自治航空运输控制系统发现了该 机场出现的问题，并且协助引导和处理受影响的航班，避免了一场可能发生的灾难。 场景2 ：一个用户要上网娱乐，是需要多个服务商来联合提供服务才能够实现的。比如网络 服务商提供带宽，h o s t i n g 服务商提供服务器和存储资源，应用服务提供商提供在线游戏引擎， 游戏工作室提供媒体内容等这些服务都会被整合到一起来提供给用户使用但是，在上网娱乐 过程中，参与者交互的行为可能会发生改变，他们要求娱乐的内容也可能会发生变化，那么如何 2 篱l 争c f 。i 对这些资源进行自治的分配和管理，以及如何实现设施和服务的动态发现和动态配置呢? 本文将在供应链管理的场景f 研究动态重构( 该背景r 的重构类型与场景2 类似) ，研究 的e j 标就是要找出一个在任务个数、要求，a g e n t 的个数、能力均动态变化情形卜，使完成任 务的a g e n t 统本身白适应变化的有效解决途径，开发实现动态重构和让动态重构有效i ： 仃的一系列算法、技术。同时，本文亦要考查，在供麻链管理这一具体问题中，具备动态重 构能力的多a g e n t 系统与普通多a g e n t 系统有何优势，以此探讨动态重构的实际应用价值。 1 3 论文研究意义 1 3 1 理论意义 论文的理论意义主要有以卜几个方面： 1 对 = a g e n t f g i = 究领域，动态重构技术使解决复杂问题的智能a g e n t 系统实现自我凋整成 为可能。这样，更灵活的智能a g e n t 系统更能适戍不同的任务和不断改变的环境，从而使复杂 u j 题被快速、高质肇的解决。 2 对丁i 网格计算领域，虚拟组织有了动态重构技术，就为智能a g e i l t 系统提供了更灵 活、更充分的基础结构，这必将大人简化维护和配置l t 基础设施所需进行的操作。从而，一 方面，用于管理i t 设备的代价会显著f 降，软件失败造成的巨人破坏也将会极人降低。另一 方面，更好的r r 设施又可以大大加强虚拟组织实际操作的能力，提高我们使_ i j 智能信息的能 力。 3 在分布式网络环境中，通过引入动态重构的机制和技术，网络中的各种联盟能够充 分实现灵活性、适应性。这样，分布式系统和网络就可以根据交易的变化，按照需求进行相 席的重配置，从根本上促进了更灵活的i t 调度和更有效的计算资源利用。 4 在本文中，我们利用最新的可计算范型a o c ，在二个不同层次上设计并刻画a g e n t 的 行为，提取臼组织和复杂系统的规则。因此，本研究不但会为智能a g e m 系统提供新的动态重 构技术，而且会为新的计算范例面向自治的计算做山贡献。 1 3 2 应用价值 i 本文的研究是对课题“基 a g e n t 的混合智能系统统一框架”的一个扩展和补充。该 框架着重于实用性设计，在这个具备动态重构能力的通用框架支持下，系统开发者只需要构 建与领域相关的部分，就可以实现一个具有动态重构能力的混合智能，不需要一切从头开 始。从一定意义上来说，本文的研究有助f 实现基于a g e n t 的、能够动态重构的混合智能系统 的 业级j ：只集。 2 基t a g e n t 系统的动态重构方法只需梢作裁剪和扩展，就能够适刖f 虚拟组织构成与 矾f 钉j 、学 i t1 j 学 一论上 管坤的动态创建、责任分配、多方 办商、对服务状态的描述、对服务能力( 语义) 的理解锋 子i l u j 题中。具有较高的麻州价值。 3 本丈提出的动态重构的模删和技术方法，不t 日适用丁供膨链管理这一实际问题，还 适川i 。叫格领域和自主计算领域的相关问题上，并对需要动态匹构的自治系统提供技术支 持，几仃满庄的商业价值。 1 4 论文主要研究内容 本文的研究目标，就是要在任务、环境，智能a g e n t 动态变化的情况f ，构建智能a g e n t 系统的动态重构模型；开发实现动态重构和让动态重构有效i ：作的一系列算法、技术；并将 这些模掣和技术运h j 剑供应链管理问题当中。 围绕这一研究目标，我们将进行如卜- 几方面的研究： 1 提取智n g a g e n t 系统动态重构的抽象特征 要提取智能a g e n t 系统动态重构的抽象模型，首先就需要对解决复杂问题的智能a g e n t 系 统的实体特征进行刻画和建模。在本文中，我们将采用一种新的计算范型面向自治的计 算( a u t o n o m yo r i e n t e dc o m p u t i n g ，简称a o c ) 【1 6 1 ，来提取智f l e a g e n t 系统动态重构的抽象 模型，构建自治实体的复杂行为特征。通过分析，提取山解决复杂问题的智能a g e n t 系统实体 特征为：自治性；涌现性：适应性：自组织性。 2 具有动态重构能力的智f l e a g e n t 系统建构 住智自e a g e n t 系统动态重构抽象模氆成功提取以后，紧接着，我们又将采用a o c 来构建 具有动态酉陶能力的智能a g e n t 系统。 简而言之，a o c 是一种循环式开发的范例。a o c 算法的每一轮循环，都包括三个阶段： 第一阶段，自然系统识别。它是实际系统建模的先行，目的是要抽取自然界与待建物理世界 的相似性特征。 第二阶段，人l ：系统建构。它包含了构建一个a o c 系统的所有元素。这一阶段义可分为 自治实体建模与环境建模两个子阶段，涉及“识别作用实体”、“定义邻居”、“定义共享知 识”、“定义本地行为规则”等多个任务。 第二阶段，性能测量。这一阶段的主要任务是评价a o c 构建的人l 系统优劣，比较其与 对麻自然系统的相符程度，并根据测苗出来的性能，判断是否需要进行f 一轮循环，直剑性 能达剑满意程度。 本文的第一项研究内容，即是在完成a o c 开发第一阶段任务：抽取自然界中与动态重构 类似问题的关键特征。自然，第一= 项研究内容就足执 ? a o c 开发的第1 二阶段任务：详细地定 义自治实体、环境、行为规! j ! l j 库、系统目标等构建动态重构人i ：系统的所有元素。 3 开发支持多a g e n t 系统动态重构的算法 4 簿i 辛- j ? i 在抽象模型以及人i ：系统构建完成之后。还需要开发支持a g e n t 系统动态重构有效运行 的算法。算法需要着重考虑两个u j 题，一是怎样对动态匹构进行控制：什么时候麻该重构， 什么时候不重构；如果重构，自治实体应该要做哪屿行为：什么时候重构结束。二是要考虑 当重构发生后，自治实体麻该剑哪里找、怎么找替换a g e n t ：怎样判断某个a g e n t 是否是合适 的替换者。 对于第一个问题，我们将设计动态重构算法a s d r 。对j ：第二个问题，我们将改进采用 a o c 思想来解决约求满足问题的算法e r a ( e n v i r o n m e n t r e a c t i v er u l e s a g e n t ) 【1 7 】，用来对 s a g e n t 系统动态重构的人工系统提供支持。 4 将多a g e n t 系统的动态重构方法运用到供应链管理问题中去 有了多a g e n t 系统动态重构的模硝、方法和技术，我们还需要考察它们的实际应用价值和 实际运行情况。因此，本文选择国际贸易a g e n t 竞赛中的供应链管理单元作为研究背景 ( h t t p ：w w w s i c s s e t a c ) ( t a cs c m ) 来考察动态重构模型、技术、方法的l e 确性和有效性。 t a cs c m 是在供应链管理问题中检验贸易a g e n t 能力的一个国际竞赛，每年都吸引数十 个大学和研究机构参加。在国际上具有较大影响。在t a cs c m 中，a g e n t 将模拟一家小型计 算机装备j ：厂的管理人员，它需要对从配件获取、产品生产到完成客户订单的褴条供应链进 行良好的管理，以获取最人的利润。但是，在这样的一个供应链管理的过程当中，可能会有 一些不可预知的事情发生。比如，某个供货商可能冈为遭遇了突发性的、毁灭性的自然灾害 而导致在较长的一段时间不能按时剑货；客户可能在向l ：厂下单之后改了主意，希望改换部 分配置。这种时候，就需要：厂具备动态重构能力，以能快速的从这些变故中调整过来，避 免遭受更大的损失。 本文将探讨如何将基f a o c 的动态重构模型进行改进和扩展，并将其运用剑供应链管理 问题当中。 1 5 论文主要贡献 本文所做的主要贡献主要在以下3 个方面： 1 采用计算范犁面向自治的计算a o c 提取出了智能a g e n t 系统动态重构的抽象模 型，对基于该模璎构建出的人r 系统中的关键要素进行了定义，构建了自治实体的行为规则 库。提出了支持动态重构的算法a s d r 。 2 对于动态重构中涉及到的建组及组维持问题，我们通过改进算法e r a 获得两个适用 于动态、分布式、实时情况下建组的算法：i e r a 及启发式h i e r a 。并对两个算法的收敛性、 有效性进行了实验。 3 改进和扩展动态重构模型，并将其运用到供应链管理的背景中，并通过实验，对添 加和未添加动态重构能力的贸易a g e i l t 进行了比较。 一5 i 嘶i j 如f r j i 分工 1 6 论文结构安排 论文结构安排如卜： 第1 章是引言。介纠了本文的研究背景，提出要研究的问题以及该m 题的粗略现状，指 i l i 论文的主要研究内容和意义，对全文结构，立排进行了简介。 第2 章是相关研究同顾。较为详细的介绍了多a g e n t 系统动态霞构研究现状，以及供应链 管理领域的研究情况。 第3 章介绍了本研究涉及剑的相天理论：多a g e n t ：系统理论、面向自治的计算a o c 、约束 满足问题c s p 以及环境、自治实体、行为规则算法e r a 。 第4 章重点描述了基丁a o c 的动态重构系统模型a d r m ，对模犁中的关键要素进行了定 义。 第5 章给出了支持动态重构的两个算法：i e r a 和h i e r a ，并对两个算法的收敛性、参数 选择等进行了实验和分析。 第6 章主要讲述动态重构在供应链管理系统中的运用。首先给出了本文改进的应用背 景然后重点探讨了如何对动态重构模型进行改进和扩展，最后讨论了支持动态重构的供应 链管理系统d rs c m 。 第7 章主要介纠d rs c m 原魁系统的实现和基丁该原犁系统的对比实验，对实验结果进 行了评估和分析。 第8 章是全文的结求语，包括对现有_ l 作的总结和对未来j 二作的展望。 6 织2 帝相关研究p f 顾 第2 章相关研究回顾 2 1 多a g e n t 系统动态重构研究现状 多a g e n t 系统动态重构问题又被称为“运行时重构与重设计”，铍列为支持a g e n t 对环境自 适应能力的关键挑战之- - 3 。其类似的问题义铍称为“动态联盟的形成与管理”( a g e n t 领 域) 、“虚拟组织的形成与管理”( 网格领域) 5 】 1 2 】和“计算系统的自我管理”【6 】( 自主计 算领域) 。虽然在不同领域对这一问题命名有所不同，但其基本的思想都是让一个群体、组 织、系统能根据条件的变化实现自主配置、自我管理。 针对这一问题，a g e n t 研究领域的国内外学者探索了多种解决途径，也有越来越多的学者 在网格领域中展开类似 作的研究。同时，有关自配置的讨论也在自主计算【6 】、计算机通信 网络【1 8 】、自适应软件【1 4 】等其它领域进行。 2 1 1a g e n t 领域中动态重构研究现状 p a l m a 等探索了修改系统中a g e n t 地理分布的重构技术【1 0 】。p a l m a 等提出了一个基 丁结构描述语言a d l 的分布式系统模犁，在该模型中，中间件的基础机构为大规模 麻_ i j 提供了分布、通信、因果排序等属性的支持。该模璎主要致力于解决动态重构 的其中两个方面：( 1 ) 改变应用的体系结构( 比如增加删除a g e n t s ，改变内部联接 模式等) ；( 2 ) 改变一个应用的地理分布( 比如改变a g e n t s 所在位置) 。 s y c a r a 等提出了利用不同种类的中间a g e n t ，以实现系统中a g e n t 的动态增加或删除 【8 1 。他们在服务的提供者和需求者之间定义了匹配者( 黄页服务) 、经纪人、公告 板等多种类型的中间a g e n t ，以便于能够在服务和提供服务的a g e m 均不断变化的网 络中搜寻和挑选到合适的服务。 h a n n e b a u e x 提出了侧重于个体a g e n t ( 微观) 而不是社会( 宏观) 级剐的两种重配置 操作一一“a g c l l t 混合( a g e n tm e l t i n g ) ”与“a g e n t 分解( a g e n ts p l i t t i n g ) ”【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 分离的过程，它很可能会产生另外的新 a g e n t 。通过以上两种途径，实现那些需要协同求解问题的自治、动态的配置调整。 v a i ld e rh o e k 和w o o l d r i d g e 提出了授权和协作的动态逻辑d c d - p c ，利j j d c l - p c ，交餐 可以在a g e n t 联盟中动态分配，使得联盟的能量结构( p o w e rs t r u c t u r e ) 发生变化 【1 9 。 目前，国内一些研究小组也在开展与该问题类似的研究 作，如“网络资源的智能 聚融”( h t t p ：w w w s e m g n d n e t ) ， 一7 婀t 何，、 砸f j ，f ? ，诊上 但是f l 以卜| 的研究中，都没能提出一个住任务个数、要求，a g e n f f f j 个数、能力均动态变 化怙形f ，使完成任务的多a g e n t 系统本身 i 适应变化的有效解决途彳争。 2 1 2a g e n t 联盟形成研究现状 多a g e n t 系统的动态重构| u j 题义l _ j a g e n t 联盟问题紧密相天，它实际上是对某种a g e n t 联盟 联合成功后的动态管理过程。 近些年来犬丁a g e n t 联盟形成的研究在分布式人r 智能领域( d t s t n 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 ，d a i ) 【2 0 1 、多a g e n t 系统 2 1 1 和电子商务领域中蓬勃发腱，久致可分为静态联盟 形成和动态联盟形成两人类。 静态联盟形成又可分为基丁效用( u m i t y - b a s e dm o d e l ) 和基f 补充模型 ( c o m p l e m e n t a r y b a s e d m o d e l ) 这两种途径1 2 2 。当前的研究多与效i h 相天，主要的技术手段 取材丁- 博弈论和经济学，着眼丁如何在联盟内a g e i l t 间划分联盟的额外效用和联盟结构生成这 两人方面【l l 】 2 3 】。 s h e h o r y 等提出了一个在人规模电子市场中的多a g e n t 联盟形成模硝，描t a g e n t j j d 入、离开直至达剑联盟稳定状态的宏观行为【2 4 1 n a t h a ng r f f i t h s 和m i c h a e ll u c k 给出了基于动机和信任的联盟形成机制，阐述了自利 的a g e n t 如何建立、维持、解体一个部落( c l a n ) 的过稃【2 5 】： w o o l d r i d g e 和j e n n i n g s 提出了完牲的包含联合意图、全局规划等协商备阶段的多 a g e n t 协作问题求解方案 2 6 】； k r a u s 等人提出了一_ 种协议，某个a g e n t 可以用边际启发和专家启发的方法来选择联 盟的伙伴，而不需要确切的知道其他a g e m 完成子任务的耗费，从而使a g e n t 面对 不完全信息