（运筹学与控制论专业论文）一个具有偏好的多目标优化新的进化算法.pdf

摘要 实际情况下，一些多目标优化问题常常伴随着多个决策者的偏好，并且决策者对各 目标的偏好往往是不能精确定量的，为此，本文提出了一种新的偏好方法：多决策者随 机性偏好。该偏好方法基于多个决策者的偏好，并且各目标的权重是在特定区间内随机 产生的。结合遗传算法，形成了一种求解多目标优化问题的混合遗传算法。数值实验的 结果显示了不同偏好下，多目标优化问题的决策结果也不一样，这与实际情形相吻合。 在实际中，该偏好方法具有一定的现实意义，因而，为研究多目标优化问题提供了一种 新的偏好模型。 有关多目标优化进化算法收敛性理论的研究结果相对较少，本文提出了一种新的多 目标优化问题模型，并证嘎了该模型的全局收敛性。 关键词：多目标优化偏好进化算法全局收敛性 a b s t r a c t 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 s ( m o p ) u s u a l l yc o r r e l a t ew i t hm u l t i p l ed e c i s i o n m a k e r s p r e f e r e n c ea n d t h ed e c i s i o nm a k e r s p r e f e r e n c e c a l ln o tb e q u a n t i f i e db yu s i n gp r e c i s e v a l u e s i nt h i s p a p e r ，a n o v e l p r e f e r e n c e m e t h o db a s e do n m u l t i p l e d e c i s i o nm a k e r s p r e f e r e n c e ( m d p ) i sp r e s e n t e d i nt h ep r o p o s e dm e t h o d ，s t o c h a s t i cv e c t o r sa l eg e n e r a t e di n f i x e di n t e r v a l sa st h ep r e f e r e n c ev e c t o r s w h i c ha r eu s e d 船t h ew e i g h t so ft h eo b j e c t i v e s b y i n t e g r a t i n gp r e f e r e n c ew i t hg e n e t i co p e r a t o r s ，an e wh y b d dg e n e t i ca l g o r i t h mw i t hp r e f e r e n c e i s p r o p o s e d t h e s i m u l a t i o nr e s u l t si n d i c a t et h a tt h ed i f f e r e n tp r e f e r e n c e sw i l lr e s u l ti n d i f f e r e n to p t i m a ls o l u t i o n s ，w h i c hs h o w s 也em o d e li sr e a s o n a b l e t h e r ea r es o m ep r a c t i c a l p r o b l e m sw h i c hc a nb em o d e l e d a sa l lm o pw i t hp r e f e r e n c e t h e r e f o r e ，t h i ss t u d y i n gi so f g r e a tv a l u e i ns o l v i n gs o r tm u l t i p l e d e c i s i o n m a k i n g p r o b l e m s c o m p a r e dt o t h ee v o l u t i o n a r y a l g o r i t h m s ，c o n v e r g e n c eo ne v o l u t i o n a r ya l g o r i t h m si s r e l a t i v e l yr a r e ，an e w m o p e v o l u t i o n a r ya l g o r i t h mm o d e li ss e tu pa n di t sg l o b a lc o n v e r g e n c e i sp r o v e di nt h i sp a p e r k e v w o r d ：i u i t i _ o b j e c t i v oo p t i m i z a t i o np r e f e r e n o ee v o l u t i o n a r ya l g o r i t h = bio b al c o n v e r g e n c e 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已 经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做 了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：垒聋旁 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发 表论文或使用论文( 与学位论文相关) 工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部 分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵 守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 日期兰翌呈：墨! 乡 日期墨趟l 丛 第一章绪论 第一章绪论 1 1 引言 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是近几十年发展起来的一种随机全局优化算 法，它是根据达尔文生物进化论的自然选择学说和群体遗传学原理而建立的。经 过短短几十年的发展，遗传算法的理论分析日趋完善。 在最近十年里，遗传算法被广泛应用于各方面的优化问题卜1 0 】，如人工智能、 模式识别、图象处理、系统控制等等。其中，用遗传算法来求解多目标优化问题 ( 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 r a s ，m o p ) 是遗传算法的一个典型应用 1 1 1 5 】。多目 标优化问题在科学技术，经济管理和工程设计等领域大量存在，许多实际的多目 标优化问题具有很大的复杂性。求解多目标优化问题的方法比较多，大体上可分 为传统的解法i l 6 j 和现代的软计算方法1 1 7 l ，可用传统的优化方法来求解的多目标优 化问题十分有限，传统的优化方法对多目标优化问题中目标函数和约束函数的特 性，如连续性，可导性的要求比较高，并且传统的优化方法容易陷入局部最优， 因此，传统的优化方法难以求解那些复杂的多目标优化问题，如目标函数在自变 量空间中不连续或者目标函数在可行域中是多蜂极值函数等等，作为软计算方法 中的一种，遗传算法求解多目标优化问题的过程不受目标函数的连续性和可导性 限制，并且遗传算法是一种全局搜索算法，故遗传算法是一种比较理想的求解多 目标优化问题的算法。 传统遗传算法的进化算子包括杂交，变异，选择算予，故用它来求解复杂的多 目标优化问题并不理想，其主要原因是进化算子搜索全局最优解的效率很低。因 此，在实际中，往往把遗传算法和其它优化方法相结合来进行求解多目标优化问 题。这种方法是目前求解多目标优化问题的主要方法。 实际中盼多目标优化问题可大体上分成两类，第一类是不存在决策者的偏好， 即视各目标的重要性均等。对这类多目标优化问题，只能求出它的一些折衷解。 第二类是存在着决策者的偏好，即各个目标函数的重要性不一样。根据所采用的 偏好方法不同，所求得的最优解也不相同。为此，本文提出了一种新的偏好方法， 并结合遗传算法来进行求解多目标优化问题。 1 2 遗传算法的基本理论 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全 2 一个具有偏好的多目标优化新的进化算法 局优化概率搜索算法。它最早由美国密执安大学的h o l l a n d 教授提出，起源于6 0 年 代对自然和人工自适应的研究。7 0 年代d ej o n g 基于遗传算法的思想在计算机 上进行了大量的纯数值函数优化计算实验”9 1 。在一系列研究工作的基础上，8 0 年 代由g o l d b e r g 进行归纳总结，形成了遗传算法的基本框架1 2 0 - - 2 4 1 。 i 2 i 遗传算法的基本框架 遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择 ( s e l e c t i o n ) ，交3 l ( c r o s s o v e r ) 和变异( m u t a t i o n ) 是遗传算法的三个主要操作算子。遗传 算法包括6 个基本要素：参数编码、初始种群的设定、适应度函数的设计、遗传 算子的设计、停止运行准则及结果的编码、控制参数设定( 包括种群规模、交叉 概率、变异概率，停止运行准则韵参数等。) 1 编码 把问题空间中的参数或解转化成遗传空间中的染色体或个体，称作编码 ( e n c o d i n g ) ，相反过程称为译码( d e c o d i n g ) 。由于遗传算法通常不能直接处理解空问 的数据，所以必须通过编码将它们表示成遗传空间的基因型串结构数据。编码规 则有： 1 ) 完备性( c o m p l e t e n e s s ) ：问题空间中的所有点都成为编码后空间中的点； 2 ) 健全性( s o u n d n e s s ) ：编码后空间的点能对应原问题空间的所有点； 3 ) 非冗余性( n o n - r e d u n d a n c y ) ：编码后空间的点与原问题空间的点一一对应； 4 ) 有意义积木块编码规则：应使用能易于产生与所求问题相关的底阶，短定 义长度模式的编码方案。 对于实际应用问题，必须对编码方法、交叉操作方法、变异操作方法、解码方 法等统一考虑，以寻求到一种对问题的描述最为方便、遗传算法效率最高的编码 方案。编码方法有很多，如：二进制编码、格雷码编码、实数编码、符号编码、 多参数级联编码、多参数交叉编码。对不同问题，应选用合适的编码方法。 2 初始种群的生成 一定数量的个体组成了神群( p o p u l a t i o n ) ，种群中个体的数目称为种群规模 ( p o p u l a t i o ns i z e ) 。由于遗传算法的种群型操作需要，所以必须为遗传操作准备一个 由若干初始解组成的初始种群。初始种群的每个个体都是通过随机方法产生，它 也称为进化的初始代。种群规模是遗传算法的控制参数之一，其选取对遗传算法 效能的发挥有影响。一般种群规模在几十到几百之间取值，问题越难，维数越高， 种群规模越大。 初始种群的设定可采取以下策略： 第一章绪论3 1 ) 设法把握最优解在整个问题空间的分布范围，然后在此分布范围内均匀设 定初始种群。 2 ) 先随机生成一定数目的个体，然后从中选出最好的个体加入到种群中，不 断重复这一过程，直到达到种群规模。 3 适应度函数 各个体对环境的适应程度叫适应度( f i t n e s s ) 。遗传算法在进化搜索过程中一般不 需要其它外部信息，仅用适应度来评估个体或解的优劣，并作为以后遗传操作的 依据。 1 ) 评价个体适应度的一般过程是：对个体编码串进行解码处理后，可得到个 体的表现型，由个体的表现型可计算出对应个体的目标函数值，根据最优 化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。 2 ) 适应度尺度变换，在遗传算法中，种群的进化过程是以种群中各个体的适 应度为依据，通过一个迭代过程，不断地寻求出适应度较大的个体，最终 就可得到问题的最优解或近似最优解。在遗传算法运行的不同阶段还需要 对个体的适应度进行适当的扩大或缩小，这就是适应度尺度变换。在进化 的初期，为避免未成熟收敛，应缩小个体间的差异；在进化的最后阶段， 为了加快收敛，应放大个体问的差异。常用的尺度变换有三种：线性尺度 变换、乘幂尺度变换、指数尺度变换。 4 选择算子 选择操作就是用来确定如何从父代种群中按某种方法选取哪些个体遗传到下 一代种群的遗传运算。选择操作建立在对个体的适应度进行评价的基础上，其主 要目的是为了避免基因缺失，提高全局收敛和计算效率。 常用的选择算予有：比例选择、保留最佳个体选择、期望值选择、排序选择、 随机联赛选择。 5 交叉算子 交叉操作是遗传算法中最主要的遗传操作，交叉算子的设计和实现与所研究的 问题密切相关，一般要求即不要太多破坏个体编码串中表示优良性状的优良模式， 又要能够有效地产生一些较好的新个体模式，它的设计要和个体编码设计统一考 虑。 常用的交叉算子有：单点交叉、双点交叉、多点交叉、均匀交叉、算术交叉。 6 变异算予 变异运算是指将个体染色体编码串的某些基因座上的基因值用该基因座的其 4 一个具有偏好的多目标优化新的进化算法 它等位基因来替换，从而形成了一个新个体。变异操作是产生新个体的主要方法， 它决定了遗传算法的全局搜索能力：而变异操作只是产生新个体的辅助方法，它 决定遗传算法的局部搜索能力，维持种群的多样性，防止出现早熟现象。 常用的变异算子有：基本位变异、均匀变异、边界变异、非均匀变异、高斯变 异。 7 参数设定 遗传算法中需要选择的参数主要有串长，种群规模h ，交叉概率p ，变异概 率p 。等，这些参数对遗传算法的性能影响比较大。在简单遗传算法( s c 徂) 【3 】或标准 遗传算法( c o a ) e e ，这些参数是不变的。然而，许多学者意识到这些参数需要随着 遗传算法的进程而自适应变化，这种有组织性能的遗传算法具有更高的鲁棒性、 全局最优性和效率，但会增加算法的复杂性和计算量等。还有一些参数的改进方 法，比如，模糊控制参数、模拟退火方法、基于均匀设计的参数设定等。 1 2 2 遗传算法的运算步骤 步l 初始化，设置进化代数计数器f 卜0 ，设置最大进化代数m a xg e n ，种群 规模，随机产生个个体作为初始种群m o ； 步2 个体评价，计算种群m 中各个体的适应度； 步3 选择操作，将选择算子作用于种群盯： 步4 交叉操作，将交叉算子作用于种群m 。； 步5 变异操作，将变异算子作用于种群m 。种群m 经过选择、交叉、变异操 作后得到下一代种群m “： 步6 终止条件判断，若f + l = m a xg e n ，则算法停；否则置t = f + 1 ，转步2 1 2 3 遗传算法的基础理论研究概述 1 遗传算法早期的基础理论【2 1 ，2 5 】 1 ) 模式定理 模式表示一些相似的模块，它描述了在某些位置上具有相似结构特征的个体编 码串的一个子集。在模式中具有确定基因值的位置数目称为该模式的阶；模式中 第一个确定基因值的位置和最后一个确定基因值之间的距离称为该模式的模式定 义长度。： 2 ) 积木快假设( b u i l d i n g b l o c kh y p o t h e s i s ) 由于遗传算法的求解过程并不是在搜索空间中逐一地测试各个基因的枚举组 第一章绪论5 合，而是通过一些较好的模式，像塔积木一样，将他们拼接在一起，从而逐渐地 构造出适应度越来越高的编码串。 积木块假设；个体的基因块通过选择、交叉、变异等遗传算子的作用，能够 相互拼接在一起，形成适应度更高的个体编码串。 3 1 遗传算法骗问题( g ad e c e p f i v cp r o b l e m ) 存在着一类用遗传算法难以求解的问题，这类称为“g a 难”的问题往往不满 足积木块假设，即出基因块之间的拼接，往往会欺骗遗传算法，使其进化过程偏 离最优解。硬究表面，属于“g a - 难”的问题一般包含有孤立的最优点，即在这个 最优点的周围是一些较差的点，从而使g a 较难通过基因之间的相互拼接而达到 这个最优点的模式。 4 ) 隐含并行性( i m p l i c i tp a r a l l e l i s m ) 在遗传算法的运行过程中，每代都处理了个个体，但由于一个个体编码串中 隐含有多种不同的模式，所以算法实质上却并行处理了更多的模式，所处理的模 式总数与群体规模的立方成正比。 5 ) 经典遗传算法的收敛性分析 经典遗传算法可描述为一个齐次的m a r k o v 链，因为经典遗传算法的选择、交 叉和变异操作都是独立随机进行的，新群体仅与其父代群体及遗传操作算子有关， 而与其父代之前的各代群体无关，即群体无后效性。并且各代群体之间的转移概 率与时间的起点无关。 已经证明【2 6 j 7 】：经典遗传算法收敛于最优解的概率小于l 和使用保留最佳个体 策略的经典遗传算法能以概率“1 ”收敛于全局最优解。 2 遗传算法的基础理论研究1 2 8 】 1 1 模式定理的拓广和深入 r a d c l i f f e 把模式分析进行了一般化，提出了完整的f o r m a 分析理论。在解决积 木块假设是否成立的问题上，主要研究遗传算法的骗函数，主要方法是w a l s h 变 换。目前尚未有人对隐含并行性提出改进办法，只是加以主观默认。 2 ) 遗传算法的收敛性分析 到目前为止，还没有一套完整的理论可以准确、全面地阐述一般遗传算法的 收敛性，从而对其在大量应用中所表现出的全局优化能力作出理论解释；也还没 有找到一个恰当的度量与论证方法精确刻画遗传算法在不同实现下的收敛速度， 从而对遗传算法的各种改进作出统一、公正的评判。为了保证遗传算法的收敛速 度，有两个参数非常重要：一个参数是过程进入满意解后下一步脱离满意解集的 可能性；另外一个是过程进入满意解时下一步仍不能进入满意解的可能性。这两 个参数的匹配构成了遗传算法收敛的一般理论，用这种方法研究收敛性变为纯概 6 一个具有偏好的多目标优化新的进化算法 率的方法。已有的遗传算法收敛性结果可大致分为四类： 是马氏链型：将遗传算法的种群迭代序列视为一个有限的马尔可夫链来加以 研究。主要运用种群马氏链转移概率矩阵的某些一般性，分析遗传算法的极限行 为，但由于所采用的有限状态马氏链理论本身的限制，该模型只能用于描述通常 的二进制遗传算法，另外，转移概率的具体形式很难表达，因而，对于较大规模 的遗传算法，只能借助于遍历性考察而得强租糟的结论。 二是v o s e 模型：其思想是用两个矩阵算子分别刻画比例选择与组合算子( 杂 交算子与变异算予的复合) ，通过研究这两个算子不动点的存在性与稳定性来刻画 遗传算法的渐进行为。在无限种群假设下，v o s e 模型可精确刻画遗传算法，但解 释实际有限种群遗传算法行为的能力相对差些，而且该模型只适用于简单遗传 算法，对变异，杂交概率随时间变化的情形不易处理。 三是公里化模型：徐宗本等发展了个既可用于分析时齐又可用于分析非时齐 遗传算法的公里化模型，其思想是：通过公里化描述遗传算法的选择算子与重组 算子，并利用所引起的参量分析遗传算法的收敛性。 四是连续( 积分算子) 模型：这是对采用实数编码的连续变量遗传算法的收敛 性分析，但分析连续遗传算法的框架与方法均不完善，存在黄这样或那样豹有限 或不足。没有一个好的方法可用于准确描述连续遗传算法的动态行为，并在不强 加任何严格的或人为条件下给出相关的收敛性结果。 1 3 多目标优化问题的研究概况 1 3 1 多目标优化问题的基本概念 顾名思义，多目标优化问题就是同时对多个目标进行优化删。在现实生活中， 多目标优化问题广泛地存在于科技，经济等领域。例如，在设计新产品时，我们 既要考虑使产品具有较好的功能，又要考虑使其制造成本最低，同时还孳考虑产 品的可制造性、可靠性、可维修性等，这些设计目标的改善有可能是相互抵触的 ( 如好的可维修性有可能会引起可靠性降低) ，这就需要在这些设计目标之闻取一 折衷结果。再例如投资问题，一般我们都是希望所投入的资金量最少，并且所获 得的收益最大。这种多于一个数值目标在给定区域上的最优化问题就称为多目标 优化( m u l f i o b j e c f i v eo p t i m i z a t i o n ) 。 多目标优化问题一般可描述为下面的数学模型： 第一章绪论7 f m i n f ( x ) = u b ) b l ，g ) ) p ) s t x e q( 1 1 ) iq c 7 r “ 式中，r ( x ) 为向量值函数，v ( x ) r q ，m i n 表示向量极小化，即向量目标 f ( x ) = g ) ，五( x ) ，五g ) ) 中的各个子目标函数都尽可能极小化的意思。 多目标优化问题的本质在于，在很多情况下，各个子目标有可能是相互冲突的， 一个子目标的改善有可能会引起另子目标性能的降低，也就是说，要同时使这 多个子目标都一起达到最优值是不可能的，而只能是在它们中间进行协调和折衷 处理，使各个子目标函数都尽可能地达到最优。 多目标优化问题的最优解与单目标优化问题最优解有着本质的不同，所以为了 正确地求解多目标优化问题，必须对其最优解的概念进行定义 1 6 , 3 0 , 3 ”。 定义1 1 一个向量“= 杠。， ：，) 称为优于向量v = 卜。v ：，1 ，。) ，当且仅当对任 意i l ，2 ，碍 ，有虬v i 及必存在i o 1 ，2 ，g 使得“ 0 是预先指定的一个表示 小生境范围的参数。 在计算出各个体的小生境数之后，可以使小生境数较小的个体能够有更多的机 会被选中遗传到下一代群体中，即相似个体较少的个体能够有更多的机会被遗传 到下一代群体中，这样也就增加了群体的多样性，相应地也就增加了解的多样性。 5 混合法 前面所介绍的几种求解多目标优化问题的遗传算法各有各的优点，也各有各的 缺点。例如，并列选择法易于生成单个目标函数的极端最优解，而较难生成一种 多个目标在某种程度上都比较满意的折衷解；共享函数法虽然易于生成分布比较 广的p a t e t o 最优解集合，但其搜索效率比较低。于是会很自然地意识到，如果混 合使用上述几种求解多目标优化问题的方法，将有可能尽量地克服各自的缺点， 而充分地发挥各自的优点。 1 。4 本文的主要工作及论文安排 实际中，有许多多目标优化问题常常伴随着决策者的偏好，怎样合理引入决 策者的偏好是求解偏好多目标优化问题的关键。决策者的偏好往往是不能精确定 量的，并且带有一定的随机性，结合实际，本文提出了一种新的多目标偏好方法 模型。另外，现有的多目标进化算法收敛性理论十分欠缺，为此本文就一种多目 标优化问题模型进行了收敛性分析。主要工作包括： 1 对偏好多目标优化闯题，现有的多目标偏好方法存在着一些不足之处，结合实 际情况，本文提出了多决策者随机性偏好方法，并对该偏好方法的相关理论进 行了比较详细的分析。并对此算法进行了大量的数值实验，结果表明了该偏好 第一章绪论 多目标遗传算法的有效性和可行性。 2 对一般的多目标优化问题进化算法模型，至今还没有比较完善的收敛性理论。 以往的有关多目标收敛性理论都是针对特定的多目标优化问题模型。为此，本 文在设计出新型进化算子的基础上，提出了一种新的多目标优化问题进化算法 模型，并对其进行了比较详细的收敛性分析。 本文的安排如下： 第一章为绪论，首先介绍遗传算法的概况，包括遗传算法的基本框架、执行策 略的改进、算法步骤以及基础理论的研究概况。其次，介绍了多目标优化问题的 研究概况，包括多目标优化问题的基础理论及求解多目标优化问题的常规方法。 在第二章里，首先介绍了偏好多目标优化问题的研究概况，接着针对偏好多目标 优化问题提出了一种新型多目标偏好方法，结合遗传算子，紧接着提出了偏好多 目标遗传算法。并通过数值实验，对偏好多目标遗传算法的相关参数进行了分析。 在第三章里，首先介绍了多目标优化问题进化算法收敛性理论概况，接着在设计 新型进化算子和相关假设下，提出了一种新的多目标优化问题进化算法模型。然 后并对该多目标优化问题进化算法模型进行了比较详细的收敛性分析。 1 2 一个具有偏好的多目标优化新的进化算法 第二章多决策者随机性偏好在多目标遗传算法中的应用 2 1 引言 多目标优化问题的描述如下： ( 脚俨，啦呸曼世h 例 、 7 lx q c 震” r 其中，f ( x l r 9 ，f ( x ) 为r ”上的向量值函数。在实际生活中，多目标优化问 题广泛存在，如顾客购物问题，在购买商品时，顾客不但要考虑商品的质量好坏， 而且还要考虑商品的价格高低。如，商家投资问题，商家在投资某项冒对，既要 考虑到投入的资金，人力，物力多少，还耍考虑到利润的多少。 上述多目标问题各个单目标的最优解之间往往是相互矛盾的，一般不可能所 有目标同时达到最优解例如，当顾客购买东西时既想买到质量好的东西，又想价 格便宜往往不能同时满足。商家在投资某项目时，很难通过投入很少的资金、人 力、物力和时间来获得较高的利润。因而对多目标优化问题只能求出备目标的 些折衷解，即所谓的p a r e t o 最优解，或有效解【1 6 】。 实际中，存在很多多目标优化问题，决策者对各个单目标存在着偏好，即各 目标的重要性不一样。比如对于上述顾客购物闯题，有些顾客看重的是商品的质 量，而不太在乎商品的价格高低，但有些顾客却不太在乎商品的质量，在乎商品 的价格高低。 另外，据心理学研究显示，人们并不擅长于处理大量的没有量化的重要数据 1 3 p - - 4 0 。不能把这些数据量化成计算机所需的数据，多目标优化问题中各单目标的 重要性就是一个典型的例子，人们往往知道各单目标之问重要性并不相等，但却 不知道怎么去处理各单目标之间的重要性关系。 为此，在一些多目标优化问题中，如果各单目标之间重要性不均等，引入决 策者的偏好是有必要的。引入决策者的偏好可以帮助人们处理大量的没有量化的 重要数据，将这些数据量化成计算机所需的数据。 2 2 多目标优化问题的偏好方法研究现状 在多目标优化问题中引入决策者的偏好方法比较多。c o e l l oc o e l l o 对多目 标优化问题的偏好方法进行了专门的统计和研究】。 第二章多决策者随机性偏好在多目标遗传算法中的应用1 3 将决策者的偏好引入多目标优化问题，实质上是通过某种方式将决策者对各 目标的偏好大小转化为各目标的权重。最初将偏好应用于多目标优化问题，其实 就是给每个单目标分配一个权重，而且权重只能是0 或1 。即决策者对任意个 目标要么是完全肯定，要么是完全否定，不加以考虑。这种偏好方法明显带有很 大的局限性，现实中的多目标优化问题各目标间的关系很少有这种情况。 目前的偏好方法h 2 蛳1 大部分都是对各目标的重要性关系进行关键词的描述， 再通过某种变换将这种目标间的重要性关系转化为各目标的劝重。决策者在描述 目标间重要性关系时所采用的关键词如下： “比重要” “比重要得多” “和一样重要” “比次要” “比次要得多” 即对任意两个目标的重要性关系，决策者用上述关键词进行语言判断。这种 偏好方法存在着几个方面的缺陷。 第一、对任意两个目标，决策者部须对它们的重要性关系进行关键词的描 述( 判断) ，所需的描述次数为c ；= 去9 0 1 ) ，在现实中，这种要求 决策者进行判断次数太多，不可取。 第二、决策者对各目标间的重要性关系进行关键词描述时，描述的结果可 能出现逻辑矛盾。如：目标1 比目标2 重要，目标2 又比目标3 重 要，同时目标3 又比目标1 重要，这样目标间的关系就出现了逻辑 矛盾。 第三、尽管可以采用更多的关键词来描述各目标间的重要性关系，但还是 远远不能够满足刻画目标间重要性细微关系的需要。如：目标l 比 目标2 重要，目标2 比目标3 重要，目标3 比目标4 重要，目标4 比目标5 重要，这样目标l 和目标4 的关系就和目标l 和目标5 的 关系一样了，显然不成立。 2 3 多目标模糊性偏好方法 最近一两年内，有关多目标偏好方法的文献不多，下面介绍一种典型的多目 标偏好方法：模糊性偏好【4 5 1 。该偏好方法在目前的多目标偏好方法中具有典型性 和代表性。 该偏好方法首先定义了三个二元关系和两个一元关系，如下所示： “y 。a y ：”表示y 与y 2 同等重要； 1 4 个具有偏好的多目标优化新的进化算法 “儿 ，2 ”表示y l 不如j ，2 重要； “y l y 2 ”表示y l 远不如y 2 重要； “叫1 ”表示y l 不重要； “! ，。”表示y 。重要； 并定义以下推理规则和性质 “z ”满足自反性、对称性，传递性，即 y y f ) ，l2 y 2jy 24 y l y l y 2a y 22 y 3jy l “y 3 “ ”和“ - ”不满足自反性，和对称性，但满足传递性，等等，如下： y 1 - y 2 y 2 y 3 3 y l y 3 y y 2a y 2 y l y 3 y l 一( y 2 y 2 y 3j y l y 3 y l y 2a y 2 y ) ：y 1 y 3 只 y l y 2 1 y ja 2j y 2 y l 劁y 2 y 1 ，2a y 2 ) 与= ，y l 叫 y 3 在上述规则下，决策者只要对部分目标间的重要性关系进行判断即可由上述 推理规则推出任意两个目标问的重要性关系。 各目标的权重的产生方法如下 步l 由决策者根据偏好把所有目标分成一些等价类，即每个等价类里的目标 是同等重要的。 再从每个等价类中选出一个目标组成一个目标集合，假设为 z = 涉l ，y 2 ，y ，j 步2 由决策者根据偏好判断z 中部分个体间的重要性关系，并由这些关系根 据上述推理规则可以推出z 中任意两个目标间的重要性关系。 步3 定义如下关系 如果口“b ，则如) = 以施) = 如果口 b ，则v ( 口) = ，v ( 6 ) = 占 如果口“b ，贝o ，如) = v 岱) = 兰 二 其中口，卢，y ，6 ( o ，1 ) ，且满足口 ，叫妻 子 p ，a + = y + 6 = 1 上 步4 在步3 的定义下，根据z 中任意两个目标问的重要性关系产生偏好矩 第二章多决策者随机性偏好在多目标遗传算法中的应用1 5 阵p ； 步5 由矩阵_ p 推出z 中各目标的权重，再根据同一个等价类里各目标权重相 等，可得出所有目标的权重。 以上具体过程见文献【4 5 l 中介绍。 由上述过程可看出，该偏好方法明显存在着以下不足之处： 1 ) 决策者对各目标的偏好受推理规则的约束。即决策者在不考虑推理规则 时，完全根据偏好对任意两个目标进行重要性判断，判断的结果可能会与 推理规则矛盾。 2 ) 决策者难以确定对哪些目标问的重要性关系进行判断才可以按照推理规 则推出任意两个目标间的重要性关系。 3 ) 同样，推理规则中所采用的目标间重要性关系关键词不能亥0 画出目标问细 微的重要性关系。 基于上述考虑，提出以下偏好方法。 2 4 多决策者随机性偏好方法 2 4 1 多决策者随机性偏好方法的产生背景 现实生活中的一些多目标优化问题往往存在着决策者的偏好，即每个目标的重 要性在决策者心目中是不一样的，可能决策者很看熏某些个别目标，而对其它目 标并不是那么重视。有时，多目标优化问题会同时存在多个决策者的偏好，下面 举个实例来说明。 在跳水比赛中，裁判主要是根据运动员在跳水过程中一些主要的动作环节的 好坏情况进行打分的。比如，运动员起跳动作、空中翻转动作，落水动作等，这 些都是裁判对运动员的主要打分环节。但是，每个打分环节在裁判心目中的重要 性地位是不一样的，比如，在裁判心目中运动员落水动作可能会比起跳时的动作 重要很多，因而，运动员落水时动作优美比起跳时动作的优美对他的得分影响大 得多。 另外，跳水比赛中，往往有几个裁判同时参与评分，每个裁判对运动员的打 分情况都不一样。最后，运动员的得分就是去掉一个最高分和一个最低分后的平 均分。表2 。1 是某一跳水运动员的一次跳水后各裁判的打分情况。 16 一个具有偏好的多目标优化新的进化算法 注：该评分标准与实际评分标准有差异，只是作理论分析用。 由上可看出，如果把跳水过程中每个得分环节看作是一个优化目标，则跳水 运动员的最后得分其实就是一个多目标优化问题( 对每个目标求最大) ，只不过这 里每个目标函数没有一个具体的表达式。 由上实例可看出对某些多目标优化问题来说引入多决策者的偏好是有必要 的，具有_ 定的实际意义。 同时，决策者对各目标的偏好通常是难以精确定量的，例如，裁判员给跳水 运动员的每个动作的打分就是一个不确定的值，因为对跳水运动员一样的动作， 同一裁判多次打分的结果可能会不一样。从这个意义上来说，决策者的偏好带有 一定的随机性。而且，呈某种分布。 为此，下面介绍多决策者随机性偏好。 2 4 2 多决策者随机性偏好的产生方法 1 初始偏好向量的产生 多目标的随机性偏好方法可分为多决策者随机性偏好和单决策者随机性偏 好。对多决策者随机性偏好，其主要思想是由多个决策者根据偏好，并以某个目 标为基准目标，对其他目标进行打分，目标的分值大小表示该目标相对于基准目 标的重要性大小，由各目标的平均分值形成些特定区间，并在这些特定区间内 产生服从正态分布的随机向量，其分量就是各目标的权重，代表了各目标的重要 性大小。单决策者随机性偏好方法是多决策者随机性偏好方法的一个特例。下面 介绍多决策者随机性偏好方法的决策者打分方法。 设有k 个决策者参与打分，k l 。从上述g 个目标工，五，工中随机选一个 目标作为基准目标，为方便，取基准目标正的分值为1 0 0 ，以基准目标正的分 值为参照，任选一个目标z ，f = 1 , 2 ，q 。且i s ，对目标，：进行打分，分值的大小 代表重要性的大小。假设各决策者打分结果分别为：s c ：，胛? ，s c ，其平均分值 第二章多决策者随机性偏好在多目标遗传算法中的应用1 7 为i _ = ? 。记基准目标五的平均分值甄为1 0 0 ，则由各目标的平均分值计 算第f 个目标的初始权重分别为： 砭：i ，i ：l 2 一，q l 0 1 l 艺弼 z l 定义2 1( 偏好向量或权重向量) 由决策者偏好，对各目标z ，江1 , 2 ，吁产生一个权重国，所有目标的权重 组成的向量就是偏好向量或权重向量出= 。，：，j 。显然，每个偏好向量就 代表决策者的一种偏好。 2 偏好向量的产生 由于各决策者对目标间重要性关系的判断是一种不精确的判断，故上述基于多 决策者打分而产生的初始权重不能精确地代表各目标间的重要性关系，须对其修 正。通常。人们对某些不确定但可以定量判断的事物进行多次判断时，其多次判 断的结果往往呈正态分布。因而，可以认为偏好向量= 。，：，) 是服从某 个正态分布的随机向量。其产生方法如下： ( 1 ) 确定哦，j = 1 , 2 ，譬的产生区间为( 互一属，蕊+ 万) ，其中厂为修正决 策者对各目标重要性的判断结果不准确程度的系数，由经验值，在( 0 ，0 3 ) 内取 值较合理。 ( 2 ) 确定吐，。，f ：1 , 2 ，垡的均方差q ，为使产生的椰。基本上都落在区问 一厄，面+ 痧) 内，可取q = 喜厩； j ( 3 ) 在瓴一庖，蕊+ 厄) 内，产生服从正态分布，砰) 的随机变数脚，。 由概率论知识1 4 7 1 可以知道。落在区间随一属，瓦+ 万) 的概率大小为： p 慨一面i g e 2 ，x 1 ) ，称f 为最优系数。 由上定义，对q 中的任意两点x 1 ，x 2 ，显然g b l ，善2 ) + g b 2 ，x 1 ) l 成立。 定义2 3 ：( 基于偏好的最优解或n p 点或有效解) m 设x q ，对给定g o 和f ，若不存在另外一点f e q ，使得一- x ，则称x 为 基于偏好的n p 点或有效解。由所有的基于偏好的陋点或有效解组成的点集合称 为基于偏好的n p 点集或有效解集，记为e ( f ，q ，f ，) e ( f ，q ，r ，国) = 叫x n 且不存在一e q 使得x ；工 定义2 4 ：( 基于偏好的最优界面或p a r e t o 界面或有效界面) 对偏好多目标问题( 2 1 ) ，由所有的基于偏好的n p 点的目标函数值组成的集 合就是问题( 2 1 ) 基于偏好的p a r e t o 界面或有效界面，记为f e ，q ，f ，甸 2 进化算予 1 ) 适应度函数 甩( f ，n f ) = f g h e ，d ，l 硼 第二章多决策者随机性偏好在多目标遗传算法中的应用1 9 假设当前处于种群肘= x lx 2 , x n ，x 蔓t j m 中任意一点，则x 的适应度 函数值为： f i r n e 即g ) ；妻f 羔m i n t 即g ) 一z b ，) l o ) 1 。( - q )e 即g ) = l m i n t 即g ) 一z b ，强o ) | ( - q ) 1 l 2 i 其中，n 为种群规模，国= h ，：，峨) 为随机产生的偏好向量。根据适 应度值的大小，可对种群m 中的个体进行最优性比较，适应度值大的个体最优 性好。 2 ) 局部搜索 为了加速算法对最优解的搜索，采取对部分个体进行局部搜索。搜索方法 如下：设随机产生的偏好向量国= 。，：，) ，x 为种群m 。中以概率以选择 出来的个体，对其进行局部搜索： m i n 杰q z g ) ：妻。，g t ) 其中，一为x 搜索的后代，具体的搜索方法见文献【4 8 】。显然，种群m t 中任 一个体x 经局部搜索后，其后代的最优性不会比x 差。 3 ) 对种群进行基于偏好的n p 点分层方法 为了从种群m 及其中间种群厨中选择出下一代种群，须对其进行于偏好的 n p 点分层。由定义2 2 可以把种群m u 厨分成有限个基于偏好的n p 点层，同 一个基于偏好的n p 点层上各点在给定的偏好( 或者说偏好向量) 下最优性相等。 具体方法如下：先确定出种群m u 厨。中所有的基于偏好的n p 点，并把它们划 分到第一层c 。，然后再在m u 厨一c l 中确定出所有的基于偏好的n p 点划分到 第二层c ：，同样在m u 砑一c 。一c 2 中确定出所有的基于偏好的n p 点划分到第 三层e ，如此下去，直到将种群肘u 厨中所有点划分完毕。 所采用的算法如下： f o re a c h p m u 厨 s p = o ，一，= o ，c 1 = o ； f o r e a c hq m u 面 p ：g t h e nsetift h e ns e t s 。：s 。u g ；e n dp g。= s 。 g ； i f g j p t h e n s e t 月p2 p + l ；e n d 生二个具有偏好的多目标优化新的进化算法 e n d i f 刀，= 0 t h e ns e t p = 1 ；q = c lu 斟；e n d p m 表示，所在的层数 e n d s e ti = 1 ；e = c ，； w h i l ec 。中 q = ； f o r e a c h p c ， f o r e a c h g s 。 n q = n 口一1 ； e n d e n d f o r e a c h p m 。u m 一c i f 珂p = 0 t h e n p 越= i + 1 ；q = q u ( p ；e n d e n d i = i 十1 ；c t = 9 ；c = qu c ； e n d 用同样的方法也可对无偏好的多目标进化算法种群进行n p 分层。 4 ) 保留最优选择算子 设第f 代种群材。经过进化算子后得后代种群露，对m u 露进行基于偏好的 n p 分层，层数越小，基于偏好的最优性越好，则按照以下规则( 两个规则同时考 虑) ，可进行选择下一代种群材“1 ： a 层数小的个体优先： b 同一层中，基于偏好的适应度值大的个体优先。 3 算法的基本步骤 步1 确定种群的规模大小n ，最大进化代数m a x 一，杂交概率n ，变异 概率p 。，搜索概率p 。； 步2 由多个决策者根据偏好对各目标进行打分，确定出偏好向量的产生范 围，并随机产生偏好向量c o = 慨，：，吼) 步3 从可行解集q 中随机产生个服从均匀分布的个体，作为初始种群 m o ，令，= 0 ； 步4 对第r 代种群m 用杂交算：j 3 0 1 ，变异算子1 3 0 进行进化，并去掉不可行 第二章多决策者随机性偏好在多目标遗传算