多目标优化方法课件.ppt

1、第二部分第二部分 多目标优化方法多目标优化方法 Multi-Objective Optimization 第一节第一节 概述概述 第三节第三节 多目标优化的第一类方法多目标优化的第一类方法 第二节第二节 多目标优化设计理论多目标优化设计理论 第四节第四节 多目标优化的第二类方法多目标优化的第二类方法 第五节第五节 多目标优化的第三类方法多目标优化的第三类方法国际上通常认为多目标最优化问题最早是在国际上通常认为多目标最优化问题最早是在18861886年由法国经年由法国经济学家济学家ParetoPareto从政治经济学的角度提出的。多目标规划的真从政治经济学的角度提出的。多目标规划的真正发达时期，

2、并正式作为一个数学分支进行系统的研究，是正发达时期，并正式作为一个数学分支进行系统的研究，是上世纪七十年代以后的事。上世纪七十年代以后的事。现在，对多目标规划方面的研究集中在以下几个方面现在，对多目标规划方面的研究集中在以下几个方面:一、关于解的概念及其性质的研究，一、关于解的概念及其性质的研究，二、关于多目标规划的解法研究，二、关于多目标规划的解法研究，三、对偶问题的研究，三、对偶问题的研究，四、不可微多目标规划的研究，四、不可微多目标规划的研究，五、多目标规划的应用研究。五、多目标规划的应用研究。到现在为止，多目标优化不仅在理论上取得许多重要成果，到现在为止，多目标优化不仅在理论上取得许多

3、重要成果，而且在应用上其范围也越来越广泛，多目标决策作为一个工而且在应用上其范围也越来越广泛，多目标决策作为一个工具在解决工程技术、经济、管理、军事和系统工程等众多方具在解决工程技术、经济、管理、军事和系统工程等众多方面的问题也越来越显示出它强大的生命力。面的问题也越来越显示出它强大的生命力。第一节第一节 概述概述1.1.多目标优化设计示例多目标优化设计示例11221 max()45 max()f XxxfXx目标函数示例示例1 1：某工厂生产两种产品：某工厂生产两种产品A A和和B,B,每件产品每件产品A A需制造工时需制造工时和装配工时分别为和装配工时分别为1 1时和时和1.251.25时

4、，每件产品时，每件产品B B需制造工时和需制造工时和装配工时分别为装配工时分别为1 1时和时和0.750.75时，每月制造车间和装配车间时，每月制造车间和装配车间能够提供的最多工时为能够提供的最多工时为200200时，另外，每月市场对产品时，另外，每月市场对产品A A需需求量很大，而对产品求量很大，而对产品B B的最大需求量为的最大需求量为150150件，产品件，产品A A和产和产品品B B的售价分别为的售价分别为4 4元和元和5 5元，问如何安排每月的生产，最元，问如何安排每月的生产，最大限度的满足市场需求，并产值最大？大限度的满足市场需求，并产值最大？12ABxx设计变量：产品 的件数，产

5、品 的件数0,1 .*61 max*min21222122121xxxxt sxxxx示例示例2.2.用直径为用直径为1(1(单位长单位长)的圆木制成截面为矩形的圆木制成截面为矩形的梁的梁,为使重量最轻为使重量最轻,而强度最大而强度最大,问截面的高与宽问截面的高与宽应取何尺寸应取何尺寸?解解:设矩形截面的高与宽分别设矩形截面的高与宽分别 为和为和 ,这时这时梁的面积为梁的面积为 ,它决定重量它决定重量,而梁的强度取而梁的强度取决于截面形决于截面形 。1x2x21*xx221*61xx因此因此,容易列出容易列出 梁的数学模型梁的数学模型:示例示例3 3 物资调运问题物资调运问题:某种物资寸放三个

6、仓库某种物资寸放三个仓库 里里,存放量分别为存放量分别为 (单位单位:t);:t);现要将这些物资运往四个销售现要将这些物资运往四个销售点点 。其需要量分别为。其需要量分别为 且且 ，已知，已知 到到 的距离和单位的距离和单位运价分别为运价分别为 (km)(km)和和 (元元),),现要决定如何现要决定如何调运多少调运多少,才能使总的吨才能使总的吨,公里数和总运费都尽量少公里数和总运费都尽量少?123,A A A123,a a a1234,B B B B1234,b b b b34ijijabiAjBijdijc解:设变量 表示由 运往 的货物数,于是总吨公里数为 ,总运费为 ,问题优化设计模

