多目标优化方法

第二部分多目标优化方法

Multi-ObjectiveOptimization第一节概述第三节多目标优化的第一类方法第二节多目标优化设计理论第四节多目标优化的第二类方法第五节多目标优化的第三类方法国际上通常认为多目标最优化问题最早是在1886年由法国经济学家Pareto从政治经济学的角度提出的。多目标规划的真正发达时期，并正式作为一个数学分支进行系统的研究，是上世纪七十年代以后的事。现在，对多目标规划方面的研究集中在以下几个方面:一、关于解的概念及其性质的研究，二、关于多目标规划的解法研究，三、对偶问题的研究，四、不可微多目标规划的研究，五、多目标规划的应用研究。到现在为止，多目标优化不仅在理论上取得许多重要成果，而且在应用上其范围也越来越广泛，多目标决策作为一个工具在解决工程技术、经济、管理、军事和系统工程等众多方面的问题也越来越显示出它强大的生命力。第一节概述1.多目标优化设计示例示例1：某工厂生产两种产品A和B,每件产品A需制造工时和装配工时分别为1时和1.25时，每件产品B需制造工时和装配工时分别为1时和0.75时，每月制造车间和装配车间能够提供的最多工时为200时，另外，每月市场对产品A需求量很大，而对产品B的最大需求量为150件，产品A和产品B的售价分别为4元和5元，问如何安排每月的生产，最大限度的满足市场需求，并产值最大？示例2.用直径为1(单位长)的圆木制成截面为矩形的梁,为使重量最轻,而强度最大,问截面的高与宽应取何尺寸?解:设矩形截面的高与宽分别为和,这时梁的面积为,它决定重量,而梁的强度取决于截面形。因此,容易列出梁的数学模型:示例3物资调运问题:某种物资寸放三个仓库里,存放量分别为(单位:t);现要将这些物资运往四个销售点。其需要量分别为且，已知到的距离和单位运价分别为(km)和(元),现要决定如何调运多少,才能使总的吨,公里数和总运费都尽量少?解:设变量表示由运往的货物数,于是总吨公里数为,总运费为,问题优化设计模型为示例4：如图所示，设计一苦空心阶梯悬臂梁，根据结构要求，已确定梁的总长为1000mm，第一段外径为80mm，第二段外经为100mm，梁的端部受有集中力F＝12000N，梁的内径不得小于40mm，梁的许用弯曲应力为180MPa，确定梁的内径和各段长度，使梁的体积和静挠度最小。12D1=100D2=80L=1000x1x2F多目标优化设计模型

多目标最优化问题的一般形式为:S.t.或者记作:minD=其中:=()

