多目标优化方法讲义.ppt

《多目标优化方法讲义.ppt》由会员分享，可在线阅读，更多相关《多目标优化方法讲义.ppt（64页珍藏版）》请在金锄头文库上搜索。

1、第二部分 多目标优化方法 Multi-Objective Optimization,第一节 概述,第三节 多目标优化的第一类方法,第二节 多目标优化设计理论,第四节 多目标优化的第二类方法,第五节 多目标优化的第三类方法,国际上通常认为多目标最优化问题最早是在1886年由法国经济学家Pareto从政治经济学的角度提出的。多目标规划的真正发达时期，并正式作为一个数学分支进行系统的研究，是上世纪七十年代以后的事。,现在，对多目标规划方面的研究集中在以下几个方面: 一、关于解的概念及其性质的研究， 二、关于多目标规划的解法研究， 三、对偶问题的研究， 四、不可微多目标规划的研究， 五、多目标规划的应

2、用研究。,到现在为止，多目标优化不仅在理论上取得许多重要成果，而且在应用上其范围也越来越广泛，多目标决策作为一个工具在解决工程技术、经济、管理、军事和系统工程等众多方面的问题也越来越显示出它强大的生命力。,第一节 概述,1. 多目标优化设计示例,示例1：某工厂生产两种产品A和B,每件产品A需制造工时和装配工时分别为1时和1.25时，每件产品B需制造工时和装配工时分别为1时和0.75时，每月制造车间和装配车间能够提供的最多工时为200时，另外，每月市场对产品A需求量很大，而对产品B的最大需求量为150件，产品A和产品B的售价分别为4元和5元，问如何安排每月的生产，最大限度的满足市场需求，并产值最

3、大？,示例2. 用直径为1(单位长)的圆木制成截面为矩形的梁,为使重量最轻,而强度最大,问截面的高与宽应取何尺寸? 解: 设矩形截面的高与宽分别 为和 , 这时梁的面积为 ,它决定重量,而梁的强度取决于截面形 。,因此,容易列出 梁的数学模型:,示例3 物资调运问题: 某种物资寸放三个仓库 里,存放量分别为 (单位:t);现要将这些物资运往四个销售点 。其需要量分别为 且 ，已知 到 的距离和单位运价分别为 (km)和 (元),现要决定如何调运多少,才能使总的吨,公里数和总运费都尽量少?,解: 设变量 表示由 运往 的货物数,于是总吨公里数为 ,总运费为 ,问题优化设计模型为,示例4：如图所示

4、，设计一苦空心阶梯悬臂梁，根据结构要求，已确定梁的总长为1000mm，第一段外径为80mm，第二段外经为100mm，梁的端部受有集中力F12000N，梁的内径不得小于40mm，梁的许用弯曲应力为180MPa，确定梁的内径和各段长度，使梁的体积和静挠度最小。,多目标优化设计模型,多目标最优化问题的一般形式为: S.t. 或者记作:min D=,其中: =( ),2. 多目标优化设计模型,注意，这里以及之后的所有讲述同时适合于线性和非线性的多目标优化,多目标优化设计几何描述,在单目标优化问题中，任何两个解都可以比较出其优劣，这是因为单目标优化问题是完全有序的；而在多目标优化设计中，任何两个解不一定

5、都可以比较出其优劣，这是因为多目标优化问题是半有序的。,3. 多目标优化问题解的特点,第一类：转化法。这类多目标最优化方法的基本思想是将多目标问题转化为一个或一系列的单目标优化问题，通过求解一个或一系列单目标优化问题来完成多目标优化问题的求解。,4. 多目标优化方法分类,第二类：非劣解集法。这类多目标最优化方法的基本思想是求得多目标问题的非劣解集，然后在非劣解集中进行协调和选择，确定出优惠解。,第三类：交互协调法。这类多目标最优化方法的基本思想是通过在分析者与抉择者间的不断交互，逐渐搞清抉择者的选择意图，获得多目标问题的优惠解。,第二节 多目标优化设计理论,1. 多目标优化设计模型,简记为,V

6、OP,多目标优化问题(Multi-Objective Optimization Problem)又称为向量优化问题(Vector Optimization Problem) 。,2. 决策空间与目标空间,以设计变量为坐标的实空间Rn称为决策空间。,以目标函数为坐标的实空间Rm称为目标空间。,决策空间可行域：,目标空间可行域,示例1,示例2,决策空间可行域,目标空间可行域,3. 解的定义,（1） 理想解(ideal solution),在目标空间内，以单目标最小值为分量而形成的点，称为多目标问题的理想解。,在多目标优化问题中，由于各个目标间往往是矛盾的，所以一般不存在使各目标皆达到各自最优值的理

7、想解。,（2） 非劣解（Noninferior Solution）或 Pareto 解,对于可行点XPD，若不存在另一个可行点XD，使,成立，则称Xp为多目标问题的非劣解。,向量不等式的含义为,7.1 模型举例,例7.1. 用直径为1(单位长)的圆木制成截面为矩形的梁,为使重量最轻,而强度最大,问截面的高与宽应取何尺寸? 解: 设矩形截面的高与宽分别 为和 , 这时梁的面积为 ,它决定重量,而梁的重量取决于截面矩形 。,因此,容易列出 梁的数学模型:,例7.2 物资调运问题: 某种物资寸放三个仓库 里,存放量分别为 (单位:t);现要将这些物资运往四个销售点 .其需要量分别为 且 ，已知 到