7、型为11ijijijxd4,3,2,1;3,2,1,jixijiAjB4,3,2,1;3,2,1,04,3,2,1,3,2,1,.*min*min314131413141jixjbxiaxtsxcxdijijijiiijijijijijijij11ijijijxc示例示例4 4：如图所示，设计一苦空心阶梯悬臂梁，根据结构要如图所示，设计一苦空心阶梯悬臂梁，根据结构要求，已确定梁的总长为求，已确定梁的总长为10001000mmmm，第一段外径为，第一段外径为8080mmmm，第二段外经为第二段外经为100100mmmm，梁的端部受有集中力，梁的端部受有集中力F F12000N12000N，梁的内

8、径不得小于梁的内径不得小于4040mmmm，梁的许用弯曲应力为梁的许用弯曲应力为180MPa180MPa，确定梁的内径和各段长度，使梁的体积和静挠度最小。确定梁的内径和各段长度，使梁的体积和静挠度最小。1 12 2D1=100D1=100D2=80D2=80L=1000L=1000 x1x2F F 多目标优化设计模型多目标优化设计模型6117422232419.78 10.()18004.096 10()75.20()400()0 xstg XxgXxgXxgXx12xx设计变量：第一段梁的长度，梁的内径22221122112()()()()4f Xx DxLxDx33214444442212

