（控制科学与工程专业论文）基于模糊理论的双边多议题协商相关技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 双边协商策略机制是目前多智能体( m u l t i a g e n ts y s t e m ，m a s ) 研究的重要方 向。本文在充分调研自动协商相关理论与技术的基础上，针对m a s 自动协商技术 中的自动协商模型和提议产生策略展开了研究。 首先，简要介绍了m a s 中的自动协商基本概念、类型和协商结果的衡量标准， 详细分析了双边多议题自动协商系统的特性、参数和通信语言。 然后，提出了一种包含定性议题的双边多议题多a g e n t 系统自动协商模型： 改进的m m a n ，给出了其形式化描述，并仔细设计和讨论了模型中所涉及的议题 表达、效用评价机制、协商协议、a g e n t 描述、时间依赖的提议生成策略等内容。 相比于现有的研究，改进的m m a n 模型能够利用模糊集合更好地处理协商中的定 性议题。利用模糊集合的贴近度概念，定义了合理的定性议题效用函数，将定性 议题和定量问题置于一致的整合效用评估框架之内。设计了定性议题的时间依赖 的提议生成策略，使得改进的m m a n 模型不仅能处理定量议题，而且能处理定性 议题，具备更强的实用性。还修正了现有研究的效用评价中，议题效用值未能归 一化的错误，使得在计算整合效用时，议题的权重能真正发挥其作用。 随后，利用模糊逻辑系统作为逼近器，选择算法简单、计算量小的最近邻学 习算法同时对该系统进行参数和结构自适应调整，以得到最优解。在利用仿真手 段验证其精度水平的基础上，采用这种逼近器利用当前协商周期内对手a g e n t 的 提议值历史数据，对其时间依赖提议产生函数进行在线学习，来预测对手在未来 时刻的提议值，并据此对a g e n t 协商中的提议产生策略进行了修正，以保证既能 较快地达成协作，又能很好地兼顾协商双方各自的利益，实现“双赢的目标。 最后，利用j a v a 语言在e c l i p s e 平台下设计实现了一个实验系统b m n s ( 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 ns y s t e m ) ，并对所提提议生成策略的有效性进行了验证。实验 结果表明，算法对于加快双边协商进程、改善协商具有重要作用。 主题词：多智能体系统自动协商双边多议题协商模型提议生成策略 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t s t r a t e g ym e c h a n i s mp l a y sa l li m p o r t a n tr o l ei nb i l a t e r a ln e g o t i a t i o n , w h i c hi so n e o ft h em o s ta c t i v ea r e a si nr e s e a r c ho fm u l t i a g e n ts y s t e m b a s e do nt h es t a t u sq u oo f a u t o m a t e dn e g o t i a t i o nr e l a t e dt h e o r e ma n dt e c h n i q u e s ，t h em o d e lo fa u t o m a t e d n e g o t i a t i o na n ds t r a t e g yo fp r o p o s a lg e n e r a t i o na r es t u d i e di nt h i st h e s i s f i r s t l y ，ab i l a t e r a lm u l t i - i s s u em o d e lo fm u l t i a g e n ts y s t e mn e g o t i a t i o n ( r e v i s e d m m a n ) i sp r o p o s e da n dt h ed e t a i l e df o r m a l i z a t i o ni sd e s c r i b e d m o r e o v e r , m a n y c r i t i c a lp a r t si nr e v i s e dm m a na r ed e s i g n e da n dd i s c u s s e d ，i n c l u d i n gi s s u ee x p r e s s i o n ， m e c h a n i s mo fu t i l i t ye s t i m a t i o n ，p r o t o c o lo fn e g o t i a t i o n , d e s c r i p t i o no fa g e n t , t i m e r e l i a n tp r o p o s a lg e n e r a t i o n ，a n ds oo n c o m p a r e d 诵t i lc u r r e n tr e s e a r c h ，r e v i s e dm m a n i sm o r ea p p r o p r i a t et oc o p e 、) l ，i t hq u a l i t a t i v ei s s u ei nn e g o t i a t i o nb e t t e rv i au s i n g 缸珂 s e t s i nr e v i s e dm m a n ，t h ec o n c e p to fc l o s e d e g r e ei nf u z z ys e ti si n t r o d u c e dt od e f i n e ar e a s o n a b l ef u n c t i o no fq u a l i t a t i v ei s s u eu t i l i z a t i o n ，s oq u a l i t a t i v ei s s u e sc a nb et r e a t e d a sq u a n t i t i v ei s s u e s e s p e c i a l l y ，t h es t r a t e g yo fp r o p o s a lg e n e r a t i o na b o u tq u a l i t a t i v e i s s u e si sg i v e no u tt oi n c r e a s et h ep r a c t i c a b i l i t yo fr e v i s e dm m a n f u r t h e r m o r e ，t h e u n i t a r yt r e a t m e n to fu t i l i t yv a l u eo fs i n g l ei s s u ei sa d d e di nc u r r e n tu t i l i t ye s t i m a t i o n p a r t ，s oa st om a k et h ew e i g h tc o e f f i c i e n to fi s s u em o r ee f f e c t i v ew h i l ec a l c u l a t i n gt h e h o l i s t i cu t i l i t yo f n e g o t i a t i o n s e c o n d l y ，i no r d e rt of i n dt h eo p t i m a ls o l u t i o no fn e g o t i a t i o n , t h ef u z z yb a s e d a p p r o a c ha l g o r i t h ma n dn e a r e s tl e a r n i n gm e t h o da r eu s e dt oa d j u s tt h ep a r a m e t e r sa n d c o n f i g u r a t i o no ft h en e g o t i a t i o ns y s t e m t h ep r e c i s i o no fp r o p o s e dm e t h o dh a sb e e n v a l i d a t e dv i au s i n gc o m p u t e rs i m u l a t i o na n da d o p t e dt oo n l i n el e a r nt h ef u n c t i o no ft i m e r e l i a n tp r o p o s a lg e n e r a t i o nu s i n gh i s t o r i c a lp r o p o s a lo fo p p o n e n ta g e n ti nc u r r e n t n e g o t i a t i o np e r i o d s ot h ef u t u r ep r o p o s a li sa n t i c i p a t e da n d t h es t r a t e g yo fs e l fp r o p o s a l g e n e r a t i o ni sc o r r e c t e d f i n a l l y ，t h en e g o t i a t i o nc a nb ef i n i s h e ds u c c e s s f u l l ya n dt h ed e a l i sd o n ef a i r l y i nt h ee n d ，ab 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 ns y s t e m ( b m n s ) i sd e s i g n e da n d r e a l i z e du s i n gj a v ai nt h ep l a t f o r mo fe c l i p s e ，a n db m n si su s e da sap l a t f o r mi nw h i c h t h ee f f e c t i v e n e s so fp r o p o s e ds t r a t e g i e sa n da l g o r i t h m si sv a l i d a t e d k e yw o r d s ：m u l t i a g e n ts y s t e m ；a u t o m a t e dn e g o t i a t i o n ；m o d e lo fb 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 n ；s t r a t e g yo fp r o p o s a lg e n e r a t i o n 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表2 1 协商通信原语语义表17 表5 1 信封参数定义表4 7 表5 2s e l l e ra g e n t 各议题上下界与权值4 8 表5 3b u y e ra g e n t 各议题上下界与权值4 8 表5 4 纨船畔，取值表4 8 第1 v 页 国防科学技术大学研究生院硕士学位论文 图目录 图2 1 协商效率1 2 图2 2k q m l 结构。1 5 图2 3k q m l 消息结构1 6 图2 4 协商通信方式1 6 图3 1 定性指标量化两极比例法2 3 图3 2 模糊集合的分布2 4 图3 3 协商一方单回合流程2 8 图3 4 正向议题的时间依赖策略。3 1 图3 5 反向议题的时间依赖策略。3 1 图4 1 模糊逻辑系统的结构3 5 图4 2 对急切型时间依赖策略预测的误差4 3 图4 3 对耐心型时间依赖策略预测的误差4 3 图4 4 对冷静型时间依赖策略预测的误差4 3 图5 1b m n s 的s e r v e r - c l i e n t 结构4 6 图5 2a g e n t 的基本结构4 6 图5 3 协商双方整合效用对比一4 9 图5 4 协商成功时间对比5 0 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：基王搓塑堡迨鲍区垫垒这题垃直担差撞苤盟究 学位论文作者签名：。2 蓥札 日期：搠年，月。日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：基王搓搠堡诠的区垫垒这题协直担羞撞盔盟壅 学位论文作者签名： 作者指导教师签名： 、奄渤六 日期：o 伽j 年，月，口日 日期：沙o 年f 月o 日 国防科学技术大学研究生院硕士学位论文 第一章绪论 随着人工智能技术和分布式系统的发展，人们不再局限于研究单个智能体的 个体和社会行为。7 0 年代开始，分布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ， d a i ) 的研究开始受到人们的普遍关注，出现了许多相关理论和典型系统。分布式 人工智能涉及到协调这一具有社会性的智能行为，该行为使智能实体能协调它们 的知识、技能和规划。通常人们将分布式人工智能的研究分为两个领域，一个是 分布式问题求解( d p s ) ，另一个则是多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 是一些具有特别技能的个体，这 些个体的有机组合构成m a s 。s i m o n 认为，如果有一个良好的结构能够把多个个 体组织起来，可以弥补个体工作能力上的局限性；而单个个体负责一项专门的任 务可以弥补个体学习新任务能力的局限性；而结构中有组织、有目的的信息流动 可以弥补个体知识的有限：精确的社会机构和明确的个体任务可以弥补个体处理 信息和应用信息能力的有限。实际上，这说明了m a s 相对于一个复杂的a g e n t 在 功能上( 问题求解、处理) 上的优势；然而，就另外一个角度而言，如果没有较 好的一个资源协调机制和方法，对m a s 内的资源进行有效、合理的调配和调度， m a s 将不具备上述优势。 协商作为一种有效的m a s 协作、资源分配与协调手段，其基本的策略方法日 益受到人们的重视，其技术的成熟也能够有效推动的m a s 技术的发展与应用。本 文研究m a s 中的协商机制、策略、方法，特别针对双边多议题协商问题展开研究， 以兼顾协商双方各自的利益，最终实现“双赢的目标。下面首先对a g e n t 、m a s 的基本概念和研究现状加以讨论，了解目前m a s 协商技术的发展现状，最后对本 文的主要研究内容和章节安排加以阐述。 1 1 1a g e n t 技术概况 1 1 a g e n t 与m a s 概述 1 1 1 1a g e n t 的基本概念 a g e n t 的概念始于7 0 年的a i 研究的物理符号假设，认为智能任务可以通过对 符号的内部表示进行操作，因而“符号的内部表示+ 推理进程 形成了智能体a g e n t 的雏形。7 0 年代末到8 0 年代初，随着计算机科学与技术的进展， a g e n t 可以模 第1 页 国防科学技术大学研究生院硕士学位论文 拟更为复杂的人类智能行为。8 0 年代末以来，关于a g e n t 的研究和应用得到了迅 猛的发展，来自不同领域的研究者构造了各自需要a g e n t 。a g e n t 也就有了各种更 为具体的名字，如用于接口上的i n t e l l i g e n c ei n t e r f a c e ，用于知识处理的k n o w b o t ， 用于人机、网络通讯的u s e b o t 和n e t b o t 等。 作为a i 的一个原语，迄今为止，很难给出一个明确的a g e n t 定义。在国内， a g e n t 一词的译法尚无定论，通常翻译为“智能体”、“主体 或“代理等，但 这些译法都不能准确表达a g e n t 一词的丰富内涵。因此，许多研究者依据不同的 研究内容和目标对术语“a g e n t 赋予不同的含义。一般认为，在m 中，a g e n t 被 看作是处于一定环境下包装的计算机系统，在其他的a g e n t 存在的情况下，能够 连续、白主地处理环境中发生的时间的功能总和。这里所说的“自主是指a g e n t 工作时不要求由人经常不断的引导和干预。许多a g e n t 是与它的物理表征密切相 关的。 w o o l d r i g e 和j e n n i n g s 1 】在总结了前人在a g e n t 领域的一些工作后，给出了现 在基本被学术界公认的定义。他们从狭义和广义两个方面给出a g e n t 的两种定义： 弱定义与强定义。 智能体a g e n t 弱概念( w a ，w e a ka g e n t ) 该定义从广义的角度规定了a g e n t 最基本的特性。定义中明确指出，被称为 a g e n t 的系统应具有如下特性： 自治性( a u t o n o m y ) ：a g e n t 能够在没有人或其他a g e n t 干预下完成其大部分 功能，控制其内部状态； 社会能力( s o c i a la b i l i t y ) 或称为可通信性( c o m m u n i c 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 能感知周围环境，并对其变化实时产生响应，这 些动作的执行通常基于行为规则； 能动性( p r o a c t i v i t y ) ：a g e n t 能够主动地进行基于自身目标和信念的活动， 即a g e n t 能够在感知周围环境变化的情况下，并做出基于目标的行为( g o a l d i r e c t e d b e h a v i o r ) 。 一般情况下，a g e n t 并不是单个出现的，因此它们的行为既具有局部效应又具 有全局效应。a g e n t 的弱概念不仅可应用于人工智能领域，而且广泛地应用在诸如 人机界面、通信、并行工程、软件工程、搜索引擎等。 智能体a g e n t 强概念( s a ，s t r o n ga g e n t ) 在人工智能领域，a g e n t 的智力行为往往更受关注，从而构成了s a 的概念。 s a 与w a 不同，它除了w a 所具有的特性外，还强调计算机系统中人的智力和精 神上、情感上的因素，比如知识、信念、意图、拒绝、承诺等精神状态。 第2 页 国防科学技术大学研究生院硕士学位论文 s h o h a m 以认知逻辑为基础，分析了a g e n t 的精神状态的形式化问题，采用公 理和规则【2 1 ，对a g e n t 进行了定义：一个智能体a g e n t 是这样的一个实体，它的状 态可以看作是由信念( b e l i e f ) 、能力( c a p a b i l i t y ) 、选择( c h o i c e ) 、承诺( c o m m i t m e n t ) 等部分( m e n t a lc o m p o n e n t ) 组成。s h o h a m 认为应根据实际应用领域的需要，对 a g e n t 精神状态的范畴和性质进行选择，且精神状态的描述应与计算匹配。当前对 s a 的研究主要集中在理论方面。 1 1 1 2a g e n t 的属性 除了a g e n t 弱定义中给出的属性外，a g e n t 通常还具有下述属性1 2 】= 可移动性( m o b i l i t y ) ：a g e n t 可携带数据和指令移动到网络其他环境中，并 执行指令； 学习能力( l e a r n i n g ) ：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 d a p t a b i l i t y ) ：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 总试图去做向它请求的事情来帮助其他a g e n t ； 合理性( r a t i o n a l i t y ) ：a g e n t 的活动总是为了达到它的目标进行的，而不是以 某种方式阻止目标的到达，至少在信念中是这样的； 时间连续性( 1 0 n g e v i t y ) ：a g e n t 的进程是连续的，而不是像一般程序那样只 一遍就结束； 协作和协商的能力( c o o p e r a t i o na n dn e g o t i a t i o n ) ：a g e n t 应能在多个a g e n t 环 境中协同工作和冲突消解，以执行和完成一些相互受益且自身无法独立求解的 复杂问题。 1 1 2m a s 技术研究现状 1 1 2 1m a s 技术发展概况 人工智能研究中的并发性与分布性导致了分布式人工智能( d a i ，d i s t r i b u t e d a r t i f i c i a li n t e l l i g e n c e ) 的产生。 作为d a i 研究的分支之一，m a s 借用了对策论与社会科学的原则，认为a g e n t 第3 页 国防科学技术大学研究生院硕士学位论文 必须是理性的( r a t i o n a l ) 。但是组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 控制世界的系统是研究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 可以采用新的规划或求解方法来处理不 完全的、不确定的知识【3 j 。 第二，通过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 协调与协作等方面。其中，多a g e n t 协调与协作是m a s 研究的核心问题， 其他各个方面的问题几乎都与此相关或以此为基础。 1 1 2 2m 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 ，包 括局部功能、局部接口、应用或问题参数。 系统控制位置可以是中心的，也可以是分布的。 系统集成机制：功能、语音、表示方法、应用或问题。 a g e n t 组成既可以是同构的，也可以是异构的。 a g e n t 可以是人、机器或人和机器的混合。 m a s 中a g e n t 的意识状态是目前m a s 研究中的一个热点。己经有许多学者 从意识态度的表示和形式化等方面作了大量的研究。其中最重要最通用的研究成 果是w o o l d f i d g e 和j e n n i n g s t 4 】等人提出的信念和目标模型等。实际上，这些都未超 出b d i 模型1 5 j 的范畴。 第4 页 国防科学技术大学研究生院硕士学位论文 1 2自动协商技术的发展现状 1 2 1 协商的基本概念 协商是d a i 研究中一种重要的信息交换和冲突消解模式，一般来讲，它是指 用来增进系统协调的通讯机制【6 】。即使不出现冲突，协商也是十分重要的，因为它 所产生的系统承诺将超过参与协商的主体个人承诺。协商能够在任意层次上实现， 它便于灵活地运用冲突消解策略，不同层次上可采用不同的机制。 m a s 中，协商是指两个或两个以上的a g e n t 彼此交换消息，努力就某一事情 达成相互可接受的意见的过程。它是一种决策的方式，在协商中两个或多个对象 为了达到各方利益的一致而共同致力于寻找一个可能的解决途径。 协商被认为是解决分布式计算和多a g e n t 社会中存在的各种问题的有效途径 p j ，目前被广泛地用于解决多个方面的问题，例如问题分解、任务分配、网络相关 性、冲突检测和解决机制等【8 】。a g e n t 之间的自动协商模型是对电子商务中不同对 象之间交互进行建模的重要模型 9 1 ，在自动协商中，特别强调了a g e n t 的合作性和 协调性。 协商是m a s 中交互的主要形式，由于a g e n t 是自治的，因此具有高度的自我 决策能力，即它们自己决定在何时何种条件下执行何种活动。一个a g e n t 不能直 接控制另一个a g e n t ，必须通过协商来管理它们之间的关系。因此，协商可以视为 双方或多方做出联合决策的过程【l o 】。 1 2 2 自动协商技术的基本类别 m a s 自动协商技术包括：基于博弈论的技术，基于启发式方法的技术和基于 争论的技术。 基于博弈论 博弈论从经济学的角度研究a g e n t 之间的交互。基于博弈论的协商将a g e n t 间的交互看作一种博弈【1 1 1 。基于博弈论的研究由来己久，它在协商成功率、社会 收益的最大化、p a r e t o 最优、稳定性、简单性等方面具有很好的表现。但是，它通 常需要a g e n t 对合同空间和可能状态进行穷举式搜索，这就导致了a g e n t 在反应时 间方面的缺陷，另外，它假设a g e n t 有完全的个体理性且计算能力无限，这种假 设在现实中很难满足。 m a s 协商与协作的研究在8 0 年代末至9 0 年代主要集中在应用对策论研究近 似完备知识情况下，固定a g e n t 在封闭环境下静态协商规划模型【1 2 j 。值得注意的是， 对策论在m a s 协商、协作甚至在计算生态学的研究中都起着非常重要的作用，这 是因为对策论被公认为研究人类社会交互的最佳数学工具。 第5 页 国防科学技术大学研究生院硕士学位论文 传统对策论的协商一般通过建立对方效用模型实现。而基于对策论的m a s 协 商、协作主要有以下两种方法： 1 、没有通讯的协商：方法与传统对策论相似。 2 、协商：其种类繁多，主要有基于n a s h 合作对策求解的两a g e n t 协商，基 于n a s h 非合作对策求解的多a g e n t 协商，基于r u b i n s t e i n 协商理论的方法，以及 基于s h a p l e y 值或特征函数的多a g e n t 联盟对策。 对策论为m a s 协商、协作的研究提供了坚实的理论基础。但是目前基于对策 论的m a s 协商、协作研究远未达到完善。 基于启发式方法 为弥补基于博弈论的研究在应对现实协商问题中的不足，基于启发性方法的 技术应运而生。基于启发式方法的研究采用一些启发式技术制导对合同空间的搜 索，采用的是非穷举式搜索，从而减少了计算上的代价，增加了a g e n t 的反应速 度，并且它不需要完全的个体理性和计算能力无限这类苛刻的前提假设，从而增 加了它的应用范围。 基于争论 基于争论的协商【1 3 ，1 4 】通过增加a g e n t 的交互能力来实现，参与协商的a g e n t 不仅仅只能发送提议和反提议等简单的交互语句，它们还可以通过争论和提问等 人类社会中更复杂的交互语言进行交互，通过争论，来改变彼此的认知，以将协 商向更满意的方向发展。然而，该类技术由于其复杂性，在协议的设计，协商语 义的表示和推理，协商策略的制订等方面都面临了很大的困难。 1 2 3 双边多议题自动协商技术研究现状 双边多议题自动协商技术是m a s 协商中最受关注的一类。通常可分为非合作 环境的多议题自动协商和合作环境的多议题自动协商。在非合作环境，研究往往 集中进行严格的协商模型化，分析改进协商对策，选择合适协商方式，安排合理 的协商议程：在合作环境，代表性的研究者n a s h 和其他人则着重于公理的研究， 任何一种协商方法都试图满足这些公理并且达到p a r e t o 最优。 双边多问题自动协商的研究主要在于设计合理的自动协商模型和好的协商代 理机制，利用具有智能特点的a g e n t 进行多问题自动协商，尽管协商结果不一定 是最好的，但是它对于协商方法的自动化和协商的应用带来了巨大的影响。目前 研究工作主要从协商框架，协商权衡机制和协商空间搜索方法三个方面开展。 协商框架 协商框架是自动协商技术研究的基础工作【i5 1 ，其重要性不言而喻，目前的主 要研究有下述几种： 第6 页 国防科学技术大学研究生院硕士学位论文 f a t i m a 等人提出基于协商议程的框架【l 伊j 。在这个协商框架中，a g e n t 可以提 出针对一个问题的协商独立提议，也可以提出有关几个协商问题的组合提议，同 样在进行决策的时候也可以独立决策或组合决策。在这个框架下，效用函数在正 常情况下应该是线性增加的。 s y c a r a 等人是基于实例推理方法进行协商框架的研究【1 4 1 9 , 2 0 1 。每一次协商， a g e n t 都会从几个方面( 比如：协商问题，协商对手，协商背景等) 分析相似的协商实 例，从中进行学习，再确定当前的协商策略和协商框架。他们把这种协商方法主 要应用于劳工管理的协商环境中，并且将时间因素加以考虑。这种方法在有专家 指导的现实环境有着较好的应用。s y e a r a 等人还在此基础上提出了协商中的劝诱 机制【2 l 】，期望通过协商策略中的诱惑因素对于协商策略的影响，吸引另外一方更 趋向于接受当前的协商提议。 l u o 等人研究出了一种应用于商务环境的基于模糊约束的多问题自动协商框 架 2 2 1 。在这个框架中，协商最初由买方针对协商中的多个问题定义一个模糊约束 集，并且按照优先级从高到低依次提交给卖方，卖方在收到后，可以进行这样的 选择，要么在约束范围内给出提议，要么提出要求请买方放宽约束条件，买方再 根据卖方回复，选择接受或者拒绝提议，或者放宽约束条件，还可以选择协商失 败。研究者认为在这种方法下，即使不给出a g e n t 的效用函数，也可以在a g e n t 之间达成具有较好收益的协商结果。 协商权衡机制 协商过程中，a g e n t 常常会遇到需要权衡让步的情况，权衡的前提是希望达“双 赢”的目标。f a r a t i n 等人在【8 】中提出了一种基于相似度原则的权衡折衷方法。每 次当a g e n t 需要提出新的协商提议时，新的提议要尽量保持上一轮提议的效用值， 可以在无差异集合中选择新的提议。实验表明这种方法有助于a g e n t 之间达到更 为满意的共识，同时协商结果也更容易满足p a r e t o 优化条件或者接近。 协商空间搜索方法 许多研究者利用计算原理提出了许多协商空间搜索方法。 k l e i n 等人团】基于随机搜索方法来对复杂的合同进行协商，在协商过程中引入 协调a g e n t 角色。协商过程中，协调a g e n t 产生一个提议，同时发给协商双方，由 他们决定是否接受。如果双方都接受，则协商结束；如果有任何一方反对，则协 调a g e n t 选择最接近当前效用的可替换协商提议继续请求协商的意见。这个过程 一直持续到没有更好的协商提议，或者协商时间终止。k l e i n 定义了两类协商方： 一类为爬山者，另一类为模拟退火者。爬山者在协商过程中比较简单，只要当前 协调者给出的提议好于上一次协商共识就接受，而模拟退火者的协商过程复杂些， 他通过蒙特卡洛学习法计算概率来确定是否接受当前的协商提议。通过实例，可 第7 页 国防科学技术大学研究生院硕士学位论文 以发现这些方法都是收敛的，当协商双方都是模拟退火者的时候协商结果要好于 协商双方都是爬山者的情况。如果在协商过程中，一个模仿爬山者，一个模仿模 拟退火者，则协商结果可能有利于爬山者，而爬山者在这种情况下所获得的效益 还要好于双方都是模拟退火者的情况。因此，这种方法类似于囚徒困境问题。k l e i n 在研究过程中也采用了相应方法，在协调a g e n t 的帮助下避免陷入困境。 t e a s u r 0 1 2 4 1 和l i t 2 5 】基于贝叶斯规则研究协商中的搜索方法。他们假设协商 a g e n t 预先都知道对方的效用函数，协商过程中需要退让时，将会利用有限深度的 组合搜索方法和已有的协商信息改进协商提议；当有需要时，则利用贝叶斯规则 改进协商信息。 1 3 本文主要研究内容 本文主要针对m a s 自动协商技术中的自动协商模型和提议产生策略展开研 究，在充分调研自动协商相关理论与技术的基础上，提出了一种双边多议题自动 协商模型和基于模糊系统学习的提议产生策略，并在e c l i p s e 平台上基于所提自动 协商模型设计开发了双边多议题自动协商环境，对提议产生策略的效果进行分析。 本文各章内容安排如下： 第一章主要对a g e n t 与m a s 的基本概念和发展现状进行调研，重点考察自动 协商技术在m a s 相关技术研究中的重要性，并给出本文的主要研究内容。 第二章主要介绍m a s 自动协商技术的相关理论，特别针对双边多议题自动协 商过程中的系统特性、参数和协商通信语言展开深入研究，为进一步的自动协商 模型和提议生成策略研究奠定了理论基础。 第三章提出一种包含定性议题的双边多议题多a g e n t 系统自动协商模型：改 进的 心嗄a n ，给出其形式化描述，并仔细设计和讨论了模型中所涉及的议题表达、 效用评价机制、协商协议、a g e n t 描述、时间依赖的提议生成策略等内容。 第四章利用模糊逻辑系统作为逼近器，选择算法简单、计算量小的最近邻学 习算法同时对该系统进行参数和结构自适应调整，以得到最优解。在利用仿真手 段验证其精度水平的基础上，采用这种逼近器利用当前协商周期内对手a g e n t 的 提议值历史数据，对其时间依赖提议产生函数进行在线学习，来预测对手在未来 时刻的提议值，并据此对a g e n t 协商中的提议产生策略进行了修正，以保证既能 较快地达成协作，又能很好地兼顾协商双方各自的利益，实现“双赢”的目标。 第五章基于所提协商模型，利用e c l i p s e 开发平台创建自动协商环境，对基于 模糊逻辑系统学习的提议生成策略的效果进行验证。 第8 页 国防科学技术大学研究生院硕士学位论文 第二章m a s 自动协商相关理论 本章将主要介绍自动协商的定义、分类，探讨自动协商系统的组成，分析协 商结果的衡量标准，对双边多议题自动协商系统的特性加以探讨，分析自动协商 过程中的通信原语等基本内容，为进一步的双边协商相关技术研究奠定理论基础。 2 1自动协商的基本概念 2 1 1 自动协商的定义 自动协商的重要性和协商系统的实用性，已经由许多学者广为研究和讨论。 由于各自考虑的侧重点不一致，所以存在许多动协商的定义。 在传统的语义解释中，协商就是若干实体就某个问题进行讨论，并且达成某 种共识的过程。l e i 等人主要从自动协商系统的过程方面给出定义 2 6 1 ，他们认为自 动协商过程可分为三个阶段，包括系统定义将要进行的协商议题、根据精确的协 商协议的自动协商活动、达成协议后的相关行为履行。o l i v e r 等人则将自动协商系 统定义为一个可以有效提高参与协商者效益系统1 2 7 1 ，它具有高效率，电子化及自 动化的特性。s 锄d l l o h n 【2 8 】等人认为，自动协商系统可以节省人为协商的时间，并 且透过复杂的策略及准确的运算后，通常会产生较佳的协商结果。n u r f e e 等人将 协商定义为通过相关信息的交换，以达成共同协议( 减少不一致性以及不确定性) 的某一过程。j e r 血n g s 【4 】等人基于a g e m 的自动化、主动及自我感知等特性，强调 自动协商适合在多a g e n t 系统中实现，并能解决各种冲突问题。a l e s s i o 等人将自 动协商定义为多a g e n t 之间针对某特定事件或资源、共同寻求可接受的共识的过 程。 尽管定义的形式各有侧重，但综合各定义，协商主要具有下述特征：涉及两 个或两个以上的成员；协商成员互相依赖；存在明显或者潜在的利益；具有共同 解决的意愿。 2 1 2 协商的基本类型 2 1 2 1 根据数量的分类 根据协商双方a g e n t 的数目，可以分为双边协商( 一对一) 、多边协商( 一 对多或多对一) 和双向协商( 多对多) 【2 9 1 。 2 1 2 2 根据相互关系的分类 根据协商各a g e n t 之间关系的不同，可将协商分为下列两种不同类型。 第9 页 国防科学技术大学研究生院硕士学位论文 分配型协商 分配型协商( d i s t r i b u t i o ni nn e g o t i a t i o n ) 是协商双方在互相冲突目标上进行协 商的过程。在协商过程中，协商双方为对立关系，如果其中一方获得利益有所增 加，将使另外一方利益减少。这种协商从博弈论的角度出发，整个协商过程为一 个零和游戏。这种类型的协商关键在推导对方的底线，并寻找恰好使对方接受的 解决方案，这样才可以使得自己的利益达到最大。但是如果一方对另一方的底线 误判，则可能会导致协商失败。这样的协商中，协商双方不是赢便是输。因此， 协商成功的概率并不是很大。 整合型协商 整合型协商( i n t e g r a t i o ni nn e g o t i a t i o n ) 则站在合作角度上来做协商考虑，由 于双方在协商过程中，对于相同属性存在不同偏好，因此，使得对策的结构有所 改变。协商双方要寻求彼此最大价值区域，它的过程并不是要使得每个议题都要 达到最大利益，而必须指出自己较为重视的议题，使得协商双方的这些多议题上 进行相互折衷，进而寻求一个整合性的解决方案。在协商过程中，由于交易双方 存在互惠的弹性选择，因此这类型的协商称之为整合性协商，从理论上而言，它 能促成更多协商的成功，同时也可以提高彼此的满意度，达到双赢局面。 2 2自动协商系统的组成 自动协商系统一般由协商协议( n e g o t i a t i o np r o t o c 0 1