（计算机软件与理论专业论文）基于依赖关系的多议题协商模型研究.pdf

郑州大学硕士学位论文 基于依赖关系的多议题协商模型研究 摘要 i n t e r n e 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 s ，m a s ) 也正在成为人工智能研究和分布式软件 智能化的重要技术。多议题协商问题是m a s 研究中的一个重要问题，在现实世 界中各议题之间往往存在着依赖关系，多议题协商中的依赖关系一直是近年来协 商问题研究中的重点和难点。 本文所研究的多议题协商是一种多议题多取值协商，协商中涉及到多个议 题，每一议题取值离散且允许存在多个取值，两两议题取值之间存在依赖关系。 由于在多议题协商中考虑了单个议题的多取值问题和不同议题取值之间的依赖 关系问题，使得基于依赖关系的多议题多取值协商问题研究的重点和难点转变成 了如下问题的解决：议题取值之间依赖关系的定义；议题之间依赖度( 依赖 关系强度) 度量公式的定义；协商中议题之间依赖关系的形式化表示；该协 商背景下的协商a g e n t 的提议产生机制协商a g e n t 效用函数的表示；协商 a g e n t 对协商对手非线性效用函数的学习；基于该协商背景下的协商优化问题。 本文基于扩展后效用图和g a i 网来研究多议题多取值协商中的依赖关系， 用条件概率来表示和衡量议题取值之间的依赖关系与议题之间的依赖度；在协商 过程中，通过强化己方策略机制和大量反复的协商，协商a g e n t 使用人工神经网 络学习算法学习并获得协商对手的非线性效用函数；最后，协商a g e n t 使用关联 组合优化算法r c o a 对协商进行优化，以获得使协商结果达到较好p a r e t o 最优 结局的提议；实验表明在多议题多取值协商当中，协商a g e n t 能较好地学习到各 个议题间的依赖关系和依赖强度；通过强化自身的策略机制，卖方a g e n t 能较好 地获得买方a g e n t 的非线性效用函数；r c o a 算法是有效的，并且具有较好的全 局和局部搜索能力。 关键词：多a g e n t 系统；多议题多取值；依赖关系； 依赖度；关联组合优化算 法 郑州大学硕士学位论文 a b s t r a c t t h er a p i dd e v e l o p m e n to fi n t e r a c th a sg r e a t l ya f f e c t e dt h ec o n v e n t i o n a lm e a n so f o p e r a t i n gb u s i n e s s c u r r e n t l y , t h ea g e n t - b a s e de - c o m l n e r c er e s e a r c hh a sb e c o m i n ga h o t s p o t a g e n ta n dm u l t i a g e n ts y s t e m ( m a s ) a r eb e c o m i n gt ob eo n eo ft h em o s t i m p o r t a n tt e c h n i q u e s i nt h er e s e a r c ho na r t i f i c i a l i n t e l l i g e n c e a n dd i s t r i b u t e d i n t e l l i g e n ts o f t w a r e m u l t i i s s u en e g o t i a t i o nh a sb e c o m e 觚i m p o r t a n ti s s u eo ft h e m a sr e s e a r c h e s i nt h er e a l i t ym u l t i - i s s u en e g o t i a t i o n ，t h ed e p e n d e n c i e so f t e ne x i s t a m o n gs o m en e g o t i a t i o ni s s u e s ，a n dt h ed e p e n d e n c i e sa m o n gm u l t i - i s s u e sn e g o t i a t i o n h a v eb e e nt h ek e ya n dd i f f i c u l ti t e m s ，i nr e c e n ty e a r s t h em u l t i - - i s s u en e g o t i a t i o nr e s e a r c h e db yt h i sp a p e ri sak i n do fm u l t i i s s u ea n d m u l t i - v a l u en e g o t i a t i o n t h e r ea r em a n yi s s u e si nt h en e g o t i a t i o n e a c hi s s u ei s s c a t t e r e da n dc a nh a sm a n yd i f f e r e n tv a l u e s ，a n dt h ed e p e n d e n c i e se x i s t sb e t w e e n d i f f e r e n ti s s u e s s i n c ei nt h em u l t i i s s u en e g o t i a t i o no n ei s s u ec a nh a sm a n yv a l u e s a n dt h ed e p e n d e n c i e se x i s ta m o n gd i f f e r e n ti s s u e v a l u e s ，t h ep r i o r i t ya n dd i f f i c u l t p o i n to ft h er e s e a r c ho fm u l t i - i s s u ea n dm u l t i - - v a l u en e g o t i a t i o nc a nt r a n s f o r mi n t oa s f o l l o w st h ep r o b l e m ss o l v i n g ：t h ed e f i n i t i o no ft h ed e p e n d e n c i e sa m o n gd i f f e r e n t i s s u e v a l u e s ； ) t h ed e f i n i t i o no fm e a s u r e m e n tf o r m u l ab e t w e e nd i f f e r e n ti s s u e s ； ( 重) f o r m a l i z e dd e s c r i p t i o no fd e f i n i t i o na m o n gd i f f e r e n ti s s u e s ；o f f e rp r o v i d i n g m e c h a n i s mo fn e g o t i a t i o na g e n tb a s e dt h en e g o t i a t i o nb a c k g r o u n d ；t h ee x p r e s so f n e g o t i a t i o na g e n t st h en o n l i n e a r i t y su t i l i t yf u n c t i o n ；t h el e a r n i n go ft h eo p p o n e n t s t h e n o n l i n e a r i t y su t i l i t yf u n c t i o n ；t h en e g o t i a t i o no p t i m i z a t i o n b a s e dt h e n e g o t i a t i o nb a c k g r o u n d w er e s e a r c ht h ed e p e n d e n c i e si nt h em u l t i - i s s u e s 、m u l t i v a l u e sn e g o t i a t i o n ，b a s e d o nt h ee x p a n d e du t i l i t yg r a p ha n dg a i n e t w o r k ，u s i n gc o n d i t i o n a lp r o b a b i l i t yt o s h o wt h ed e p e n d e n c i e so fd i f f e r e n ti s s u e v a l u e sa n dt oc a l c u l a t et h ed e p e n d e n c i e s d e g r e eo fe v e r yt w od i f f e r e n ti s s u e s ；d u r i n gt h ep r o c e d u r eo fn e g o t i a t i o n ，t h e n e g o t i a t i o na g e n tu s e sa r t i f i c i a ln e u r a ln e t w o r k sl e a r n i n ga l g o r i t h mt oo b t a i nt h e o p p o n e n t st h en o n l i n e a r i t y su t i l i t yf u n c t i o n ；f i n a l l y , t h en e g o t i a t i o na g e n tu s e st h e i i 郑州大学硕士学位论文 r e l a t e d - c o m b i n a t o r i a lo p t i m i z a t i o na l g o r i t h m s ( r c o a ) t og e tab e t t e ro f f e rw h i c h m a k e st h en e g o t i a t i o nh a sap a r e t o o p t i m a l i t ya g r e e m e n t sb ys t r e n g t h e n i n gn e g o t i a t i o n a g e n t ss t r a t e g ym e c h a n i s ma n dl o t so fn e g o t i a t i o n s e x p e r i m e n t a lr e s u l t ss h o wt h a t ， i nm u l t i i s s u ea n dm u l t i v a l u e n e g o t i a t i o n ，n e g o t i a t i o n - a g e n t c a nl e a r nt h e d e p e n d e n c i e s a n dd e p e n d e n c i e sd e g r e ev e r yw e l l b ys t r e n g t h e n i n gs e l f - s t r a t e g y , t h e s e l l e r - a g e n tc a nl e a r nt h en o n - l i n e a ru t i l i t yf u n c t i o n so fb u y e r - a g e n tb e r e r t h e r o c a a l g o r i t h mi se f f e c t i v e ，a n dh a sag o o do v e r f l l l o c a ls e a r c h i n ge f f e c t i v e 。 k e yw o r d s ：m u l t i - a g e n ts y s t e m ；m u l t i i s s u e a n dm u l t i - v a l u e ；t h e d e p e n d e n c i e s ；t h e d e p e n d e n c i e sd e g r e e ；r e l a t e d - c o m b i n a t o r i a lo p t i m i z a t i o na l g o d t h m s ( r c o a ) i i i 郑州大学硕士学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律责任由本人承担。 学位敝作者：谷明厝咽 醐：2 0 0 9 年5 月2 0 日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学 可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印 或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文 或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。 保密论文在解密后应遵守此规定。 学位论文作者：谷明 居咱 r 期：2 0 0 9 年5 月2 0 日 郑州大学硕士学位论文 1 1 研究背景 第一章绪论 多议题协商问题是m u l t i - a g e n t 系统( m a s ) 研究中的一个重要问题，其研究 主要是在多议题效用理论【1 2 , 3 , 4 1 ( m a u t ) 的基础上进行的，即假设各个议题之间是 相互独立的。但是现实世界中，各个议题之间往往存在依赖关系，这种依赖关系 无疑会增加多议题协商问题研究的复杂度。近年来，研究者们提出了一些多议题 依赖协商问题的解决方法。例如，m a e kk l e i n 等人【5 l 首次将多议题依赖引入到多 议题协商模型中，协商a g e n t 使用模拟退火和爬山搜索方法搜索p a t a t o 最优解。 k o e nv h i n d r i k s 等人【6 j 利用一种加强平均技术对议题间的依赖度进行削减，从 而简化了协商a g e n t 效用空间的复杂性。g u o m i n gl a i 等人【7 1 在协商a g e n t 具有 非线性偏好( 即考虑议题间的依赖关系) 的条件下，利用基于协商基线的协商协 议对多议题协商模型进行了研究。v a l e n t i nr o b u 等人【8 】提出了基于效用图的多 议题协商模型，该模型利用效用图表示买方a g e n t 非线性偏好并利用图形结构特 点大大降低了多议题依赖协商问题的复杂性，随后v a l e n t i nr o b u 等人【9 , 1 0 提出 了通过合作过滤方法来学习多议题协商中效用图的结构，最后v a l e n t i nr o b u 等人【】在自动供应链协商中应用了这种学习方法并且证实它的有效性，但是该模 型仅研究了买方a g e n t 具有线性可连加效用且协商议题取值为0 、i 的二值议题 协商问题，而对协商中的依赖关系也仅仅研究了各个议题问有无依赖关系，同时 没有对协商中的依赖关系提出严格的定义和度量公式。在实际的协商当中，协商 议题大多是多取值的，并且各个议题的各个不同取值之间也常常存在着依赖关 系，同时买方a g e n t 的效用往往也是非线性的。 g o n z a l e sc 等人【挖】提出了基于g a i 网的多议题协商模型，每个议题允许有 多个( 大于2 个) 取值，考虑了多议题协商中的多元依赖关系，且刻画了协商 a g e n t 的效用函数与各个议题效用之间的线性求和关系，但文章假定协商中关联 议题之间的效用函数为线性可迭加的，没有刻画议题取值之间的二元依赖关系且 并未对协商中依赖关系提出严格的度量公式，但是现实生活中的多议题协商中关 联议题之间的效用函数一般都是非线性的，这无疑限制了 1 2 的协商模型的适用 郑州大学硕士学位论文 范围。 本文研究的多议题多取值协商是一种特殊的多议题协商问题，协商中涉及到 多个议题，议题取值离散且取值个数可以大于2 ；同时，不同议题取值之间还存 在着一定的依赖关联关系。协商议题取值组合涉及到基于依赖关系的关联组合优 化问题，由于其复杂性，该问题构成了基于依赖关系的多议题多取值协商中的一 个重点和难点问题。最终，基于依赖关系的关联组合优化问题的解决直接关系到 这类协商的成败与协商效果。 文献 1 3 ，1 4 把遗传算法引入到了组合优化问题，并最终取得了较好的搜索 效果，但是 1 3 ，1 4 中所涉及到的组合问题，两两组合间无关联关系且优化的目 标仅仅是单目标，而本文基于依赖关系的多议题多取值协商中的组合优化则是一 个复杂的、多目标的基于依赖关系的关联组合优化问题。 1 9 8 4 年，s c h a f f e r 1 5 】对多目标遗传算法作了开创性工作，第一次把遗传算 法引入到多目标寻优问题中来，将多个优化目标通过加权和形成单一目标来进行 优化。至今为止，国内外已有大量基于多目标优化问题的多目标遗传算法出现， 例如国外的m o g a 16 1 ，n s g a 1 7 1 ，n s g a i i 1 8 1 ，n p g a 19 1 。m o g a 算法执行简单且全 局搜索效率高，但是算法容易受小生境大小影响；n s g a 中的优化目标个数可以 任选，非劣最优解分布均匀，允许存在多个不同等效解，但是是由于p a r e t o 排序 要重复多次，计算效率较低，计算复杂度为o ( m n 3 ) ( 其中m 为目标数量，n 为 种群大小) ，未采用精英保留策略，共享参数os h a m 需要预先确定；n s g a i i 算法 采用了借助外部种群的精英保留策略，并且在进化中引入了拥挤距离，但对于每 个解，需要确定多少解支配它和它支配的解集，运算烦琐，实际应用困难；n p g a 将传统的算子改进为基于p a r e t o 优劣的比武选择策略，能很快的找到一些好的 非劣最优解域，并能维持一个较长的种族更新期，但需要设置的参数多，还需要 选择一个适当的锦标赛规模，限制了算法的实际应用效果。国内大量的研究主要 集中于这些经典的多目标遗传算法在各个领域内的具体应用和改进，例如文献 2 0 ，2 1 在各自的应用领域内对所采用的多目标遗传算法做出了一些具体的改 进，从而在相应的问题域内取得了很好的效果。概括起来，所做的改进主要包括 以下几个方面：初始群设定的改进适应度函数设定的改进遗传算子操作的 改进进化策略的引入等，但是改进后算法的局部搜索能力仍然较差。 2 郑州大学硕士学位论文 1 2 研究内容 针对基于依赖关系的多议题协商所存在的不足，本文使用统计概率方法描述 和度量议题取值之间的依赖关系和依赖度；使用扩展后的效用图表示议题取值和 议题之间的二元依赖关系，使用扩展后g a i 网表示和刻画议题之间的多元依赖关 系以及协商a g e n t 的效用函数与各个簇【8 , 9 , 1 0 所对应的子效用函数的线性求和关 系。由于簇内的子效用函数是非线性的，则整个协商a g e n t 的效用函数仍然是非 线性的；使用确定性有穷自动机来刻画基于依赖关系的多议题多取值协商中协商 b u n d l e 8 】的产生机制，并称之为b - d f a ；使用复合映射算子将多维空间离散点转 换为二维空间离散点，并使用人工神经网络学习算法学习获得买方a g e n t 的非线 性效用函数( 云) ( 云【8 ，9 ，1 0 】表示b u n d l e 取值向量，b 表示买方) 。 最后，针对多议题多取值协商中基于依赖关系的关联组合优化问题，本文提 出了适合于解决该类问题的关联组合优化算法( r e l a t e d c o m b i n a t o r i a l o p t i m i z a t i o na l g o r i t h m sr c o a ) ，该算法基于传统多目标遗传算法【1 3 1 9 】的一些 进化思想，引入了概率分布评估机制，选择概率的动态调整因子一和单点变异 策略，以提高算法的搜索能力。实验表明，该关联组合优化算法适合于解决多议 题多取值协商中的议题取值关联组合优化问题，并且在一定的进化阶段取得了较 好的搜索效果。 1 3 论文结构 本文结构安排如下： 第一章绪论 在本章中，介绍了多议题多取值协商的依赖关系研究的研究背景、研究内容 和论文结构。 第二章多议题协商综述 在本章中，介绍了a g e n t 的定义和m a s 的特性和应用；简要介绍了3 个多议 题协商模型：m a s 中多议题协商交互模型、基于效用图的协商模型和基于g a i 网 的协商模型；简要介绍了k & s 中常用的协商策略，人工神经网络学习算法，多目 标优化问题和一些经典的多目标遗传算法。 郑州大学硕士学位论文 第三章基于依赖关系的多议题多取值协商模型 详细定义了依赖关系和依赖度的度量公式，使用有限自动机严格地描述了考 虑依赖关系的多议题多取值协商中协商b u n d l e 的产生机制，对效用图和g a i 网 进行了扩展，并详细论证了基于依赖关系的多议题多取值协商中协商a g e n t 非线 性效用函数的产生原因和具体表示。 第四章多议题多取值协商中协商策略和学习算法的研究 本章详细了介绍了卖方a g e n t 的谨慎表态策略和对买方a g e n t 非线性效用函 数的学习，学习的过程中采用了复合映射算予技术；详细介绍了基于依赖关系的 关联组合优化算法以及该算法中所采用的概率分布评估机制、选择概率的动态调 整因子一和单点变异策略。 第五章实验及分析 本章主要是对第三章和第四章中结论、协商策略和关联组合优化算法进行试 验论证，并详细地进行了对比分析，最后经过试验验证了本文对效用图和g a i 网改进是可行性，协商策略和关联组合优化算法的有效性。 第六章总结和展望 对本文进行了总结，提出了下一步需要进行的工作。 4 郑州大学硕士学位论文 第二章多议题协商综述 2 1 a g e n t 的概念和特征 a g e n t 的概念源于人工智能学科，最早出现于上个世纪7 0 年代并于8 0 年代 后期得到深入研究。随着计算机网络、计算机通信等技术的发展，特别是i n t e r n e 和w o r l dw i d ew e b 的普及，对于a g e n t 以及多a g e n t 系统的研究己成为分布式 人工智能( d a i ) 研究的一个热点。 m i n s k y 2 2 1 在1 9 8 6 年出版的“思维的社会 中提出了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 d g e 和j e n n i n g s 2 3 】认 为a g e n t 应具有自主性、社会交互性、反应能力和预动能力。r u s e ll 认为a g e n t 能通过感知环境，并做出动作。h e w i t t 认为定义a g e n t 与定义什么是智能一样 的困难。 2 1 1a g e n t 的定义 目前，对于a g e n t 的严格定义，人们并没有一个普遍接受的说法，一般说讲， 以下一些定义表达了a g e n t 应具备的一些基本能力： 1 a g e n t 就是一种计算机系统，它能适应一定的环境，且能根据环境自发行动， 以达至u a g e n t 自身设计的目的f 2 4 】。 2 a g e n t 就是一种能够通过传感器感知环境信息，并且对环境施加一定影响的 事物f 2 5 】。 3 a g e n t 就是一种处于复杂动态环境中的计算系统，为了实现设计目标、任务， 它能够感知并影响自身所处的环境【2 6 1 。 2 1 2 多a g e n t 系统的特性及应用 自7 0 年代后期至今，伴随着计算机网络、计算机通信以及并行程序设计技 术的发展，分布式人工智能d a i ( 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 i l c e ) 的研究及应用逐 郑州大学硕士学位论文 渐成为一个热点，早期的研究主要为分布式问题求解，目标是建立大粒度的协作 群体，他们之间协同工作以对某一问题进行求解；9 0 年代，多a g e n t 系统 m a s ( m u l t i a g e n ts y s t e m ) 的研究已成为分布式人工智能的一个热点，实际系统中 的分布性、负载性和动态性有望通过对单个个体能力的有效分工、协调和组织以 达到对系统进行整体优化的目的。 多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 7 】：( 1 ) 每个a g e n t 具有解决问题的不完全信息或能力；( 2 ) 没有系统全局 控制；( 3 ) 计算是异步的；( 4 ) 数据是分散的。 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 中的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 d 尸a g e n t 的目 标并不能保持完全一致，有时还有可能相互抵触，某个a g e n t 在追求自身目标最 大化的同时，有可能就损害了其它a g e n t 的利益。 随着m a s 研究的深入，自8 0 年代中期至今，m a s 的实际应用也越来越广泛， 涵盖了敏捷制造【2 8 】、过程控制【2 9 1 、交通控制【3 0 】和信息处理【3 1 1 等领域。 2 2 多议题协商模型综述 2 2 1m a s 中多议题协商交互模型 m a s 中多议题协商模型t 4 3 2 】( m u l t i i s s u en e g o t i a t i o nm o d e lm i n m ) 可 以用如下一个1 0 元组来表示，即m i n m = ( ，i ，x ，c ，u ，t ，形，g a s ，p r o ，a c t ) ，其 中： z - - z 占+ s 是协商a g e n t 的集合，其中口= 且9 - 0 - 9 吃) 为买方旭e n t 集合， 6 郑州大学硕士学位论文 p 为买方a g e n t 的个数；s = 墨，& 为卖方a g e n t 集合，g 为卖方a g e n t 的个数。 ，= ，厶) 是协商议题集合，其中议题总数为n 。 x = 五，也) 是各个议题取值的值域集合，其中置是议题，的值域且取 离散值。 c = g + g 是协商中所有簇的集合，其中g = c l ，c k 和g = c i ，c r ) 分 别是协商中a g e n tb 和a g e n ts 簇的集合 u = ，u s 是协商a g e n t 效用函数组成的集合。= u ( 云) 一风( 云) ， 虬= 一。= n 一鼢r ( 云) 或u s = 蝴一一= u ( 云) 一c f ( 云) 且 叼抽，u ， 蜉“，町x 。p bl o s 尸分别表示a g e n tb 和a g e n t s 对议题取值向量云提出的标价，p 是所有标价组成的集合。 t = r f f l n t n ，五) 是整个协商过程的最后期限，乃是a g e n tb 协商最后期限，五 是a g e n ts 协商最后期限。 = wlie 1 ，l ) ，w 是a g e n t 为协商议题f 所赋的一个权值，0 - w 一 - + 坼，且i j 则称议题i 和议题j 之间的关系为可补充关系，并用符号+ 表示。 定义2 5 ( 可替代关系8 9 1 ) 如图1 所示，如果一 + 吩，且i j 则称议题i 和议题i 之间的关系为可替代关系，并用符号一表示。 图2 1 效用图 基于效用图的多议题协商模型的主要优点是能直接的表示议题之间的二 元依赖关系：能具体的表示议题之问的二元依赖关系的积极作用( 可补充关系) 或消极作用( 可替代关系) 。主要缺点是：议题的取值只能取0 或l 不能表 示议题之间的多元依赖关系改协商模型假设协商的效用函数是线性可迭加的， 限制了该协商模型的使用范围。 郑州大学硕士学位论文 2 2 4 基于g a i 网的多议题协商模型 定义2 6 ( 议题集合及其取值向量4 1 ) l - - f , ，厶 表示协商议题集合，其中n 表示协商议题的个数。x = ( x 1 ，毛) 表示关于议题集合啪一个取值向量，其中， 喊ei ，以表示议题l 的一个取值，以表示议题l 取值的值域，表示 第m 个议题的第k 个取值。 定义2 7 ( g a l 分解1 3 3 ) 设z = 兀：五，厶是集合，= 厶，l ) 的忌个子集 且u ：。v f ，l - - j 时，协商买卖双方都是自私的，即离线协商的过程中a g e n tb 和 a g e n ts 都采用局部让步策略。 如果买方的叫价是递增的，且a g e n tb 的叫价策略是时间让步策略，a g e n tb 的时间让步策略函数【3 2 】如下： p r i c e t b 。【q 】_ i i l i n ：+ ( f ) ( m a x ：一m i n ：) ；其中， ( r ) = 磷+ ( ，一醚) ( 竺垫笔粤) 万，q c ，。( ，) - ，磷、均是常量。 如果卖方的叫价是递减的，且a g e n ts 的叫价策略函数是时间让步策略和模 拟对手行为策略，其中a g e n ts 的时间让步策略函数( 文献 3 2 ) 如下： p r i c e s 姐砌。【q 】= 砌v s ( 一q s 、t ) ) ( mq s i i l i n ；) 万；其中， ( ，) = + ( t 一硭) ( 竺尘笔掣 万，q 互c ，。( r ) ，、均是常量。 a g e n ts 的模拟对手行为策略函数如下： p r i c e r s ，从。【q = p r i c p ，t - 。i 【c , 1 - ( p r i c e z 【c i - p r i c e r - 【q 】) 且qs c 。 综上，a g e n ts 的叫价策略函数是：p 成p l e 】2r ! * p r i c e s _ 8 ：砌。【q 】+ 郑州大学硕士学位论文 ( 1 一刁) p 慨：圳嘲【q 】；其中，qc _ c ，0 - r - 1 。p r i c e s 占表示第t 个协商回合 买方a g e n t 向买方a g e n t 针对组合q 所提交的叫价。 2 3 2 精英保留策略 定义2 9 ( 精英选择方法0 3 4 1 ) 在遗传算法中，设到第j 代时，群体中口。( ) 为 最优个体。又设a ( j + i ) 为新一代群体，若彳( + 1 ) 中不存在口( _ ，) ，则把口( _ ，) 加 入到a ( j + i ) 中作为a ( j + 1 ) 的第n + 1 个个体，n 为群体的大小。 由定义2 9 知，精英选择方法主要是针对遗传算法而提出的，在遗传算法中 采用了精英选择方法的策略，被称为“精英选择”策略，或“精英保留”策略。 在遗传算法运行过程中，由于交叉、变异等遗传操作具有一定的随机性，那 么使用这些操作产生的子代个体有可能优于其父代个体也有可能劣于其父代个 体，因此遗传算法固有的概率随机性就可能影响到遗传算法自身的运行效率和收 敛性。并且r u d o l p h 在文献 3 5 】中也得出了如下结论：对于仅采用选择、交叉和 变异三个遗传算子的标准遗传算法( c a n o n i c a lg e n e t i ca l g o r i t h m ，c g a ) ，如果交 叉概率p c 0 ，l 】，变异概率p m ( 0 ，1 ) ，同时采用比例选择法，那么该c g a 就 不能收敛到全局最优值。 “精英保留”策略的提出是为了防止当前群体的最优个体在下一代发生丢失， 进而导致标准遗传算法不能收敛到全局最优解。精英个体是初始种群进化到当前 为止标准遗传算法搜索到的适应度值最高的个体。采用精英保留的优点是，标准 遗传算法在进化过程中，父代中的精英个体一定不会在其子代中丢失。精英保留 策略对标准遗传算法的全局收敛能力产生了很大的改进作用，r u d o l p h 3 5 】也从理 论上证明了具有精英保留的标准遗传算法是全局收敛的。 2 4 多议题协商中的优化算法 2 4 1 多目标优化问题 多目标优化问趔3 6 1 ( m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m ，m o p ) 是指具 1 2 郑州大学硕士学位论文 有两个或更多目标需要同时优化的问题，且多个目标之间相互制约。m o p 并不局 限于单个解，也可能是多个解的某种折衷或妥协，求解m o p 常归结为求解问题的 p a r e t o 最优解集。多目标优化问题数学描述如下： m i n f ( x ) = e f ( x ) ，五( x ) ，以( x ) s j g t ( z ) ( o ，f = 1 ，2 ，h ，x r ) ( 2 1 ) 其中，z ( 1 f k ) 为目标函数，为约束条件，问题具有1 1 个决策变量、k 个 目标函数和h 种约束。当只有单个目标时，最优解就是在已知约束条件下使目标 函数值最大的解，当多个目标需要同时最优时，最优解就是p a r e t o 最优集。m o e a 常涉及到如下几个基本概念： ( 1 ) p a r e t o 支配( p a r e t od o m i n a n c e ) 解而支配五( 五) ，当且仅当 z ( ) 彳( ) ，v i = l ，2 ，k ；z ( 而) 石( 西) ，9 i l ，2 ，k 。 ( 2 ) p a r e t o 最优( p a r e t oo p t i m a l )解而是p a r e t o 最优组合，当且仅当 毛：五- 4x o 。 ( 3 ) p a r e t o 最优解集( p a r e t oo p t i m a ls e t )所有p a r e t o 最优解的集合： b = i 甄_ ) 。 ( 4 ) p a r e t o 前沿或均衡面( p a r e t of r o n t )所有p a r e t o 最优解所对应的目 标函数值形成的区域，表示为：层2 厂( x ) = ( z ( x ) ，厶( x ) ，六( 工) ) ix 弓) 。 2 4 2 多目标遗传算法 1 9 8 4 年，s c h a f f c r t l 5 】对多目标遗传算法作了开创性工作，首次把遗传算法引入 到多目标寻优问题中，将多个优化目标通过加权求和以形成单一目标优化。1 9 9 3 年，c a r l o sm f o n s e c a 和p e t e rj f l e m i n 提出了m o g a 【1 6 1 ，m o g a 是最具有代 表性的标准多目标遗传算法，优点是执行相对简单且全局搜索能力比较强，缺点 是容易收敛到局部p a r r t o 最优解且局部搜索能力较差。至今为止，国内外已有大 量的多目标遗传算法出现，例如国外的n s g a ，n s g a i i 18 1 ，n p g a 1 9 1 等，都对 m o g a 进行的很好的改进，具有很强的全局搜索能力。 1 3 郑州大学硕士学位论文 m o g a t l 6 】是一个具有代表性的标准多目标遗传算法，其执行步骤与标准的 g a 很相似，主要包括：构建评估函数并初始化各个参数；构建初始群： 迭代执行选择算子；迭代执行交叉算子：迭代执行变异算子。 m o g a 的进化思想与g a 也很相似，是模拟生物在自然环境中的遗传和进 化过程而形成的一种具有自适应概率搜索的全局优化算法。m o g a 操作过程简 单，容易理解。但研究表明m o g a 存在局部搜索能力差等缺陷。其缺陷产生的 主要原因有以下几个： ( 1 ) 进化之前初始群的创建是基于概率随机进行的，不能保证初始群的样本 空间具有良好的概率分布，如果初始群分布过分集中且偏离p a r e t o 最优解很远， 这样就降低了对p a r e t o 最优解搜索的收敛速度。 ( 2 ) 进化过程中选择操作也是基于概率随机进行的，有一定的鲁棒性，但这 种进化缺少一定的控制机制，交叉、变异操作产生的个体是完全随机的，即子代 产生的个体既可能优于父代个体也可能劣于父代个体，从而降低了在优良父代个 体附近区域进行有效搜索的收敛速度。 ( 3 ) 进化过程中，适应度高的个体仅仅执行了复制操作，没有能很好地参与 交叉、变异操作，同样也降低了在优良父代个体附近区域进行有效搜索的收敛速 度。 n s g a t1 7 1 是s r i m i v a s 和d e b 在19 9 4 年提出的，发表在i e e e 的“e v o l u t i o n a r y c o m p u t a t i o n 杂志上。n s g a 基于g o l d b e r g 的建议对个体分类，形成多个层次。 在选择操作之前，个体基于非劣最优解进行排序：所有非劣的个体被分为一类， 并引入决策向量空间的共享函数法，以保持种群的多样性。然后，忽略这些已经 分类的个体，考虑另一层非劣个体；该过程一直持续，直到将所有个体分类。由 。 于第一个p a r e t o 前沿中的个体具有最大的适应度，因此它们被复制的机会更多。 n s g a 的优点是优化目标个数可以任选，非劣最优解分布均匀，且允许存在多个 不同等效解；缺点是p a r e t o 排序要重复多次，计算效率较低，计算复杂度为o ( m n 3 ) ( m 为目标数量，n 为种群大小) ，未采用精英保留策略，共享参数o 。k 需要预先确定。 n s g ai i 1 8 1 是2 0 0 2 年提出的n s g a 的改进版本。在n s g ai i 中，每个解都需 要确定有多少解支配它和它支配的解集。n s g ai i 需要估计围绕种群中一个特定 1 4 郑州大学硕士学位论文 解的解密度，即需要沿问题的每个目标计算两解间的平均距离，该距离被称为密 集距离( c r o w d i n g m e a s u r e ) 。在选择期间，n s g a i i 密集比较算子既了考虑种群中 个体的非劣解，也考虑了密集距离。也就是说，优先选择非劣解：但当两解具有 相同的非劣解时，则选择不处于拥挤距离区域内的解。n s g ai i 的精英保留策略 使用( p + 入) 选择，包含了最好的父代和子代个体。这种机制使新一代种群比前 一代种群更有效，效果更好。 j e f f r e yh o r n 等在1 9 9 4 提出了n p g a 1 9 】，使用基于p a r e t o 支配的锦标赛选择 模式。算法的基本思想很巧妙：随机选择两个个体，与种群的一个子集比较( 一 般来讲，子集占整个种群的1 0 ) ，若其中一个个体支配子集，而另一个个体被子 集支配，则非劣个体获胜；其它所有情况被视为一结( t i e ，即互不支配) 。当有结 存在时，可通过适应度共享来确定锦标赛结果。由于该算法的非劣最优解选择是 基于种群的部分而非全体，所以其优点是能很快找到