9、126411()()3LfXxEDxDxDx12min()(),)(TF Xf XfX 多目标最优化问题的一般形式为多目标最优化问题的一般形式为:S.t.或者记作:min D=12min(),(),()mf xf xfx()0,1,2.,()0,1,2,ijg xiph xjq()f x|()0,()0nxEg xh x xD 其中:=()()f x 1(),()mf xfx1()()()pg xg xgx1()()()qh xh xh x 2.2.多目标优化设计模型多目标优化设计模型iGxFy为满足所有目标的参数 组成的参数空间为根据 按照目标函数 映射的组成的目标函数空间注意，这里以及注意

10、，这里以及之后的所有讲述之后的所有讲述同时同时适合于线性适合于线性和非线性的多目和非线性的多目标优化标优化多目标优化设计几何描述多目标优化设计几何描述在单目标优化问题中，任何两个解都可以比较出其优劣，这是在单目标优化问题中，任何两个解都可以比较出其优劣，这是因为单目标优化问题是完全有序的；而在多目标优化设计中，因为单目标优化问题是完全有序的；而在多目标优化设计中，任何两个解不一定都可以比较出其优劣，这是因为多目标优化任何两个解不一定都可以比较出其优劣，这是因为多目标优化问题是半有序的。问题是半有序的。3.3.多目标优化问题解的特点多目标优化问题解的特点T(1)(1)(1(1)(1)()(1)1

11、2T(2)(2)(2)(2)12(1)(2)(1)(21)()2()(),(),()()(),(),(),()()(1,2,)mmllF Xf XfXfXF Xf Xff XfXfXXXlmXXXXX设为多目标优化问题的两个可行解，其对应若对于每一个分量，都则显然，优的目标函数于，记为有为(1)(2)(1)(2)(2)(1)(2)(1)(2)()()()()()()()jjllF XF XfXfXF Xf Xf XXX大多数情况下，的某几个分量小于的对应分量，但另外几个分量大于的对应分量 则显然，与无法比较优劣。1f2f213第一类：转化法。这类多目标最优化方法的基本思想是将多目标第一类：转化

12、法。这类多目标最优化方法的基本思想是将多目标问题转化为一个或一系列的单目标优化问题，通过求解一个或一问题转化为一个或一系列的单目标优化问题，通过求解一个或一系列单目标优化问题来完成多目标优化问题的求解。系列单目标优化问题来完成多目标优化问题的求解。4.4.多目标优化方法分类多目标优化方法分类第二类：非劣解集法。这类多目标最优化方法的基本思想是求第二类：非劣解集法。这类多目标最优化方法的基本思想是求得多目标问题的非劣解集，然后在非劣解集中进行协调和选择，得多目标问题的非劣解集，然后在非劣解集中进行协调和选择，确定出优惠解。确定出优惠解。第三类：交互协调法。这类多目标最优化方法的基本思想是通第三类

13、：交互协调法。这类多目标最优化方法的基本思想是通过在分析者与抉择者间的不断交互，逐渐搞清抉择者的选择意过在分析者与抉择者间的不断交互，逐渐搞清抉择者的选择意图，获得多目标问题的优惠解。图，获得多目标问题的优惠解。第二节第二节 多目标优化设计理论多目标优化设计理论 1.1.多目标优化设计模型多目标优化设计模型.()0 1,2,()0 1,2,uvstgXuph Xvq 简记为简记为 VOP多目标优化问题多目标优化问题(Multi-Objective Optimization Problem)又称为向量优化问题又称为向量优化问题(Vector Optimization Problem)。12min

14、()(),(),()TmF Xf XfXfX()V-mi nnF XXDR 2.2.决策空间与目标空间决策空间与目标空间()0 1,2,()0 1,2,=uvngXupXhXvqDXR 以设计变量为坐标的实空间以设计变量为坐标的实空间Rn称为决策空间。称为决策空间。以目标函数为坐标的实空间以目标函数为坐标的实空间Rm称为目标空间。称为目标空间。决策空间可行域：决策空间可行域：目标空间可行域目标空间可行域12=(),(),(),mTFmXDFRFfXfXfXXD 示例示例1 1112212324152.()2000()200 1.250.750()1500()0()0stg XxxgXxxgXx

15、gXxgXx决策空间决策空间可行域可行域目标空间目标空间可行域可行域T121max F()45 Xxxx，示例示例2 26117422232419.78 10.()18004.096 10()75.20()400()0 xstg XxgXxgXxgXx22221122112()()()()4f Xx DxLxDx决策空间决策空间可行域可行域目标空间目标空间可行域可行域12min()(),()TF Xf XfX33214444442212126411()()3LfXxEDxDxDx3.3.解的定义解的定义（1 1）理想解理想解(ideal solution)000012,TmFfff在目标空间内

16、，以单目标最小值为分量而形成的点，在目标空间内，以单目标最小值为分量而形成的点，称为多目标问题的理想解称为多目标问题的理想解。0min()njjffXXDR其中 在多目标优化问题中，在多目标优化问题中，由于各个目标间往往是由于各个目标间往往是矛盾的，所以一般不存矛盾的，所以一般不存在使各目标皆达到各自在使各目标皆达到各自最优值的理想解最优值的理想解。fxX(0)f1(0)f2(0)f1f2（2 2）非劣解（非劣解（Noninferior Solution）或）或 Pareto 解解()()pF XF X对于可行点对于可行点XP D，若不若不存在另一个可行点存在另一个可行点X D，使使()()1

17、,2,()()ppjjllfXfXjmfXfX 但至少有一个 成立，则称成立，则称Xp为多目标问题的非劣解。为多目标问题的非劣解。向量不等式的含义为向量不等式的含义为决策空间决策空间非劣解集非劣解集目标空间目标空间非劣解集非劣解集7.1 模型举例0,1 .*61 max*min21222122121xxxxt sxxxx例7.1.用直径为1(单位长)的圆木制成截面为矩形的梁,为使重量最轻,而强度最大,问截面的高与宽应取何尺寸?解:设矩形截面的高与宽分别 为和 ,这时梁的面积为 ,它决定重量,而梁的重量取决于截面矩形 。1x2x21*xx221*61xx因此,容易列出 梁的数学模型:例7.2 物

18、资调运问题:某种物资寸放三个仓库 里,存放量分别为 (单位:t);现要将这些物资运往四个销售点 .其需要量分别为 且 ，已知 到 的距离和单位运价分别为 (km)和 (元),现要决定如何调运多少,才能使总的吨,公里数和总运费都尽量少?123,A A A123,a a a1234,B B B B1234,b b b b34ijijabiAjBijdijc解:设变量 表示由 运往 的货物数,于是总吨公里数为 ,总运费为 ,问题优化为求解11ijijijxd4,3,2,1;3,2,1,jixijiAjB4,3,2,1;3,2,1,04,3,2,1,3,2,1,.*min*min31413141314

19、1jixjbxiaxtsxcxdijijijiiijijijijijijij11ijijijxc由于求最大都可以转化为求最小由于求最大都可以转化为求最小,所以多目标最优化问所以多目标最优化问题的一般形式为题的一般形式为:S.t.或者记作:min D=12min(),(),()pf xf xfxljxhmixgji,2,1,0)(,.2,1,0)()f x|()0,()0pxEg xh x xD 其中:=()()f x 1(),()pf xfx1()()()mg xg xgx1()()()mh xh xhx 当P=1时,(VP)就是非线性规划,称为单目标规划。对于单目标问题Min ,总可比较 与

20、 的大小.对于多目标规划(VP),对于 ，与 都是P 维向量,如何比较两个向量的大小?()f x 12,x xD1()f x2()f x12,x xD1()f x2()f x可以看到：可以看到：多目标优化的非劣解集Noninferior solution for the model*xxx(xx)x若，且对于 不存在，使得：与能同时成立，那么则定义 为多目标优化问题的非劣解。例如：A,B点属于非劣解，因为不满足定义条件（3 3）满意解（最佳协调解或优惠满意解（最佳协调解或优惠解）解）11(),(),()mUU f Xf XfX效用函数值的大小反映决策者对多目标值的喜爱程度，效用函数值的大小反映

21、决策者对多目标值的喜爱程度，一般来说，决策者希望效用函数的值越大越好。一般来说，决策者希望效用函数的值越大越好。效用函数：效用函数：决策者对多目标函数优化解进行评价的函数，记为决策者对多目标函数优化解进行评价的函数，记为使效用函数取最大值的非劣解称为最佳协调解。使效用函数取最大值的非劣解称为最佳协调解。对于效用函数未知对于效用函数未知的情况，无法直接的情况，无法直接求得最佳协调解。求得最佳协调解。我们把多目标优化我们把多目标优化过程满意结束的解过程满意结束的解称为优惠解。称为优惠解。满意解满意解4 4 多目标优化问题的多目标优化问题的K KT T条件条件对于多目标优化问题对于多目标优化问题.(

22、)0 1,2,()0 1,2,uvstgXuph Xvq VOP(),1,2,;(),1,2,;(),1,2,;juvfXjm gXup h Xvq设*VOPjuvXXw皆为连续可微函数，为可行点，则为（）的非劣解的必要条件为：存在、与使*1*1()()()02()01,2,301,2,401,2,pqmjjuuvvjuvuuujwfXgXh XgX up up w jm （）（）（）（）（）（）（）（）12min()(),(),()TmF Xf XfXfX7.4 求解多目标规划的评价函数法求解多目标规划的评价函数法 尽管多目标优化问题有各种意义下的最优解.但在应用中,需要的还是有效解和弱有效

23、解.本节介绍求有效解和弱有效解最基本的方法-评价函数法.评价函数法的基本思想是:借助于几何或应用中的直观效果.构造所谓的评价函数.从而将多目标优化问题转化为单目标优化问题.然后利用单目标优化问题的求解方法求出最优解.并把这种最优解当作多目标优化问题的最优解.这里关键的问题是转化后的单目标优化问题的最优解必须是多目标问题的有效解和弱有效解.否则是不能接受的.所谓评价函数,是利用(VP)的目标函数 ,构造一个复合函数 .然后在(VP)的约束集D上极小化 ,的构造必须保证在一定条件下,min 的最优解是(VP)的有效解或弱有效解.下面先讨论在什么条件下,min 的最优解才能是(VP)min 的有效解

24、or弱有效解.()f x()f x()f x()f x()f x()f x定义6.设 :1.若 ,总有 ,则称 为 的严格单增函数.2 若 时,总有 ,则称 为 的单增函数.,:pnPEEfDEE12ZZ12()()ZZ()ZZ12ZZ12()()ZZ()ZZ定理1 .设：:,又设 ，是问题min 的极小点,那么:若 为Z的严格单增函数,则 是min 有效解.若 为Z的单增函数,则 是min 的弱有效解.pEE:nPfDEE*x()f x*x*x()f x()f x重要定理几种常用的构造评价函数的方法一.理想点法:在(VP)中,先求解P个单目标问题 j=1，2，p xD 设其最优值为 ,我们称

25、 为值域中的一个理想点。min()jfx*jf*12(,)Tpffff 因为一般很难达到它,这样,就期望在某种等量下,寻求距最近的f作为近似值,一种最直接的想法是构造评价函数 =（7.2）()Z2*1()piiiZf 然后极小化即求解：并将它的最优解 作为(VP)在这种意义下的“最优解”,由于 ,因此由7.2构造的 是严格单增的,从而 是(VP)的有效解.*21min()()piiif xf xf*x*()iiiZf xf()Z*x二.线性加权和法.在具有多个指标的问题中,人们总希望对那些相对重要的指标给予较大的权系数,基于这种现实,自然如下的构造评价函数,令 12,1(,)|01pTpiii

26、 且12,1(,)|01pTpiii 且称之为权向量集,令 再求解而将它的最优解,作为(VP)在该意义下的最优解.1()*,pTiiiP ZZZormin()*()Tf xf x*x三.极大极小法 在决策时，采取保守策略是稳妥的。即在最坏的情况下，寻求最好的结果。按照这种想法，可以构造如下评价函数 然后求解 并将它的最优解 作为（VP）在这种意义下的最优解。ipizz1max)()(maxmin)(min1xfxfipiDxDxx 1.1.主目标法主目标法 转化为转化为 第三节第三节 多目标优化的第一类方法多目标优化的第一类方法主目标法就是从多目标中依据重要程度选择一个目标主目标法就是从多目标

27、中依据重要程度选择一个目标作为主目标，而将其它目标转化为约束，即将多目标作为主目标，而将其它目标转化为约束，即将多目标优化问题优化问题12min()(),(),()s.t.()01,2,()01,2,TmuvF Xf XfXfXgXuph Xvq0min ()s.t.()01,2,()01,2,()1,2,kuvllfXgXuph Xvqf Xflm lk主目标法中约束目标的约束值选取主目标法中约束目标的约束值选取0*1,2,lllfflm lk*()min()1,2,XllllXDff Xff Xlm lk式中为目标函数的单目标极小值，即 *()0.010.02)1,2,llllf Xflm