2.多目标优化设计模型注意，这里以及之后的所有讲述同时适合于线性和非线性的多目标优化多目标优化设计几何描述在单目标标优化问问题中，，任何两两个解都都可以比比较出其其优劣，，这是因因为单目目标优化化问题是是完全有有序的；；而在多多目标优优化设计计中，任任何两个个解不一一定都可可以比较较出其优优劣，这这是因为为多目标标优化问问题是半半有序的的。3.多多目标优优化问题题解的特特点213第一类：：转化法法。这类类多目标标最优化化方法的的基本思思想是将将多目标标问题转转化为一一个或一一系列的的单目标标优化问问题，通通过求解解一个或或一系列列单目标标优化问问题来完完成多目目标优化化问题的的求解。。4.多多目标优优化方法法分类第二类：：非劣解解集法。。这类多多目标最最优化方方法的基基本思想想是求得得多目标标问题的的非劣解解集，然然后在非非劣解集集中进行行协调和和选择，，确定出出优惠解解。第三类：：交互协协调法。。这类多多目标最最优化方方法的基基本思想想是通过过在分析析者与抉抉择者间间的不断断交互，，逐渐搞搞清抉择择者的选选择意图图，获得得多目标标问题的的优惠解解。第二节多多目目标优化化设计理理论1.多多目标优优化设计计模型简记为VOP多目标优优化问题题(Multi-ObjectiveOptimizationProblem)又称为为向量优优化问题题(VectorOptimizationProblem)。2.决决策空间间与目标标空间以设计变变量为坐坐标的实实空间Rn称为决策策空间。。以目标函函数为坐坐标的实实空间Rm称为目标标空间。。决策空间间可行域域：目标空间间可行域域示例1决策空间可行域目标空间可行域示例2决策策空空间间可可行行域域目标标空空间间可可行行域域3.解解的的定定义义（1））理理想想解解(idealsolution)在目目标标空空间间内内，，以以单单目目标标最最小小值值为为分分量量而而形形成成的的点点，，称称为为多多目目标标问问题题的的理理想想解解。在多多目目标标优优化化问问题题中中，，由由于于各各个个目目标标间间往往往往是是矛矛盾盾的的，，所所以以一一般般不不存存在在使使各各目目标标皆皆达达到到各各自自最最优优值值的的理理想想解解。fxX(0)f1(0)f2(0)f1f2（2））非非劣劣解解（（NoninferiorSolution）或或Pareto解对于于可可行行点点XPD，，若不不存在在另另一一个个可可行行点点XD，使成立立，，则则称称Xp为多多目目标标问问题题的的非非劣劣解解。。向量量不不等等式式的的含含义义为为决策空间非劣解集目标空间非劣解集7.1模模型型举举例例例7.1.用用直直径径为为1(单单位位长长)的的圆圆木木制制成成截截面面为为矩矩形形的的梁梁,为为使使重重量量最最轻轻,而而强强度度最最大大,问问截截面面的的高高与与宽宽应应取取何何尺尺寸寸?解:设设矩矩形形截截面面的的高高与与宽宽分分别别为为和和,这这时时梁梁的的面面积积为为,它它决决定定重重量量,而而梁梁的的重重量量取取决决于于截截面面矩矩形形。。因此此,容容易易列列出出梁的的数数学学模模型型:例7.2物资资调调运运问问题题:某种种物物资资寸寸放放三三个个仓仓库库里里,存存放放量量分分别别为为(单单位位:t);现现要要将将这这些些物物资资运运往往四四个个销销售售点点.其其需需要要量量分分别别为为且，，已已知知到到的的距距离离和和单单位位运运价价分分别别为为(km)和和(元元),现现要要决决定定如如何何调调运运多多少少,才才能能使使总总的的吨吨,公公里里数数和和总总运运费费都都尽尽量量少少?解:设设变变量量表表示示由由运运往往的的货货物物数数,于于是是总总吨吨公公里里数数为为,总总运运费费为为,问问题题优优化化为为求求解解由于于求求最最大大都都可可以以转转化化为为求求最最小小,所所以以多多目目标标最最优优化化问问题题的的一一般般形形式式为为:S.t.或者者记记作作:minD=其中中:=()当P=1时时,(VP)就就是是非非线线性性规规划划,称称为为单单目目标标规规划划。。对于于单单目目标标问问题题Min,总总可可比比较较与的的大大小小.对于多目标标规划(VP),对对于，，与与都都是P维向向量,如何何比较两个个向量的大大小?可以看到：：多目标优化化的非劣解解集

