（管理科学与工程专业论文）基于进化算法的多目标电子谈判的研究.pdf

武汉科技大学硕士学位论文第1 页 摘要 随着电子商务的发展，电子谈判成为电子商务必须的部分。由于现在商品社会中对于 交易对象的选择需要考虑众多的因素，同时这些因素之间可能并不存在明显的联系。对于 一个决策过程而言，正确权衡这些因素也等同于在交易中达成多个目标。因此在电子谈判 过程中能否选择一种合适方法来达成谈判前制定的多个目标是衡量谈判是否成功的重要 依据。而围绕多目标电子谈判方法的研究还需要不断发展和改善。 本文针对目前电子谈判系统中急需解决的技术问题进行了深入的研究，提供了一些新 的解决思路和有效的开发方法。文章提出了使用进化算法来解决多目标电子谈判的选择问 题，并建立了包括算法和操作环境的算法模型对谈判的决策提供有效的支持。用进化算法 的思想与多目标谈判的理论基础对电子合同及其目标、责任、约束以及不可抵赖性证据进 行形式化定义，可以证据相互配合，迫使达到商业目标。文章以数据分析为基础，引入多 目标分析的概念，提供了一个全新电子谈判分析的实施方法。文章中提的一种新的多目标 进化规划算法，大大减少了检验非劣解所需的工作，加快了算法的收敛速度。仿真试验表 明，与传统的基于非优超排序的多目标进化规划算法相比，该算法在效率上有很大的改善， 并能更好地逼近p a r e t o 前沿。 使用进化算法来解决电子商务中的多目标谈判问题，不仅可以全面的接受和组合各种 复杂信息，而且可以帮助决策者在最短的时间内做出最优的决策。相比于其他优化算法而 言，进化算法有较强的融合性。在进化算法中，可以包含多目标管理中的博弈理论思想， 还有决策者自己所需要的附加条件。同时，由于算法本身还有很多种改良的方式，所以决 策者可以自己根据需要来调整各个参数以达到最好的选择效果。 关键词：电子谈判多目标进化算法电子谈判媒体多样性 第1 i 页武汉科技大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fe l e c t r o n i cc o m m e r c e 。e l e c t r o n i cn e g o t i a t i o nb e c o m e st h e e s s e n t i a lp a r to fi t s i n c et h e r ea r em u l t i p l ef a c t o r sn e e dt oc o n s i d e rb e f o r et h ed e a l ，t h e p r o c e s s i n gi st ob ea c h i e v em u l t i p l eg o a l si nt h et r a d i n g n em e t h o do fe - n e g o t i a t i o nw i l lt a k e g r e a ti n f l u e n c et ot h er e s u l t a n dt h ea l g o r i t h mi ss t i l li 1 1r e s e a r c ha n dd e v e l o p i n g t od e a lw i t ht h ec u r r e n tt e c h n i c a lp r o b l e m sw h i c hn e e ds o l u t i o n si ne l e c t r o n i cn e g o t i a t i o n , n e wm e t h o d sh a v e b e e nr e s e a r c h e da n dp r o v i d e di nt h i sp a p e r e v o l u t i o n a r ya l g o r i t h mh a sb e e n u s e dt od i s p o s a lt h ec h o o s i n gp u z z l ei nm u l t i o b j e c t i v ee l e c t r o n i cn e g o t i a t i o na n dp r o v i d e d g r e a te f f o r t st ot h ef m a ld e c i d i n g a n dam o d e lh a sb e e ns e tu pt oe n s u r et h ee n v i r o n m e n ta n d b a s e sf o rt h ep r o c e s s i n go f t h ea l g o r i t h m e v o l u t i o n a r ya l g o r i t h mi st a k e na se f f i c i e n tm e t h o dt o s o l v et h em u l t i o b j e c t i v ep r o b l e m sa n dd e c l a r eg o a l ，r e s p o n s i b i l i t ya n dr e s t r i c t s d u r i n g e l e c t r o n i cn e g o t i a t i o n b a s ew i 恤d a t aa n a l y s i sa n dt h ec o n c e p to fm u l t i - o b j e c t i v ea n a l y s i s a b r a n dn e ws y s t e mm o d e lh a sb e e ns c tu pi nt h i sp a p e r w ep r o p o s ea ni m p r o v e de v o l u t i o n a r y p r o g r a m m i n gf o rt h em u l t i - o b j e c t i v eo p t i m i z a t i o n ，u s i n ga ne x t e r n a lf i l et o s t o r et h en o d o m i n a t e dv e c t o r sf o u n dd u r i n gt h ee v o l u t i o n a r yp r o c e s s 1 1 l ep o p u l a t i o nm e m o r yi sd i v i d e di n t o t w op a r t s ：r e p l a c e a b l ea n dn o n - r e p l a c e a b l ep o r t i o n i nt h i sw a yw ec a nr e d u c et h ec h e c k i n gf o r n o n - d o m i n a n c e , t h ev a l i d i t yo ft h ea l g o r i t h mi ss h o w nb yc o m p u t e rs i m u l a t i o nr e s u l t s t 1 1 i sa l g o r i t h mw i l ls o l v et h em u l t i - o b j e c tn e g o t i a t i o ni ne b u s i n e s s i tw i l ln o to n l ya c c e p t a l la s p e c t so fc o m p l i c a t e di n f o r m a t i o na n dm e t h o d s a n da l s oc o u l dh e l pt h ed e a l e rt om a k et h e f i t t e s td e c i s i o nt ot h ep r o b l e m c o m p a r ew i t ho t h e ra l g o r i t h m s ，i to w nt h ef l e x i b i l i t y m e a n w h i l e ， s i n c et h e r eal o tam e t h o d st oi m p r o v et h ea l g o r i t h m t h ed e c i d e r sc a l lm a k et h eb e s tf i to ft h e v a l u et om a k es u r et h er e s u l tt ob et h eo n et h e yn e e d k e y w o r d s ：e l e c t r o n i cc o m m e r c e m u l t i o b j e c t i v e e v o l u t i o n a r ya l g o r i t h m e l e c t r o n i c c o m m e r c em e d i a d i v e r s i t y 武汉科技大学硕士学位论文 第1 页 第一章绪论 1 1 引言 谈判作为社会中一种普遍存在且重要的社会现象，涉及到社会生活中的方方面面。谈 判至少需要两个人类实体参与：两个人或多人、两个或多个代表团。谈判是把面临分歧， 并相互依附的两个角色联系起来的一项活动。谈判的各方因持有分歧而相互对立，但彼此 又相互依存。他们选择策略，谋求达成协议，以便解决分歧。各方在这项活动中不是求助 某种解决纠纷的办法，诸如：回避、对抗、行政命令等，而是谋求一个“可接受的结局”， 致力于达成某种协议。在商业活动中，谈判是一个广泛接受的国际惯例，是有关各方协商 合同的一种常用方式。常规的谈判方式一般是谈判各方在同一地点进行面对面的谈判，交 换意见，进行协商。随着国际互联网( i n t e m e t ) 的不断发展，它将我们带入了一个新的信 息化的时代。传统的商业活动逐渐被电子商务所代替，电子商务中的电子谈判就不可避免 成为了重要的研究项目。然而，目前已有的对电子商务技术的研究中，大部分的中外学者 都把主意力集中在电子数据交换、电子资金转账、数字签名、加密、安全协议、智能卡等 技术领域，而对网上的交易谈判这一主要环节却涉及较少，使得交易谈判系统这个整个电 子商贸业务中十分关键的一个环节，却恰恰成为目前各类电子商务应用系统研究中最为薄 弱的一个环节。在目前电子商务的实际动作中，大多数的情况只是网上开展广告、查询、 订货、展览等经济活，而对于谈判仍采用传统的面对面的方式进行。电子商务发展到高级 阶段就是交易前、交易中、交易后三个阶段都实现电子化处理，如果面向电子商务的电子 谈判得不到有效的研究，无疑会阻碍电子商务的发展。 谈判理论本身已经由语言行为科学、社会科学、经济科学和管理科学等多方面的学者 进行了广泛的研究，并取得了丰硕的成果，这不是本文研究的内容，我们主要应用他们的 研究成果实现电子媒体上的商务谈判。 1 2 电子商务谈判中的问题和本文需要解决的工作 在电子商务中，不论是消费与企业，还是企业与企业之间的商务活动都要求谈判处理 的自动化，当需要人参入交互时，也至少是半自动的。电子谈判的目标就是要用电子谈判 系统代替人或帮助人自动进行谈判处理，迅速、高效地达成商务协议，签订电子合同，迫 使达到双方的目标。要在基于互联网的电子商务系统上完成电子谈判的目标，必须解决以 下几方面的问题： ( 1 ) 组织并选择有效因子 为了保证自己谈判或帮助人进行有效的谈判，电子谈判系统必须是智能化的。它必须 拥有关于人们和商业组织的谈判需求，对不同选择的偏好和谈判的策略、技巧，以及商业 政策方面的信息和知识。这些信息必须由人类谈判专家提供，因此需要有有效表达知识的 方法，使其在谈判的过程中能够有效、充分地使用这些知识，在必要时，能够方便、快捷 第2 页武汉科技大学硕士学位论文 地选择这些因子。 ( 2 ) 谈判的决策过程 基于人类的谈判决策过程可以因时间、地点、所涉及的人、规则、习惯等方面的因素 任意进行。然而，如果没有对谈判的决策过程进行形式化的分析和定义，要用计算机进行 自动谈判是非常困难的。特别是，我们需要分析决策过程，保证谈判系统知道怎样决定接 受、拒绝建议，或生成反建议我们还需要确定什么类型的信息才能支持谈判的决策过程。 ( 3 ) 电子谈判系统的结果有效 传统上，谈判伙伴之间的交互是通过自然语言进行的。虽然自然语言有很强的表达能 力，但含糊、多义，计算机处理非常困难。因此需要形式化的谈判语言、谈判协议、消息 的规格说明。使得到的结果真实有效是衡量方法好坏的重要因素。 ( 4 ) 适应性强的媒体结构 为了充分利用互联网作为大众资源和基础结构的优势，电子谈判系统的体系结构必须 兼容于互联网，必须是可升级的，在高度分布式环境下必须能够支持谈判服务的并发应用。 在很多情况下，计算机还不能完全代替人类谈判，再者，谈判系统的知识库中不可能包含 一个实际谈判策略所需要的全部知识和信息，必须经常通过人工对其进行维护和定义，所 以谈判系统的易用性也是一个很重要的问题。 到目前为止，上述这些问题还仍然没有得到有效的解决，对正运行的商业系统就更不 用说了。这几年我们都在努力寻找解决问题的方法与途径，希望对电子商务的发展能有所 贡献。本文就是我们最近两年研究工作的总结果。 1 3 本文的结构 全文分七章，第二章对进化算法的概念、发展和使用方法进行了详尽的阐述，为后面 使用进化算法进行多目标电子谈判分析做铺垫：第三章是对电子谈判的发展和特点进行一 个较为全面的综述；第四章介绍了电子谈判常用的策略以及他们各自的使用范围；第五章 中，我们将进化算法使用于多目标电子谈判的分析应用中，试图用数学方法解决电子谈判 中出现的复杂问题；我们在第六章中提供了一种电子谈判模型的设计，并简单阐述了实现 的方法。最后对研究工作做了一个总结，并对对未来研究作了一个展望。 武汉科技大学硕士学位论文第3 页 第二章进化算法简介 2 1 起源与发展 仿生进化研究主要有3 类：遗传算法( g e n e t i ca l g 耐t h m s ) 、进化策略( e v o l u t i o n s 们t e g i e s ) 和进化规划( e v o l m i o np r o g r a m m i n g ) 。第一类方法比较成熟，现已广泛应用， 进化策略和进化规划在科研和实际问题中的应用也越来越广泛。遗传算法的主要基因操作 是选种、交配和突变，而在进化规则、进化策略中，进化机制源于选种和突变。就适应度 的角度来说遗传算法用于选择优秀的父代( 优秀的父代产生优秀的子代) ，而进化规则和 进化策略则用于选择子代( 优秀的子代才能存在) 。遗传算法强调的是父代对子代的遗传 链，而进化规则和进化策略则着重于子代本身的行为特性，即行为链。进化规则和进化策 略一般都不采用二进制编码，省去了运作过程中的编码一解码手续更适用于连续优化问 题。进化策略可以确定机制产生出用于繁殖的父代，而遗传算法和进化规则强调对个体适 应度和概率的依赖。此外，进化规则把编码结构抽象为种群之间的相似，而进化策略抽象 为个体之间的相似。”。 ，； 进化策略和进化规则已应用于连续函数优化、模式识别、机器学习、神经网络训练、 系统辨识和智能控制的众多领域。 2 1 1 进化规划的起源与发展 进化规划是由美国人u f o g e l 于2 0 世纪6 0 年代提出来的。他提出采用有限字符集上的 符号序列表示模拟的环境，采用有限状态机表示智能系统腑”。这种方法与遗传算法有许 多共同之处，但不像遗传算法那样注重父代与子代的遗传细节，而是把侧重点放在父代与 子代表现行为的联系上。当时学术界对进化规划持怀疑态度，直到9 0 年代才逐渐受到重视 并开始解决实际问题。 2 1 2 进化策略的起源与发展 进化策略是在欧洲独立于遗传算法和进化规划而发展起来的。1 9 6 3 年德国大学的2 名 学生r e c h e n b e r g 和h p s c h w e f e l ，在利用流体工程研究所的风洞做实验室时，r e c h e n b e 唱 提出了按自然突变和自然选择的生物进化思想的进化策略思想。同样，当时人们无法接受， 直到1 9 9 0 年欧洲召开了第一届“基于自然思想的并行问题求解”的国际会议。“。1 。 2 1 3 进化计算的起源与发展 1 9 9 0 年，遗传算法开始与进化规划和进化策略有所交流，1 9 9 2 年，进化规划和进化 策略这两个不同领域的研究人员首次接触到对方的研究工作，通过深入交流，他们发现彼 此在研究中所依赖的基本思想都是基于生物界的自然遗传和自然选择等生物进化思想，于 是将这类方法统称为进化计算，相应的算法称为进化算法或进化程序。1 9 9 3 年进化计算这 一专业领域的第一份国际杂志问世，1 9 9 4 年i e e e 神经网络委员会主持召开了第一届进化 第4 页武汉科技大学硕士学位论文 计算国际会议。近年来，国际上掀起了进化计算的研究热潮，各种新的研究结果和应用实 例不断涌现，将来有一天可能会出现一门内容包括进化计算但比进化计算更为广泛的科 学，这一科学可能被称为“自然计算( n a t u r a lc o m p u t a t i o n ，n c ) ”9 3 。 2 2 基本框架及其特点 2 2 1 基本步骤 进化计算是基于自然选择和自然遗传等生物进化机制的一种搜索算法。与普通的搜索 方法一样，进化计算也是一种迭代算法，不同的是进化计算在最优解的搜索过程中，一般 是从原问题的一组解出发改进到另一组较好的解，再从这组改进的解出发进一步改进。而 且在进化问题中，要求当原问题的优化模型建立后，还必须对原问题的解迸行编码。进化 计算在搜索过程中利用结构化和随机性的信息，使最满足目标的决策获得最大的生存可 能，是一种概率型的算法。一般来说，进化计算的求解包括以下几个步骤：给定一组初始 解；评价当前这组解的性能；从当前这组解中选择一定数量的解作为迭代后的解的基础； 再对其进行操作，得到迭代后的解；若这些解满足要求则停止，否则将这些迭代得到的解 作为当前解重新操作。 2 2 2 基本特点 进化计算是一种具有鲁棒性的方法，能适应不同的环境不同的问题，而且在大多数情 况下都能得到比较满意的有效解。他对问题的整个参数空间给出一种编码方案，而不是直 接对问题的具体参数进行处理，不是从某个单一的初始点开始搜索，而是从一组初始点搜 索研。搜索中用到的是目标函数值的信息，可以不必用到目标函数的导数信息或与具体问 题有关的特殊知识。因而进化算法具有广泛的应用性，高度的非线性，易修改性和可并行 性。 2 3 理论研究及其应用现状 2 3 1 理论基础 进化计算的理论基础有待充实，尤其是进化规划和进化策略，这在一定程度上制约了 进化计算的实际应用。建立进化计算的数学模型，奠定进化计算的理论基础，更深刻地认 识进化计算的本质，是目前的热点和难点。算法的复杂性分析、算法的收敛性、收敛速度， 与其他优化方法结合而成的混合算法以及在非优化算法中的应用都是亟待解决的问题。 2 t 3 。2 应用现状 目前常见的软件或软件包有十几种，包括进化计算的各个方面，如遗传算法、平行遗 传算法、进化策略、进化规划、遗传规划、分类系统等，并有d o s 版本、w i n d o w s 版本、 u n i x 版本以及网络版本等。最新的软件可以通过互联网直接下载，美国海军后勤研究中心 于1 9 8 5 年首先建立了全球性的有关遗传算法的网站，不定期编辑出版遗传算法文摘，交流 武汉科技大学硕士学位论文第5 页 有关遗传算法的最新信息。进化计算几乎在所有的科学和工程问题中都具有应用前景，尤 其是一些典型的领域：复杂的非线性最优化问题，复杂的组合规划或整数规划问题，起源 于生物学又应用于生物学，可以利用进化算法研究小生境理论和生物物种的形成；计算机 科学的图像处理、自动识别以及文档自动处理。进化算法已经越来越多地应用于工程实际： 通讯网络的优化，超大规模集成电路的布线，飞机外型的设计。进化计算还广泛地应用于 社会科学领域，如人类行为规范进化过程的模拟，人口迁移模型的建立“。 2 3 3 在智能控制中的应用 将进化计算引入鲁棒控制系统是一种新的有效的方法，对于鲁棒控制领域中的某些控 制结构和控制作用，进化算法可以提供比传统数值优化方法更快更好的优点。同其他传统 的鲁棒系统设计方法相比，基于进化算法的鲁捧控制系统设计直接法具有算法简便，灵活 性大，能够得到低阶控制器，可以达到全局最优的特点；而间接法是对传统方法的发展， 能够缩短设计时间，提高自动化程度。模糊进化神经网络融合模糊逻辑、进化计算和神经 网络理论与技术，是符号智能和计算智能的有机融合。是一种综合智能理论技术，其基本 思路是利用模糊逻辑解决进化计算中控制参数的初选、编码、调节和对优化结果的综合评 价；利用模糊进化计算解决神经网络和模糊神经网络的全自动高效优化设计，以及模糊逻 辑系统中控制参数的优化。他是在3 种现有的智能理论技术基础上发展起来的，作为崭新 的智能理论技术进行研究的，旨在分析进化算法中的模糊智能行为智能和属性、神经网络 设计、模糊建模和控制中的进化智能行为和属性，解决进化计算、神经网络、模糊控制理 论本身许多无法解决的难题，模糊进化神经网络主要是利用模糊进化算法来设计神经网 络，包括训练神经网络权重，拓扑结构等所有参数，以提高神经网络学习效率，建立合理 最优的网络模型，并对神经网络模型进行评价研究。进化算法的全局采样特性可以与传统 的神经学习算法的局部搜索行为相结合，先用进化算法寻找a n n 初始权空间，然后采用传 统神经网络梯度下降学习法，还可以用进化算法优化标准神经学习算法中关键参数的问 题。以如何对神经网络的结构进行编码为主要研究内容的进化神经网络，即网络参数编码 的确定( 包括选择待编码的参数、为各参数分配串长、定义串值与参数值之间的映射关系 等) ，随着大规模计算机的不断发展，使其实用化成为可能“。 用遗传算法设计模糊逻辑控制器具有许多其他方法所没有的优越性：遗传算法可以优 化模糊逻辑控制器从结构到参数数值的各个方面；可以不需要设计者对控制对象有任何先 验知识，可以没有良好的训练数据对；易于融入设计者的知识以提高学习效率；基于规则 的模糊逻辑控制器摆脱了全局隶属函数的束缚，规则数可以自由改变，尤其适合用遗传算 法来设计。综合运用匹兹堡方法和密歇根方法，在控制器级和规则级同时进化模糊系统的 方法，克服了二者的缺点，大大提高了进化的效率。模糊控制器是刺激响应型的分类器系 统，每一控制周期均与环境进行交互，因而避免了繁琐的分值分配算法，为简单的规则评 价方法提供了可能。规则评价的关键是解决系统状态变量之间的可能的冲突，将状态变量 边界附近的误差加以放大，则在边界附近状态变量的任何较小的改变，都能产生较大的反 第6 页武汉科技大学硕士学位论文 馈“6 ”1 。 微遗传算法实现的自适应控制器，对于多模态情况以及非平稳函数的优化，都取得了 性能卓越的结果。遗传算法可以应用到前向神经网络的学习中，把权值和节点的连接作为 基因组，不管是前向还是反馈，任何一种连接方式，都可作为基因的一种随机组合方式， 而基因组可以随意形成，通过遗传算法可以得到输入与输出正确映射的网络结构和网络权 值。遗传算法用于神经网络自适应k n 0 控制系统是通过遗传算法训练神经网络而构成的自 适应控制系统，实现了遗传算法、神经网络、k n 0 控制者的有机结合，获得了优异的控制 效果，收敛快、鲁棒性强、动态响应良好，。 基于遗传算法的自学习故障诊断方法，利用了自学习诊断规则能够缓解知识获取上的 困难，特别是当对故障缺乏了解时，为从一组训练数据中自动建立规则提供了有效手段。 遗传算法作为一种实质上的随机搜索技术，难免由于随机性太大而陷入盲目搜索，以 至于以搜索失败而告终。若与专家系统结合，以有效的启发知识来引导种群规模的界并设 定交配概率和突变概率以及这两项操作的基因串的位置，则可快速获得满意解。此外，遗 传算法用于图像恢复、图像识别和作业调度都是当前实用的研究课题。进化理论技术蓬勃 发展的同时也暴露出一些亟待解决的问题。算法的收敛性将严重影响控制系统的稳定性， 尤其对于实时控制，可能使整个系统陷入恶性循环完全失去控制。即便算法在实质上隐含 高度并行性，当种群规模庞大及搜索空间广阔时，算法的收敛速度及搜索效率便成为突出 问题，所以进化计算应该同智能控制的其他技术有效结合。在过渡过程初期，为加快响应 速度，以传统方法为主，过渡过程中期便可采用进化计算辨识控制系统模型以及优化控制 器参数，而为避免控制器参数的剧烈改变所引起的干扰影响，可以在过渡过程后期全面恢 复到传统控制状态，以利于整个系统平稳地达到目标状态o ”。 2 3 4 多目标进化算法的研究 工程实践和科学研究中优化问题大多是多目标优化问题( m u l t i o b j e c t i v eo p t i m i z a t i o n p r o b l e m ，m o p ) ，各目标之间通过决策变量相互制约，对其中一个目标优化必须以其它 目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优 劣性。例如，在设计一座桥梁时，我们一方面希望建设桥梁的费用最小，另一方面希望桥 梁具有最大的安全性。与单目标优化问题的本质区别在于，多目标优化问题的解不是唯一 的，而是存在一个最优解集合，集合中元素称为p a r e t o 最优或非劣最优( n o n d o m i n a n c e ) 。 求解它们需要用不同于单目标优化的数学工具，甚至最优的含义也发生了变化啪1 。 自1 9 5 0 年以来，运筹学研究人员已经建立了许多方法解决m o p 。在专业文献中，有许 多数学规划技巧解决m o p ，如多目标加权法、分层序列法、约束法、目标规划法等。然而， 传统数学规划方法存在一些缺陷，例如有些方法对p a r e t o 前沿比较敏感，当p a r e t o 前沿是 凹的或者不连续时，这些方法失效：有些方法要求目标函数和约束条件可微；有些方法每 次运行只产生一个解，求多个解时需要运行多次，效率较低。而自1 9 7 5 年j o h nh o l l a n d 提出 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 以来，基于生物模拟的进化算法( e v o l u t i o n a r ya l g o r i t h m ， 武汉科技大学硕士学位论文第7 页 e a ) 得到了深入研究，由于其具有并行、不需要求导或其它辅助知识、一次产生多个解 和简单易于实现等优点，被视为求解m o p 的有效方法。将进化算法用于求解多目标优化问 题，被称为进化多目标优化( e v o l u t i o n a r ym u l t i 2 0 b j e c t i v eo p t i m i z a t i o n ，e m o ) ，研究人 员已经提出多种求解多目标的进化算法( m u l t i 2 0 b j e e t i v ee v o l u t i o n a r ya l g o r i t h m ，m o e a ) 洲。进化多目标优化始于1 9 6 7 年，r s r o s e n b e r g 在其博士论文提出了使用遗传算法解决 m o p ，然而他当时并没有建立实际的多目标优化算法，m o p 被表述为单目标问题，并用 遗传算法求解。d a v i ds c h a f f e r 是2 0 世纪8 0 年代中期第一个设计多目标进化算法的人，其方 法称为向量评价遗传算法( v e c t o re v a l u a t e dg e n e t i ca l g o r i t h m ，v e g a ) 。一般认为，m o e a 发展到今天经历了两个阶段：第一阶段从2 0 世纪8 0 年代中期至1 9 0 年代中期，m o e a 以简单 为特征，称为第一代m o e a ，主要包括n s g a 、n p g a 、m o g a 等；第二阶段从2 0 世纪9 0 年代中期至今，m o e a 以效率为特征，以精英保留策略为实现机制，称为第二代m o e a ， 主要包括s p e a 、s p e a 2 、p a e s 、n s g ai i 、p e s a 等。 2 3 5 多目标问题的数学描述 多目标优化问题是指具有两个或者两个以上目标需要同时优化的问题，且多个目标相 互制约，有时还存在目标约束。m o p 的解并不局限于单个解，而可能多个解，是某种折衷 或妥协，求解m o p 常求解问题的p a r e t o 最优解集。多目标优化问题数学描述如下： m i n f 动= l 丸( x ) 矗( x ) 】 置t f & ) 一= j ，2 ，h ，xe r n 例，公式( 4 1 ) 其中，厂以) f l g 鱼j 为目标函数，g “) 是约束，问题具有f 个决策变量、| 个目 标函数和h 种约束。当只有单个目标时，最优解就是在给定约束条件下使目标函数值最大 的解，当多个目标要同时最优时，最优解就是p a r e t o 最优集。m o e a 常用到如下几个基本 概念： ( 1 ) p a r e t o 支配( p a r e t o d o m i n a n c e ) ，解? 支配x 。r 妒，一) ，当且仅当 艄甄d 0 ，i 口，2 ，夥 公式( 4 2 ) m o ) 五伍0 ，f 口，2 ，目 公式( 4 3 ) ( 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 j j s 劣最优( p a r e t on o n - d o m i n a n c e ) 。如果解 妒是p a r e t 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 最优解的集合： p s = 扛o i x l ，7 公式( 4 4 ) ( 4 ) p a r e t o 前沿或均衡面( p a r e t of r o n t ) ，所有p a r e t o 最优解对应的目标函数值所形成 的区域，表示为： 厅= f f 俐= 倒，f 2 倒，五阳川x 风， 公式( 4 5 ) 2 3 6 以简单为特点的第一代m o e a 的研究 m o e a 的研究可以追溯至1 j 1 9 6 7 年，r s r o s e n b e r g 在其博士论文提出了使用遗传算法解 第8 页武汉科技大学硕士学位论文 决m o p ，然而他当时并没有建立实际的多目标优化算法，m o p 被表述为单目标问题，并 且用遗传算法求解。一般认为，d a v i ds c h a f f e r 是2 0 世纪8 0 年代中期第一个设计多目标进化 算法的人，其方法称为向量评价遗传算法v e g a ，是一种修改了选择机制的简单g a 。在每一 代，根据各个且标函数按比例完成选择，生成多个子种群，并在子种群上使用通常的交叉 和变异操作，然后将这些种群混合在一起，形成新的种群。这种将所有个体混合起来的做 法等价于将适应度函数线性加权求和，只不过权重取决于当前世代；同时，v e g a 也无法 保证优良个体遗传到下一代。v e g a 之后，研究人员采用了几种简单方法解决m o p 。最主 要的当属线性加权函数法，即把所有目标函数线性加权成一个单一值，将其直接作为e a 的 适应度。非线性加权函数也比较流行。分层排序法也是一种常用的方法，它首先选出最重 要的目标，即第一目标，在不考虑其他目标的情况下，采用单目标优化方法对其进行优化； 在保持第一目标性能的情况下，对第二个目标求优；依次类推，直至求出所有目标。尽管 当时已经有很多研究，但真正把p a r e t o 最优结合到e a 的是d a v i d e g o l d b e r g 。在分析了v e g a 之后，o o l d b e r g 提出使用非劣最优排序( s o r t i n g ) 和选择机制使种群向多目标优化问题的 p a r e t o 前沿移动，其思想是首先找出种群中非劣的解集，赋予它们最高的秩( r a n k ) ，并将 它们从下种群中删除；再从剩余的种群中找出下一个非劣的解集，并赋予它们次高的秩； 这一过程继续下去，直到确定种群所有个体的秩才结束。o o l d b e r g 也建议使用小生境( n i c h e ) 技巧以防止收敛到单个p a r e t o 解，例如适应度共享方法( s h a r i n gm e t h o d ) 允许e a 个体都 分布在p a r e t o 前沿。尽管g o l d b e r g 没有实现实际的算法过程，但后来建立的算法都受到这种 思想的影响o “。 最有代表性的第一代i d 0 g a 方法包括： ( 1 ) m o g a ( m u l t i - o b j e c t i v eg e n e t i ca l g o r i t h m ) 1 9 9 3 年，c a r l o sm f o m e c a 和p e t e rj f l e m i n g 提出了m o g a 。在m o g a 中，一个个 体的秩等于当前种群中支配它的染色体数目，所有非劣个体的秩均为1 ( 所有这样的个体 适应度都相同，以便能以相同的概率被选择使用) ，而被支配的个体依据属于它们所在区 域的种群密度被惩罚( 适应度共享用于验证个体区域的拥挤程度) 。适应度的分配方式如 下： ( a ) 基于个体的秩将种群排序。 ( b ) 利用线性或非线性的插值方法在最低序号( 非劣最优个体) 与最高序号( 5 n ) 之间进行插值。 ( c ) 具有相同序号的个体的适应值共享，即通过除以相同序号的个体数得到新的适应 值；可以给不同序号的个体分配固定不变的适应值。m o g a 算法的主要优点是算法执行相 对容易且效率高，缺点是算法易受小生境大小影响，但值得一提的是f o n s e c a 与f l e m i n g 已 经从理论上解决了小生境的大小的计算问题3 。 ( 2 ) n s g a ( n o n - d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h m ) n s g a 是由s r i m i v a s 和d e b 在1 9 9 4 年提出的，发表在i e e e 的“e v o l u t i o n a r yc o m p u t a t i o f f 杂志上m 1 。n s g a 基于g o l d b e r g 的建议 对个体分类，形成多个层次。在选择操作之前，个体基于非劣最优进行排序：所有非劣的 武汉科技大学硕士学位论文第9 页 个体分为一类，并引进决策向量空间的共享函数法，保持种群的多样性。然后，忽略这些 已经分类的个体，考虑另一层非劣的个体；这个过程一直持续，直到将所有个体分类。由 于在第一个p a r e t o 前沿中的个体有最大的适应度，因此它们被复制的机会更多。n s g a 的优 点是优化目标个数任选，非劣最优解分布均匀，允许存在多个不同等效解；缺点是由于 p a r e t o 排序要重复多次，计算效率较低，计算复杂度为d ( 刎3 ) ，( 其中朋为目标数量， 伪种群大小) ，未采用精英保留策略，共享参数a s h a r e 需要预先确定。 ( 3 ) n p g a ( n i c h e d 2 p a r e t o g e n e t i c a l g o r i t h m ) j e f f r e y h o r n 等于1 9 9 4 提出了n p g a ，使 用基于p a r e t o 支配的锦标赛选择模式。算法的基本思想非常巧妙：随机选择两个个体，与 来自种群的一个子集比较( 典型地。子集占整个种群的1 0 ) ，若其中一个个体支配子集， 而另一个个体被子集支配，则非劣个体获胜；所有其它情况被视为一结( t i e ，即互不支 配) 。当有结存在时，通过适应度共享确定锦标赛结果。因为该算法的非劣最优解选择是 基于种群的部分而非全体，所以其优点是能很快找到一些好的非劣最优解域，并能维持一 个较长的种群更新期：缺点是除需要设置共享参数外，还需要选择一个适当的锦标赛规模， 因而限制了该算法的实际应用效果。 在第一代m o e a 发展期间，很少进行不同方法之间的比较研究。但比较上述三种方法 的人一致认为，m o g a 最优，依次是n p g a 和n s g a 。这一时期的特点是强调算法的简单 性，但缺乏验证方法，也没有标准测试函数。这一时期的一个重要成果是m a s f l h i r ot a n a k a 建立了第一个结合用户偏好的m o e a 。这点非常重要，因为现实应用中用户往往并不需要 求得整个p a r e t o 解集，而只是需要小部分解( 或者仅一个) 。若用户可以定义一种偏好， 则可缩小搜索空间。 只扩大p a r e t o 前沿的某些区域。许多年来，没有几个研究人员关注这一问题。另一成 果是f o n s e n c a 和f l e m i n g 在1 9 9 5 年的进化计算杂志上发表了该时期的研究进展，f o n s c n c a 提 出了第一个性能测试量度函数，其特点是不需要预先知道问题的p a r e t o 前沿；同时， f o n s e n c a 也给出了为处理约束时修改p a r e t o 支配关系的方法。这一时期主要的教训是：一个 成功的m o e a 除了要结合一种好的机制选择非劣的个体外( 但未必基于p a r e t o 支配概念) ， 还应具有好的机制维护种群多样性( 如适应度共享方法就是其中的一种) 。 2 3 7 以效率为特点的第二代m o e a 的研究 一般认为，第二代m o e a 以精英保留策略为标志，并以其作为一种标准机制。尽管在 早期的m o e a 研究中有些方法已经涉及到了精英保留策略的思想，但多数作者认为e c h a r t z i t z l e r 的贡献可以作为m o e a 的一个里程碑，主要因为i e e et r a n s a c t i o n so ne v o l u t i o n a r y c o m p u t a t i o ni i 发表了他的s p e a 方法。在他的文章发表之后，许多研究人员开始把外部种 群( e x t e m a lp o p u l a t i o n ； s e c o n d a r yp o p u l m i o n 次种群) 结合到他们的m o e a 中，使用精 英保留策略成了共同的实践。事实上，使用精英保留策略是保证m o e a 收敛的一个理论要 求，因此就体现了其重要作用。在m o p 中，精英保留策略通常指使用外部种群保存进化过 程中所出现的非劣个体。使用精英保留策略的动机主要源于这样的事实：在当前种群非劣 第1 0 页武汉科技大学硕士学位论文 的个体未必在后面形成种群非劣，故需要用一种方法来保证向用户报告的解对于算法产生 的其它解也非劣。因此，一种直观的方法就是在外部档案( e x t e r n a lm c h i v e ) 中存放已经 发现的非劣解。若一个解是劣的，则不允许其进入外部档案；相反地，若一个解支配外部 档案中的解，则需要删除被支配者。外部档案的使用也引起了一些问题： ( 1 ) 外部档案如何与主种群交互? 换句话说，我们如何从外部档案和主种群中选择 个体? 或者是否仅从主种群选择个体，忽略外部档案的个体吗? ( 2 ) 若外部档案的容量有限，当存满外部档案之后，应如何处理? 因为外部档案总 是有限的，这个问题必须考虑和关注1 。 ( 3 ) 除了使用p a r e t o 支配，是否对一个欲进入外部档案的非劣个体旅加附加的标准? 如能否使用解的分布密度作为附加标准? 与外部档案相关的问题已经从经验和理论方面进 行了研究。除了使用外部档案，精英保留策略也可以使用( 肛峨) 选择机制，让父代与予 代进行竞争，对那些非劣的个体增加一些附加标准，再选择进入下一代。例如，是否能够 提供更好的解分布。第二代m o e a 期间代表性方法包括以下几种： ( 1 ) s p e a ( s 仃e n g t h p a r e t o e v o l u t i o n a f y a l g o r i t h m ) 和s p e a 2 ( s 仃e n g t l l p 删o e v o l u t i o n a r ya l g o r i t h m2 ) s p e a 是由z i t z l e r 于1 9 9 9 年提出的，借助外部种群实现精英保留 策略。在每一代，将非劣个体复制到外部种群，然后计算外部种群中每个个体的强度。这 个强度值与支配个体的染色体数目成比例，类似于m o g a 中的排序值。在s p e a 中，当前 种群个体的适应度值是按照外部种群中支配它的非劣解的强度之和计算的，适应度值的计 算同时考虑了接近真正p a r e t o 前沿的程度和解的分布。s p e a 使用基于距离的小生境半径和 p 甜e t o 支配，确保解沿着p 甜e t o 前沿分布，但其效率依赖于外部种群非劣解的多少。事实上， 由于外部种群非劣解参与到了s p e a 的选择过程中，若其规模太大，就会减小选择压力，放 慢收敛速度。作者采用了聚类技巧删除其中的个体，从而使其大小限制在一定的门限之内。 然而，s p e a 也有其不足之处，具体表现是：在选择压力非常低时，s p e a 几乎变成随机搜 索；s p e a 使用聚类删除外部种群个体，有可能丢失外部种群中的非劣解。2 0 0 1 年，z i t z l e r 提出了s p e a 的改进版本s p e a 2 ，主要改进包括： ( a ) 采用了一种细粒度的适应度分配策略。对每个个体，既考虑了支配它的个体，又 考虑了被它支配的个体。 ( b