28、 lk式中为对目标函数的单目标极小值的放大值，一般可取 （2.2.线性加权法线性加权法 转化为转化为线性加权法就是将多目标的加权和作为单目标，即将线性加权法就是将多目标的加权和作为单目标，即将多目标优化问题多目标优化问题12min()(),(),()s.t.()01,2,()01,2,TmuvF Xf XfXfXgXuph Xvqmin()()s.t.()01,2,()01,2,mllluvF Xw f XgXuph Xvq(2(2）对权系数的要求）对权系数的要求(3)(3)权系数的确定权系数的确定 0 1,2,lwlm非负要求1 1mllw归一化要求 老手法老手法*1 min()lllXDl

29、wff Xf线性加权法的有关说明：线性加权法的有关说明：（1)1)线性加权之前，各目标应进行无量纲化处理。线性加权之前，各目标应进行无量纲化处理。3.3.极小极大法极小极大法 转化为转化为极小极大法就是求取多目标函数中的最大值，然后使极小极大法就是求取多目标函数中的最大值，然后使最大值函数在可行域内极小化，即将多目标优化问题最大值函数在可行域内极小化，即将多目标优化问题12min()(),(),()s.t.()01,2,()01,2,TmuvF Xf XfXfXgXuph Xvq1min max ()s.t.()01,2,()01,2,ll muvf XgXuph Xvq (2)(2)极小极大

