（计算机软件与理论专业论文）基于相似度的协商策略机制研究.pdf

郑州大学硕士学位论文 摘要 双边系统的协商策略机制是目前m a s ( m u l t i a g e n ts y s t e m ) 研究的重要方向。 协商策略研究关注的一个重要方面，就是协商中的动态因素和不确定因素。这方 面的研究包括：基于博弈论的研究、基于启发式方法的研究和基于争论的研究。 在基于启发式方法的研究中，针对协商议题动态性，j e n n i n g s 等指出，由于 议题的动态变化导致协商问题空间的变化，在协商中允许议题的动态变化给提议 生成策略机制的设计带来了很大难度，f a r a t i n 等将议题集合处理机制引入到提议 生成策略机制中，并提出了一种建立在m e t a 策略上的折衷机制，在他们的策 略机制中，允许议题的动态变化，但是他们的折衷算法并不能很好地适应议题动 态变化。 本文详细分析了m a s 中多议题协商过程，简要介绍了协商的概念，对协商 各个不同的类型进行了详细地介绍。并针对协商过程中的动态性、不确定性进行 了单独论述。 本文研究在双边多议题协商中，协商双方在信念不完全、协商时间有限的情 况下，如何既保证a g e n t 的联合效用和协商时间，又能够适应协商中的议题动态 变化。为了实现上述目标，本文提出了一个通用的双边多议题协商模型 b l m i n m ( b i l a t e r a lm u l t i i s s u en e g o t i a t i o nm o d e l ) ，然后基于多属性效用理论提 出了一个双边多议题协商的效用评估决策机制，并利用协商各议题效用的相关性 对现有的基于相似度的折衷算法进行了扩展。该策略机制和折衷算法在保证协商 参与者整合效用接近p a r e t o 最优、协商时间没有延长的前提下，允许动态调整协 商中的议题集合，并结合具体的实验表明了该机制对议题动态变化的良好适应能 力。 另外，本文研究了现有的基于遗传算法的提议生成策略，针对其基于欧几里 德的适应度函数的局限性，基于相似度理论提出了一个新的适应度函数，提出了 一个改进后的提议生成策略机制g a s ( g e n e t i c a l g o r i t h ms t r a t e g y ) ，实验表明，改 进后的算法在有非线性效用函数存在时，在协商成功时间和双方联合收益方面都 比原算法好，算法的稳定性也通过对比实验进行了分析。 关键词：协商；多a g e n t 系统；多议题协商；策略机制；折衷算法；遗传算法 郑州大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，b i l a t e r a ln e g o t i a t i o ns t r a t e g ym e c h a n i s mi sa ni m p o r t a n ta r e ai nt h e p r a c t i c a lr e s e a r c ho nm a s ( m u l t i a g e n ts y s t e m ) i nt h er e s e a r c h o nn e g o t i a t i o n s t r a t e g y , d y n a m i c sa n du n c e r t a i n t i e s a r ei m p o r t a n ti s s u e s i nt h el i t e r a t u r eo f n e g o t i a t i o ns t r a t e g y , t h e r ea r et h r e em a i nr e s e a r c hm e t h o d s ，k n o w na sg a m et h e o r y , h e u r i s t i ca p p r o a c ha n da r g u m e n t a t i o nb a s e dn e g o t i a t i o n i nt h er e s e a r c ho fh e u r i s t i ca p p r o a c h ，j e n n i n g se ta 1 p o i n t e do u ti tw o u l db r i n ga 1 0 to fd i f f i c u l ti n t ot h ed e s i g no fn e g o t i a t i o ns t r a t e g ym e c h a n i s mt oi n t r o d u c ei s s u e d y n a m i c si n t on e g o t i a t i o nb e c a u s e i tw o u l dr e s u l ti nt h ec h a n g e so fc o n t r a c ts p a c e t o s o l v et h i sp r o b l e m ，f a r a t i ne ta 1 i n t r o d u c e di s s u em a n i p u l a t i o nm e c h a n i s mi n t ot h e p r o p o s a lg e n e r a t i o ns t r a t e g ym e c h a n i s ma n dp u t f o r t hat r a d e o f fm e c h a n i s mb a s e do n f u z z ys i m i l a r i t yt h e o r yw i t ht h es u p p o r to fm e t as t r a t e g y i nt h e i rr e s e a r c h ，i s s u e d y n a m i c sa r ea l l o w e d ，b u tt h e r ea r es o m ep r o b l e m s i nt h e i rt r a d e o f fa l g o r i t h m t h en e g o t i a t i o np r o c e s so fm a si sd e t a i l e d ，t h ec o n c e p to fn e g o t i a t i o ni s d e p i c t e da n dt y p e so fn e g o t i a t i o na r ed e t a i l e di nt h i sp a p e r a l s o ，t h ed y n a m i c sa n d u n c e r t a i n t i e sa r ed e t a i l e ds e p a r a t e l y t h i sp a p e rf o c u s e so nh o wt og u a r a n t e et h ej o i n tg a i na n dt h en e g o t i a t i o nt i m e u n d e rab i l a t e r a ln e g o t i a t i o nb a c k g r o u n dw h i c hi n c o r p o r a t e st h ef o l l o w i n gp r o p e r t i e s ： i n c o m p l e t ei n f o r m a t i o n ，l i m i t e dn e g o t i a t i o n t i m ea n di s s u es e tc a nc h a n g e d y n a m i c a l l y t oa c h i e v ei t ，ag e n e r i cb i l a t e r a l m u l t i i s s u en e g o t i a t i o nm o d e li s p r o p o s e da tf i r s t ，t h e na b i l a t e r a lm u l t i i s s u en e g o t i a t i o nu t i l i t ye v a l u a t i o nm e c h a n i s m b a s e do nm u l t i ：a t t r i b u t eu t i l i t yt h e o r yi sp u tf o r t ha n dt h et r a d e - o f fa l g o r i t h mb a s e do n f u z z ys i m i l a r i t yi se x t e n d e da c c o r d i n g t ot h er e l a t i o n sb e t w e e ni s s u e s i na d d i t i o n ，ag a ( g e n e t i ca l g o r i t h m ) b a s e dp r o p o s a lg e n e r a t i o ns t r a t e g y i s a n a l y z e d ，i nw h i c ht h el i m i t so nt h ew e i g h t e de u c l i d e a nd i s t a n c e s o ft h ef i t n e s s f u n c t i o na r ep o i n t e do u t t or e m o v et h e s el i m i t s ，a ni m p r o v e dg ab a s e dp r o p o s a l g e n e r a t i o ns t r a t e g yg a s ( g e n e t i ca l g o r i t h ms t r a t e g y ) i sp r o p o s e d t h ee x p e r i m e n t s i i 塑! ! ! 查兰塑圭兰堡堡苎 s h o wt h a tt h ei m p r o v e dg e n e t i ca l g o r i t h mg a i ( g e n e t i c a l g o r i t h mi m p r o v e d ) c a l l g i v ea1 ) e t t e rp 髓f o 蚰撇o v e rn o n - l i n eu t i l i t yr u n d o n s t h e s t a b i l i t yo ft h e a l g o r i t h m si sa n a l y z e db ye x p e r i m e n t s k e y w o r d ：m u l t i - a g e n ts y s t e m , m u l t i - i s s u en e g o t i a t i o n , s t r a t e g ym e c h a n i s m , t r a d e - o f f , a l g o r i t h m , g e n e t i c a l g o r i t h m 1 1 1 郑州大学硕士学位论文 1 1 研究背景 第一章绪论 计算机技术自出现以来，发展日新月异当前，计算机作为一种快捷、有效 的辅助工具，在军事、航天、电信、金融、商业等领域己经得到了广泛应用。这 种应用是深刻的、卓有成效的，促进了整个社会的跨越式进步，带领人类进入信 息时代。计算机在诞生初期，仅用来完成简单、重复的数学运算，并且应用范围 也局限于军事和电信领域，短短几十年间，计算机无论从运算速度，运算质量方 面都得到了飞跃式的提升，应用范围也已经渗透到了人类生活的方方面面，可以 毫不夸张地说，在二十一世纪，不懂计算机就等于半个文盲。 在计算机技术的广泛应用过程中，用户对这种工具要求也在不断提高。各种 各样需求的不断增加，刺激并促进计算机技术的飞速发展，同时也推动了计算机 科学向智能化、实用化、多元化延伸。 在目前信息化和全球经济竞争日益激烈的情况下，依托高度发达的计算机技 术，企业级电子商务己经蓬勃发展起来，并且成为现代商业的一个显著特点。随 着电子商务【1 , 2 , 3 1 的飞速发展，商品交易种类、交易量的急速增长，以及业务涉及 者对交易的发生时间、地点等多种因素越来越高的要求，商业中传统的谈判模式 逐渐不能适应交往日趋频繁的商业发展。正是在这个广阔的应用背景下，在线谈 判已经逐步发展成为电子商务过程的重要组成部分。通过网络进行洽谈和交易的 商务活动虽然给供应商带来了无限的商机和利润，但是对于每一位客户，供求双 方都必须花费人力和时间协商之后才能最终签订协议。当交易涉及的客户群体数 量达到一定规模时，供求双方进行网上谈判的开销也随之成倍增加。 在这种背景下，使用a g e n t 实现自动或半自动的协商和谈判【4 5 】，将大大提高 远程商务的运作效率。a g e n t 协商可以充分利用计算机技术的快捷性、准确性和 智能性，减少了商业谈判在时间、地点、环境等方面的投入。 1 2 研究现状 双边系统的协商策略机制是目前m a s ( m u l t i - a g e n ts y s t e m ) 研究的重要方向。 郑州大学硕士学位论文 协商策略1 6 】研究关注的一个重要方面，就是协商中的动态因素、不确定因素等。 这方面的研究包括：基于博弈论【7 j ，9 ，埘的研究、基于启发式方法 1 1 , 1 2 , 1 3 , 1 4 的研究 和基于争论 i s j 6 , 1 7 】的研究。 基于博弈论的研究将协商交互过程看作一种博弈，它从博弈论的角度分析协 商过程，从而寻找最优策略和n a s h 均衡 1 8 j 9 1 ，它以v o nn e u m a n n 2 0 ( 1 9 4 4 ) 的效 用理论为基础，研究二人或多人情况下的零和和一般和对策。在6 0 年代初，博 弈论风靡全球，7 0 年代中期以后，博弈论的研究逐渐突破传统博弈论偏重完备 知识、单调、n a s h 均衡的方法，向多步对策、重复对策方向转移，以求利用交 互的历史信息，弥补知识的不完备，这成为当前博弈论研究的热点。 基于博弈论的研究其优点在于可以获得良好的计算结果，很多研究都可以保 证p a r c t oo p t i m a l t l 2 1 、n a s h 均衡【1 8 , 1 9 ，然而，基于博弈论的研究往往在计算理性 和计算能力方面设置一些不合理的假设【2 1 1 。具体来讲，大多数此类方法假设 a g 铋t 有无限的计算资源并且a g e n t 具有个体理性但是，在现实中，a g e n t 可 能是资源有限的、自私的、恶毒的、甚至是编码较差的，所以a g e n t 可能不能遵 循个体理性瞄】这一限制。 基于启发式方法的研究针对博弈论的缺点展开，该方法重视计算和决策的代 价，它利用启发式信息以非完全的方式搜索协商空间，该方法致力于找到“好的 解”，而非“最优解”，启发式方法在计算性上与对策论相似，是非形式化协商模 型的计算实现。对特定启发式方法的评估主要是基于经验评估和实验证明1 2 2 3 】。 基于启发式方法的协商在应对现实中的大状态空间、状态空问改变等问题时，比 基于博弈论的研究表现好，近年来，该方法受到了研究者广泛的关注。如f a r a t i n 等 1 2 ，2 4 ( 2 0 0 0 ，1 9 9 7 ) 基于多属性效用理论给出了各种用来评估和产生提议的启 发式决策函数。f a r a t i n 等人【2 5 】( 2 0 0 2 ) 给出了一个用来寻找可替换提议的折衷算 法k o w a l c z y k 和b u i 【1 3 ( 2 0 0 1 ) 基于分布式约束满足问题提出了一个协商模型， 该模型后来被r a i l w 锄等人 2 6 ( 2 0 0 2 ) 扩展以支持多方并发协商和模糊约束。l u o 等人 2 7 ( 2 0 0 3 ) 后来又对模糊约束满足进行了深入研究。虽然启发式方法确实克 服了博弈论方法面临的一些困难，该方法也有其局限性脚1 。一方面，该方法由 于采用的是个体理性的近似形式或者对合同空间进行非全局搜索，它所找到的合 同往往是子最优的，另一方面，在该方法中，精确预测a g e n t 的行为很困难，这 郑，l 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 的智能化程度要求也较高，现实中的研 究还停留在相对简单的层面。 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 的联合效用和协商时间，又能够 适应协商中的议题动态变化。为此，本文从协商协议、协商策略机制、折衷算法 等角度进行了一系列的研究。本文首先提出了一个通用的双边多议题协商模型 b l m i n m ( b i l a t e r a lm u l t i i s s u en e g o t i a t i o nm o d e l ) ，然后基于多属性效用理论【 】 提出了一个双边多议题协商的效用评估决策机制，并利用协商各议题效用的相关 性对现有的基于相似度【纠的折衷算法【i 硼进行了扩展。该策略机制和折衷算法在 允许动态调整协商中的议题集合的前提下，不仅无需重启协商，而且保证协商参 与者整合效用接近p a t i o 最优、协商时间没有延长。最后本文通过具体的实验展 示了该机制对议题动态变化的良好适应能力。 另外，本文研究了现有的基于遗传算法的提议生成策科2 9 l ，针对其基于欧几 里德计算适应度函数的局限性，基于相似度理论提出了一个新的适应度函数，提 出了一个改进后的提议生成策略机制g a s ( g e n e t i ca l g o r i t h ms t r a t e g y ) ，实验表 明，改进后的算法在有非线性效用函数存在时，在协商成功时间和双方联合收益 方面都比原算法好，算法的稳定性也通过对比实验进行了分析。 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 协商过程研究 简要介绍了几种得到广泛认可的协商概念，并对协商研究的内容与形式 4 郑州大学硕士学位论文 进行了系统的介绍。 第四章基于相似度和议题动态特性的协商策略 在本章中，给出了相似度的概念，并针对协商中议题集合动态变化，从 协商协议、协商策略机制设计、折衷算法这几个方面对现有的研究进行了扩 展和改进。最后，结合具体的实验说明了所做工作的有效性。 第五章基于相似度和遗传算法的协商研究 本章首先提出了一个双边多议题协商模型b l m i n m f g a ( b i l a t e r a l m u l t i i s s u en e g o t i a t i o nm o d e lf o ro a ) ，然后基于多属性效用理论【1 3 】提出了一 个新的双边多议题协商效用评估决策机制，并利用协商各议题效用的相关性 和相似度理论闭改进了现有的g a 【2 9 1 。最后，结合具体的对比实验说明了改 进的有效性，并将p c ( p r o p o s a lg e n e r a t i n g ) 机制与g a s ( g e n e t i ca l g o r i t h m s t r a t e g y ) 机制进行了对比实验，分析了两者在稳定性方面的差异。 第六章总结与展望 对本文进行总结，提出了下一步需要进行的工作。 邦州大学硕士学位论文 第二章a g e n t 技术分析 二十世纪七十年代，a g e n t 的概念起源于人工智能学科，此后的几十年间， 得到了深入地研究。随着信息技术在人类社会应用的臼益普及，特别是近二十年 来计算机网络的飞速发展，a g e n t 技术e t 益得到科学界、教育界、工业界和娱乐 界的广泛关注。当前，a g e n t 技术已经成为鲇研究乃至整个计算机科学研究的 热点之一。 人工智能的目标是制造出人工的智能机器或系统，模拟人类智能活动以延伸 人类智能。基于a g e n t 的研究，人们将人工智能定义为：“人工智能是计算机科 学的一个分支，它的目的是构造出能表现出一定智能行为的a g e n t ”。斯坦福大 学计算机科学系的h a y o s - r o t h 在i j c a i 9 5 的特邀报告中谈到；“智能的计算机 a g e n t 既是人工智能的最初目标，也是人工智能的最终目标” 可见，无论从应用的价值还是理论的意义方面，a g e n t 作为一个交叉性的学 术领域，正日益受到世人的关注。 2 1a g e n t 的定义 a g e n t 是在人工智能领域里发展起来的一种新型计算模型 3 0 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 的多种不同定义。 c a r lh e w i t t 在 v i e w i n gc o n t r o ls t r u c t u r e sa sp a s s i n gm g 【3 1 ( 1 9 7 7 ) 一 文中提出了并发对象模型( c o n c u r r e n t a c t o r m o d e l ) 的概念，定义了具有自兼容性、 交互性和并发处理机制的对象，称之为“a c t o r ”，这是a g e n t 可追溯的最早概念 起源。 m m i n s k y 出版了 s o c i e t yo fm i n d s 【3 2 ( 1 9 8 6 ) - - 书。这本书将“社会”与 6 郑州大学硕士学位论文 “社会行为”这些概念引入计算，指出个体存在于社会中，社会中的个体在有矛 盾的前提下通过协商或者竞争的方法得到对问题的求解，这些个体被称作 “a g e n t ”。 m i i l s k y 在“c o m m u n i c a t i o no f a c m ”( 1 9 9 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 是能完成一些特定任务的个体，社会不关心它是如何工作的；而对 个体而言，则要求它们具有一定的技能，否则将不为社会所接受。 m w o o l d r i d g e 在“a g e n t - b a s e ds o f t w a r ee n g i n e e r i n g ”( 1 9 9 7 ) 0 0 提出了另一种 观点： 单个a g e n t 是一个封装的计算机体系( e n c a p s u l a t e dc o m p u t e rs y s t e m ) 。它可 以适应周围不断变化的环境，根据外界刺激而采取耜应灵活、自主的( a u t o n o m o u s ) 动作，完成设计者预先设定的目标。 另外，从弱定义和强定义两个角度，学者们也给出了各种各样的定义： 弱定义的a g e n t 需要具有这样的特征： 自主能) b ( a u t o n o m y ) ，a g e n t 可以在没有人或其它a g e n t 直接干预的情况 下运作，而且对自己的行为和内部状态有某种控制能力。 社交能，j ( s o c i a b i l i t y ) ，a g e n t 和其它a g e n t 能够通过某种a g e n t 交流语言 进行交互。 反应能力( r e a c t i v i t y ) ，a g e n t 能够观察其环境( 可能是物理世界、图形世 界、一系列其它a g e n t 、i n t e m e t 等) ，并在一定时间内做出反应，以改变 该环境。 预动能力( p r o - a c t i v e n e s s ) ，a g e n t 不仅能够简单的对环境做出反应，而且 能够通过接受某些启示信息，体现出面向目标的行为。 在强定义方面，一些学者，特别是来自a i 届的研究人员认为，a g e n t 不仅应 该具有以上定义的特性，而且还应具有一些人类才拥有的东西，如：知识、目的、 信念、义务等。另外，以下特征也被研究者关注： 移动性( m o b i l i t y ) ，指a g e n t 可以在信息网络上移动，从一个地方移动到 7 郑州大学硕士学位论文 另一个地方而保持其内部状态不改变。a g e n t 可以携带数据和能够在远 程执行的指令。 真实性( v e r a c i t y ) ，假设a g e n t 不会传输错误信息。 仁慈性( b e n e v o l e n c e ) ，假设a g e n t 没有冲突的目标，因此每个a g e n t 通 常有求必应。 合理性0 h t i o n a l i t y ) ，假设a g e f i t 总是为实现目标而努力，而不阻碍目标 的获得，至少在它的信念中应该如此。 一些学者将具有自主性、交互性及反应性的计算实体称作反应式a g e n t 。d a i 领域的学者则要求a g e n t 具有信念、愿望、意图等认知特性。c s c w 领域的学者 则要求a g e n t 具有更加友好、灵活的人机交互。另外，我们经常讨论的关于a g e n t 的其他属性还有： 长寿性( l o n g e v i t y ) ，传统程序由用户在需要时激活，不需要时或运算结 束后停止。a g e n t 则不然，它应该至少在相当长的时间内连续运行。 推理能力( r e a s o n i n g ) ，a g e n t 可以根据其当前的知识和经验，以理性的、 可再生的方式推理或推测。 规划能力( p l a n n i n g ) ，根据目标、环境等的要求，a g e n t 应至少对自己的 短期行为做出规划。虽然程序设计人员可以提供一些常见情况的处理策 略，但这些策略不可能覆盖a g e n t 将遇到的所有情况。故a g e n t 应该有 生成规划的能力。 学习和适应能力( l e a r n i n ga n da d a p t a b i l i t y ) ，a g e n t 可以根据过去的经验 积累知识，并修改其行为以适应新的环境。 在上述定义中，m i n s k y 从多a g e n t 系统的社会智能角度出发，认为a g e n t 是独立的、具有简单智能的个体，它本身只会做一些特定领域的、不需要思考的 简单事情，但是当我们用某些特定的方法将这些a g e n t 组成一个社会时，就产生 了真正的智能。而w o o l d d d g e 和j e n n i n g s 从a g e n t 在实际系统应用中所应表现 出来的结构性、通用性和智能性方面给出了具体说明。他们的这些观点在a g e n t 研究领域得到了愈来愈多的支持和发展。 郑州大学硕士学位论文 2 2a 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 e l i e fd e s i r ei n t e n t i o nt h o a r y ) 模型最具代表性。这一理论的哲学基础是 b r a t m a n 对理性和意图的分析，b r a t m a n 3 3 1 ( 1 9 8 7 ) ：安1 j 画了意图的客观性以及在理 性平衡中的中心位置。其后，一系列研究者进一步完善了这方面的研究。c o h e n 和l e v e s q u e 3 4 ( 1 9 9 0 ) 基于正规模态逻辑的可能世界模型，定义了a g e n t 信念的 基本性质，并将意图定义为一种持续目标，初步描述了意图在a g e n t 行为中的作 用。r a o 和g e o r g e , 3 5 ( 1 9 9 5 ) 3 彩用计算树逻辑，将可能世界的时间结构由线性扩 充为分支，进一步阐述了b d i 的概念及相互关系k o n o l i g e 和p o l l a c k 3 6 ( 1 9 9 3 ) 提出认知结构和意图关系图的概念，由此定义的意图不仅包含对目标世界的期 待，也包含对不希望的世界状态的描述，在一定程度上解决了副作用问题。在这 些模型的基础上，s h o h a m 3 7 ( 1 9 9 7 ) 从系统实现角度讨论了a g e n t 的结构和行为 特性。提出了面向a g e n t 的程序设计。h a d d a d i 3 8 ( 1 9 9 6 ) 分析了联合承诺，用以 描述合作推理和协商。d u n i n - k e p l i e z 和v e r b r u g g e 3 9 ( 1 9 9 6 ) 也对多a g e n t 的承诺 问题作了探讨，分析了3 种社会承诺机制。c a s t e l f i a e h i 4 0 ( 1 9 9 5 ) i i 从社会行为 角度研究了社会承诺。国内学者在这一领域也作了很多开拓性的工作。1 9 9 8 年， 史忠植【4 l 】等人提出了描述多主体系统的逻辑系统r a o 逻辑。1 9 9 9 年，毛新 军 4 2 】等人提出了一种计算的意愿理论。 这些工作一方面表达了b r a t m a n 对意图和理性的研究，另一方面，从智能系 统的定义、构造和应用等角度对意图和理性的含义进行了阐述。 下面简单介绍一下b d i 理论、b d i 模型和r a o 逻辑。 一、b r a t m a n 的b d l 理论嘲 传统的人工智能一般是针对具体问题由程序安排a g e n t 进行推理、计算的。 这种方法不适合于a g e n t 在开放、动态的环境中保持更强的解决问题的能力。1 9 8 7 年b r a t m a n 从哲学上对行为意图的研究，对人工智能产生了广泛的影响，被公认 9 郑州大学硕士学位论文 为是b d i 理论的基础之一 b r a n i l a n j & 为只有保持信念( b e f i e o 。愿望( d e s i r e ) 和意图( i n t e n ) 的理性平衡 才能有效地解决问题。他认为在开放世界中，理性a g e n t ( r a t i o n a l a g e n t ) 的行为 不能直接由信念、愿望，以及由两者组成的规划驱动，在愿望与规划之间应有一 个基于信念的意图存在。 在开放和分布的环境中，一个眦g e n t 的行为受制于意图。a g e n t 不会无理 由地随意改变自己的意图，也不会坚持不合实际的意图。理性平衡的目的在于使 理性a g e n t 行为符合环境的特性这包含了环境的客观条件，同时也包含环境中 的社会团体因素，如社会团体关于理性行为的判断法则。 另外，b r a t m a n 给出了意图一行为原则：如果a g e n t a 进行行为b 的当前行为 意图是合理的，那么a 把意图首先转化为行为，有意进行的行为b 就是合理的。 在给定时间里，a g e n t 理性表现为： 1 、性能测度规定成功的程度； 2 、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 内部知识的基础上，应该做的所期望的动 作使它的性能测度为最大。 二、r a o 和o e o r g e f l 拘b d l 模型 a r a o 和m g e o r g e f 在b r a t m a n 3 3 ，3 4 ( 1 9 8 7 ，1 9 9 0 ) 等人的前期工作基础上，给 出了一系列相关的研究成果 4 3 ，4 4 ( 1 9 9 1 ，1 9 9 2 ) ，成为a g e n t 理论研究领域最有代 表性的基础工作 4 5 1 。a 黜痢m g e o r g e f 给出了一个b d i t 拘形式化模型，包括： 基础逻辑的定义、信念、愿望和意图，作为模态操作符的描述、这些模态操作符 的可能世界语义的定义、b d i 操作符之间关系定义的公理等。与大多数哲学理论 相比，r a o 和g e o r g e 肥意图作为一类成员，即作为与信念和愿望具有相同地位的 概念。 在该模型中，世界采用时序结构描述，该结构是以未来为分支时间、以过去 为线性的结构，称为时间树。描述这些结构的形式语言是计算树逻辑c t l ，有两 郑州大学硬士学位论文 种公式：状态公式( 考虑在特殊的时间点) 和路径公式( 考虑时间树中的一段路径) 。 一个典型的b d ia g e n t 通常包含4 个主要数据结构： l 、信念集，用于表示a g e n t 的世界模型，其中的信息可能不完全或不正确； 2 、期望或目标( g o a l s ) 集，对应于分配给a g e n t 要执行的任务： 3 、意图集，表示a g e n t 尸, 决定或承诺完成的期望，a g e n t 将持续它对一个意 图的承诺，直到它相信该意图已满足，或由于某些原因该意图不再可能完成0 4 1 ； 4 、规划库，包括一组预定义规划或方法，表示a g c n t 为完成各种意图所遵循 的过程性知识或程序。 三、r a o 逻辑 r a o 逻辑是史忠植研究员等提出的描述多a g e n t 系统的逻辑系统。r a o 逻 辑引入信念操作数、时态操作数、宣称操作数以及a g e n t 名操作数等。该逻辑借 鉴了言语行为理论和情境演算的若干思想，最终目标是能够用一种自然的方式来 描述多a g e n t 系统中关于a g 锄t 状态的推理过程。该研究对于提高a g e n t 的自治性 和主动性具有重要的意义。 综上所述，a g e n t 理论试图解决以下三个问题： l 、什么是a g e n t 7 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 e n t 体系结构研究与其它方面的进展，促进a g e n t 研究的进一步发展。 2 3a g e n t 的体系结构 a g e n t 的体系结构是指构连z 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 匝过传感器感知环境，通过执行器作用于环境。a g e n t 如何与环境进行 交互它如何处理和解释接收的信息，采用何种行动达到自己的目的。从功能应用 角度来讲，研究者对a g e n t 结构的看法已经趋于一致，然而，在a g e n t 的模型结构 郑州大学碗士学位论文 方面仍没有一个统一的标准1 4 6 1 s h o h a m 把a g e n t 的模型结构看作4 个智能构件的组合。他们包括：信念 ( b e l i e f s ) 、能力( c a p a b i l i t i 哟、选择( c h o i c e s ) 和责任( c o m m i t m e n t s ) 。其中，b e l i e f s 是a g e n t 主观和客观世界所具有的信念，c a p a b i l i t i e s 是a g e n t 对信息和知识的响应 及处理能力，c h o i c e s 是a g e n t g q 行动方案的选择和执行，c o m m i t m e n t s 贝l j 描述了 a g c n t 对其它a 鲫t 所承担的责任和义纠3 0 】。 国内的史忠植 4 1 ( 1 9 9 8 ) 和王怀l 毛 4 2 ( 1 9 9 8 ) 等人从结构的角度，将a g e n t 分成 三类：慎思型a g e n t ( d e l i b e r a t i v ea g e n t ) 、反应型a g e n t ( r e a c t i v ea g e n t ) 和混合型 a g e n t 。 一、 慎思型a g e n t ( d e l i b e r a t i v e a g e n t ) w o o l d r i d g e f 铂j e n n i n g s 将慎思型a g e n t 定义为：“慎思型a g e n t 既是包含世界显 式表示的模型，又是符号的模型，并且其决策是通过基于模式匹配和符号操作的 逻辑推理实现。”慎思型a g e n v g , 须具有主体应有的意识状态( m e n t a ls t a t e ) ，如 信念、期望、意图、承诺等这种结构是一个显式的符号模型结构，具有环境和 智能行为的逻辑推理能力。它源于符号人工智能，是一种基于知识的系统。图2 1 所示为慎思型a g e n t 的体系结构图，其中环境模型一般是预先实现的，形成主要 的部件知识库。a g e n t i i l 过传感器接收外界环境的信息，根据内部状态形成对世 界的认识，产生修改当前状态的描述。然后，在知识库的支持下制定行动规划， 进而在目标的驱动下产生系列动作指令，通过执行机构对环境发生作用。 图2 1 慎思型a g e n t 郑州大学硕士学位论文 慎思型a g e n t 主体的结构框架可用伪码描述如下： c l a s sd e l i b e r a t e - a g e n t p r i v a t e ：e n v i r o n m e n t ；严描述当前世界环境4 k b ；知识库吖 p u b l i c ：。 a c t i o nm a i n - o p e r a t i o n ( p e r o e p t ) 严p e r c e p t 表示传感器感知+ e n v i r o n m e n t = u p d a t e - w o r l d - m o d e l