8、的距离和单位运价分别为 (km)和 (元),现要决定如何调运多少,才能使总的吨,公里数和总运费都尽量少?,解: 设变量 表示由 运往 的货物数,于是总吨公里数为 ,总运费为 ,问题优化为求解,由于求最大都可以转化为求最小,所以多目标最优化问题的一般形式为: S.t. 或者记作:min D=,其中: =( ),当P=1时,(VP)就是非线性规划, 称为单目标规划。 对于单目标问题Min , 总可比较 与 的大小. 对于多目标规划(VP),对于 ， 与 都 是P 维向量,如何比较两个向量的大小?,可以看到：,多目标优化的非劣解集 Noninferior solution for the model

9、,例如：A,B点属于非劣解，因为,不满足定义条件,（3） 满意解（最佳协调解或优惠解）,效用函数值的大小反映决策者对多目标值的喜爱程度，一般来说，决策者希望效用函数的值越大越好。,效用函数：,决策者对多目标函数优化解进行评价的函数，记为,使效用函数取最大值的非劣解称为最佳协调解。,对于效用函数未知的情况，无法直接求得最佳协调解。我们把多目标优化过程满意结束的解称为优惠解。,4 多目标优化问题的KT条件,对于多目标优化问题,VOP,7.4 求解多目标规划的评价函数法,尽管多目标优化问题有各种意义下的最优解.但在应用中,需要的还是有效解和弱有效解.本节介绍求有效解和弱有效解最基本的方法-评价函数法

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

11、 ,总有 ,则称 为 的严格单增函数. 2 若 时,总有 ,则称 为 的单增函数.,定理1 . 设：: ,又设 ，是问题min 的极小点,那么: 若 为Z的严格单增函数,则 是min 有效解. 若 为Z的单增函数,则 是min 的弱有效解.,重要定理,几种常用的构造评价函数的方法 一. 理想点法: 在(VP)中,先求解P个单目标问题 j=1，2，p xD 设其最优值为 ,我们称 为值域中的一个理想点 。,因为一般很难达到它,这样,就期望在某种等量下,寻求距最近的f作为近似值,一种最直接的想法是构造评价函数 = （7.2）,然后极小化即求解： 并将它的最优解 作为(VP)在这种意义下的 “最优解

12、”,由于 ,因此由7.2构造的 是严格单增的,从而 是(VP)的有效解.,二. 线性加权和法. 在具有多个指标的问题中,人们总希望对那 些相对重要的指标给予较大的权系数,基于这种 现实,自然如下的构造评价函数,令,称之为权向量集,令 再求解 而将它的最优解, 作为(VP)在该意义下的最优解.,三. 极大极小法 在决策时，采取保守策略是稳妥的。即在最坏的情况下，寻求最好的结果。按照这种想法，可以构造如下评价函数 然后求解 并将它的最优解 作为（VP）在这种意义下的最优解。,1. 主目标法,转化为,第三节 多目标优化的第一类方法,主目标法就是从多目标中依据重要程度选择一个目标作为主目标，而将其它目

13、标转化为约束，即将多目标优化问题,主目标法中约束目标的约束值选取,2. 线性加权法,转化为,线性加权法就是将多目标的加权和作为单目标，即将多目标优化问题,(2）对权系数的要求,(3) 权系数的确定,老手法,线性加权法的有关说明：,（1) 线性加权之前，各目标应进行无量纲化处理。,3. 极小极大法,转化为,极小极大法就是求取多目标函数中的最大值，然后使最大值函数在可行域内极小化，即将多目标优化问题,(2)极小极大法也可以引入一个变量和m个约束，即,极小极大法的有关说明：,（1) 考虑到各目标的重要程度差别，可以对各目标乘以权系数，然后再求最大值函数，即,4. 理想点法,转化为,理想点法就是将距理

14、想点最近的点作为多目标问题的优惠解，即将多目标优化问题,理想点法的有关说明：,考虑到各目标的重要程度差别，可以对各目标乘以权系数，即,权系数的选取可以参阅线性加权法。,5. 功效系数法,在多目标优化问题，各目标的要求不全相同，有的要求极小化，有的要求极大化，有的要求有一个合适的数值。为了反映这些不同的要求，故引入如下的功效函数：,功效系数的确定：,1.直线法,2.折线法,3.指数法,6. 分层序列法,将多目标优化问题的各目标分清主次，按其重要程度逐一排序，然后依次对各目标函数求最优解，但应注意后一目标应在前一目标的最优解域内进行寻优。,照此继续下去，最后求得第m个目标函数得最优解，真个解即为多

15、目标优化问题的最终解。,在分层序列法中，当前面有某个目标函数的最优解唯一时，该方法就发生中断现象，因此需要引入目标容差。,7. 协调曲线法,协调曲线法主要用于求解两个目标函数的多目标优化设计问题。,目标规划法 Goal Attainment Method,引入目标概念：F*，令非劣解集到目标的距离（或称范数）最小，选出一个非劣解。 Wi引入了一个松弛度的概念，松弛度最小的一个非劣解就是对于目标F*的最可行解。 优点：不漏解，目标明确，计算量小。 缺点：对于非线性规划设计：运用连续二次形规划(SQP - sequential quadratic programming)，线性的权值松弛在局部搜索范围内，会导致拒绝可大幅改进总体目标的小步搜索。只针对连续问题，可能只能给出局部最优解。 改进：阅读Matla