30、法也可以引入一个变量极小极大法也可以引入一个变量 和和m个约束，即个约束，即极小极大法的有关说明：极小极大法的有关说明：（1)1)考虑到各目标的重要程度差别，可以对各目标考虑到各目标的重要程度差别，可以对各目标乘以权系数，然后再求最大值函数，即乘以权系数，然后再求最大值函数，即1min max ()s.t.()01,2,()01,2,lll muvw f XgXuph Xvq min s.t.()01,2,()01,2,()1,2,uvllgXuph Xvqw f Xjm 4.4.理想点法理想点法 转化为转化为理想点法就是将距理想点最近的点作为多目标问题的理想点法就是将距理想点最近的点作为多目

31、标问题的优惠解，即将多目标优化问题优惠解，即将多目标优化问题12min()(),(),()s.t.()01,2,()01,2,TmuvF Xf XfXfXgXuph Xvq200()min()s.t.()01,2,()01,2,mlllluvf XfU XfgXuph Xvq00012mfff其中，为多目标问题在目标空间中的理想点。理想点法的有关说明：理想点法的有关说明：考虑到各目标的重要程度差别，可以对各目标乘以权考虑到各目标的重要程度差别，可以对各目标乘以权系数，即系数，即权系数的选取可以参阅线性加权法。权系数的选取可以参阅线性加权法。200()min()s.t.()01,2,()01,2

