（计算机软件与理论专业论文）一种多agent并行计算模型及其应用研究.pdf

种多a g c n l 蚌j 亍计弹模型h 成用 摘要 本文在对目前多a g e n t 计算本质分析的基础上，基于二分图的理 论，建立了多a g e n t 并行计算模型。构建了动态的多a g e n t 系统。主 要包括如下工作： 1 ( 1 ) 基于二分图的理论，构建了多a g e n t 并行模型； ( 2 ) 分析了当前多a g e n t 模型的研究状况，构建了动态多a g e n t 系 统： ( 3 ) 给出了动态多a g e n t 系统的流程算法： ( 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 系统 作者：郝水侠 导师姓名：李凡长( 教授) a b s t r a c l 种多a g e n t 并行汁算模型驶u 雌用 a b s t r a c t b a s e do na n n l y s i n gt h ea b s e n c eo fc o m p u t i n ga n ds t u d y i n g b i p a r t i t eg r a p h st h e o r y ，t h ep a p e r i sb u i l t m u l t i a g e n t p a r a l l e lc o m p u t i n gm o d e lb yu s i n gb i p a r t i t eg r a p h st h e o r ya n d m a so fd y n a m i co p e ns y s t e mf o rt h i sm o d e l 。 o u rm a i nw o r ki n c l u d e sf o u ra s p e c t sa sf o l l o w s ： ( 1 )b a s e do nb i p a r t i t eg r a p h st h e o r y ，t h ea u t h o rb u i l d s m u l t i a g e n tp a r a l l e lm o d e l ； ( 2 ) a n a l y s i n g a c t u a ls t a t u so fm u l t i a g e n ts y s t e m ，t h e a u t h o rg i v e sm a so fd y n a m i co p e ns y s t e m 。 ( 3 )g i v em a sf l o wa l g o r i t h mo fd y n a m i co p e ns y s t e m 。 ( 4 )g i v eaf e wa l g o r i t h m so fs o l v i n gp r o b l e mb yu s i n gb u i l t m a s 。 t h r o u g h t h ew o r ka b o v e ，w ep r o p o s et h eb a s i ct h e o r yo f s o l v i n gp a r a l l e lp r o b l e mf o rm u l t i a g e n tp a r a l l e lc o m p u t i n g m o d e l 。o n ea s p e c tw em a k eu pi sf o rt h ea b s e n c eo ft h e o r y 。 a n o t h e ra s p e c tp r o v i d e sam e t h o do fs o l v i n gp r o b l e m 。 k e yw o r d s ：m u l t i - - a g e n t ，p a r a l l e lc o m p u t i n g ， m u l t i a g e n ts y s t e m w r i t t e nb y ：h a os h u i x i a s u p e r v i s e db y ：l if a n z h a n g y6 4 5 7 5 7 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进彳亍研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均己在文中以明确方式标赐。本人承担本 声明的法律责任。 研究生签名：童圭坚! 叁e l 学位论文使用授权声明 期： 仁“ 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复俸4 手段保存论 文。本人电子文档的内容和纸质论文的内容耜一致。除在保密期内的 保密论文外，允许论文被查阅和借阆，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理e 期： 垒整 期：龋 第一章引论 i 1 多a g e n t 的基本概念 1 1 1 a g e n t 的概念n 1 经过二十几年的发展，a g e n t 逐步成为a i ( 人工智能) 及其它计 算机领域内的一个重要研究课题。目前a g e n t 技术的研究领域非常广 泛，包括了m o b i l ec o d e ( 移动代码) 、i n t e l l i g e n tr o u t e r s ( 智能 路由器) 、w e bs e a r c ht o o l s ( 网络搜索工具) 、r o b o t s ( 机器人) 、 i n t e r f a c e ( 接口技术) 等计算机科学的各个领域，因此a g e n t 的概念 有很多的版本。w o o l d r i d g e 和j e n n i n g s 在1 9 9 5 年提出了目前较权 威的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 2 a g e n t 的特点n 1 a g e n t 的特点主要包括自主性、反应性、协作性、进化性、通信 种多a g e n t 片行 十算横掣艇j t 心r l l j f 冗 性、移动性等。 ( 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 ) 社会性 a g e n t 具有社会性的能力，这种能力是指与人一样，a g e n t 与外 界环境和其它a g e n t 之间存在一定的交互，这种交互使得a g e n t 能够 对外进行学习，了解外界环境和r 句j b 施加影响，并可使多个具有独立 性的a g e n t 聚合起来形成一个整体，对外显现出它们的社会特性。 a g e n t 之间的通信语言称为a c l ( a g e n tc o m m u n i c a t i o nl a n g u a g e ) 。 一个a g e n t 能够通过某种a c l 与其它a g e n t 进行交互，向其施加一定 影响，要求其完成一定的服务或拒绝提出的要求等。a g e n t 之间主要 有三种交互类型：协作( c o o p e r a t i o n ) 、协调( c o o r d i n a t i o n ) 和协 商( n e g o t i a t i o n ) 。 ( 4 ) 进化性( 开放性) a g e n t 是一个开放的系统，应具有进化的能力，即能够在推理活 动中适应外部环境的要求，动态的扩充、限制和修改自身的局部知识 的状态。随着与环境和用户之间的交互作用，a g e n t 能够主动适应环 境，扩充自身的知识。 ( 5 ) 通信性 a g e n t 之间能够进行信息交换，通信既保证了a g e n t 之间的相互 交流，a g e n t 的独立性，且有助于提高a g e n t 的内聚力，防止相互之 间的耦合。在i d a s 系统中，a g e n t 的通信性是相互协作、协商的基础。 ( 6 ) 移动性 从严格意义上说，移动性只是一部分a g e n t 的特性。所谓的移动 性是指a g e n t 可以在任何状态下( 包括在运行过程中) 从一个节点移 到一个新的节点上，并维持原有的运行状态。a g e n t 把代码和数据封 装在一个线程中。 1 1 3 a g e n t 计算的本质。1 一般来说，关于a g e n t 计算的定义集中在a g e n t 概念应具有的必 耍条件上，即描述使它可以和其它实体( 如对象、组建等) 区分的特 性，文献 4 中关于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 和对象，组件的主要区别。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 可以说“”。 ( 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 之 间相互作用采用类型消息( t y p e dm e s s a g e ) 方式。 ( 3 ) a g e n t 具有适应环境性。 ( 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 系统中，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 的计算可以视为对人类组织机构的模仿。 1 1 4 用a g e n t 进行问题求解的思路 a g e n t 是处于某个环境中的一个封装好的计算实体，它能够在该 环境中灵活、主动地活动以达到为它设计好的目标。a g e n t 具有自治 性、交互性、主动性和反应性等，它不仅能作用于自身，而且可以旖 种多a g e n t 并行i l 算艇型及址应用冗 动作于环境，并能接收环境的反馈信息，重新评估自己的行为；同时， 它能与其他的a g e n t 协同工作。儿。随着a g e n t 技术的发展，它在基 于网络的分布计算领域发挥着越来越重要的作用：一方面a g e n t 技术 为解决新的分布式应用问题提供了有效的途径；另一方面，a g e n t 技 术为全面准确地研究分布式计算系统的特点提供了合理的概念模型 口1 。由此可知，用a g e n t 技术求解分布式问题的思路是：嘲 ( 1 ) 采用a g e n t 技术可以将一个大而复杂的问题分解成许多较小、 较简单的问题，使问题得以简化。 ( 2 ) 现实世界的实体和它们之间的关系可以直接映射成具有问题求 解能力的a g e n t ，它们拥有自己的资源以及协作求解问题的交 互能力。 ( 3 ) 多个a g e n t 可以组成一个合作的小组以完成特定的复杂任务， 这些a g e n t 之间能够协调相互之间的行为，协商以解决相互之 间的冲突，相互合作以达到共同的目标等。 ( 4 ) 单个a g e n t 或一组a g e n t 可以单独进行开发，并且可以以增量 方式动态地加入到一个基于a g e n t 的系统中来，从而增强该系 统的能力。 ( 5 ) 每个a g e n t 都是面向功能需求而设计的，利用a g e n t 可以快速 地搭建一个复杂的应用系统，具有很好的可重用性。 1 1 5 多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 c i n 并行计算摸型技j 0 心用 些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 $ 目前还没有一个完美的系统，如何构 建一个良好的m a s 是决定系统解决问题的关键，构建一个m a s 的关键 问题之一如何组织系统内的单个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 建模方法，其中大多数都是基于现有方法的扩 展。这些方法大致上可以分为三类：基于面向对象( 0 0 ) 方法的扩展、 基于知识工程( k e ) 方法的扩展和( 纯) 面向a g e n t ( a o ) 的方法。 1 2 1 基于0 0 方法的扩展 基于0 0 方法扩展面向a g e n t 的建模方法是利用现有的成熟的0 0 技术，并加以扩展，使之具有a g e n t 方面的内涵。这些方法主要运用 的0 0 技术包括o m t ，o o s e ，u m l 等 ( 1 ) k i n n y 定义了一个基于o m t 的b d ia g e n t 系统建模方法“， 他提出了从内部和外部两级建立a g e n t 系统模型的思想。从外部视 角，将系统分解为a g e n t ，按目标、责任、执行的服务、需要维护的 信息和外部的交互来建模目标系统，建立a g e n t 模型和交互模型。从 内部视角，描述b d ia g e n t 体系结构中的必须元素，即信念、愿望和 目标，建立信念模型、目标模型和规划模型。 ( 2 ) b u r m e i s t e r 的“面向a g e n t 的分析和设计”方法“提出了 三个分析a g e n t 系统的模型：a g e n t 模型，组织模型和协作模型。该 方法首先使用一种o o s e 的c r c 卡扩展形式来识别a g e n t 的角色建立 组织模型，并以o m t 表示法描述a g e n t 继承层次和a g e n t 之间的关系。 最后通过识别协作和协调的参与方法j 分析消息类型和使用的协议， 建立协作模型。 ( 3 ) k e n d a l l 提出了一个面向a g e n t 的企业建模方法m 1 ，该方 法结合了o o s e 中u s ec a s e 驱动的方法、企业建模的方法i d e f ( i n t e g r a t i o n d e f i n i t i o nf o rf u n c t i o n m o d e l i n g ) 和c i m o s a ( c o m p u t e ri n t r g r a t e dm a n u f a c t u r i n go p e ns y s t e ma r c h i t e c t u r e ) 技术。该方法首先使用i d e f o 图描述系统的功能( 包括输入、输出机 制和控制) ，然后建立u s ec a s e 模型，分析对象之间的交互。然后进 行面向a g e n t 系统的构造，任务包括：识别a g e n t ，使用状态图描述 协同协议或脚本，使用顺序图来扩展事件跟踪图，描述规划调用等。 1 2 2 基于k e 方法的扩展 当前k e 方法的扩展主要是是基于c o m m o n k a d s 的扩展。 c o m m a n d k a d s 是一种用于开发基于知识的系统( k b s ) 的软件工程方 法，它被视为欧洲的知识建模标准。 ( 1 ) i g l i s i a s 等的m a s c o m m o n k a d s “3 3 方法不仅扩展了 c o m m o n k a d s 定义的模型，并结合了一些0 0 方法中的技术( 包括o o s e 、 o m t ) ，以及协议工程和m s c 9 6 中的技术。该方法首先是一个概化阶段， 利用o o s e 中的用例技术获取系统的需求。在其后的分析和设计阶段， 主要任务是建立7 个模型，即a g e n t 模型，任务模型，专家知识模型， 协作模型，组织模型，通信模型，设计模型。 ( 2 ) m e s s a g e 是由欧洲电信组织的p 9 0 7 项目中提出的一种面向 a g e n t 的、旨在支持整个软件生命周期的方法 m e s s a g e 该方法在很 多方面借鉴了 i a s - - c o m m o n k a d s 方法中的内容。m e s s a g e 分析阶段的 模型包括5 个模型：a g e n t 模型，组织模型，目标任务模型、领域 模型和交互模型。该方法具体地定义了如何构造这些分析模型的工作 流，以及不同模型之间相互关联的方式。 1 2 3 面向a g e n t 的方法和技术 g a i a 方法是最早提出的、纯面向a g e n t 的方法之一，其主要思 想是将分析和设计m a s 看作是构建一个计算组织的过程。该方法将 m a s 看作是由大量自治、交互的实体组成一个有组织的社会。在分析 阶段，该方法建立角色模型、交互模型。角色模型由一组使用f u s i o n 表示法表示的“角色模式”( r o l es c h e m a ) 构成，描述每个角色的责 任( 即角色的功能) 和权限( 在执行该角色时能使用的资源类型及数 量) 。交互模型是一组协议定义组成。协议的内容包括：目的、发起 者、响应者、协议的输入输出、以及处理过程简述。该g i g a 的设计 阶段，任务是建立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 计算模型，如k o z e a 的模态演算，l a m p o r t 的t l a l ( t e m p o r a ll o g i c o fa c t i o o u s ) ；基于进程代数方法的a g e n t 计算模型，如c c s 、c s p 、 a c p ，i 0 自动机、a c t o r 等。根据m a s 的特点，a g e n t 的计算模型从 串行计算向并行计算转换。由此，本文进行大胆的尝试，利用二分图 的基本理论来构建多a g e n t 并行计算模型。 1 3 本文的研究目标及内容安排 本文利用多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 并行汁弹模型驶j i f 衄 第二章构建多a g e n t 并行模型的理论基础 21 引言 目前人们用于构建多a g e n t 并行理论的基础主要是：文献 1 8 在 基于i n t e r n e t 的环境下，把a g e n t 技术引入到并行计算来，提出了 基于i n t e r n e t 的并行计算模型，提供了一种使用大量的分散的计算 资源来进行大规模的、复杂的计算的方法。文献 1 9 提出了一种基于 多a g e n t 的分布式计算模型，研究了模型中的各a g e n t 的功能及它们 之间的协调关系，但该模型缺乏通用性。文献 2 0 用移动代理实现并 行计算，由于移动代理的自治性、移动性、可扩展性可进一步提高计 算性能。文献 1 8 、 2 0 都是充分利用空闲资源，但对系统的如何运 作及a g e n t 之间的了解并没有涉及到，只是从a g e n t 的概念和角度出 发，针对这些问题，本课题借助二分图的思想，将多个a g e n t 组织起 来，真正达到多个a g e n t 并行的解决问题。 二分图最初是解决这样的实际问题的：某公司有工作人员x 。， x 。，x 。，他们去做工作y ，y ：，y 。，每人适合做其中的一项或 几项工作? 问能否每人能分配一项合适的工作? 如果不能，最多几人 可以得到合适的工作? 试给出此分工问题的算法。由解决此问题我们 就联系到多a g e n t 并行问题，如果能让每个a g e n t 都能找到合适自己 的任务，并且多个a g e n t 只执行一个任务，达到最大化的并行。在每 次接受任务之前先让任务分配最优化，然后再执行任务。 2 2 二分图的基本概念n ” 坠翌生堕唑盟塑燮 2 2 1 二分图 如果图中的结点集合v = x u y ，x n y = a ，且图中的每条边均为 【x ，y ，其中，x x ，y y ，卿j 该图称为二分图，记作 ，其中，表示边集合。 令x ： l ，2 ，n ，在二分图 中定义 a = y iy y ，【i ，y 】a o i n ) ， 则可将二分图与集族联系起来。 图1 例如，设x ：( 1 ，2 ，3 ，4 ，y = ( y ，y 。，y a ，y 一，y s ) 则图1 所示的 二分图 关联的集旗 a ，a z ，a 。，a a ) 为 a = ( y ；，y 。) 儿= y ，y 。) a ：i = y ：，y 。，y 一) a 。= y ，y 2 ，y y 。，y 5 ) 该集族的相异代表系y 。，y 。，y 。，y s 关联的4 条边 1 ，y 。 ， 2 ，y 。 ， 3 ，y ， ， 4 ，y d 没有公共结点。 2 2 2 二分图匹配 在二分图 的某个边集合 ( x y 】，【x y 。：】，【x y 】) 种多a g e n t ， 行汁算模型发j e j 训1 1 中，如果x x ，x 。及y0 y i ，y 。都是两两互不相 同的，则称它是该二分图的一个匹配。 2 2 3 覆盖 在二分图 中，如果结点集合s c x u y ，使得中的每 条边至少有一个结点在其中，则称s 是的一个覆盖。例如，图l 中， 1 ，2 ，3 ，4 ) ， 3 ，4 ，y 。，y 。，y 。) 都是的覆盖。 2 2 4 相关事实和定理 令x = l ，2 ，n ) ，二分图 关联的集族为( a 。，a ：， a ) 则有以下事实： ( 1 ) 若 【i ，y 。， ， iz ，y 。：】 - “。，y 。”是二分图的一 个匹配，则y y ，y ，、是集族a a 一，a ，。的一个相 异代表系； ( 2 ) a ，a 。，a n 有相异代表系，当且仅当二分图有一个n 边的匹配( 称为完全匹配) ； ( 3 ) a 。，a ：，a 。) 有相异代表系的最大子集数等于二分图的 最大匹配边数。 定理：设 是一个二分图，它的匹配的最大边数等于覆 盖的最小结点数。 证明：令m 是二分图 具有最大边数的匹配，其边数为 q ，令s 是具有最小结点数的覆盖，其结点数为1 3 。因为m 中没有 两边是公若结点，并且m 中的a 条边每边至少有一个结点在s 中，所 以q 1 3 。 种多a g e n t 并行计算模型技j c 心h 设x = l ，2 ，1 1 ，n 所关联的集族 a 。，a 。，a 。 有相异代表系的最大子集数等于 的最大匹配数q 。由推论 集族 a 。，a 。，a 。) 有相异代表系的最大子集数等于 1a i u 彳j ，u u af 。l + ( 玎一k ) 的最小值，其中，k - - - - - 1 ，2 ，n ，以及所有选择i 。，i ：，i 。( 1 i 。 i2 ( i 。n ) 知，必定有整数k ( 1 k n ) i 并且选择i ，i 。， i 。( 1 i 。 i ： i 。n ) ，使得 1 i a “u 么f ：u u4 “l + ( 珂一k ) 现考虑结点集合 t2 fa f 。u a i2 u ua i 。fu ( x 一( i ，i ：，i 。 ) 任取中一条边 x ，y ，如果x i ，i ：，i 。) ，即存在1 4 1 k ，使得x 2 i t ，那么y ai ，于是y t ；如果 x x 一 i ，i ：，i 。) ，则x t 。又 i 丁1 = ia ua i ：u u4j 。1 + lx 一 i ，i ：，f 。) i 2 ia f u 4 f ：u u 彳j 。l + ( ，2 一k ) = 口 从而t 是的具有q 个结点的覆盖。而b 是覆盖的最小结点数，显 然b a 。 综合以上分析，知a 2 9 。 2 3 相关并行计算模型公约 公约一：多a g e n t 的并行计算是指多个a g e n t 同时处理不同问题 或同一个问题的不同部分； 例1 假定问题p ( n ，n 。，n 。n ，) 由4 个部分组成，并且各部 一种多a g e n t 并行计算摸型驶j e 用 分是相互相容的，为了提高求解问题的能力，可以由4 个a g e n t 同时 求解，用a g i p ( n 。) ，a g ：l p ( n 。) ，a 9 3 l p ( n 。) ，a g 。| 一p ( n 。) ，最 后把所有求解结果归并：( a g 。，a g 。，a g 。，a g 。) j p ( n 。，n z ，n ”n 4 ) ， 这样在相同的一段时间内问题p 就解决了，从而缩短了问题求解的时 间。 公约二：并行计算模型是用来描述多个个体a g e n t 如何以同步的 方式进行问题求解的。 例2 上例中的4 个a g e n t 同步求解问题p ( n 。，n 。，n 。，n 一) 。 公约三：多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 ) 将a g e n t 从传统的“客户”和“服务器”两种固定角色中解 放出来。 ( 2 ) 将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 的模型可用一个五元组 表示：即a g = b ，d ，i ，p ，a ) ，其中b 表示a g e n t 的信念，是a g e n t 解决问题的依据；d 表示a g e n t 的愿望，是解决问题的动力；i 表示 种多a g e n t 并行计尊模型驶1 0 j 虹川 a g e n t 的意图，按照某种规划设定解决问题的行为或行动；p 表示问 题；a 表示a g e n t 的b d i 对应求解问题的知识库。他们都由一系列状 态组成，b - - - - b ；) ，d - - - - d ； ，i = i ； ，i = l ，2 ，n 。p _ - - p j ) ，j = l ，2 ， m ，p j = ( n ，n 。，n k ) ，a 可能对应b 、d 、i 一个要素，也可能对 应b 、d 、i 二个要素或三个要素，一般情况对应三个要素形成的知识 库。 2 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 只能对一个问题进行求解。 多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 的研究中，其中以b d i 模型的研究最为典型，那我们就 以b d i 模型为a g e n t 计算模型的研究基础，约定：a g e n t s ( a g 。，a g 。， 一种多a g e n t 并 ：计算模型及l e 心用 a g ) 表示一组a g e n t ，k l ( k l ，k 1 2 ，k l ，) 表示a g e n t 的知识库。 2 4 1 多a g e n t 关系图 多a g e n t 关系图表示为： ，其中，表示a g ， a g e n t s 和k l 。k l 之间的关联。 多a g e n t 之间，除了a g e n t 与知识库之间的关联以外，多个a g e n t 还存在多种关联。我们应充分挖掘他们之间的这种关联问题，以便更 好地实现问题求解目的。下面我们就以a g e n t 的b d i 进行研究，从多 方面考虑它们之间的关联问题。 我们约定：每个a g e n t 用a g 。( b ，d 。，i 。，p ；，a ；) 表示，其中的 每一个b ，d 。i ；，p ；，a ；都是以一维数组的形式表示。对于某个a g 。 来说，b x d i 表示：每个a g e n t 都根据自己的信念和愿望形成自己 的意图，也就是形成自己的行动规划。在这个过程中，a g ，要调用知 识库中的知识。在多个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 s 之间的冲突，减少资源的浪费，在进行问题求解时，应该找 到更多的共同点，我们就可以借助a g e n t 之间的关系。利用数学工具 描述a g e n t 找其最大共性的过程。 多个a g e n t s 的信念组用( b ，b 。) 表示，这样就组成了 一个矩阵，可以用矩阵求其共同的信念，那表示为： 种多a g e n t 并行i t s ：模型及j 0 心用 。7 = c b ，b ：，b 。户c 至。曼： ! 曼，。 f ，d 。；d 。：d ，。、 。，：( 。，】) ：，】) 。) 。= = l 曼：- 曼： ： 曼：n j l d m d m 。：d m m 。， 一种多a g e n t 并行计算模型驶j e 心用 在形成最大的信念矩阵和共同愿望后，利用b 。d c i 这个公 式，形成新的意图，每一个愿望形成一个新的意图，然后将意图送 给a g e n t s 小组的每个成员，然后对问题进行求解。 b 。d 。= ( b ：b ；b ：) ( d ：d ；d ：) f ，( b ：b ；b ：) 一l ( b b 一- b ：) 。 l ( b ?b i b ：) d d d 令a g e n t s = 1 ，2 ，n ) ，在多a g e n t 关系图 中定义 a = k l ik l k l ，【i ，k t 】) ( 1i n ) ， 则可将a g e n t 与知识库关联起来。 2 4 3 多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 k li 】，【a g k l i ，】，【a g i 。，k l i 、】) 中，如果a g a g 一，a g i 及k i k i ，k i 都是两 两互不相同的，则称多a g e n t 的一个并行计算模型，记为a ( a ，a 矿一， a 。) 并行策略及其分类：从a g e n t 的思维状态看，每个a g e n t 都有自 3 9 、l，l、 c l c 2 c n 11 一 1 ，。，。l i i 一、l，；ll， 一种多a g c n t 并行汁算模型技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 + 的协作是为了解决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 并行模型，尽量避免调用时冲 突，另外也可以充分利用资源。 例如：4 个a g e n t ，( a g 。，a g ：，a g 。，a g 。) 去完成5 个任务( t 。， t ：，t 。，t 。，l ) 。每完成一个任务，对应一个k 1 。如何能保证a g e n t 最大的并行化，我们就可以寻求a g e n t 的最大并行模型。假设a g ，能 完成t 。，t 。，t 4 ，r ；a g ：能完成任务t ，r ，t 4 ；a g 。能完成t ：，t 4 ；a g 。 能完成t 。，t 。，t 3 ，l 。我们就可以利用下面的求多a g e n t 并行计算 模型的最大匹配来解决这个问题。 2 4 4 利用匈牙利算法求多a g e n t 的并行计算模型他2 3 算法：设 是一个多a g e n t 关系图，其中，a g e n t s = a g ，a g 矿一，a g ，y = k 1 ，k l 。，k 1 。m 是该关系图的一个匹 配。 首先用( 爿c ) 标记a g e n t s 中所有与m 中的边不相关联的结点，接 一种多a g e n t 并行h 算艇型及j 0 脚用 下去反复执行下面两步，直到不能进一步标记为止： 第一步，对于所有的最新标记的结点a g ；，经由不在m 中的边， 用( a g ；) 标记该边关联的所有k l 中的结点。如果该结点已被标记，则 不再重新标记。 第二步，对于所有最新标记的结点k l ；，经由在m 中的边，用( k l ；) 标记该关联的所有x 中的结点。如果该结点已被标记，则不再重新标 记。 所谓不能进一步标记，有如下两种情况： ( 1 ) 在第二步中，存在最新标记的结点不与m 中的任何边相关 联，这时叫做第二步结束。此时，从该结点开始，通过标记回朔到标 记为( 木) 的a g e n t s 中结点，得到一条关于匹配m 的交错链r 。用r 中不在m 中的边代替r 中在m 中的边，再加上不在r 中的m 中的边， 构成新的匹配m7 。显然，m7 比i d 的边数多l 。用m7 重新执行算法。 ( 2 ) 在笫一步中，所有新标记的结点或者不关联非m 的边，或者 经由不在m 中的边所关联的k l 中的结点均己被标记，这时叫做第一 步结束。此时，匹配m 是多a g e n t 关系图具有最大边数的匹配。 利用这个算法，上例的问题就可以解决了，a g 。完成任务t 5 ，a g ： 完成任务l ，a g 。完成任务t ：，a 昏完成任务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 并行计算模型及j l 随 j 知识库，它就不能执行任务，这样就造成资源的浪费。我们采用的方 法是重新在接收任务来解决此问题。 2 4 5 多a g e n t 并行计算模型的相关