（计算机软件与理论专业论文）基于动态模糊关系的多agent系统组合模型与测试系统设计.pdf

基于动态模糊关系( d f r ) 的多a g e n t 系统组合模2 - j 测试系统设计 摘要 摘要 多a g e n t 协作是求解复杂问题的有效途径之一，而在多a g e n t 协作 过程中a g e n t 如何组合是问题的关键。本文通过研究a g e n t 的关系入手， 基于动态模糊关系( d y n a m i cf u z z yr e l a t i o n ，d f r ) 建立了多a g e n t 系统 组合模型，主要包括如下几个方面的工作： ( 1 ) 分析当前多a g e n t 系统在a g e n t 组织、联合心智等方面的研究现 状，给出了基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型。 ( 2 ) 研究了多a g e n t 系统组合模型的稳定性，并给出了相关结论。 ( 3 ) 设计了基于d f r 的多a g e n t 系统组合模型的测试系统，对模型进 行了验证。 通过上述的研究工作，本文给出了基于d f r 的多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 b s t r a c t 基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型与测试系统设计 a b s t r a c t m u l t i a g e mc o l l a b o r a t i o ni so n eo f t h ee f f e c t i v em e t h o d st or e s o l v et h e c o m p l e xp r o b l e m s t h ec r u c i a lp o i n ti sh o wt oc o m b i n et h ea g e n t s b y s t u d y i n gt h er e l a t i o no fa g e n t s ，w eu s ed y n a m i cf u z z yr e ! a t i o n ( d f r ) t o d e v e l o pm u l t i a g e n ts y s t e mc o m b i n a t i o nm o d e l o u rm a i nw o r ki n c l u d e s t h r e ea s p e c t sa sf o l l o w s ： 1 t h r o u g ha n a l y z i n ga c t u a ls t a t e m e n t m e n t a l s t a t e ，t h e a u t h o rb u i l d s t h e c o m b i n a t i o nb a s e do nd f r o fa g e n to r g a n i z a t i o na n dj o i n t m o d e lo fm u l t i a g e n ts y s t e m 2 t os t u d yt h es t a b i l i t yo ft h em u l t i a g e n ts y s t e mc o m b i n a t i o nm o d e l ， s o m er e l a t i v er e s u l t sa r eg i v e n 3 at e s ts y s t e mi sd e s i g n e dt op r o v et h ev a l i d i t yo ft h em u l t i a g e n ts y s t e m c o m b i n a t i o nm o d e l t h r o u g ht h ew o r ka b o v e ，w eg i v et h ed e s c r i p t i o no nm u l t i _ a g e n ts y s t e m c o m b i n a t i o nm o d e l s e r i e so fb a s i cr e s u l t sa l s oa r eg i v e n i ti st op r o v i d e s o m et e c h n i c a ls u p p o r t sf o ra g e n tc o o p e r a t i o n h o w e v e r , f o rc o m p l e x i t yo f m u l t i a g e n ts y s t e m ，a l lt h e s ew o r k sa r et e n t a t i v ea n dm a n yo ft h e mn e e d a d v a n c e dr e s e a r c h k e y w o r d s ：m u l t i a g e n ts y s t e m ，m u l t i a g e n ts y s t e m c o m b i n a t i o n m o d e l ，d y n a m i cf u z z yr e l a t i o n w r i t t e nb yz h uw e i s u p e r v i s e db yl if a n z h a n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：赝提交的学位论文是本人在导师的指导下，独立进 行硖究工作所取褥的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获彳导苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 石并究生签名： 学位论文使用授权声明 目期：“彤沪 苏州大学、中圈科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位沦文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生 导师签 霸期： “弘 日期：号么汐矽 基于动态模糊关系( d f r ) 的多a g e n f 系统组合模型与测试系统匠计 第一童 1 1a 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 m ， 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 之间的合作来完成，合作是m a s 求解任务的 基本过程。在这里a g e n t 的合作是指多个a g e n t 通过执行一定的动作， 共同完成任务的行为。a g e n t 是具有内部状态及外部行为的实体。它被认 为是一个意识系统( i n t e n t i o n a ls y s t e m ) 1 ，a g e n t 的内部状态也被称为 心智状态( m e n t a ls t a t e ) ，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 对自身的状态、资源 进行协调是解决这个矛盾的一个方面，另一方面需要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 的合作一般是 由系统中多个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 行为的驱动因素。a g e n t 可能通过组合使信念更加坚定， 第一章 基于动态模糊关系( d f 鼬的多a g e n t 系绕组合模型与测试系统设计 愿望更加强烈，目标更加一致，当然，相反的状况也可能会发生。所以 如何组合，以什么因素作为组合的依据与基础，是a g e n t 组合问题中的 关键问题。 1 2 国内外研究情况 人工智能的理论与技术是a g e n t 研究的主要的理论基础。s t a n f o r d 大 学计算机科学系的h a y e s r o t h 4 ，在i j c a i 。9 5 的特邀报告中谈到：“智 能的计算机主体既是人工智能最初的目标，也是人工智能最终的目标。” 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 的研究 的理论基础很多来自于与人类社会行为研究相关的决策科学、管理与组 织科学、经济学、对策论等 2 】。可以说，人类社会是m _ a s 研究非常好的 参照物。关于人类社会方面的科学理论是m a s 研究的理论基础之一。 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 社会性的基本行为。目前很多m a s 的研究都直接或间接地建立在对这类行为的研究上。 目前国内外在理论研究的同时也对a g e n t 技术的应用进行大胆的探 索，这样就产生了很多学术研究以及商业用途的a g e n t 工具。而在d a i 研究方面早期提出的一些经典模型 2 ，如合同网协议，a c t o r 系统，黑板 系统等，时至今日仍然在m a s 研究中扮演重要的角色。 基于动态模糊关系( d f r ) 的多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 的一种特殊结构形式，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 组织一般没有明显的组织结构表示，而预先设计的组织往往定义了 一个显式的组织结构。目前的研究中，由于显式的有明确目标的组织定 义方式，比较符合人类社会的组织形式，已经被越来越多地使用 5 】。 a g e n t 组织在不同的理论、技术基础上，已经形成了多种方法。 在s m i t hr g 6 提出的合同网协议的基础上，通过协商形成组织是 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 之间 便形成了顾客与服务员合同的组织。文献 7 对合同网协议进行了改进， 提出通过报酬奖励换取服务的这种更接近人类合同行为的方式。文献 8 结合a g e n t 群体智能提出了一种适应环境及a g e n t 能力动态变化的动态 合同网协议，对经典的合同网协议进行了改进以适应动态的m a s 。 文献 9 ，l o 提出在m a s 中，a g e n t 之间存在社会依赖，包括行为依赖， 资源依赖以及兼有两种依赖。通过对a g e n t 之间依赖关系的社会推理， 发现与目标有依赖关系的其它a g e n t ，并与之形成不同形式的合作组织。 这又是一种形成a g e n t 组织的方法。 文献【1 1 引入了一个表示a g e n t 之间联系的熟人关系网模型，对 a g e n t 之间的可信任度关系进行了讨论，并分析了a g e n t 熟人关系链上可 3 第一章 基于动态模糊关系( d f r ) 的多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 的行为是受其心智状态的控制的，而多个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 联合心智研究方面，c o h e n 等在单个a g e n t 思维状态b d i 模型的基础上，描述了a g e n t 群体的联合意图等概念【1 3 】，定义了弱目标 w g 、联合持续目标j p g 、联合意图j i 并推出了一些结论。 文献 1 4 在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 5 研究了团队的活动中如何采用言语动作形成、维护、解除联 合意图，在概念上明确区分了联合请求与委托请求，指出委托请求言语 动作不能充分支持团队协作。基于联合请求动作，提出了一种主体团队 基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型与测试系统设计 第蕈 交互协议，并给出了协议的形式化语义。 在a g e n t 应用方面，m a s 在商业方面的应用目前面向a g e n t 的软件 工程方法还不成熟。a g e n t b u i l d e r 1 6 是a c r o n y m i c s 用j a 、，a 开发的套 a g e n t 与m a s 的实现工具。a g e n t b u i l d e r 包括一个运行支撑环境和一个 工具包，前者是a g e n t 的驱动引擎，后者是a g e n t 的设计调试工具。 a g e n t b u i l d e r 中a g e n c y 指a g e n t 的群体，用这种方式提供了对m a s 的一 定设计能力。a g e n t b u i l d e r 从对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 的社会性，一般以a g e n t 组织表 示a g e n t 的社会结构。形成a g e n t 组织的方法则更多的倾向于是采用预 先定义的方式，系统的设计者预先定义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 组合是形成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 的行为，而联合 第一章 基于动态模糊关系( d f r ) 的多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 的内部世界是个充满动态模糊性的世界。同时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 的动态模糊性( 微观上的动态模糊性) 使m a s 整个表现出动态模 糊性( 宏观上的动态模糊性) 。由此不难看出，无论从a g e n t 的个体还是 从m a s 的整体来看，m a s 都是一个普遍存在动态模糊性的系统。 动态模糊集合及动态模糊逻辑系统理论是研究动态模糊现象的理论 工具。因此，我们根据a g e n t 组合的实际问题需求，选择动态模糊关系 理论来研究a g e n t 组合的相关问题。 1 4 研究目标、内容及其安排 本文针对m a s 的动态模糊性，借助动态模糊集合理论建立一个基于 动态模糊关系的m a s 组合模型，内容安排如下： 第一章绪论，主要介绍了本文的研究背景以及本文的主要研究内容。 第二章动态模糊关系，动态模糊关系理论是本文建立m a s 组合模型的 主要形式化工具，所以本章主要介绍了动态模糊关系的主要理论。 第三章基于d f r 的m a s 组合模型，从m a s 组合模型的各个要素进行 基于动态模糊关系( d f r ) 的多a g e n t 系统组台模型与测试系统设计 第一章 讨论，并建立基于动态模糊关系的m a s 组合模型。 第四章m a s 组合模型分析，对本文提出的m a s 组合模型进行稳定性等 分析。 第五章m a s 组合模型测试系统设计，设计测试系统验证本文提出的模 型的有效性。 第六章总结与展望，总结本文的内容并对以后的工作给予展望。 一 第二奇基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型与测试系统设计 2 1 引言 第二章动态模糊关系 a g e n t 是一个具有自治性的实体，它对整个世界( m a s ) 的视图是不 准确的，对系统的未来的状态是未知的，而自身的行为显然也是不确定 的。上一章我们已经分析了在a g e n t 及m a s 中动态模糊性是普遍存在的。 为了更好地建立它们之间的组合协调群体问题的基本模型，因而研究心 智状态之间的关系表示则是其关键问题之一。因此，本文借助动态模糊 关系( d f r ) 理论作为形式化工具，下面首先介绍动态模糊关系理论。 2 2 动态模糊关系( d f r ) 理论 2 3 1d f r 的定义 定义2 1 设( 牙，牙) ，( 穸，矿) 为论域，若( 豆五) d 罗( ( 宕，贾) ( p ，罗) ) ，称( 应，夏) 为 ( 宕，贾) 到( j ；，p ) 的动态模糊关系( d y n a m i cf u z z y r e l a t i o n ，d f r ) ；特别的， 当( 戈，牙) = ( 穸，) ，则称( 豆厦) 是( 牙，贾) 上的动态模糊关系。( i ，五) ( ( 暑，葺) ，( 歹，只) ) 是( 豆再) 的隶属函数。 由定义2 1 可知，d f r 是一类特殊的d f 集合 3 】。d f r 的论域是构 成d f r 的两个集合中元素的对应关系( 即两个集合的笛卡几积) 。d f r 可以用来描述具有动态模糊性的客体( a g e n t ) ，例如“同学之间的友好 关系”，而“友好关系”是建立在“同学”之间的。同学之间的友好关系 具有模型性和动态性，可以用动态模糊关系来描述。 作为特殊的d f 集合，d f r 也具有d f 集合的交、并等运算模式，以 基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型与测试系统设计 第二章 及d f 集合的一般性质。此外，d f r 又由于其论域的特殊性，使它具有 不同于普通的d f 集合的性质。 d f r 可以用动态模糊( d f ) 矩阵来表示。 定义2 2 若( 豆豆) ：( 牙，牙) x ( ，矿) 寸 o ，1 卜，j 】，( 反，辰) 为d f 矩阵，记为 r ( i ，i ) ( 豆，晨) = i j i ( ，。) ( 五。i 。，) 1 l ( ，。) j 其中，( 弓，弓) = ( 豆，天) ( ( 墨，霉) ，( 歹，歹，) ) ( 1 f sn , 1 ，m ) 。 d f 矩阵是d f r 不同形式的等价表示。表格化的结果使得某些d f r 的性质描述更加直观，d f r 的计算更为方便。以下将d f r 与d f 矩阵等 同看待，在论及d f r 的性质时，不作说明时也同样适用于d f 矩阵，反 之亦然。 2 2 2 动态模糊关系( b f r ) 的基本计算 定义2 3 设( 詹，辰) ，( 五，五。) ，( 爱：，辰：) d f ( ( 2 ，牙) ( 穸，矿) ) ，记 a ) ( 宠。，爰，) c ( 豆：，豆2 ) 畚( 霞1 ，五、) “i ，牙) ，( 歹，歹) ) ( 衷2 ，厦：) ( ( j ，牙) ，( 夕，罗) ) ( ( 牙，i ) ，( 夕，夕) ( ( j ，贾) ，( ，尹) ” b ) ( 衷。，j i 。) u ( 晨：，晨2 ) ( ( i ，牙) ，( 夕，歹) ) = ( j 。，孟，) ( ( 贾，牙) ，( 歹，夕) ) v ( 豆2 ，j i ：) ( ( 舅，冤) ，( 歹，歹) ) ( r ，r ，) n ( r ：，r ：) ( ( 曼，i ) ，( 夕，歹) ) = ( r ，r ，) ( ( 更，i ) ，( 歹，歹) ) ( r ：，r ：) ( ( 冤，i ) ，( 歹，歹) ) c ) ( r ，尺) 1 ( ( 膏，i ) ，( 夕，歹) ) = ( r ，r ) ( ( 歹，歹) ，( 章，元) ) 定理2 1 ( 五，j i ) 一1 具有如下性质： 第二章 基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型与测试系统设计 ( 1 ) ( 五。，五。) 亡( 豆，厦2 ) j ( 应。，夏，) “c ( 克：，r 一：) “ ( 2 ) ( ( 应，j i ) “) = ( 豆，夏) ( 3 ) ( ( 矗，r 一，) u ( 夏：，r 一：) ) = ( 衷，豆) 。u ( 豆2 ，r 一：) ( 4 ) ( ( 豆，五，) n ( 衷，辰：) ) = ( 豆，五，) “n ( r 一2 ，r 一1 ) 一 证明】( 1 ) 和( 2 ) 显然。 现证( 3 ) 。由于v ，贾) ( j ，戈) ，( 夕，歹) ( p ，矿) ，有 ( ( j i 。，豆i ) u ( 豆：，r 一2 ) ) 。( ( 牙，贾) ，( 歹，夕) ) = ( ( 应。，j ，) u ( j ：，豆：) ) ( ( 夕，歹) ，( 舅，王) ) = ( 厦，孟。) ( ( 歹，夕) ，( 冤，牙) ) v ( 爱2 ，孟2 ) ) ( ( 夕，歹) ，( 舅，夏) ) = ( 兵。，孟1 ) 1 ( ( j ，i ) ，( 歹，夕) ) v ( 豆2 ，r 一：) ) 。1 ( ( 更，i ) ，( 歹，歹) ) = ( 豆，孟) - 1u ( 应：，五：) 一( ( 量，冤) ，( 歹，歹) ) 则( 3 ) 成立，( 4 ) 类似可证。 证毕 定义2 4 设( 贞，晨) d 罗( ( 戈，足) ( 穸，p ) ) ，( s ，s ) d f ( ( 矿，p ) ( 2 ，乞) ) ，( 五，辰) 牙口 ( s ，蜃) 的复合运算为： ( r ，r ) 。( s ，s ) ( ( j ，牙) ，( 三，；) ) = ，一v 。，、( r ，r ) ( ( j ，i ) ，( 夕，歹) ) ( s ，s ) ( ( 夕，罗) ，( 三，；) ) 。 【，y je 【，j d f r 的复合运算是由两个有联系的关系获得新的关系的运算，我们 可以通过多层关系描述一些对象之间合成的关系，例如“同学之间的友 好关系”、“同学之间的学习竞争关系”可以复合成新的关系“同学之间 友好的学习竞争关系”。 定理2 2d f r 的复合运算具有以下的性质： ( 1 ) ( ( 詹，辰) 。( 雪，雪) ) = ( j ，j ) 。( 豆，豆) 基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型与测试系统设计 第二蕈 ( 2 ) ( 五。，天，) 仁( 夏：，r 一：) j ( 再。，爰。) 。( 雪，雪) c ( j i ：，r 一：) 。( s ，雪) ( 3 ) ( 墨，s ，) c ( 9 2 ，雪：) ( 豆，豆) 。( s 。，雪，) c ( 衷，豆) 。( 9 2 ，s ：) ( 4 ) ( 再，辰) 。( ( s ，j ) 。( 于，于) ) = ( ( 蠢，五) 。( 掌，s ) ) 。( 于，于) ( 5 ) ( 辰，夏) u ( ( 豆，s ，) 。( 曼，s 一：) ) = ( ( 友，五) 。( 量，墨) ) u ( ( 夏，五) 。( 丑，受) ) ( 6 ) ( ( 豆。，豆，) u ( 矗：，五：) ) 。( j ，雪) = ( ( 再。，五。) 。( j ，s ) ) u ( ( 豆：，r 一：) 。( s ，雪) ) ( 7 ) ( ( 詹，詹，) r l ( 宠：，五：) ) 。( j ，雪) = ( ( 胄。，辰。) 。( s ，雪) ) n ( ( 是，五：) 。( s ，雪) ) ( 8 ) ( 豆，爱) n ( ( 掌。，s ，) 。( s ：，s ：) ) = ，( ( 豆，反) 。( 墨，s 、) ) n ( ( 矗，五) 。( s ：，雪：) ) 其中( j 。，豆。) ，( 袁：，j i ：) ，( j ，豆) d 罗( ( 贾，贾) ( ，p ) ) ， ( 墨，雪、) ，( & ，雪：) ，谚，s ) d 罗( ( 穸，j ；) ( 2 ，2 ) ) ，且仃，于) d 7 ( ( 2 ，2 ) ( 旷，旷) ) 【证明 由于 【( 蠢，豆) u ( ( s 。，雪。) 。( s ：，s ：) ) ( ( j ，i ) ，( ；，j ) ) 2 ( 歹，歹) v ( p ，p ) ( ( 胄，再) ( ( 舅，王) ，( 歹，夕) ) 0 ( ( 雪- ，雪t ) f l y ，歹) ，( 三，i ) ) v ( 9 2 ，g z ) f l y ，歹) ，( 三，；) ) ) = ( ( 夕，歹) ：( p ，p ) ( ( 反：豆) ( ( 冤，夏) ，( 歹，歹) ) ( s t ，s - ) ( ( 夕，罗) ，( 三，艺) ) ) ) v ( ( 夕，罗) ：( p ，f ) ( ( 豆，再) ( ( 置i ) ，( 歹，罗) ) n ( 雪：，s z ) f l y ，歹) ，( 云；) ) ) ) = ( ( 厦，五) 。( s ，s ，) ) ( ( 膏，j ) ，( j ，：) ) v ( ( 爱，五) 。( s ：，s 一2 ) ) ( ( 牙，j ) ，( j ，；) ) = ( ( j i ，豆) 。( 墨，雪。) ) u ( ( 豆，辰) 。( s ：，s ：) ) ，贝0 证( 5 ) 其它情况类似可证。 证毕 第二章 基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型与测试系统设计 定义2 5 设( 应，五) e d 罗( ( z 牙) ( j ，贾) ) ，即( 豆豆) 是( j ，牙) 到自身的动态 模糊关系，对于自然数i 1 记 ( 应，五) 2 = ( 豆，厦) 。( 蠢，辰) ( 矗，詹) “= ( 五，辰) 。( 五，辰) n 。1 并规定，( 豆，五) o = a ( 豆，辰) = ( 厦，豆) 其中，是恒同关系，即 定义2 6 是( 宜，贾) 上的恒同关系，如果 蛳瓤m 如胪僻篱嚣； 由定理2 2 ( 4 ) 易知，对任意满足i 呵= 胛的自然数i ， ( 辰，五) “= ( 贞，五) 5 。( 五，晨) 2 3 几个性质特殊的动态模糊关系 在实际的应用中，与普通的d f r 比较，具有特殊性质的d f r 往往 更具有实用价值。所以在这里介绍下文中将涉及到的几个特殊的d f r 。 定义2 7 设( 豆，豆) 是( 七，贾) 上的d f r ，如果a c ( 豆豆) ，则称( 袁，j ) 是自反的 d f r 。 定义2 8 设( 豆再) 是( 宏，贾) 上的d f r ，如果( 友，厦) = ( 厦，五) ，则称( 应，五) 是对 称的d f r 。 定义2 9 设( 蠢，豆) 是( 戈，贾) 上的d f r ，如果( 是豆) 2 ( 屈五) ，则称( 豆j ) 是传 递的d f r 。 基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型与测试系统设计 第二童 自反的、对称的以及传递的d f r 是几种比较常见的d f r ，也是研究 其它特殊性质的d f r 的基础。对应于d f 矩阵，自反的d f r 对角线元素 都是( i ，i ) ；对称的d f r ，d f 矩阵是关于对角线对称的；传递的d f r 没 有这样的明显特征。 有时我们得到一个普通的d f r ，需要通过它获得一个具有上述特性 的d f r 。 定理2 3 设( 孟，天) 是( 只贾) 上的d f r ，如果( 豆j i ) 是自反的，则 ( 兵，豆) ”( 豆辰) 1 ) ，且( 豆，五) ”( 月1 ) 也是自反的。 证明】用归纳法证明。首先，( 豆j i ) 2 ( ( i ，j ) ，( 只夕) ) = i 仨! ) b 0 ( 宠，j i ) ( ( 膏，训三，；) ) n ( 宠，j i ) ( ( 三，引夕，夕) ) ) ( 厦，j ) ( ( i ，砌，罗) ) 贝0 ( 五，五) ( 五，五) 2 。 假设( 瓦，再) ”。( 豆，天) ”，即( 豆，五) ”1 ( ( j ，i ) ，( 歹，夕) ) ( 豆，晨) “( ( j ，牙) ( 夕，夕) ) 。 ( 衷，孟) ”= ( 袁，豆) 胪1 。( 衷，晨) ， ( 爰，晨) 舯1 = ( 兵，爰) ”。( 豆，豆) 由复合运算的定义以及假设，易知 ( 豆，反) ”。( 应，豆) ( ( 膏，更) ，( 歹，歹) ) ( 五，厦) ”。( 应，五) ( ( j ，牙) ( 歹，歹) ) 即( j i ，j ) 一( j ，豆) ”1 。又由a ( 衷，j i ) 量( 宠，豆) 2 - ( 衷，更) ”可知( 兵，j i ) ”( n 1 ) 是自 反的。 证毕】 定理2 4 设( 衷，兵1 ) ，( 衷：，r 一：) 对称，则( 豆。，霞i ) 。( 宠：，晨：) 对称的充要条件 为：( 囊，五，) 。( 衷：，詹：) = ( j i ，j j i ：) 。( 五。，五。) 。 证明 若( 点，豆) 。( 豆：，r 一：) 对称，则 第二童 基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型与测试系统设计 ( 豆。，r 一，) 。( 袁：，r 一：) = ( ( 五，辰。) 。( j | ：，辰：) ) = ( 爱：，孟：) 。( 衷。，五。) = ( 真：，r 一：) 。( j i 。，j i 。) 反之，若( 矗。，五。) 。( 爱：，五：) = ( 豆：，五：) 。( 豆，j i 。) ，贝0 ( ( 五。，詹。) 。( 五：，五：) ) 一= ( 矗：，五：) 。1 。( 豆，五。) = ( 衷：，厦：) 。( 夏，辰。) = ( 豆。，豆) 。( 衷：，豆：) 于 是( 真。，五。) 。( 爱：，r 一：) 是对称的。 【证毕 定理2 5 设( 囊，五) 是( 足，牙) 上的d f r ，若( j i ，再) 是对称的、自反的，则 f ( ( 豆，五) ) = u ( 五，厦) 。是自反、对称、传递的。 女= l 证明】 f ( ( 尼j i i ) ) 2 = ( u ( 兵，五) ) 2 = ( u ( 应，j i ) ) 。( u ( j i i ，夏) “) = u ( ( u ( 尼j i ) ) 。( 尼孟) ) k = i ；1月，= lm 】i = l = u ( k ，五) 7 r ( ( 真，j i ) ) 因此f ( ( j i ，j i ) ) 是传递的。而由定理2 3 和定理2 4 可知( 豆五) 。是自反的、 对称的。则易知f ( ( 厦，五) ) = u ( 豆，豆) 也是自反、对称的。 k = l 证毕 当需要由一个自反的、对称的d f r 计算一个自反的、对称的、传递 的d f r ，我们只需要计算r ( ( 应，五) ) 便可达到目的。而对于有限论域 f ( ( 豆五) ) = u ( 尼五) 。= ( 豆，五) ”。 k = l 2 4 小结 本章主要介绍了本文的研究所需要使用的主要形式化工具，动态模 糊关系理论。 基于动态模糊关系( d f r ) 的多a g e n t 系统组合模型与测试系统设计 第三章基于d f r 的m a s 组合模型 p a n z a r a s a 和j e n n i n g s 认为a g e n t 的社会性将成为m a s 研究的新理论 基础 1 4 】。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 组合依据的是什么因素，就成为 一个关键的问题。本文试图在这方面做一些探索。 3 2i i a s 组合模型的要素 m a s 组合模型是形成a g e n t 群体的形式化方法，但群体为匹配m a s 的任务求解随时可能会在m a s 运转过程中发生变化，m a s 组合模型还 需要能够调整群体以适应这种情况的变化。因此m a s 组合模型至少需要 如下几个要素： ， ( 1 ) 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 组合模型能正常运行。我们把这 些规则称之为m a s 组合模型的组合规则。 第三章 基于动态模糊关系( d f r ) 的多a g c n t 系统组合模型与测试系统设计 ( 3 ) m a s 组合模型的组合基础。组合模型组合所依据的关键要素。它 是包含了m a s 某些特性，并能够反应系统的特征，从而能够使a g e n t 组合满足m a s 任务求解的要求。 a g e n t 通过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 而言这是个随时可能发生的过程，但为 了方便系统计算可以认为这种调整过程是阶段性进行的。在m a s 中， a g e n t 的重要使命便是完成a g e n t 所面临的一个个的任务。我们可以利用 求解任务的顺序来区分m a s 组合模型调整群体组合的阶段。以一个任务 的完成作为一个调整群体组合的阶段划分点，这种方法的好处是能够在 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 求助于群体 ( 依据m a s 组合模型计算形成的群体) 。群体中的a g e n t 在协商、规划 之后便能够进入合作求解过程，最终完成任务的求解。组合群体的目的 是更高效的合作求解问题。组合的群体必须是为合作求解问题服务的， 这是判断群体组合优劣的标准。虽然希望能够事先就判断群体求解的效 率，以使任务求解能够成功，但在合作过程中仍然会发生无法完成任务 的状况。而此时m a s 组合模型就需要调整群体，改变a g e n t 的群体构成， 基于动态模糊关系( d fr ) 的多a g e n t 系统组合模型与测试系统设计 第三章 比如接纳a g e n t 进入群体，扩大群体的规模，以使群体具有足以解决所 面临的合作任务的能力。而还有种情况是m a s 系统可能会由于系统资 源、计算能力分布的不平衡或者系统负载的限制等，暂时无法完成合作 求解的任务，只能推迟或取消这个任务。对于这些结果m a s 组合模型都 需要对群体进行调整，为将来任务的求解做准备。 当然，m a s 组合模型在a g e n t 中的计算过程并不一定具有这样明显 的阶段性，根据实际情况也可以按其它规律进行安排。m a s 组合模型提 供的是群体组合与调整的形式化的方法，而具体的操作则由a g e n t 来实 现，如何安排m a s 组合模型的计算很自然的也是由a g e n t 具体来实现。 3 3 基于d f r 的m a s 组合模型设计 兰 3 3 1 组合模型要素的选择依据 选择m a s 组合模型的组合基础，很大程度上决定了模型的有效性。 a g e n t 的系统中可以选则的因素有很多，但并不是每一个都非常适合作为 m a s 组合模型的组合基础。这个组合基础既要能够反应m a s 运行状况， 即它应该包含有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 之间的相互作用和相互影响。显然a g e n t 之间可能存在很 多关系。文献 1 9 1 从a g e n t 的社会角色的角度，分析了a g e n t 之间的预先 定义的关系，并在此基础上分析了a g e n t 组织之间的结构、责任、权利 第三章 基于动态模糊关系( d f r ) 的多a g