32、,mllllluvf XfU XwfgXuph Xvq 5.5.功效系数法功效系数法在多目标优化问题，各目标的要求不全相同，有的要在多目标优化问题，各目标的要求不全相同，有的要求极小化，有的要求极大化，有的要求有一个合适的求极小化，有的要求极大化，有的要求有一个合适的数值。为了反映这些不同的要求，故引入如下的功效数值。为了反映这些不同的要求，故引入如下的功效函数：函数：0110jjjjjccfcf的取值为，表示目标 的值最满意；表示目标 的值最不满意。()1,2,jjcF fjm1 2 maxUjmmcc cc取所有 的几何平均值为多目标问题的评价函数，即功效系数的确定：功效系数的确定：1.1

33、.直线法直线法 2.2.折线法折线法 3.3.指数法指数法 6.6.分层序列法分层序列法将多目标优化问题的各目标分清主次，按其重要程度将多目标优化问题的各目标分清主次，按其重要程度逐一排序，然后依次对各目标函数求最优解，但应注逐一排序，然后依次对各目标函数求最优解，但应注意后一目标应在前一目标的最优解域内进行寻优。意后一目标应在前一目标的最优解域内进行寻优。()1,2,jfXjm设目标函数的重要程度排序为*11 min()f XfXD首先对第一个目标函数求最优值*22*11 min()()fXfXDX f Xf在第一个目标函数的最优解域中，求第二个目标函数的最优解，即照此继续下去，最后求得第照

34、此继续下去，最后求得第mm个目标函数得最优解，个目标函数得最优解，真个解即为多目标优化问题的最终解。真个解即为多目标优化问题的最终解。在分层序列法中，当前面有某个目标函数的最优解唯一在分层序列法中，当前面有某个目标函数的最优解唯一时，该方法就发生中断现象，因此需要引入目标容差。时，该方法就发生中断现象，因此需要引入目标容差。*11 min()f XfXD首先对第一个目标函数求最优值*22*111 min()()fXfXDX f Xf在第一个目标函数的最优解容差域中，求第二个目标函数的最优解，即 7.7.协调曲线法协调曲线法协调曲线法主要用于求解两个目标函数的多目标优协调曲线法主要用于求解两个目

35、标函数的多目标优化设计问题。化设计问题。目标规划法目标规划法Goal Attainment Method 引入目标概念：引入目标概念：F*，令非劣解集到目标的，令非劣解集到目标的距离（或称范数）最小，选出一个非劣解。距离（或称范数）最小，选出一个非劣解。Wi引入了一个松弛度的概念，松弛度最小引入了一个松弛度的概念，松弛度最小的一个非劣解就是对于目标的一个非劣解就是对于目标F*的最可行解。的最可行解。优点：不漏解，目标明确，计算量小。优点：不漏解，目标明确，计算量小。缺点：对于非线性规划设计：缺点：对于非线性规划设计：运用连续运用连续二次形规划二次形规划(SQP-sequential quadr

36、atic programming)，线性的权值松弛在局部，线性的权值松弛在局部搜索范围内，会导致拒绝可大幅改进总体搜索范围内，会导致拒绝可大幅改进总体目标的小步搜索。目标的小步搜索。只针对连续问题，可只针对连续问题，可能只能给出局部最优解。能只能给出局部最优解。改进：阅读改进：阅读Matlab Optimization Toolbox 3.0.1 Users Guide中中Algorithm Improvements for Goal Attainment Method一节内容。一节内容。1.1.变权系数法变权系数法 对于非负的权系数，若线性加权函数对于非负的权系数，若线性加权函数在线性加权法

37、中，系列地改变权系数值，可获得大量在线性加权法中，系列地改变权系数值，可获得大量的非劣解，形成非劣解集。的非劣解，形成非劣解集。第四节第四节 多目标优化的第二类方法多目标优化的第二类方法存在唯一的最优解，则该最优解是多目标问题的存在唯一的最优解，则该最优解是多目标问题的非劣解。非劣解。min()()s.t.()01,2,()01,2,mllluvF Xw f XgXuph Xvq 2.2.约束法约束法 转化为转化为从多目标中依据重要程度选择一个目标作为主目标，从多目标中依据重要程度选择一个目标作为主目标，而将其它目标转化为约束，即将多目标优化问题而将其它目标转化为约束，即将多目标优化问题12m

