《多目标及离散变量优化方法精选PPT.ppt》由会员分享，可在线阅读，更多相关《多目标及离散变量优化方法精选PPT.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、多目标及离散变量优化方法第1页，此课件共45页哦第六章多目标优化方法和离散变量优化多目标优化方法和离散变量优化方法简介方法简介第一节第一节 多目标优化问题多目标优化问题第二节第二节 多目标优化方法多目标优化方法第三节第三节 离散变量优化问题离散变量优化问题 与离散变量优化方法与离散变量优化方法第2页，此课件共45页哦第六章 重点内容1.什么是非劣解？什么是非劣解？2.多目标优化方法主要有哪四种方法？多目标优化方法主要有哪四种方法？3.统统一一目目标标法法中中的的线线性性加加权权法法，如如何何将将各各目目标标函函数数值值的的变变化化范范围均统一为从围均统一为从0到到1的变化范围？的变化范围？4.
2、统一目标法中的线性加权法，确定加权因子的方法有哪几种？统一目标法中的线性加权法，确定加权因子的方法有哪几种？5.统一目标法中的理想点法是如何构造统一的目标函数的？统一目标法中的理想点法是如何构造统一的目标函数的？6.统一目标法中的功效系数法可以怎样确定功效系数？统一目标法中的功效系数法可以怎样确定功效系数？7.用宽容分层序列法求解的思路用宽容分层序列法求解的思路8.构造离散惩罚函数构造离散惩罚函数 9.离散变量组合型法中如何产生初始复合形的顶点？离散变量组合型法中如何产生初始复合形的顶点？约束条件和迭代终止是如何处理的约束条件和迭代终止是如何处理的?第3页，此课件共45页哦第六章结束第4页，此
3、课件共45页哦机械设计中，同时要求几项设计指标达到最优的问题机械设计中，同时要求几项设计指标达到最优的问题 多目标优化设计问题多目标优化设计问题多目标优化问题的类型：多目标优化问题的类型：(1)(1)整体多目标优化整体多目标优化 (2)(2)分层分层(步步)多目标优化多目标优化多目标优化问题与单目标优化问题有根本性区别多目标优化问题与单目标优化问题有根本性区别:单目标问题可以得到最优解，而多目标问题往往得单目标问题可以得到最优解，而多目标问题往往得不到最优解，而只能得到非劣解（有效解）不到最优解，而只能得到非劣解（有效解）多目标优化问题的任意两个设计方案，往往不易多目标优化问题的任意两个设计方
4、案，往往不易于比较其优劣。于比较其优劣。第一节第一节 多目标优化问题多目标优化问题TlRxRxxfxfxfxFnn)()(),()(21minmin.=第六章第六章 第一节第一节 多目标优化问题多目标优化问题第5页，此课件共45页哦判别方案的优劣：判别方案的优劣：单目标：只要用单目标：只要用f(x)去比较即可去比较即可 绝对最优解：绝对最优解：多目标优化设计时，几个分目标同时达到多目标优化设计时，几个分目标同时达到 最优的解最优的解。绝对最优解几乎不可能找到，。绝对最优解几乎不可能找到，因为各分目标函数有时会相互矛盾。因为各分目标函数有时会相互矛盾。非劣解非劣解(有效解有效解)：指有指有m个目
5、标函数，找不到一个个目标函数，找不到一个x，使得其中一个目标函数，使得其中一个目标函数值值fi(x)比比fi(x*)更好，而其余更好，而其余(m-1)个目标函数值不变坏，则称个目标函数值不变坏，则称x*为非劣解（有效解）为非劣解（有效解）;多目标优化设计时，各分目标往往互相矛盾，甚至对立，这多目标优化设计时，各分目标往往互相矛盾，甚至对立，这就需在各分目标函数之间协调，互相作些让步，以便取得较好的就需在各分目标函数之间协调，互相作些让步，以便取得较好的方案。方案。多目标：多目标：（j=1,2,l）第六章第六章 第一节第一节 多目标优化问题多目标优化问题第6页，此课件共45页哦例例1 在在最优解
6、为：最优解为：但两者无共同的最优解但两者无共同的最优解 内两单目标函数内两单目标函数2,0 x第六章第六章 第一节第一节 多目标优化问题多目标优化问题第7页，此课件共45页哦 内，内，(若若，对任意，对任意都有都有，则，则x*是多目标优化的绝对最优解是多目标优化的绝对最优解)若若，且不存在，且不存在使使，则，则x*为非劣解。为非劣解。的所有点均为非劣解。的所有点均为非劣解。是绝对最优解。是绝对最优解。内，内，a，a点都是劣解（若点都是劣解（若，存在，存在，有，有则则x*成为劣解。）成为劣解。）Dxx*第六章第六章 第一节第一节 多目标优化问题多目标优化问题例如例如b点。点。第8页，此课件共45
7、页哦一、主要目标法一、主要目标法 基本思想：多个目标中选择一个目标作为主要目标，而其基本思想：多个目标中选择一个目标作为主要目标，而其它目标则只需满足一定的要求即可，即将目标它目标则只需满足一定的要求即可，即将目标转化为约束条件转化为约束条件 目标函数转化为：目标函数转化为：二、统一目标法二、统一目标法 基本思想：将多目标优化问题，通过一定方法转化为统一基本思想：将多目标优化问题，通过一定方法转化为统一目标函数或综合目标函数作为多目标优化问题的目标函数或综合目标函数作为多目标优化问题的评价函数。评价函数。第二节第二节 多目标优化方法多目标优化方法式中，式中，f imin和和f imax为第为第
8、i个目标函数的上、下限。个目标函数的上、下限。一般一般 只有单边限制只有单边限制第六章第六章 第二节第二节 多目标优化方法多目标优化方法第9页，此课件共45页哦1线性加权法线性加权法 基本思想：将各个分目标函数基本思想：将各个分目标函数依其数量级和在整体设计中的重要程度相应地给出一组依其数量级和在整体设计中的重要程度相应地给出一组构成一新的统一的目标函数构成一新的统一的目标函数F(x)wi加权因子加权因子 (wi0，i=1,2,，l)加权因子取值对计算结果的正确性影响较大。加权因子取值对计算结果的正确性影响较大。常用的方法有：线性加权法、理想点法（目标规划法）常用的方法有：线性加权法、理想点法
9、（目标规划法）、功、功效系数法和极大极小法等。效系数法和极大极小法等。加权因子，加权因子，,取取fi(x)和和wi(i=1,2,，l)的线性组合，的线性组合，第六章第六章 第二节第二节 多目标优化方法多目标优化方法第10页，此课件共45页哦为消除各分目标在量级上的差别，先将分目标函数为消除各分目标在量级上的差别，先将分目标函数fi(x)转化转化为无量纲等量级目标函数为无量纲等量级目标函数再组成统一目标函数。再组成统一目标函数。wi按各分目标的重要程度来决定按各分目标的重要程度来决定如各分目标有相同的重要性，则取如各分目标有相同的重要性，则取wi=1(i=1,2,l)称为称为均匀计权均匀计权，否
10、则取各分目标不同的加权因子，否则取各分目标不同的加权因子，取取将将fi(x)转换为无量纲的等量级目标函数转换为无量纲的等量级目标函数的方法的方法 第六章第六章 第二节第二节 多目标优化方法多目标优化方法将各分目标转化后加权将各分目标转化后加权 加权因子加权因子w wi i确定的方法确定的方法:第11页，此课件共45页哦设各分目标函数值的变动范围为：设各分目标函数值的变动范围为：即将各单目标函数的最优值的倒数作为权系数，即将各单目标函数的最优值的倒数作为权系数，它反映了各单目标函数离开各自最优值的程度。另外它反映了各单目标函数离开各自最优值的程度。另外相当于各分目标函数进行了无量纲的处理，而消除
11、了相当于各分目标函数进行了无量纲的处理，而消除了各分目标在数量级上的差别。各分目标在数量级上的差别。第六章第六章 第二节第二节 多目标优化方法多目标优化方法第12页，此课件共45页哦其中，其中，w1i本征权因子，反映各分目标的重要程度本征权因子，反映各分目标的重要程度w2i校正权因子，调整各分目标间量级差别的影响校正权因子，调整各分目标间量级差别的影响加权因子加权因子w2i愈小，反之，亦然。这样可调整不同的目标函愈小，反之，亦然。这样可调整不同的目标函数值同步下降。数值同步下降。直接加权法直接加权法一个分目标函数一个分目标函数fi(x)变化越快，变化越快，的值越大，的值越大，将加权因子分成两部
12、分将加权因子分成两部分一般取：一般取：wi=w1iw2i (i=1,2,l)第六章第六章 第二节第二节 多目标优化方法多目标优化方法第13页，此课件共45页哦基本思想：先定出各分目标函数的最优值，根据多基本思想：先定出各分目标函数的最优值，根据多目标优化设计的总体要求对这些最优值进行调目标优化设计的总体要求对这些最优值进行调整，定出各分目标的最合理值整，定出各分目标的最合理值（也可以是最优值（也可以是最优值），再构造新的统一的），再构造新的统一的式中，除式中，除如引入加权系数如引入加权系数wi，则目标函数为：，则目标函数为：2 2理想点法（目标规化法）理想点法（目标规化法）是为使目标函数无量纲
13、化。是为使目标函数无量纲化。目标函数：目标函数：第六章第六章 第二节第二节 多目标优化方法多目标优化方法第14页，此课件共45页哦V其中，其中，则统一目标函数为则统一目标函数为即要求位于分子的各分目标函数应尽量小，而位于分母的即要求位于分子的各分目标函数应尽量小，而位于分母的各分目标函数应尽量大。各分目标函数应尽量大。一般要求各分目标函数一般要求各分目标函数fi(x)在在D上均取正值。上均取正值。3分目标乘除法分目标乘除法多目标混合优化问题：多目标混合优化问题：第六章第六章 第二节第二节 多目标优化方法多目标优化方法第15页，此课件共45页哦基本思想基本思想：对应每一目标函数都用功效系数对应每
14、一目标函数都用功效系数来表示该项指标的好坏来表示该项指标的好坏总功效系数（评价函数）总功效系数（评价函数）C值越大越好，值越大越好，C=1-方案最满意方案最满意C=0-表示此方案不能被接受。表示此方案不能被接受。只要有一个方案，只要有一个方案，Ci=0，此方案都不能被接受，此方案都不能被接受功效系数类型：功效系数类型：1）Ci与与fi成正比，即要求目标函数越大越好成正比，即要求目标函数越大越好2）Ci与与fi成反比，即要求目标函数越小越好成反比，即要求目标函数越小越好3）fi取某适当值时，取某适当值时，Ci就越大；就越大；否则否则Ci就越小。就越小。4功效系数法功效系数法第六章第六章 第二节第
15、二节 多目标优化方法多目标优化方法第16页，此课件共45页哦功效系数的确定方法：功效系数的确定方法：直线法直线法折线法折线法第六章第六章 第二节第二节 多目标优化方法多目标优化方法第17页，此课件共45页哦指数法指数法功效系数法的优点：功效系数法的优点：1、各分目标函数的值数量级大小对优化无影响、各分目标函数的值数量级大小对优化无影响 2、评价函数比较直观、易于调整、评价函数比较直观、易于调整 3、适于要求目标函数取值适中的情况、适于要求目标函数取值适中的情况第六章第六章 第二节第二节 多目标优化方法多目标优化方法第18页，此课件共45页哦基本思想：多目标优化问题中，存在目标函数间相互矛盾的基
16、本思想：多目标优化问题中，存在目标函数间相互矛盾的情况，一个（些）目标函数值的减小，将导致另一个情况，一个（些）目标函数值的减小，将导致另一个（些）目标函数值的增大。因此，各分目标函数值之间（些）目标函数值的增大。因此，各分目标函数值之间需要进行协调，以便取得合理的方案。需要进行协调，以便取得合理的方案。如图所示，两维双目标函数如图所示，两维双目标函数f1(x)、f2(x)的等值线和两个不等式的等值线和两个不等式约束曲面约束曲面.三、协调曲线法三、协调曲线法第六章第六章 第二节第二节 多目标优化方法多目标优化方法第19页，此课件共45页哦 f1(x)最优点最优点T点，点，f2(x)最优点最优点
17、P点点 可行域中任意一点可行域中任意一点R.从从R点起沿点起沿f1(x)=5等值线，向约束面移动等值线，向约束面移动f2(x)不断改善，不断改善，直至边界上直至边界上S点。点。从从R点起沿点起沿f2(x)=8等值线，向约束面等值线，向约束面f1(x)移动不断改善，移动不断改善，直至边界上直至边界上Q点。点。f1(x)=5时，对应时，对应f2(x)的最佳点为的最佳点为S点点由此可得由此可得f1(x)（或（或f2(x)）为定值时对）为定值时对应的最佳应的最佳f2(x)（或（或f1(x)）的点关系曲）的点关系曲线线T-Q-S-P协调曲线。协调曲线。f2(x)=8时，对应时，对应f1(x)的最佳点为的
18、最佳点为Q点。点。均为约束边界点均为约束边界点第六章第六章 第二节第二节 多目标优化方法多目标优化方法S、Q点都比点都比R点优点优第20页，此课件共45页哦 该该曲曲线线反反映映了了两两个个设设计计目目标标全全部部最最佳佳方方案案的的调调整整范范围围,再再建建立立一一个个衡衡量量设设计计方方案案满满意意程程度度的的准准则则，建建立立一一组组反反映映不不同同满满意意程程度度的的曲曲线线u(f1,f2)，使使随随着着满满意意度度增增加加，同同时时使使目目标标函函数数f1(x)和和f2(x)都有所下降。都有所下降。满满意意度度曲曲线线与与协协调调曲曲线线的的切切点点，即即为为最最优优设设计计方方案案
19、。如如图图所示所示O O点点 满意度曲线不同，则最优设计方案也不同。满意度曲线不同，则最优设计方案也不同。第六章第六章 第二节第二节 多目标优化方法多目标优化方法第21页，此课件共45页哦基本思想：将多目标优化问题的各目标函数按重要程度排基本思想：将多目标优化问题的各目标函数按重要程度排列，然后，依次对各个目标函数求最优解，而后一目标函数列，然后，依次对各个目标函数求最优解，而后一目标函数应在其前面目标函数最优解的集合域内寻优。应在其前面目标函数最优解的集合域内寻优。1、分层序列法、分层序列法设分目标函数重要程度次序为：设分目标函数重要程度次序为：f1(x)、f2(x)，则首先对则首先对f1(
20、x)寻优：寻优：在在的集合内对的集合内对f2(x)寻优：寻优：四、分层序列法和宽容分层序列法四、分层序列法和宽容分层序列法第六章第六章 第二节第二节 多目标优化方法多目标优化方法问题：如其中第问题：如其中第k k个目个目标函数的最优解为唯一标函数的最优解为唯一时，再往下求解就失去时，再往下求解就失去意义，而后面意义，而后面l l-k k个目个目标函数也没法得到最优标函数也没法得到最优化解。化解。以下类推。以下类推。第22页，此课件共45页哦2、宽容分层序列法、宽容分层序列法 基本思想：即先对各目标函数的最优值取一定的宽容量基本思想：即先对各目标函数的最优值取一定的宽容量1，2，l(0)，使求后
21、一个目标函数最优值时，对前一些目标，使求后一个目标函数最优值时，对前一些目标函数的约束扩大为在其最优值附近的某一范围内。函数的约束扩大为在其最优值附近的某一范围内。第六章第六章 第二节第二节 多目标优化方法多目标优化方法第23页，此课件共45页哦如图，两目标优化问题，不作宽容时，如图，两目标优化问题，不作宽容时，为最优解，即为最优解，即f1(x)的严格最优解，给定宽容值的严格最优解，给定宽容值1，则最，则最优解为优解为x(1)第六章第六章 第二节第二节 多目标优化方法多目标优化方法第24页，此课件共45页哦例例1 用宽容分层序列法求解用宽容分层序列法求解式中，式中，解：如图所示，由解：如图所示
22、，由给定给定1=0.052，解解V第六章第六章 第二节第二节 多目标优化方法多目标优化方法第25页，此课件共45页哦 等间隔的离散变量等间隔的离散变量 非均匀间隔离散变量非均匀间隔离散变量 特例：整数变量特例：整数变量整数规划问题整数规划问题最简单处理办法：按连续变量处理，得最优解后，最简单处理办法：按连续变量处理，得最优解后，再再圆整为最近的离散值圆整为最近的离散值问题：问题：圆整后的点在非可行域圆整后的点在非可行域;圆整为哪一个附近的离散值难于确定圆整为哪一个附近的离散值难于确定;有些情况下设计变量不允许最后取整。有些情况下设计变量不允许最后取整。第三节第三节 离散变量优化问题与离散变量优
23、化方法离散变量优化问题与离散变量优化方法一、概述一、概述离散离散变量变量 第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第26页，此课件共45页哦式中式中 离散变量子集合离散变量子集合xD为空集时，为连续变量型问题为空集时，为连续变量型问题xC为空集时，为全离散变量型问题为空集时，为全离散变量型问题连续变量子集合连续变量子集合约束非线性混合离散约束非线性混合离散变量优化问题的数学模型：变量优化问题的数学模型：第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第27页，此课件共45页哦二、约束非线性离
24、散变量的优化方法二、约束非线性离散变量的优化方法 常用方法：常用方法：1)以连续变量优化为基础的方法：以连续变量优化为基础的方法：圆整法、拟离散法、离散型罚函数法圆整法、拟离散法、离散型罚函数法 2)离散变量随机优化方法：离散变量随机优化方法：随机试验法，随机离散搜索法随机试验法，随机离散搜索法 3)离散变量搜索优化方法：离散变量搜索优化方法：组合优化法，整数梯度法组合优化法，整数梯度法 4)其它离散变量优化方法：其它离散变量优化方法：非线性隐枚举法，分支定界法非线性隐枚举法，分支定界法(一一)以连续变量优化为基础的方法以连续变量优化为基础的方法1、整型化、离散化法、整型化、离散化法 基本思想
25、：先按连续变量方法求得最优解基本思想：先按连续变量方法求得最优解x*，再进一，再进一 步寻找整型量或离散量优化解。步寻找整型量或离散量优化解。第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第28页，此课件共45页哦设最优点设最优点的的n个实型分量为个实型分量为，则最靠近，则最靠近的两个离散量（或整型量）的两个离散量（或整型量）由这些离散（整型）分量的不同组合，便构成了最邻近于由这些离散（整型）分量的不同组合，便构成了最邻近于实型最优点实型最优点x*的两个整型（离散）分量及其相应一组离散的两个整型（离散）分量及其相应一组离散（整型）点群共（整型）
26、点群共2n个设计点。去除不在可行域内点，其余个设计点。去除不在可行域内点，其余在可行域内的若干点中，选取一个目标函数值最小的点在可行域内的若干点中，选取一个目标函数值最小的点作为最优解输出。作为最优解输出。第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第29页，此课件共45页哦问题：问题：如如中中图图:x*点点（通通常常在在约约束束边边界界上上）附附近近的的离离散散点点（整整型型点点）均不在可行域内的情况均不在可行域内的情况 如右图如右图:离离x*较远的点较远的点P为离散最优点的情况。为离散最优点的情况。如左图，如左图，x x*点附近整型（离散
27、）点群为点附近整型（离散）点群为ABCDABCD。B B点在可行域点在可行域外，外，C C点为最优点。点为最优点。第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第30页，此课件共45页哦2拟离散法拟离散法 基基本本思思想想：在在求求得得连连续续变变量量最最优优解解x*后后，在在x*点点附附近近按按一一定定方法进行搜索来求得优化离散解。方法进行搜索来求得优化离散解。(1)交替查找法：适于全整数变量优化问题（略）交替查找法：适于全整数变量优化问题（略）(2)离散分量取整，连续分量优化法：离散分量取整，连续分量优化法：适用于混合离散变量优化问题（略）
28、适用于混合离散变量优化问题（略）第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法基本思想：将设计变量的基本思想：将设计变量的离散性视为离散性视为对该变量的一种对该变量的一种约束条件约束条件，再用连续变量的优化方法来计算离散变量问题的优化再用连续变量的优化方法来计算离散变量问题的优化解。解。1）构造一个具有下列性质的离散惩罚函数项）构造一个具有下列性质的离散惩罚函数项Qk(xD)3、离散惩罚函数法、离散惩罚函数法RD设计空间离散点的集合设计空间离散点的集合 其意义为：当离散变量趋于离其意义为：当离散变量趋于离散值时，惩罚函数值为零散值时，惩罚函数值
29、为零 第31页，此课件共45页哦离散惩罚函数定义方法离散惩罚函数定义方法:其中，其中，xi为相邻两离散点为相邻两离散点xij和和xij+1间任一点坐标。间任一点坐标。Qk(xD)为为规规范范化化的的对对称称函函数数，其其最最大大值值为为1，xi取取xij或或xij+1时时为为0。如图如图,对对k1情形，情形，在离散值之间范围内，在离散值之间范围内，函数的一阶导数是连函数的一阶导数是连续的。续的。第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法(1)第32页，此课件共45页哦2）将离散惩罚函数项）将离散惩罚函数项Qk(xD)加到内点法加到内点法SU
30、MT的惩罚项中，的惩罚项中，得离散惩罚函数为：得离散惩罚函数为：其中，其中，s(k)为离散惩罚因子，为离散惩罚因子，时第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第33页，此课件共45页哦例例1 求求f(x)=x/2的最小整数优化解，约束函数的最小整数优化解，约束函数 g1(x)=1.3-x0如图所示，分别表示如图所示，分别表示k不同时，不同时，离散优化点离散优化点 最终离散最优解为最终离散最优解为x2 变化情况变化情况随着随着k不断变化，不断变化，r减小，减小，s增加增加第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量
31、优化问题与离散变量优化方法第34页，此课件共45页哦 方法缺点：离散惩罚函数易出现病态，使优化搜索带方法缺点：离散惩罚函数易出现病态，使优化搜索带 来困难。来困难。(二二)离散变量搜索型方法离散变量搜索型方法离散复合形法离散复合形法特特点点：在在离离散散空空间间直直接接搜搜索索，每每次次得得到到的的复复合合形形顶顶点点都都是是离离散散点点，通通过过不不同同的的搜搜索索方方法法来来改改变变其其形形状状，使使复复合合形形逐逐步步向离散最优点趋近。向离散最优点趋近。算法步骤：算法步骤：1)在在n维维空空间间产产生生由由2n+1个个顶顶点点构构成成的的初初始始复复合合形形，并并将将各各顶点移到各自附近
32、的离散点上。顶点移到各自附近的离散点上。2)将各项点按目标函数值由大到小排列，找出最坏点将各项点按目标函数值由大到小排列，找出最坏点AH3)找找出出除除最最坏坏点点外外复复合合形形的的几几何何中中心心，并并求求出出最最坏坏点点AH相相对于中心点的反射点对于中心点的反射点Ap并移到附近离散点上。并移到附近离散点上。4)如如Ap点点可可行行，且且目目标标函函数数值值比比AH点点好好，则则用用Ap替替代代AH点点，组成新复合形组成新复合形转步骤转步骤2第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第35页，此课件共45页哦 否则，沿反射的反方向搜索定
33、新点。否则，沿反射的反方向搜索定新点。5)如用上述方法失败，则依次用次坏点如用上述方法失败，则依次用次坏点代替最坏点代替最坏点 作为映射点，转步骤作为映射点，转步骤3）6)如用最好点代替如用最好点代替AH作为映射点，仍找不到好点，或作为映射点，仍找不到好点，或 复合形退化到复合形退化到n-1维空间时，表示算法收敛。此时，维空间时，表示算法收敛。此时，取复合形顶点中最好的点作为离散优化解。取复合形顶点中最好的点作为离散优化解。(三三)离散变量型网格法离散变量型网格法 1.离散变量型普通网格法离散变量型普通网格法 基基本本思思想想：以以一一定定的的变变量量增增量量为为间间隔隔，把把设设计计空空间间
34、划划分分为为若若干干个个网网格格，计计算算在在可可行行域域内内每每个个网网格格节节点点上上的的目目标标函函数数值值，比比较较其其大大小小，再再以以目目标标函函数数值值最最小小的的节节点点为为中中心心，在在其其附附近近空空间间划划分分更更小小的的网网格格，并并计计算算各各节节点点上上的的目目标标函函数数值值，直直至至网网格格小小到到满满足足精精度度网网格格节节点点密密度度与与离离散散点点密度相等。密度相等。第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第36页，此课件共45页哦开开始始时时网网格格比比较较稀稀疏疏网网格格节节点点密密度度逐逐渐渐增
35、增加加直直至按一个离散增量划分网格节点为止。至按一个离散增量划分网格节点为止。2离散变量型正交网格法离散变量型正交网格法 普通网格法的缺点：普通网格法的缺点：变量维数增加时，计算工作量大大增加变量维数增加时，计算工作量大大增加正交网格法基本思想：正交网格法基本思想：根根据据正正交交试试验验法法的的原原理理，利利用用正正交交表表均均匀匀地地选选取取网网格格法法中中一一部部分分有有代代表表性性的的网网格格点点作作为为计计算算点点，又又称随机正交网格法。称随机正交网格法。正正交交网网格格法法的的特特点点：只只计计算算部部分分网网格格点点的的目目标标函函数数值值，计算工作量少。计算工作量少。第六章第六
36、章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第37页，此课件共45页哦(四四)离散变量的组合型法（离散变量的组合型法（MDCP法）法）工程离散优化通用方法工程离散优化通用方法 基本思想：以离散基本思想：以离散复合形法复合形法为基础，采用多种离散搜索策略，为基础，采用多种离散搜索策略，形成的具有多种功能的组合型算法。形成的具有多种功能的组合型算法。适于求解非线性混合离散变量优化问题适于求解非线性混合离散变量优化问题1初始离散复合形顶点的形成初始离散复合形顶点的形成复合形顶点数复合形顶点数k=2n+1给定初始离散点给定初始离散点x(0)，x(0)须满足变量
37、值的边界条件，但不必满足须满足变量值的边界条件，但不必满足约束条件，即约束条件，即式中，式中，ximin，ximax分别为第分别为第i个变量的下、上限个变量的下、上限 第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第38页，此课件共45页哦点号数点号数分量号数分量号数复合形的复合形的2n+1个顶点按下面方法产生个顶点按下面方法产生第第1个顶点：个顶点：第第2至至n+1个顶点：个顶点：第第n+2至至2n+1个顶点：个顶点：如此产生的复合形顶点，不要求全是可行点，如图，如此产生的复合形顶点，不要求全是可行点，如图，5个初始个初始复合形顶点中，复合形
38、顶点中，C、D两点为不可行点。两点为不可行点。例如二维：例如二维：第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第39页，此课件共45页哦2、离散一维搜索产生新点、离散一维搜索产生新点 将复合形顶点目标函数值排队，找出目标函数值最大的点将复合形顶点目标函数值排队，找出目标函数值最大的点为最坏点，为最坏点，x(b)以以x(b)为基点，向其余各顶点的几何中心为基点，向其余各顶点的几何中心x(e)方向作一维搜索，方向作一维搜索，采用采用映射、延伸映射、延伸或或收缩收缩等步骤搜索等步骤搜索搜索方向搜索方向S的各分量的各分量Si计算式为：计算式为：离散一
39、维搜索得到的新点为离散一维搜索得到的新点为x(t)其各分量为：其各分量为：取取 第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第40页，此课件共45页哦离散一维搜索得到的新点为离散一维搜索得到的新点为x(t)其各分量为：其各分量为：取取 其中其中 表示取最靠近表示取最靠近 离散一维搜索方法可采用离散一维搜索进退对分法，离散一维搜索方法可采用离散一维搜索进退对分法，步长为单位离散步长的整倍数。步长为单位离散步长的整倍数。的离散值。的离散值。T-步长因子步长因子第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量
40、优化方法在产生初始复合形顶点及一维离散搜索时，均未考虑约在产生初始复合形顶点及一维离散搜索时，均未考虑约束条件，为保证复合形迭代限制在可行域内，定义一个有束条件，为保证复合形迭代限制在可行域内，定义一个有效目标函数效目标函数EF(x)3约束条件的处理约束条件的处理第41页，此课件共45页哦式中，式中，M 数量级比数量级比f(x)大得多的常数大得多的常数SUM为一特殊函数，其值与所有违反约束量的总和成为一特殊函数，其值与所有违反约束量的总和成正比。正比。常数常数第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法如如图图所所示示为为一一维维变变量量EF
41、(x)的的几几何何图图形形。若若新新点点在在可可行行域域外外，沿沿EF(x)的的下下降降方方向向进进行行一一维维离离散散搜搜索索时时，搜搜索索点点会会自自动动滑滑入入深深井井内内；当当在在可可行行域域内内搜搜索索时时，可可行行域域的的边边界界M犹犹如如一一堵堵高高墙墙，一一到到边边界界就就会会被被挡挡住住。从从而而保保证证离离散散一一维维搜搜索索始始终终在在可可行行域域内进行。内进行。第42页，此课件共45页哦4离散变量组合形的调整（重新启动技术）离散变量组合形的调整（重新启动技术）当沿组合形的调优方向当沿组合形的调优方向S得不到新点时，则需要调整组合形的形状。得不到新点时，则需要调整组合形的
42、形状。调整方法：调整方法：1）用用次次坏坏点点（也也可可以以是是第第2、3坏坏的的顶顶点点）与与其其余余顶顶点点几几何何中中心心的连线方向取代原搜索方向继续进行调优迭代；的连线方向取代原搜索方向继续进行调优迭代；2）上上述述方方法法失失败败，则则将将每每个个顶顶点点都都向向好好点点方方向向收收缩缩1/3，构构成成新新组组合合形形继继续进行迭代。续进行迭代。5组合型算法的终止准则组合型算法的终止准则 在连续变量的复合形法中的收敛准则：在连续变量的复合形法中的收敛准则：复复合合形形各各顶顶点点目目标标函函数数值值与与几几何何中中心心点点目目标标函函数数值值的的均均方方根根差差小小于于某个很小的正数
43、，或者复合形某个很小的正数，或者复合形“边长边长”很小时。很小时。但但在在离离散散变变量量的的组组合合形形算算法法中中，由由于于各各个个设设计计分分量量的的离离散散增增量量差差距较大，所以这两个准则均无效。距较大，所以这两个准则均无效。第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法第43页，此课件共45页哦令令 第第i个坐标方向上的长度为：个坐标方向上的长度为：取连续变量的精度值（或称拟增量）为取连续变量的精度值（或称拟增量）为i，各离散变量的增量，各离散变量的增量值为值为i。预先给定的一个期望个数预先给定的一个期望个数EN (n/2ENn)。将将di与与i或或i进行比较，如满足进行比较，如满足di i(或或i)的分量个数的分量个数RN大大于于EN。RNEN，则认为已经收敛。，则认为已经收敛。第六章第六章 第三节第三节 离散变量优化问题与离散变量优化方法离散变量优化问题与离散变量优化方法这时表明离散复合形各顶点坐标值不再产生有意义的变化，这时表明离散复合形各顶点坐标值不再产生有意义的变化，将最好顶点作为离散变量的优化解输出。将最好顶点作为离散变量的优化解输出。第44页，此课件共45页哦第45页，此课件共45页哦