多目标优化方法ppt课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,多目标优化方法,Multi-Objective Optimization,第一节,概述,第三节,多目标优化的第一类方法,第二节,多目标优化设计理论,第四节,多目标优化的第二类方法,第五节,多目标优化的第三类方法,1,国际上通常认为多目标最优化问题最早是在,1886,年由法国经济学家,Pareto,从政治经济学的角度提出的。多目标规划的真正发达时期，并正式作为一个数学分支进行系统的研究，是上世纪七十年代以后的事。,现在，对多目标规划方面的研究集中在以下几个方面,:,一、关于解的概念及其性质的研究，,二、关于多目标规划的解法研究，,三、对偶问题的研究，,四、不可微多目标规划的研究，,五、多目标规划的应用研究。,到现在为止，多目标优化不仅在理论上取得许多重要成果，而且在应用上其范围也越来越广泛，多目标决策作为一个工具在解决工程技术、经济、管理、军事和系统工程等众多方面的问题也越来越显示出它强大的生命力。,第一节 概述,2,1.,多目标优化设计示例,示例,1,：某工厂生产两种产品,A,和,B,每件产品,A,需制造工时和装配工时分别为,1,时和,1.25,时，每件产品,B,需制造工时和装配工时分别为,1,时和,0.75,时，每月制造车间和装配车间能够提供的最多工时为,200,时，另外，每月市场对产品,A,需求量很大，而对产品,B,的最大需求量为,150,件，产品,A,和产品,B,的售价分别为,4,元和,5,元，问如何安排每月的生产，最大限度的满足市场需求，并产值最大？,3,多目标优化设计模型,4,示例,2,：,如图所示，设计一苦空心阶梯悬臂梁，根据结构要求，已确定梁的总长为,1000,mm,，第一段外径为,80,mm,，第二段外经为,100,mm,，梁的端部受有集中力,F,12000N,，梁的内径不得小于,40,mm,，,梁的许用弯曲应力为,180MPa,，确定梁的内径和各段长度，使梁的体积和静挠度最小。,1,2,D1=100,D2=80,L=1000,x,1,x,2,F,5,多目标优化设计模型,6,在单目标优化问题中，任何两个解都可以比较出其优劣，这是因为单目标优化问题是完全有序的；而在多目标优化设计中，任何两个解不一定都可以比较出其优劣，这是因为多目标优化问题是半有序的。,2.,多目标优化问题解的特点,7,2,1,3,8,第一类：转化法。这类多目标最优化方法的基本思想是将多目标问题转化为一个或一系列的单目标优化问题，通过求解一个或一系列单目标优化问题来完成多目标优化问题的求解。,3.,多目标优化方法分类,第二类：非劣解集法。这类多目标最优化方法的基本思想是求得多目标问题的非劣解集，然后在非劣解集中进行协调和选择，确定出优惠解。,第三类：交互协调法。这类多目标最优化方法的基本思想是通过在分析者与抉择者间的不断交互，逐渐搞清抉择者的选择意图，获得多目标问题的优惠解。,9,第二节 多目标优化设计理论,1.,多目标优化设计模型,简记为,VOP,多目标优化问题,(,Multi-Objective Optimization Problem,),又称为向量优化问题,(,Vector Optimization Problem,),。,10,2.,决策空间与目标空间,以设计变量为坐标的实空间,R,n,称为决策空间。,以目标函数为坐标的实空间,R,m,称为目标空间。,决策空间可行域：,目标空间可行域,11,示例,1,决策空间可行域,目标空间可行域,12,示例,2,决策空间可行域,目标空间可行域,13,3.,解的定义,（,1,）理想解,(,ideal solution,),在目标空间内，以单目标最小值为分量而形成的点，称为多目标问题的理想解,。,在多目标优化问题中，由于各个目标间往往是矛盾的，所以一般不存在使各目标皆达到各自最优值的理想解,。,f,x,X,(0),f,1,(0),f,2,(0),f,1,f,2,14,（,2,）非劣解（,Noninferior Solution,）或,Pareto,解,对于可行点,X,P,D,，,若不,存在另一个可行点,X,D,，,使,成立，则称,X,p,为多目标问题的非劣解。,向量不等式的含义为,决策空间非劣解集,目标空间非劣解集,15,（,3,）满意解（最佳协调解或优惠,解）,效用函数值的大小反映决策者对多目标值的喜爱程度，一般来说，决策者希望效用函数的值越大越好。,效用函数：,决策者对多目标函数优化解进行评价的函数，记为,使效用函数取最大值的非劣解称为最佳协调解。,对于效用函数未知的情况，无法直接求得最佳协调解。我们把多目标优化过程满意结束的解称为优惠解。,满意解,16,4,多目标优化问题的,K,T,条件,对于多目标优化问题,VOP,17,1.,主目标法,转化为,第三节 多目标优化的第一类方法,主目标法就是从多目标中依据重要程度选择一个目标作为主目标，而将其它目标转化为约束，即将多目标优化问题,18,主目标法中约束目标的约束值选取,19,2.,线性加权法,转化为,线性加权法就是将多目标的加权和作为单目标，即将多目标优化问题,20,(2,）对权系数的要求,(3),权系数的确定,老手法,线性加权法的有关说明：,（,1),线性加权之前，各目标应进行无量纲化处理。,21,3.,极小极大法,转化为,极小极大法就是求取多目标函数中的最大值，然后使最大值函数在可行域内极小化，即将多目标优化问题,22,(2),极小极大法也可以引入一个变量,和,m,个约束，即,极小极大法的有关说明：,（,1),考虑到各目标的重要程度差别，可以对各目标乘以权系数，然后再求最大值函数，即,23,4.,理想点法,转化为,理想点法就是将距理想点最近的点作为多目标问题的优惠解，即将多目标优化问题,24,理想点法的有关说明：,考虑到各目标的重要程度差别，可以对各目标乘以权系数，即,权系数的选取可以参阅线性加权法。,25,5.,功效系数法,在多目标优化问题，各目标的要求不全相同，有的要求极小化，有的要求极大化，有的要求有一个合适的数值。为了反映这些不同的要求，故引入如下的功效函数：,26,功效系数的确定：,1.,直线法,2.,折线法,3.,指数法,27,6.,分层序列法,将多目标优化问题的各目标分清主次，按其重要程度逐一排序，然后依次对各目标函数求最优解，但应注意后一目标应在前一目标的最优解域内进行寻优。,28,照此继续下去，最后求得第,m,个目标函数得最优解，真个解即为多目标优化问题的最终解。,在分层序列法中，当前面有某个目标函数的最优解唯一时，该方法就发生中断现象，因此需要引入目标容差。,29,7.,协调曲线法,协调曲线法主要用于求解两个目标函数的多目标优化设计问题。,30,1.,变权系数法,对于非负的权系数，若线性加权函数,在线性加权法中，系列地改变权系数值，可获得大量的非劣解，形成非劣解集。,第四节 多目标优化的第二类方法,存在唯一的最优解，则该最优解是多目标问题的非劣解。,31,2.,约束法,转化为,从多目标中依据重要程度选择一个目标作为主目标，而将其它目标转化为约束，即将多目标优化问题,32,可以证明，对于一组,值，,若,X,*,为,约束问题的唯一最优解，则其一定为多目标问题的一个非劣解。,通过系列地改变,值,，可获得大量的非劣解，形成非劣解集。,值应大于,各单目标函数的最优值，可依据实际情况在下列范围中变化：,约束法有关说明,33,1.,逐步法,在迭代过程中，分析者向决策者不断提供试验解及其相应的目标函数值，请决策者指出哪一个目标值可以增加，哪一个目标值应减少。分析者根据决策者的意图，增添新的约束，求得新的试验解，进入下一步迭代。直到求出使决策者满意的优惠解。,逐步法,(,Step Method,),是,1971,年由,Benayoun,等人提出的求解线性多目标优化问题的一种交互式方法，此方法本质是在某种范数下求距理想点最近的点。,第五节 多目标优化的第三类方法,34,对于线性多目标优化问题,定义,35,逐步法的计算步骤,（,1,）建立支付表,f,1,f,2,f,m,1,2,m,36,（,2,）求第,k,次迭代点,37,（,3,）与决策者对话,将目标函数值提供给决策者，若决策者对所有目标值皆满意，则获得优惠解，停止计算；若决策者对所有目标值皆不满意，则计算失败，停止计算；若决策者对部分目标值满意，对部分目标值不满意，则继续计算。,在满意的目标中选一个目标,f,j*,，并给出一个可以牺牲的量,f,j*,，意思是愿意让,目标,f,j*,增大,f,j*,，以换取,其它不满意目标值的减小。并进行如下计算：,38,2.,代替价值交换法,代替价值交换法,(,Surrogate Worth Trade-off Method,),是,1971,年由,Haimes,等人提出的求解非线性多目标优化问题的一种交互式方法。,其,约束问题为,对于多目标优化问题,39,约束问题的,K,T,条件,可以证明，约束目标函数对应的,Lagrange,乘子,即约束目标函数对应的,Lagrange,乘子,w,j,是目标,f,k,对目标,f,j,的交换率。,40,分析者与决策者的交互,分析者求得一个非劣解（即,约束问题的最优解）,X,(,k,),，及其对应的所有目标函数值与,约束目标函数对应的,Lagrange,乘子,w,j,，向决策者提问：,在目标值,f,1,(,X,(,k,),),f,m,(,X,(,k,),),时，你愿意,在其它目标值保持不变的条件下，以目标,f,j,增大一个单位量,，而换取,目标,f,j,减小,w,j,单位量吗？,决策者通过给代替价值函数,S,kj,赋值，回答上述问题。代替价值函数,S,kj,赋值规律如下：,41,（,1,）若决策者同意上述交换，应给,S,kj,赋正值，其值越大表示越赞成；,（,2,）若决策者同意反向交换，即赞成以目标,f,j,减小一个单位量,，而换取,目标,f,j,增大,w,j,单位量，,应给,S,kj,赋负值，其绝对值越大表示越赞成；,（,3,）若决策者对上述两种交换都不赞成，应给,S,kj,赋零值。,代替价值函数,S,kj,赋值规律,S,kj,取值范围是,10,到,10,之间的整数，其取值含义为：,42,代替价值交换法的计算步骤,（,1,）求各目标的极大值和极小值,（,2,）求非劣解,得最优解和,约束目标函数对应的乘子。,求,约束问题,43,(3),代替价值函数,S,kj,赋值,将所求得的最优解和,约束目标函数对应的乘子提供给决策者，决策者依据自己对目标函数的喜爱程度和具体问题要求，给代替价值函数,S,kj,赋值。,(4),求最终解,若对某个非劣解，对应的所有,代替价值函数,S,kj,值皆为零，则该非劣解为最终解，停止计算。否则，用回归分析法，建立代替价值函数的近似表达式,:,44,(5),构造新的,约束问题,求解方程组,得,令,形成,约束问题,转（,2,）。,45,