38、in()(),(),()s.t.()01,2,()01,2,TmuvF Xf XfXfXgXuph Xvqmin ()s.t.()01,2,()01,2,()1,2,kuvllfXgXuph Xvqf Xlm lk可以证明，对于一组可以证明，对于一组 值，值，若若X*为为 约束问题的约束问题的唯一最优解，则其一定为多目标问题的一个非劣唯一最优解，则其一定为多目标问题的一个非劣解。解。通过系列地改变通过系列地改变 值值，可获得大量的非劣解，形成非，可获得大量的非劣解，形成非劣解集。劣解集。值应大于值应大于各单目标函数的最优值，可依据实际情况各单目标函数的最优值，可依据实际情况在下列范围中变化：在

39、下列范围中变化：约束法有关说明约束法有关说明00(0.001 0.01)1,2,jjjffjm jk 1.1.逐步法逐步法在迭代过程中，分析者向决策者不断提供试验解及在迭代过程中，分析者向决策者不断提供试验解及其相应的目标函数值，请决策者指出哪一个目标值其相应的目标函数值，请决策者指出哪一个目标值可以增加，哪一个目标值应减少。分析者根据决策可以增加，哪一个目标值应减少。分析者根据决策者的意图，增添新的约束，求得新的试验解，进入者的意图，增添新的约束，求得新的试验解，进入下一步迭代。直到求出使决策者满意的优惠解。下一步迭代。直到求出使决策者满意的优惠解。逐步法逐步法(Step Method)是是

40、1971年由年由Benayoun等人提出的等人提出的求解线性多目标优化问题的一种交互式方法，此方法求解线性多目标优化问题的一种交互式方法，此方法本质是在某种范数下求距理想点最近的点。本质是在某种范数下求距理想点最近的点。第五节第五节 多目标优化的第三类方法多目标优化的第三类方法 对于线性多目标优化问题对于线性多目标优化问题 定义定义1211min()(),(),()s.t.1,2,01,2,()1,2,TmnuiiiiinjjiiiF Xf XfXfXa xbupxinfXc x jm其中12121,12,max,mmwjjjjmmFfffPp ppFPwfpWw ww两点和间的距离为 其中为

41、给定非负的权系数。逐步法的计算步骤逐步法的计算步骤 （1 1）建立支付表）建立支付表 min(),1,2,jjfXXDXjm求解得每个单目标的极小点f1 f2 fm 1 2 m 11()f X12()fX1()mfX1()mf X2()mfX()mmfX21()f X22()fX2()mfX1,min(),1,2,ijjimmfXjm各列的最小值为，为理想点。(1)1,max(),1,2,;,12ijjimMfXjm DD k各列的最大值为转（）。（2 2）求第）求第k次迭代点次迭代点()1,()()min max()(),1,2,kjjjXjmkkjwfXmXDXfXjm求解得每个单目标的极

42、小点和相应的目标函数值1/,1,2,mjjllwjm这 里12211221,0,0mjjjljljjmjjjljljMmcMMmMcMm当其中 当 （3 3）与决策者对话）与决策者对话将目标函数值提供给决策者，若决策者对所有目标将目标函数值提供给决策者，若决策者对所有目标值皆满意，则获得优惠解，停止计算；若决策者对值皆满意，则获得优惠解，停止计算；若决策者对所有目标值皆不满意，则计算失败，停止计算；若所有目标值皆不满意，则计算失败，停止计算；若决策者对部分目标值满意，对部分目标值不满意，决策者对部分目标值满意，对部分目标值不满意，则继续计算。则继续计算。在满意的目标中选一个目标在满意的目标中选

43、一个目标fj*，并给出一个可以牺牲，并给出一个可以牺牲的量的量 fj*，意思是愿意让，意思是愿意让目标目标fj*增大增大 fj*，以换取，以换取其它其它不满意目标值的减小。并进行如下计算：不满意目标值的减小。并进行如下计算：*(1)()()()*(),(),1,2,kkkjjjkjjDXDffXfffXjm jj*0,1,jkkkm令若此法失败；否则转(2).2.2.代替价值交换法代替价值交换法代替价值交换法代替价值交换法(Surrogate Worth Trade-off Method)是是1971年由年由Haimes等人提出的求解非线性多目标优化问等人提出的求解非线性多目标优化问题的一种交

