（管理科学与工程专业论文）基于GA的一对多多属性自动谈判模型研究.pdf

摘要 摘要 随着i n t e r n e t 技术的发展和传统的商务活动向网络的转移，越来越多的学 者开始研究电子商务自动谈判模型，自动谈判系统已成为解决用户与商家冲突的 重要渠道。在现实中，当买家与卖家进行交易时，往往要针对产品的多个属性进 行交涉，并希望与多个卖家同时进行，从而选取最优方案。因此一对多、多属性 谈判模型的研究更具现实意义。 本文在详细阐述自动谈判系统研究现状的基础上，总结了一对多、多属性谈 判的特点，利用模糊隶属度函数进行效用表达，引入竞争机制和贝叶斯学习机制， 设计了两个基于遗传算法( g a ) 的一对多、多属性谈判模型：竞争机制模型和报 价一反报价模型。本文模型使用模糊数学中的正态分布函数进行效用的表达，采 用双方接受度乘积的形式来计算适应度，在一定程度上避免了目前采用的线性加 权方法的弊端，同时为了提高遗传算法的收敛速度，模型中采用了动态的选择概 率和变异概率，使得具有较大适应度的个体在下一代中具有更大的存活可能性， 同时为了在下一代中获得更加多样的个体，模型加大了交叉概率，另外，本文模 型采用将上一代中所有的针对每个卖方形成的最优方案同时放到下一代中的每 一个卖方的染色体编码中的办法，体现多个卖方之间的竞争关系，另外在报价一 反报价模型里，本文采用贝叶斯学习机制动态的学习对方各个款项权重的变化， 通过不断更新对对方权重的猜想使己方获得最大效益。在最后，本文给出了对竞 争机制模型利用s w a r m 平台进行模型仿真的仿真结果，仿真结果表明本模型大幅 度提高了遗传算法的收敛速度，同时也证明了模型的合理性，得出的最终结果也 与现实相吻合。 关键词自动谈判；遗传算法；一对多；多属性；贝叶斯学习 北京t 业大学硕 j 学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e tt e c h n o l o g ya n dt r a d i t i o n a lb u s i n e s s t r a n s f e r r i n gt ot h ee c o m m e r c e ，m o r ea n dm o r es c h o l a r sp a ya t t e n t i o nt ot h ea u t o m a t i c e c o m m e r c en e g o t i a t i o n ，t h e r e f o r et h ea u t o m a t i cn e g o t i a t i o ns y s t e r nb e c o m e sa n i m p o r t a n tc h a n n e lo fs o l v i n gt h ec o n f l i c tb e t w e e nb u y e r sa n ds e l l e r s i nd a i l yl i f e w h e nab u y e rp l a n st ob u yap r o d u c t ，h ew o u l dc o n c e r na b o u tm o r et h a no n ea t t r i b u t e , a n dh ea l s ow a n t st on e g o t i a t ew i t hs e v e r a ls e l l e r sa tt h es a m et i m ei no r d e rt og a i n m o r eb e n e f i t s s oi ti sp r a c t i c a la n di m p o r t a n tt os t u d yt h eo n e t o - m a n ym u l t i - a t t r i b u t e n e g o t i a t i o n i nt h i sp a p e r , a f t e re x p a t i a t i n gt h es t a t u so fa u t o m a t e dn e g o t i a t i o ns y s t e m ，t h e a u t h o rs u m m a r i z e st h et r a i t so fo n e - t o - m a n ym u l t i a t t r i b u t en e g o t i a t i o n u s e sf u z z y m a t h e m a t i cf u n c t i o nf o rt h ee f f e c t i v e n e s se x p r e s s i o n ，i n t r o d u c e si n t oac o m p e t i t i v e m e c h a n i s ma n du s e sb a y e s i a nl e a m i n gm e c h a n i s m a tl a s td e s i g n st w oo n e t o m a n y m u l t i a t t r i b u t en e g o t i a t i o nm o d e l sb a s e do ng e n e t i ca l g o r i t h m ( g a ) t h em o d e l su s e n o r m a ld i s t i l b u t i o nf u n c t i o nt oc a r r yo nt h ea c c e p t a b i l i t yo fe a c ha t t r i b u t e ，a n dt h e n c a l c u l a t et h ef i t n e s sb yt h em u l t i p l i c a t i o no ft h eb o t ha c c e p t a n c e s ，i nt h i sw a yw ec a n a v o i dt h el i m i t a t i o no ft h el i n e a rw e i g h t i n gm e t h o d i no r d e rt oa c c e l e r a t et h e c o n v e r g e n c eo ft h eg e n e t i ca l g o r i t h m ，w eu s ed y n a m i cs e l e c t i o np r o b a b i l i t ya n d m u t a t i o np r o b a b i l i t y , s ot h ec h r o m o s o m e sw h i c hh a v eh i g h e rf i t n e s sc a nb ek e p t s u r v i v a lm o r ee a s i l y b u tc o n s i d e r i n gg e t t i n gm o r ed i f f e r e n tc h r o m o s o m e s ，w e i n c r e a s et h ec r o s s o v e rp r o b a b i l i t y m e a n w h i l ew et a k ea l lt h eb e s tc h r o m o s o m e so f e a c hs e l l e ri np r e s e n tg e n e r a t i o ni n t ot h ec h r o m o s o m e so fe a c hs e l l e ri nt h en e x t g e n e r a t i o n ，b yt h i sw a y , w et a k eb o t ht h ec o o p e r a t i v er e l a t i o n s h i po ft h en e g o t i a t o r s a n dt h ec o m p e t i t i v er e l a t i o n s h i po fd i f f e r e n ts e l l e r si n t oa c c o u n t a tl a s t ，w eg i v ea s i m u l a t i o nr e s u l to ft h ec o m p e t i t i v em e c h a n i s mm o d e lb yt h es w a r mp l a t f o r i l l ，w h i c h s h o w st h a tt h ec o n v e r g e n c eo fg e n e t i ca l g o r i t h mi sg r e a t l ya c c e l e r a t e d ，a n dt h er e s u l t t a l l i e sw i t ht h er e a l i t y , s ot h em o d e li sr e a s o n a b l e k e yw o r d s ：a u t o m a t i cn e g o t i a t i o n ；g e n e t i ca l g o r i t h m s ；o n e t o - m a n y ；m u l t i a t t r i b u t e ； b a y e s i a nl e a r n i n g i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：么缸乏日期：型擎笸! ! 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：缢灿丢导师签名：j 立篡 日期：2 丝逝 第l 章绪论 1 1 选题的背景和意义 1 1 1 选题背景 第1 章绪论 随着i n t e r n e t 技术的发展，传统的商务活动向i n t e r n e t 转移，涌现出大量的 电子商务服务，由于电子商务高效、低成本的特点，越来越受到各个企业的关注， 因而电子商务也变成了各个企业获取利益的重要渠道。而在众多的企业与企 业、企业与消费者之间的交易活动中，不可避免的会存在利益冲突问题，而谈判 是解决这种冲突的重要方式。 按谈判机制中谈判参与者数量的不同，谈判活动可以分为：一对一谈判、一 对多谈判、多对多谈判；按照谈判所涉及的属性的多少又可以有单属性谈判和多 数性谈判，然而在现实生活中，谈判的问题的属性往往多于一个，即是多属性谈 判，例如对于消费者来说，价格并不是唯一的决定性因素，消费者往往会关心其 他相关的因素，比如商品质量和配送时间等，因此对于多属性谈判的研究具有重 要的意义。 传统的商务谈判活动主要以人为主体，人们基于一定的利益对特定的内容进 行谈判、协商，最后达成各方满意的谈判协议。但是以人为主体的谈判存在诸多 问题。首先，从成本角度来看，传统的谈判需谈判双方占用大量的时间和精力就 某一问题进行多轮反复的报价与反报价，最终还不一定能达成协议，这样给双方 都产生了大量不必要的成本。其次是传统的谈判是一个技巧性要求很高的行为， 任何一方具有了更多地技巧，则其在谈判过程中所获得的利益也就相对较大。而 谈判技巧对于一般的谈判人员来说并不是很充足的，这就很可能导致谈判的效果 不会很理想。再次，传统的谈判需要双方在指定的时间，固定的地点进行，这给 双方带来了很多不便。最后，在目前的经济环境下，电子商务发展迅速，交易变 得频繁而且复杂多变，传统的谈判已很难满足要求。具有决策支持能力的决策支 持系统和自动谈判系统，已经成为电子商务研究成为业界的热点，而基于具有自 治性、交互性和智能性的a g e n t 技术的研究，如何有效的将先进的a g e n t 技术运 用于电子商务自动谈判领域，已经成为经济学家和计算机学者共同研讨的一个主 要方向m l j 谈判支持系统是将先进的计算机和信息技术与信息决策支持系统的理论、技 北京t 业大学硕 ：学位论文 术和方法引入到冲突谈判这一特殊领域，通过人机交互，融合运筹学、对策论、 决策理论、行为科学、心理学、计算机技术、信息技术、人机工程等多方面的技 术理论和方法为谈判者提供分析解决问题的工具h 3 。从8 0 年代后期出现谈判支 持系统至今，国内外许多学者都从不同角度对谈判支持系统进行了大量的研究， 并且开发出了相应的系统软件。在国外，最近几年对n s s 的研究开始引起学术 界的重视，并且实现了一些实验性系统如：m e d i a t o r 、i n s p i r e 等。在国内， 主要集中在协商模型和冲突分析的研究上。总体上，对n s s 的研究基本上是基 于效用函数，在谈判机理上存在结构性的缺陷，在系统实现上，被设计成分配式 的。n s s 是典型的用来教学、训练和实验的软件工具瞄3 。因此，难以广泛适应 b 2 b 和b 2 c 电子商务的要求与发展。这种计算机辅助支持的系统能够有效提高 谈判的效益和效率，但是随着电子商务的全球化发展，使得这种支持系统不能满 足企业的需要，从而需要一种新的谈判系统来适应电子商务全球化发展提出的需 要。 就网上谈判范畴来说，除了谈判支持系统以外，还有拍卖( a u c t i o n ) 和自 动谈判( a u t o m a t e d n e g o t i a t i o n ) 。拍卖可以看作是一种谈判；拍卖由于其过程简 单，且容易实现自动化和有效竞争，近年来在互联网上取得了非常成功的应用。 尽管拍卖可以采用公开拍卖、密封拍卖等多种机制，但拍卖是严格的分配式的， 是w i n 1 0 s e 型的，而且适用与拍卖的商品范畴有限，也不能完全满足电子商务的 要求引。 自动谈判是一组自治a g e n t 为了某个或某些与利益相关的议题相互进行通 信已求达到一致的过程订m 羽。它是多a g e n t 系统中一种重要的交互形式。自动谈 判不需要或极少需要人员的参与，能极大地适应电子商务发展的要求，降低交易 成本，提高谈判双方的满意度阻】 川。 1 1 2 选题意义 目前对于一对一谈判的研究已相对较为成熟，而对于一对多协商、多对多协 商还处于起步阶段，还没有比较完善地解决方案。然而在电子商务交易中，为了 达到更好的谈判效果，获得更多地利益，买方希望与多个卖方或者卖方希望与多 个买方同时进行谈判，然后在所有达成一致的方案中选择最佳的交易方案n 卜1 3 1 。 而理论和实践都表明，在a g e n t 决策过程中，如果能在交互的过程中学习对手 的信念和偏好信息，可以有效增加自我效用，如果所有的a g e n t 都能进行学习， 系统地联合效用将接近最优n 钔。 目前对于一对多谈判的研究主要采用多个一对一谈判的并行方法，协调 a g e n t 具有很高的复杂性，系统不易于实现，导致谈判效果并不是很理想。另外， 第l 苹绪论 谈判的问题的属性会多于一个，例如对于消费者来说价格并不是唯一的决定性因 素，消费者可能会关心其他相关的因素，比如商品质量和配送时间等，而目前的 研究还基本是只针对价格这一单一的属性进行的，很难满足现实的需求，对于一 对多、多属性自动谈判的研究具有重要的意义。 本文正是试图在这一前沿上研究一对多( 一个买家，多个卖家) 、多属性的 自动谈判系统，研究一对多谈判决策分析模型，使得自动谈判系统朝着充分自动 化、智能化、实用化的方向迈进一步，是谈判理论和博弈论、m u l t i a g e n t 技术 等理论与技术的交叉与渗透。同时本文将深入学习自动谈判理论所研究的各种学 习机制，并对遗传算法进行重要的改进。 本文将突破目前谈判系统尤其是一对多谈判系统的局限性，充分考虑商务谈 判中一对多、多属性谈判的特点。论文研究具有重要的理论意义和广阔的应用前 景。 1 2 国内外研究现状 1 2 1 谈判支持系统研究现状 谈判支持系统( n s s ) 起源于2 0 世纪8 0 年代末期n 目，被认为是群决策支持 系统的一个分支n 引。谈判支持系统( n e g o t i a t i o ns u p p o r ts y s t e m ，n s s ) 是以计 算机技术、信息技术、人机工程等技术为基础，将决策科学、行为科学、心理学 及有关学科的理论和方法引入到冲突协商领域，就谈判问题为各方提供背景材 料，协助他们明确目标，建立模型、解决争议，并提供谈判的建议解或者支持谈 判过程的谈判工具n 铂 n s s 可以看作一种能够改善谈判效率和提高谈判质量的软件支持工具。从大 量的研究成果看出，它主要在两个方面辅助谈判：过程支持和解支持乜妇： ( 1 ) 过程支持机制 1 ) 为谈判设定虚拟会议室，可供一个或几个谈判使用。对于某个谈判会议， 应设定会议名称和密码，各谈判人也应有各自的用户名和口令。谈判中，会议可 以中断。恢复谈判时，需要同样的会议名称和密码再次注册进入系统。 2 ) 当用户登陆后，系统立即产生一个热线对话框，为谈判人提供交换信息 的通道。系统的监控窗口用于自动通知对方有关系统操作的情况。 3 ) 在谈判中系统应能够产生不同窗口，比如咨询窗口等，以提供背景信息 查询服务。 4 ) 系统采用数据库方法支持双边或多边谈判，并进行谈判文件的处理和归 档。 北京t 业人学硕十学位论文 ( 2 ) 解支持机制 解驱动的n s s 应当提供谈判人用于评价谈判方案的效用函数，并为谈判人 提供建议解或方案。这种支持作用体现在三方面： 1 ) 研究情况，明确谈判项目和利益。系统帮助谈判人确定各项目的重要程 度，获得的偏好信息将用于评价谈判人自己和对方提出的各个方案。 2 ) 进行一系列的信息交换，提出各种不同的方案。根据前面确定的谈判人 偏好，对各方案进行判分，为谈判人提供一定的评价依据。 3 ) 系统按照p a r e t o 最优原则，对初步达成的协议或交易方案进行分析后， 提供更好的建议或方案，供谈判人考虑和选择。谈判人也可考虑进一步谈判，达 成另一个协议。 目前主要的n s s 系统有c a p 池1 、d e c i s i o n m a k e r 2 驯、n e g o 瞰1 、 d e c i s i o nc o n f e r e n c i n g 、m e d i a t o r 2 6 。、r u n e 蜊、p e r s u a d e r 捌等。 1 2 2 自动谈判系统研究现状 n s s 虽然在一定程度上实现了谈判的智能化，但由于其本身的特点，不能代 替谈判者进行谈判，而自动谈判系统由于利用智能a g e n t 部分替代了人进行谈 判，能够打幅度提高谈判效率、降低采购和销售成本，因此国内外学者对自动谈 判系统的研究十分重视。 目前自动谈判系统主要的研究成果有：麻省理工学院t e t e - a - t e t e 项目比9 1 ，采 用协商理论研究自动谈判。加州大学伯克利分校的f i s h e r 研究中心的o f f o r 项 目，对面向电子市场的自动谈判系统进行了研究。斯坦福的k b e m 项目，研究 电子商务环境下，采用基于知识的技术，自动化处理供应商和销售商之间的谈判 与协作。伦敦大学的a d e p t 项目对自动谈判机理进行了研究，主要应用于业务 流程之间的协作与管理啪1 。荷兰的国家研究机构c w i ，加拿大卡尔顿大学，以及 惠普公司布里斯托尔实验室等，对自动谈判的理论与方法研究也非常重视。 自动谈判最初主要是用来解决多a g e n t 系统中的协调问题，即解决多a g e n t 系统中各a g e n t 之间在资源、任务分配中存在的冲突b 订口霸。而将a g e n t 直接应用 到商业谈判活动中，解决商业谈判中的各种冲突还是比较少的。这需要针对商业 谈判活动的具体特点，结合多a g e n t 系统的协商、协调机制，重新分析和设计， 这具有相当大的难度。因此，现有的可以参考的自动谈判系统还不是很多。现有 的基于m u l t i a g e n t 的谈判系统主要有以下几个n 3 ： ( 1 ) f i r e f l y f i r e f l y 是一个邮件订购系统。f i r e f l y 的目的在帮助消费者找寻合适的产品 此系统主要是运用在贩售音乐c d 和书籍等产品上f i r e f l y 藉由自动化合作式过 第l 章绪论 滤方式( a u t o m a t e dc o l l a b o r a t i v ef i l t e r i n g ，a c f ) 来搜寻产品，并向消费者建议 购买的产品产品购买建议主要是利用目前的消费者与以往消费者的喜好品味近 似程度来做建议 ( 2 ) a u c t i o n b o t 柏1 一个通用的在线拍卖服务器，是由美国密西根大学所开发出来的商品拍卖代 理人系统。利用一个应用程序界面让使用者( 买卖双方) 建立各自的软件代理人， 并让这些软件代理人在a u c t i o n b o t 电子商场中进行竞价。用户通过选择不同的 参数来选择不同的拍卖类型，买卖双方根据所选拍卖类型的多边分布协议来投 标。在a u c t i o n b o t 的市场中，卖主在选择一个预留价格以后对拍卖进行初始化， 然后让a u c t i o n b o t 依据拍卖协议以及参数来管理投标过程。a u c t i o n b o t 一个显著 的优点是它可以提供应用设计界面( a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e s ) ，这样 用户就可以创建代表自己的a g e n t 在a u c t i o n b o t 的虚拟谈判屋中进行谈判。它的 缺点是像其他的商务拍卖网站( 例如e b a y ) 一样只允许就价格一种属性进行谈 判，不支持多属性谈判。 ( 3 ) k a s b a h 由美国麻省理工学院的媒体实验室所开发出的多重代理人c 2 c 线上交易系 统，买卖双方必须先建立自己的软件代理人，并赋予其一些买卖策略，然后将代 理人送至“软件代理人中央商场 进行买卖议价。k a s b a h 的a g e n t 没有使用任 何人工智能或机器学习技术，在卖方创建新的卖方a g e n t 时，它将建立一个引导 参数，包括买到该商品的最后期限、商品的期望成交价格、最低可接受价格。 k a s b a h 使用一个议价策略函数引导a g e n t 在谈判过程中议价。该系统有三个基 本的定价函数：线性函数、二次函数、立方函数，分别代表急切的、沉着的和贪 婪的议价态度。k a s b a h 的a g e n t 只能就价格单个属性进行谈判，而且只能根据 预先选定的谈判策略进行谈判这样有可能达不到最优的谈判效果。 ( 4 ) t e t e - a - t e t e 由美国麻省理工学院的媒体实验室所开发出的电子商务交易代理人系统。买 卖双方各自拥有一个a g e n t ，a g e n t 在交易中通过谈判来合作m 3 。他将m a u t ( m u l t i a t t r i b u t eu t i l i t yt h e o r y ) 和d c s p ( d y n a m i cc o n s t r a i n ts a t i s f a c t i o n p r o b l e m ) 技术相结合来调停消费者的购物a g e n t 和零售商的销售a g e n t 之间的 多个问题( 担保、交货期、服务合同等) 谈判。t e t e a - t e t e 中买方a g e n t 和卖方 a g e n t 争辩地谈判，并使用在产品选择和商业代理阶段生成的评估限制作为多属 性效用函数。t e t e - a - t e t e 系统是一个一对一的谈判过程。 ( 5 ) e - m e d i a t o r 下一代电子商务服务器，它使用增强了的a i 和算法技术，对策论以及g u i 设计。e m e d i a t o r 中有两类a g e n t ：e a u c t i o n h o u s e ，一个可通过定制不同参数来 北京t 业大学硕 ：学位论丈 配置不同拍卖类型的拍卖屋：e c o m m i t t e r ，一个平衡的义务合同最优化选择器。 ( 6 ) a d e p t 一个针对电信服务行业的系统，a d e p t 定义了一个面向服务谈判模型，并 在以后的工作中对其进行了改进，对a g e n t 的谈判结构增加了相对复杂的思考机 制，用于决定提议的内容，但它不支持谈判过程中问题的变更n 5 1 。 ( 7 ) t a b i c a n 用以贩售机票与套装旅行的交易协商代理人系统，其中的交易成员包括：商 场主人、旅行社、消费者。 ( 8 ) l i a n g 和d o o n g 的电子市场原型试验系统口叼 主要用来研究议价是如何吸引顾客的，以及当谈判策略有效时，个体差异是 如何影响议价结果的。这个电子市场由几个小商店组成，其中一些商品提供议价 功能7 l 。系统使用三种议价策略： 1 ) 效用递减策略：在初始出价时给出很大的折扣，以后逐渐减少让步，买 方感觉到效用在逐渐减少。 2 ) 效用递增策略：在初始出价时给出比较小的折扣，以后逐渐增加让步。 3 ) 效用均衡策略：始终用不变的价格折扣，买方感觉到不变的效用。 t i b o rb o s s e 和c a t h o l i j i nm j o n k e r 通过两个对比试验指出了人类谈判与利 用目前已有的计算机软件自动谈判各自的优劣。第一组试验是人与人谈判和计算 机与计算机谈判进行对比，第二组谈判是人与计算机谈判和计算机与计算机谈判 进行对比，其中使用的自动谈判软件是利用案例学习的a b m p 软件。通过对比 试验，作者得出结论：目前的谈判软件在解决单属性谈判问题时具有明显的优势， 但对于多属性谈判则还存在较大不足，文章最后给出了自动谈判软件研究方向的 重要建议。 相比较而言，自动谈判不受时间、人物的限制，更适合电子商务发展，尤其 是多品种大量采购的情形m 1 。b l e c h e r m a n 实验发现：当谈判能力均匀分布各谈判 方或彼此不了解各谈判方的谈判能力，并且采用自动谈判所带来的利益能平均分 配时，人们更愿意采用自动谈判。最新的研究还表明，利用自动谈判更容易使谈 判方共同获益，因此，对自动谈判系统的研究可望为电子商务谈判探索一条合理 的途径。 一对多、多属性谈判问题是谈判问题的一个重要分支，并且一对多、多属性 谈判更符合实际情况。对于一对多、多属性谈判的问题，本文将在第2 章进行详 细论述。 第1 章绪论 1 3 本文研究内容 本文在对一对多、多属性自动谈判进行深入的研究的基础上，通过综述自动 谈判的研究现状，分析一对多、多属性谈判的特点，讨论现有的谈判系统中存在 的问题，提出了利用模糊隶属度函数进行效用的表达，用遗传算法和贝叶斯学习 机制来实现学习机制的一对多、多属性自动谈判模型，并引入了竞争机制用来解 决以下问题： 谈判双方谈判效用的表达，由于谈判双方对所谈判问题的偏好的不确定性， 所以采用何种形式进行其效用的表达是一个非常关键的问题； 谈判属性的确定，即针对商品或服务的哪些方面进行谈判； 谈判效率的提高，即如何在尽可能短的时间内找到最优交易； 交易方案的选取，即如何从多个谈判者中选择一个来达成交易。 本文模型根据谈判者偏好难以确定的问题，采用模糊数学中的正态分布函数 进行效用的表达，采用双方接受度乘积的形式来计算适应度，这样在一定程度上 避免了目前采用的线性加权方法的弊端，同时为了提高遗传算法的收敛速度，本 模型采用了动态的选择概率和变异概率，使得具有较大适应度的个体在下一代中 具有更大的存活可能性，同时为了在下一代中获得更加多样的个体，模型加大了 交叉概率，另外，本文的竞争机制模型引入了竞争机制，将上一代中所有的针对 每个卖方形成的最优方案同时放到下一代中的每一个卖方的染色体编码中的办 法，体现多个卖方之间的竞争关系，因此本模型既考虑了谈判双方的合作关系， 同时也考虑了谈判多方之间的竞争关系。在选取最终交易时，模型给出了针对每 个谈判多方的最优交易，供谈判一方进行选择；本文的报价一反报价模型通过贝 叶斯学习机制动态的学习对方的款项的权重，不断更新对权重的猜想以期获得对 己方最有利的交易。本文最后给出了竞争机制模型的仿真结果，并进行了详细的 分析，同时为了体现模型的合理性，本文还进行了对比仿真。 1 4 本文组织结构 本文首先给出本文的选题背景和选题意义，以及国内外对自动谈判系统的研 究现状，介绍了谈判的定义，一对多、多属性谈判的定义及特点分析，详细阐述 了目前一对多、多属性谈判的研究现状，同时给出了多属性效用理论。 然后，本文介绍了模型中所使用的主要的几种学习机制，重点讲述了遗传算 法学习机制和贝叶斯学习机制，阐述了这两种学习机制的原理及应用过程，指出 了其在模型中的作用和意义以及实现过程，并且指出了模型中使用的竞争机制， 北京t 业人学硕i ：学位论文 曼曼皇曼曼曼曼! 曼曼曼曼曼曼曼曼量曼曼皇曼曼曼曼曼曼曼曼曼舅曼曼曼寰曼曼尝曼曼曼曼曼皇曼曼曼曼曼曼曼曼皇曼曼皇曼曼曼曼曼量曼曼曼曼曼曼曼曼鼍i i i 舅 给出了竞争机制的核心。 接下来，在前文的基础上，详细阐述了基于g a 的一对多、多属性谈判模型 的设计过程，并利用s w a r m 平台进行了模型的仿真，并对仿真结果进行了分析， 同时为了更清晰的表明模型的合理性，给出了模型对比仿真的结果和分析。 最后，对本文模型进行了全面的总结，指出了模型的不足以及对此课题进一 步研究的方向。 第2 章自动谈判理论 第2 章一对多多属性自动谈判 2 1 谈判及自动谈判 2 1 1 谈判的定义 谈判是一个被广泛讨论的课题，许多领域的研究者都在从事相关问题的研 究，经济学、社会科学、心理学、博弈论、谈判支持系统、代理技术、机器学习 等领域都有涉及。人们会在许多不同的领域进行谈判，法律问题、国际争端、家 庭事务、会议安排、产品计划、购买产品等都离不开谈判。本文着重讨论的是电 子商务环境下的涉及交易过程中的自动谈判问题h 习。 不同研究人员根据各自的理解和研究兴趣对谈判概念给出了不同的描述h 町： ( 1 ) 提出合同网( c o n i r a c t n e t ) 的s m i t h 和d a v i s 认为“谈判是有兴趣的各 方交换信息并达成妥协一致的过程”，并认为谈判是对问题求解者进行有效任务 匹配的组织原理。 ( 2 ) p r u i t t s 给出了基于社会心理学的解释“谈判是双方或多方做出联合决定 的过程。各方首先交换不一致意见，然后通过互相让步或寻求新的方法达成协 议”。 ( 3 ) s y c a r a 认为“谈判是指利用通信或通过推断系统中其他a g e n t 的状态 和意图识别a g e n t 间可能的相互作用，并通过改变其他a g e n t 的意图避免a g e n t 间的有害相互作用从而建立合作 。 ( 4 ) d u r f e e 等人认为“谈判是a g e n t 间利用相关信息的结构化交换形成一 致公共观点或规划的过程，即一组自治a g e n t 协调它们的观点及动作达到系统目 标的过程”。 ( 5 ) k r a u s 对谈判的定义是“谈判是a g e n t 对交换各自的期望并折衷妥协以 得到相互满意的协定的过程。 ( 6 ) j e n n i n g s 等人认为“谈判可以看作是对谈判空间的分布式搜索，该空间 由所有达成一致的提议构成。谈判空间的维数和拓扑结构是由谈判主题的结构确 定的，可以认为谈判主题的一个议题和该空间的一个维相关，在谈判过程中谈判 议题值的变化意味着谈判空间维数及该空间内点的数量的变化，a g e n t 对某个议 题的值的修改意味着它在谈判空间内从一个点移动到另一个点 。 从人工智能角度可以将自动谈判描述为：谈判是多个a g e n t 对某个或某些议 北京t 业人学硕 ：学位论艾 题共同搜索可能的合同空间，以达成相互可能接受的合同的一种决策过程。 在此，本文对自动谈判概念作以下总结：自动谈判是一组自治a g e n t 为了某 个或某些与利益相关的议题相互进行通信而达到一致的过程。它是多a g e n t 系统 中实现协同、协作、冲突消解和矛盾处理的一种重要交互形式。谈判的议题可以 是价格、数量、质量和交货时间等等。这些议题构成了一个合同，谈判双方a g e n t 通过轮流提议，即修改合同中不满意的议题值，从而谈判双方达成一致，即形成 一个双方都认可的合同h 2 j 。 2 1 2 谈判的目的 谈判的直接原因是因为参与谈判的各方有自己的需要，或者是自己所代表的 某个组织有某种需要，一方需要的满足可能会涉及和影响他方需要的满足。任何 一方不能无视他方的需要。因此，谈判的目的就不仅仅只在于追求自己的需要， 而是应该通过交换提议进行磋商，共同寻找双方都能接受的方案。谈判不是无限 制地满足自己的利益，而是有一定的利益界限n 3 。 2 1 3 谈判发生的条件和过程 谈判者之间是既竞争又合作的关系，谈判双方必须存在谈判的可行区域。国 外谈判专家认为谈判应遵循“双赢原则 ( w i n w i n ) h ，双方在谈判中都应 能获益。如果只是一方获胜、一方牺牲则失败的一方必会寻求一切机会来推翻协 议，导致谈判无效。 2 2 一对多多属性谈判问题描述 一对多、多属性谈判问题是谈判问题的一个重要分支，并且一对多、多属性 谈判更符合实际情况。本节给出了一对多、多属性谈判的定义，并与其他类型谈 判进行对比，分析了一对多多属性谈判的特点。 2 2 1 一对多多属性谈判的定义 对于自动谈判问题的研究，根据谈判参与者的数量将其划分为“射： 一对一谈判，即谈判双方均为一个参与者，此时由于双方之间只存在合作关 系，所以对于此问题的研究考虑的问题较少，也相对简单。 第2 币自动谈判理论 一对多谈判，即谈判双方中的某一方为一个参与者( 以下称为谈判一方) 而 另一方则有多个参与者( 以下称为谈判多方) ，此时谈判一方与谈判多方中的每 个参与者之间是和作关系，而在谈判多方之间则存在竞争关系，因为谈判一方只 可能与谈判多方中的某一个谈判者或部分谈判者达成交易，从而获取最大利益。 所以对于一对多谈判的研究，不仅要考虑到谈判双方的合作关系，更要分析谈判 多方之间的竞争关系! 多对多谈判，即谈判双方均为多个参与者的情况，此时的情况就更为复杂了， 因为相比较前两种谈判而言，此时每一个谈判者都存在合作和竞争关系，要进行 全面的考虑和衡量。 根据谈判所涉及的属性我们又可以将自动谈判划分为： 单属性谈判，即谈判双方就商品或服务所涉及的某一方面进行协商，比如价 格，服务等，在谈判时，他们只关注单一的一个方面，而不考虑其他因素。此种 情况只有在特殊情况下才会发生，对于单属性谈判的研究也相对简单。 多属性谈判，即谈判双方同时考虑商品或服务的多个属性，希望获得总体效 益的最大化。例如我们在购买商品时我们会希望价格最低同时质量最好，服务最 优等。由于目前市场的激烈竞争，是一种买方市场的状态，所以消费者具有更多 的要求和选择权利，因此对以多属性谈判的研究更符合实际情况。 上述分类标准可以进行组合，例如对以一对一谈判，我们可以只涉及商品的 某一个属性，即一对一、单属性谈判，当然我们也可以考虑多个属性，即一对一、 多属性谈判，同比类推。因此一对多、多属性谈判即为某一谈判者与诸多竞争谈 判者就商品的多个属性同时进行谈判，最终由谈判一方选择最优交易的谈判。正 如前文所述，此种谈判更符合实际情况，因此对以一对多、多属性谈判的研究更 具现实意义。 2 2 2 一对多多属性谈判的特点 一对多谈判与一对一谈判相比，有着其独有的特点h 朝： 谈判者数量不同，这点比较明显，一对一谈判谈判双方都是单一的参与者， 一对多谈判则有一方有多个参与者。 谈判者之间关系不同，一对一谈判在两个谈判者之间展开，通常，谈判双方 表现为合作关系，即双方要采取合作的态度才能最大化其自身效用。不能合作 的双方只能接受冲突的结局，这种结局对双方来说都是没有效率的。可以说两方 谈判的目的在于促进合作。一对多谈判是在谈判一方和谈判多方之间展开的。谈 判一方与每一个谈判多方之间表现出合作的愿望，而谈判多方之间则是竞争关 系。一对一谈判的合作是在谈判者明确合作对自己有利的前提下通过相互的逐渐 北京丁业人学硕f ：学位论文 让步达成的。而一对多谈判中谈判一方与谈判多方的合作是在谈判多方之间的竞 争中实现的。 协同谈判h 棚是一对多谈判的又一种形式。这类谈判是在供应链上的各个企业 展开的。谈判者通过谈判协调各自的供销需求，实现供应链上资源分配的优化。 协同谈判中，供应链上的每个企业即谈判中的谈判者与其他谈判者的利益是密切 相关的，只有通过合作在实现整个供应链上资源分配最优化的前提下才能使实现 其自身效用的最大化。这类谈判仅体现出合作关系，现实中，往往以会议的方式 进行。而本文中的一对多谈判中的谈判方根据供求关系很清楚地分为一方和多方 两类， 两类谈判者之间在争取合作，多方之间则表现为竞争。谈判并不是要实 现对所有谈判者效用整体最优，而仅仅是用这种合作和竞争使多个谈判者中的 两个实现自身效用最优。 拍卖及反向拍买是一对多谈判的特例。拍卖及反向拍卖中的参与者也可以根 据供求关系分为一方和多方两类h 5 1 。但在拍卖和反向拍卖中，一方与多方不 存在合作关系，一方只是被动地按照某一原则接受多方竞争结果。这与一对多谈 判中谈判一方表现出与谈判多方合作的愿望是不同的。 下表给出了一对多谈判与上述这些谈判模式的区别h 2 1 表2 - 1 一对多谈判与其他谈判的比较 t a b l e2 - 1t h ed i f f e r e n c e sb e t w e e no n e - t o - m a n yn e g o t i a t i o na n do t h e r s 谈判模式谈判者数量 谈判者类别谈判者之间的关系 一对多谈判 22 同类竞争，不同类合作 一对一谈判 = 22 合作 协同谈判 2 2 合作 拍卖与反向拍卖 22 同类竞争，不同类被动合作 双向拍卖 22 同类竞争，不同类被动合作 与单属性谈判形式相比，多属性谈判常常表现得更为复杂，因为单属性的谈 判过程中对报价的评估是明确的，例如以价格为例，对于买方来说价格越低越好， 对于卖方来说价格越高越好。而多属性谈判报价是由多个属性取值组成的一个向 量，而且各个属性之间并不能保证是完全独立的，这样对报价评估来说是不容易 做到的，尤其是在一对多谈判这种形式下，谈判一方如何比较各个谈判多方的报 价做出评价是很困难的，目前对多属性的报价评估常采用的多属性效用理论。另 外很多专家提出了遗传算法等学习机制来给出多属性谈判的谈判解。 2 2 3 多属性效用理论 多属性效用理论h 7 1 ( m u l t i a t t r i b u t eu t i l i t yt h e o r y ，m a u t ) 起源于j b e n t h a m 第2 荦自动淡判理论 ( 1 9 4 8 年) ，起初是个人之间偏好比较的一种工具：后来，效用函数扩展应用于 消费的需求理论和经济学及私人和公共政策问题的研究。在多属性效用理论中， 效用被用来描述偏好。效用函数对商品要谈判的属性计算一个效用值，消费者总 是偏好效用值更大的商品。在影响效用值的属性不止一个时，m a u t 主要是通 过效用分解程序，将评估多属性效用函数的多维复杂问题简化为评估一系列单一 属性效用函数的有限维独立、相关问题，求取近似单维效用函数及权重，再运用 适当的模式形态整合成多维的效用函数，进而以多属性效用值作为标准来进行多 目标决策，简单情况下可以用加权求和的方法求得整体效用值呻1 。目前，多属性 效用理论在基于a g e n t 的多属性自动谈判方面常用来评价对商品的报价h 6 】，本文 中也是采用多属性效用理论来计算双方的接受度的。 m a u t 是一种量化决策分析方法h 铂h 引，主要用来评价对最终结果起作用的 各个因素对各种选择的影响，确定最佳选择方案。该方法实施步骤如下： ( 1 ) 确定各个决策对象； ( 2 ) 确定需评价的对决策过程有贡献的各个因素； ( 3 ) 确定用来评价各因素的因子； ( 4 ) 评估各因素与各因子的权重； ( 5 ) 计算每个决策对象的各因素得分并求和； ( 6 ) 选择最大总得分的决策对象； ( 7 ) 进行敏感性分析。 2 3 一对多多属性谈判模型研究现状分析 按谈判机制中谈判参与者数量的不同，谈判活动可以分为：一对一谈判、一 对多谈判、多对多谈判m 儿鲫1 。并且按照谈判所涉及的属性的多少可以分为单属性 谈判和多属性谈判，本文就是在深入分析目前一对多谈判现状的基础上，对一 对多、多属性谈判进行研究，以期设计出合理的谈判模型。 对于一对一谈判的研究已经很多，也较为成熟，而对于一对多谈判尤其是多 属性的谈判才刚刚起步。 孙天昊，朱庆生隋朝重点研究了一对多协商中对多个并发的一对一协商进行协 调的协调策略，首先提出了相对效用理论，接着提出了基于相对效用理论的一对 多协商协调策略，该策略能够很好地解决当多个并发协商进程同时获得满足效用 评估的提议，特别是存在多个最大相同效用提议时的取舍问题，为协商更加有效、 健壮、有序地执行提供了坚实的基础，但该模型中买卖双方的地位是不平等的， 不满足商务交易公平性原则。 张谦，邱玉辉钉利用相似度来评价和一种双边多议题多a g e n t 并发协商策 北京t 业犬学硕卜学位论史 略，一方面使用相似度函数来计算对手的偏好模型，从而选择相应的协商策略， 另一方面协商一方采用该策略后能够使得对