Noninferiorsolutionforthemodel例如：A,B点属于于非劣解，，因为不满足定义义条件②（3）满满意解（最最佳协调解解或优惠解）效用函数值值的大小反反映决策者者对多目标标值的喜爱爱程度，一一般来说，，决策者希希望效用函函数的值越越大越好。。效用函数：：决策者对多多目标函数数优化解进进行评价的的函数，记记为使效用函数数取最大值值的非劣解解称为最佳佳协调解。。对于效用函函数未知的的情况，无无法直接求求得最佳协协调解。我我们把多目目标优化过过程满意结结束的解称称为优惠解解。满意解4多目目标优化问问题的K－－T条件对于多目标标优化问题题VOP7.4求求解多多目标规划划的评价函函数法尽管多目标标优化问题题有各种意意义下的最最优解.但但在应用中中,需要的的还是有效效解和弱有有效解.本本节介绍求求有效解和和弱有效解解最基本的的方法-----评评价函数法法.评价函数法法的基本思思想是:借借助于几何何或应用中中的直观效效果.构造造所谓的评评价函数.从而将多多目标优化化问题转化化为单目标标优化问题题.然后利利用单目标标优化问题题的求解方方法求出最最优解.并并把这种最最优解当作作多目标优优化问题的的最优解.这里关键键的问题是是转化后的的单目标优优化问题的的最优解必必须是多目目标问题的的有效解和和弱有效解解.否则是是不能接受受的.所谓评价函函数,是利利用(VP)的目标标函数,构造造一个复合合函数.然后在(VP)的的约束集D上极小化化,的的构造必须须保证在一一定条件下下,min的的最优解解是(VP)的有效效解或弱有有效解.下面先讨论论在什么条条件下,min的的最优解解才能是(VP)min的的有效效解or弱弱有效解.定义6.设设:1.若,总有,则称称为为的的严格格单增函数数.2若时时,总总有,则称为为的的单单增函数.定理1.设：：:,又设，，是问问题min的的极小点,那么:若为为Z的严严格单增函函数,则是是min有有效效解.若为为Z的单单增函数,则是是min的的弱弱有效解.重要定理几种常用的的构造评价价函数的方方法一.理理想点法:在(VP)中,先求求解P个单单目标问题题j=1，2，，px∈D设其最优值值为,我我们称为值域中的的一个理想想点。因为一般很很难达到它它,这样,就期望在在某种等量量下,寻求求距最近的的f作为近近似值,一一种最直接接的想法是是构造评价价函数=（7.2））然后极小化化即求解：：并将它的最最优解作作为为(VP)在这种意意义下的“最优解””,由于,因此由由7.2构构造的是严格单增增的,从而而是是(VP)的有效解解.二.线线性加权和和法.在具有多个个指标的问问题中,人人们总希望望对那些相对重要要的指标给给予较大的的权系数,基于这种种现实,自然然如下的构构造评价函函数,令称之为权向向量集,令令再求解而将它的最最优解,作作为(VP)在该意意义下的最最优解.三.极大大极小法在决策时，，采取保守守策略是稳稳妥的。即即在最坏的的情况下，，寻求最好好的结果。。按照这种种想法，可可以构造如如下评价函函数然后求解并将它的最最优解作作为为（VP））在这种意意义下的最最优解。1.主目目标法转化为第三节多多目标优优化的第一一类方法主目标法就就是从多目目标中依据据重要程度度选择一个个目标作为为主目标，，而将其它它目标转化化为约束，，即将多目目标优化问问题主目标法中中约束目标标的约束值值选取2.线性性加权法转化为线性加权法法就是将多多目标的加加权和作为为单目标，，即将多目目标优化问问题(2）对权权系数的要要求(3)权权系数的确确定老手法线性加权权法的有有关说明明：（1)线线性加加权之前前，各目目标应进进行无量量纲化处处理。3.极极小极大大法转化为极小极大大法就是是求取多多目标函函数中的的最大值值，然后后使最大大值函数数在可行行域内极极小化，，即将多多目标优优化问题题(2)极极小极大大法也可可以引入入一个变变量和m个约束，，即极小极大大法的有有关说明明：（1)考考虑到到各目标标的重要要程度差差别，可可以对各各目标乘乘以权系系数，然然后再求求最大值值函数，，即4.理理想点法法转化为理想点法法就是将将距理想想点最近近的点作作为多目目标问题题的优惠惠解，即即将多目目标优化化问题理想点法法的有关关说明：：考虑到各各目标的的重要程程度差别别，可以以对各目目标乘以以权系数数，即权系数的的选取可可以参阅阅线性加加权法。。5.功功效系数数法在多目标标优化问问题，各各目标的的要求不不全相同同，有的的要求极极小化，，有的要要求极大大化，有有的要求求有一个个合适的的数值。。为了反反映这些些不同的的要求，，故引入入如下的的功效函函数：功效系数数的确定定：1.直线线法2.折线线法3.指数数法6.分分层序列列法将多目标标优化问问题的各各目标分分清主次次，按其其重要程程度逐一一排序，，然后依依次对各各目标函函数求最最优解，，但应注注意后一一目标应应在前一一目标的的最优解解域内进进行寻优优。照此继续续下去，，最后求求得第m个目标标函数得得最优解解，真个个解即为为多目标标优化问问题的最最终解。。在分层序序列法中中，当前前面有某某个目标标函数的的最优解解唯一时时，该方方法就发发生中断断现象，，因此需需要引入入目标容容差。7.协协调曲线线法协调曲线线法主要要用于求求解两个个目标函函数的多多目标优优化设计计问题。。目标规划划法GoalAttainmentMethod引入目标标概念：：F*，令非劣劣解集到到目标的的距离（（或称范范数）最最小，选选出一个个非劣解解。Wiγ引入了一一个松弛弛度的概概念，松松弛度最最小的一一个非劣劣解就是是对于目目标F*的最可行行解。优点：不不漏解，，目标明明确，计计算量小小。缺点：对对于非线线性规划划设计：：①运用连续续二次形形规划(SQP-sequentialquadraticprogramming)，线性性的权值值松弛在在局部搜搜索范围围内，会会导致拒拒绝可大大幅改进进总体目目标的小小步搜索索。②只针对对连续问问题，可可能只能能给出局局部最优优解。改进：阅阅读MatlabOptimizationToolbox3.0.1User‘sGuide中中AlgorithmImprovementsforGoalAttainmentMethod一节节内容。。1.变变权系数数法对于非负负的权系系数，若若线性加加权函数数在线性加加权法中中，系列列地改变变权系数数值，可可获得大大量的非非劣解，，形成非非劣解集集。第四节多多目目标优化化的第二二类方法法存在唯一一的最优优解，则则该最优优解是多多目标问问题的非非劣解。。2.－约束法转化为从多目标标中依据据重要程程度选择择一个目目标作为为主目标标，而将将其它目目标转化化为约束束，即将将多目标标优化问问题可以证明明，对于于一组值，若X*为－约束问题题的唯一一最优解解，则其其一定为为多目标标问题的的一个非非劣解。。通过系列列地改变变值，可获得得大量的的非劣解解，形成成非劣解解集。值应大大于各单目标标函数的的最优值值，可依依据实际际情况在在下列范范围中变变化：－约束法有有关说明明1.逐逐步法在迭代过过程中，，分析者者向决策策者不断断提供试试验解及及其相应应的目标标函数值值，请决决策者指指出哪一一个目标标值可以以增加，，哪一个个目标值值应减少少。分析析者根据据决策者者的意图图，增添添新的约约束，求求得新的的试验解解，进入入下一步步迭代。。直到求求出使决决策者满满意的优优惠解。。逐步法(StepMethod)是1971年年由Benayoun等人提提出的求求解线性性多目标标优化问问题的一一种交互互式方法法，此方方法本质质是在某某种范数数下求距距理想点点最近的的点。第五节多多目目标优化化的第三三类方法法对于线性性多目标标优化问问题定义逐步法的的计算步步骤（1）建建立支付付表f1f2…fm1

2

m

……（2）求求第k次迭代点点（3）与与决策者者对话将目标函函数值提提供给决决策者，，若决策策者对所所有目标标值皆满满意，则则获得优优惠解，，停止计计算；若若决策者者对所有有目标值值皆不满满意，则则计算失失败，停停止计算算；若决决策者对对部分目目标值满满意，对对部分目目标值不不满意，，则继续续计算。。在满意的的目标中中选一个个目标fj*，并给出出一个可可以牺牲牲的量fj*，意思是是愿意让让目标fj*增大fj*，以换取取其它不满满意目标标值的减减小。并并进行如如下计算算：2.代替替价值交交换法代替价值值交换法法(SurrogateWorthTrade-offMethod)是1971年年由Haimes等人人提出的的求解非非线性多多目标优优化问题题的一种种交互式式方法。。其－约束问题题为对于多目目标优化化问题－约束问题题的K－－T条件件可以证明明，约束束目标函函数对应应的Lagrange乘子即约束目目标函数数对应的的Lagrange乘乘子wj是目标fk对目标fj的交换率率。分析者与与决策者者的交互互分析者求求得一个个非劣解解（即－约束问题题的最优优解）X(k