44、互式方法。题的一种交互式方法。其其 约束问题为约束问题为对于多目标优化问题对于多目标优化问题12min()(),(),()s.t.()01,2,()01,2,TmuvF Xf XfXfXgXuph Xvqmin ()s.t.()01,2,()01,2,()1,2,kuvllfXgXuph Xvqf Xlm lk 约束问题的约束问题的K KT T条件条件 可以证明，约束目标函数对应的可以证明，约束目标函数对应的LagrangeLagrange乘子乘子pqmkjjuuvvjj kuvjjjjuuufXwfXgXh XwfX w jm jk gX up*1,*1()()()()02()001,2,3

45、()001,2,（）（）（）（）（）（）kjjfw jm jkf1,2,即约束目标函数对应的即约束目标函数对应的LagrangeLagrange乘子乘子wj是目标是目标fk对对目标目标fj的交换率。的交换率。分析者与决策者的交互分析者与决策者的交互分析者求得一个非劣解（即分析者求得一个非劣解（即 约束问题的最优解）约束问题的最优解）X(k)，及其对应的所有目标函数值与，及其对应的所有目标函数值与约束目标函数约束目标函数对应的对应的LagrangeLagrange乘子乘子wj，向决策者提问：，向决策者提问：在目标值在目标值f1(X(k),fm(X(k)时，你愿意时，你愿意在其它目标值在其它目标值

46、保持不变的条件下，以目标保持不变的条件下，以目标fj增大一个单位量增大一个单位量，而换，而换取取目标目标fj减小减小wj单位量吗？单位量吗？决策者通过给代替价值函数决策者通过给代替价值函数Skj赋值，回答上述问题。赋值，回答上述问题。代替价值函数代替价值函数Skj赋值规律如下：赋值规律如下：（1 1）若决策者同意上述交换，应给）若决策者同意上述交换，应给Skj赋正值，其值赋正值，其值越大表示越赞成；越大表示越赞成；（2 2）若决策者同意反向交换，即赞成以目标）若决策者同意反向交换，即赞成以目标fj减小减小一个单位量一个单位量，而换取，而换取目标目标fj增大增大wj单位量，单位量，应应给给Skj

47、赋负值，其绝对值越大表示越赞成；赋负值，其绝对值越大表示越赞成；（3 3）若决策者对上述两种交换都不赞成，应给）若决策者对上述两种交换都不赞成，应给Skj赋赋零值。零值。代替价值函数代替价值函数Skj赋值规律赋值规律Skj取值范围是取值范围是1010到到1010之间的整数，其取值含之间的整数，其取值含义为：义为：代替价值交换法的计算步骤代替价值交换法的计算步骤 （1 1）求各目标的极大值和极小值）求各目标的极大值和极小值()min()max(),1,2,kjjjjfXfXXDfXXDmMjm选一个作为主目标函数，分别求解 和得每个单目标的极小值和极大值 （2 2）求非劣解）求非劣解得最优解和得

48、最优解和约束目标函数对应的乘子。约束目标函数对应的乘子。求求 约束问题约束问题min ()s.t.()01,2,()01,2,()1,2,kuvllfXgXuph Xvqf Xlm lk(3)(3)代替价值函数代替价值函数Skj赋值赋值将所求得的最优解和将所求得的最优解和约束目标函数对应的乘子提供约束目标函数对应的乘子提供给决策者，决策者依据自己对目标函数的喜爱程度给决策者，决策者依据自己对目标函数的喜爱程度和具体问题要求，给代替价值函数和具体问题要求，给代替价值函数Skj赋值。赋值。(4)(4)求最终解求最终解若对某个非劣解，对应的所有若对某个非劣解，对应的所有代替价值函数代替价值函数Skj值皆值皆为零，则该非劣解为最终解，停止计算。否则，用为零，则该非劣解为最终解，停止计算。否则，用回归分析法，建立代替价值函数的近似表达式回归分析法，建立代替价值函数的近似表达式:1211(,)1,2,kjkjkkmSSfffffjm jk(5)(5)构造新的构造新的 约束问题约束问题1211(,)0 1,2,kjkkmSfffffjm jk求解方程组求解方程组得得*1211,kkmfffff令令*,1,2,jjfjm jk形成形成 约束问题约束问题转（转（2 2）。）。min ()s.t.()01,2,()01,2,()1,2,kuvllfXgXuph Xvqf Xlm lk