机械优化设计及应用第七章.ppt

1、 第一节 多目标优化问题多目标优化问题 在实际问题中，对于大量的工程设计方案要评价其优劣，往往要同时考虑多个目标。例如，对于车床齿轮变速箱的设计，提出了下列要求：1）各齿轮体积总和尽可能小，使材料消耗减少，成本降低；2）各传动轴间的中心距总和尽可能小，使变速箱结构紧凑；3）齿轮的最大圆周速度尽可能低，使变速箱运转噪声小；4）传动效率尽可能高，亦即机械损耗率尽可能低，以节省能源。此外，该变速箱设计时须满足轮齿不根切、不干涉等几何约束条件，还须满足齿轮强度等约束条件，以及有关设计变量的非负约束条件等。按照上述要求，可分别建立四个目标函数：若这几个目标函数都要达到最优，且又要满足约束条件，则可归纳为

2、：1234min()min.01,2,01,2,nTRjkVFffffstgjphkqxxxxxxxxLL又例如，在机械加工时，对于用单刀在一次走刀中将零件车削成形，为选择合适的切削速度和每转进给量，提出以下目标：1）械加工成本最低；2）生产率最高；3）刀具寿命最长。此外，还应满足进给量小于毛坯所留最大余量以及刀具强度等约束条件。显然，这个问题也属于多目标优化问题。类似的问题还可以列举很多。一般地说，若有个目标函数，则多目标优化问题的表达式可写成为：12min()min.01,2,01,2,nTlRjkVFfffstgjphkqxxxxxxxLLL在多目标优化模型中，还有一类模型，其特点是，在

3、约束条件下，各个目标函数不是同等的被最优化，而是按不同的优先层次先后地进行优化。如某工厂生产：1号产品，2号产品，3号产品，n号产品。应如何安排生产计划，在避免开工不足的条件下，使工厂获得最大利润，工人加班时间尽量地少。若决策者希望把所考虑的两个目标函数按其重要性分成以下两个优先层次：第一优先层次工厂获得最大利润；第二优先层次工人加班时间尽可能地少。那么这种先在第一优先层次极大化总利润，然后在此基础上再进行第二优先层次同等地极小化工人加班时间的问题就是分层多目标优化问题。以上诸例说明，在实际问题中确实存在着大量多目标优化问题。这类问题要同时考虑多个指标，而且有时会碰到多个定性指标，且有时难于判

4、断说那个决策更好。这就造成多目标优化问题的特殊性。多目标优化设计问题要求各分量目标都达到最优，如能获得这样的结果，当然十分理想。但是一般比较困难，尤其是各个分目标的优化互相矛盾时更是如此。如机械优化设计中技术性能的要求往往与经济性的要求互相矛盾。所以解决多目标优化设计问题也是一个复杂的问题。近年来国内外学者虽然做了许多研究，也提出了一些解决的方法，但比起单目标优化设计问题来，在理论上和算法上都还很不完善，也不够系统。本章将在前述各章的单目标优化方法的基础上，扼要介绍多目标优化设计问题的一些基本概念、求解思路和处理方法。由上述有关多目标优化问题的数学模型可见，多目标（向量）优化问题与单目标（标量

5、）优化问题的一个本质的不同点是：多目标优化是一个向量函数的优化，比较向量函数值的大小，要比标量值大小的比较复杂。在单目标优化问题中，任何两个解都可以比较其优劣，因此是完全有序的。可是对于多目标优化问题，任何两个解不一定都可以比出其优劣，因此只能是半有序的。例如设计某一产品时，希望对不同要求的A和B为最小。一般说来这种要求是难以完美实现的，因此它们没有确切的意义。除非这些性质完全靠不同的设计变量组来决定，而且全部约束也是各自独立的。假设产品有D1与D2两个设计，A（D1）和A（D2）小于全部可接受D的任何一个A（D），而B（D1）和B（D2）也小于全部可接受D的任何一个B（D）。设A（D1）A（

6、D2）和B（D2）B（D1）,可见上述D1与D2两个设计，没有一个是能同时满足A与B为最小的要求。即没有一个设计是所期望的。更一般的情形，设 和 是多目标优化问题的满足约束条件的两个方案（即设计点），要判断这两个设计方案的优劣，需先求出各自目标函数的值：0 x 1x 0001211112,llffffffxxxxxxLL若 101,2,iiffilxxL则方案 肯定比方案 好。1x 0 x 但是，绝大多数的情况是：对应的某些 的值小于 对应的某些 的值；而另一些则刚好相反。因此对多目标设计指标而言，任意两个设计方案的优劣一般是难以判别的，这就是多目标优化问题的特点。1x 1fx 0 x 0fx

7、 这样，在单目标优化问题中得到的是最优解，而在多目标优化问题中得到的只是非劣解。而且非劣解往往不止一个。如何求得能接受的最好非劣解，关键是要选择某种形式的折衷。所谓非劣解是指若有m个目标 ，当要求（m-1）个目标值不变坏时，找不到一个 ，使得另一个目标函数值 比 更好，则将此 作为非劣解。0ifxx ifx*ifx*x例例 求求 12minTVFfxfx x 2122,02fxxx fxxDxx 分别求得其最优解：1122121,1,2,2xfxxfx 进一步分析多目标优化问题解的可能情况。1）若 ，对任意 都有 则 是多目标优化问题的绝对最优解。如图所示，在 内，共同最优解*Dx*Dx*1,

8、2,iiffilxxL*x0,1x*1x*11f x 就是绝对最优解。*21f x 2）若 ，又存在 ，有 ，它表示 对应的 中，存在着 的某个或某些解比 对应 的中每个分目标值都要小。所以 就成为劣解。*DxDx*FFxxx 1,2,ifilxLx*x*1,2,ifilxL*x 3）若 ，且不存在 ，有 ，则 为非劣解。这意味着在约束集 中已找不到一个 ，使得对应的 中每个分目标值都不比 中相应的更大，并且 中至少有一个分目标值要比 中相应值为小。如图所示，在 中，所有点都是非劣解。例如b点，不存在另一点 满足 ，所以b点是非劣解。*DxDx*FFxx*x*xx 1TlFff xxxL *1

9、TlFff xxxL F x*F x0,2xb F bF b 4）若 且不存在 ，使 ，则 为弱非劣解，或称弱有效解。*DxDx*FFxx*x 显然，多目标优化问题只有当求得解是非劣解或弱非劣解时才有意义，劣解是没有意义的，而绝对最优解存在的可能性很小。第二节第二节 多目标优化方法多目标优化方法 多目标优化的求解方法很多，其中最主要的有两大类：一类是直接求出非劣解，然后从中选择较好的解。属于这类方法的如合适等约束法等。另一类是将多目标优化问题求解时作适当处理。处理的方法分为两种：一种是将多目标优化问题重新构造一个函数，即评价函数，从而将多目标（向量）优化问题转变为求评价函数的单目标（标量）优化

10、问题。另一种是将多目标（向量）优化问题转化为一系列的单目标（标量）优化问题来求解。属于这一大类求解的前一种方法有：主要目标法，线性加权和法，理想点法，平方和加权法，分目标乘除法，功效系数法几何平均法，极大极小法等。属于后一种的有分层序列法等。此外还有其它类型的方法，如协调曲线法等。下面简要介绍几种常用的方法。先介绍几种用评价函数处理多目标优化问题的方法。一、一、主要目标法主要目标法 主要目标法的思想是抓住主要目标，兼顾其它要求。求解时从多目标中选择一个目标作为主要目标，而其它目标只需满足一定要求即可。为此，可将这些目标转化成约束条件。也就是用约束条件的形式来保证其它目标不致太差。这样处理后，就

11、成为单目标优化问题。设有 个目标函数 、，其中 求解时可从上述多目标函数中选择一个 作为主要目标，则问题变为：l 1fx 2fx lfxDx kfx minmaxmin1,2,1,1,kkDkiiifDfffikklDxxxxxLL 二、二、统一目标法统一目标法 统一目标法又称综合目标法。它是将原多目标优化问题通过一定方法转化为统一目标函数或综合目标函数作为该多目标优化问题的评价函数，然后用前述的单目标函数优化方法求解。其转化方法如下：1.1.线性加权和法线性加权和法 线性加权和法又称线性组合法，是处理多目标优化问题常用的较简便的一种方法。这种方法因为有一定理论依据，故已被广泛应用。但这种方法

12、的成功与否在很大程度上取决于一个确定方向的凸性条件。如果缺乏凸性，这种方法将归于失败。所谓线性加权和法即将多目标函数组成一个综合目标函数，把一个要最小化的函数规定为有关性质的联合。例如，设计时希望对不同要求的A和B为最小的问题，可写成综合目标函数：FA DB Dx 12FW A DW B Dx或 式中W为某一系数，称为权系数或加权因素 建立这样的综合目标函数，要注意其原有单位已脱离通常概念，例如A的单位为mm，B的单位为元，则A+B作为目标函数是完全可以接受的。线性加权和法的一般表示如下：根据多目标优化问题中各个目标函数 、的重要程度，对应的选择一组权系数 、，并有 1fx 2fx lfx1W

13、2WlW1101,2,liiiWWilL 用 与 的线性组合构成一个评价函数 ifxiW 1minliiiFW fxx 将多目标优化问题转化成单目标优化问题，即求评价函数 1minminliiDDiFW fxxxx的最优解 ，它就是原多目标优化问题的解。*x 使用这个方法的难处在于如何找到合理的权系数，以反映各个单目标函数对整个多目标函数中的重要程度。使原多目标优化问题较合理的转化为单目标优化问题，且此单目标优化问题的解又是原多目标优化问题的好的非劣解。权系数的选取，反映了对各分目标的不同估价、折衷，故应根据具体情况作具体处理，有时要凭经验、凭估计或统计计算并经试算得出。下面介绍一种确定权系数

14、的方法。对于多目标优化问题的评价函数 1minminliiDDiFW fxxxx其中*1min1,2,iiiiDWfffilxxL 即将各单目标最优化值的倒数取作权系数。可见，这种函数反映了各个单目标函数值离开各自的最优值的程度。在确定权系数时，只需预先求出各个单目标最优值，而无需其它信息，使用方便。此法适用于需同时考虑所有目标或各目标在整个问题中有同等重要的场合。此法的本质也可理解为对各个分目标函数作统一量纲处理。这时在列出综合目标函数时，不会受各分目标值相对大小的影响，能充分反映出各分目标在整个问题中有同等重要含义。若各分目标重要程度不同，则可在上述统一量纲的基础上再另外赋以相应的权系数值

15、。这样权系数的相对大小才能充分反映出各分目标在全问题中的相对重要程度。2.2.理想点法与平方和加权法理想点法与平方和加权法 先对各个目标函数分别求出最优值和相应的最优点。一般所有目标难于同时都达到最优解，即找不到一个最优解使各个目标都能达到各自的最优值。因此对于向量目标函数 来说，向量 这个理想点一般是都达不到的。但是若能使各个目标尽可能接近各自的理想值，那么就可以求出较好的非劣解。1TlFff xxxL12TlFfffL 根据这个思想，将多目标优化问题转化为求单目标函数（评价函数）的极值，构造出理想点的评价函数为：21liiiiffUfxx 求此评价函数的最优解，即是求原多目标优化问题的最终

16、解。式中用相除是使之无量纲化。若在理想点法的基础上引入权系数，构造的评价函数为：21liiiiUWffxx 此即为平方和加权法。这个评价函数既考虑到各个目标尽可能接近各自的理想值，又反映了各个目标在整个多目标优化问题中的重要程度。加权系数的确定可参照前面线性加权和法中权系数的确定方法。求得评价函数的最优解，就是原多目标优化问题的解：21minliiiDiWffxx 3.3.分目标乘除法分目标乘除法 多目标优化问题中，有一类属于多目标混合优化问题，其优化模型为：minmaxFVFxDxx 1TrFff xxxL 1TrmFff xxxL 求解上述优化模型的方法可用分目标乘除法。该法的主要特点是将

17、模型中的各分目标函数进行相乘和相除处理后在可行域上求解。即求解 11,min,rx DrmffffxxxxLL 由上述数值极小化问题所得的优化解，显然是使位于分子的各目标函数尽可能小，而位于分母的各目标函数取尽可能大的值的解。以上所述利用极小化乘除分目标函数求解模型的方法，实际上是对它构造了评价函数：111,rmrmffU FUffffxxxxxxLLL 为使上式有意义，在使用上面所述的通过乘除分目标函数求解时，一般要求各自目标函数在可行域上均取正值。其求解极小化方法与单目标方法类同。三、三、分层序列法及宽容分层序列法分层序列法及宽容分层序列法 分层序列法的基本思想是将多目标优化问题中的个目标

18、函数分清主次，按其重要程度逐一排除，然后依次对各个目标函数求最优解，不过后一目标应在前一目标最优解的集合域内寻优。假设 最重要，其次，再其次，。1fx 2fx 3fx首先对第一个目标函数求解，得最优值*11min ffDxx 在第一个目标函数的最优解集合域内，求第二个目标函数的最优值，也就是将第一个目标函数转化为辅助约束，即求 2*111min fDffxxxx 然后再在第一、第二个目标函数的最优解集合域内求第三个目标函数的最优值，此时，第一、第二个目标函数转化为辅助约束，即求 3*2min1,2iifDffixxxx 照此进行下去，最后求第个目标函数的最优值，即求 *1min1,2,1lli

19、ifDffilxxxxL 采用分层序列法，在求解过程中可能会出现中断现象，使求解过程无法继续进行下去。当求解到第 个目标函数的最优解是唯一时，则再往后求第 、个目标函数的解就完全没有意义了。这时可供选用的方案只有这一个，而它仅仅是由第一个至第 个目标函数通过分层序列求得的，没有把第 个以后的目标函数考虑进去。尤其是当求得的第一个目标函数的最优解是唯一时，则更失去了多目标优化的意义了。k1k 2k lkk 为此引入“宽容分层序列法”。这种方法就是对各目标函数的最优值放宽了要求，可以事先对各目标函数的最优值取给定的宽容量，即 ，。1020 这样，在求后一个目标函数的最优值时，对前一目标函数不严格限

20、制在最优解内，而是在前一目标函数最优值附近的某一范围内进行优化，应而避免了计算过程的中断。*11*22*1111*33*2*1min1)min2)min3)1,2min4)1,2,1iiillliiiffDffDffffDffiffDffilxxxxxxxxxxxxxxL LL 不作宽容时，为最优解，它就是第一个目标函数的严格最优解。若给定宽容值 ，则宽容的最优解为 ，它已经考虑了第二个目标函数，但是，对第一个目标函数来说，其最优值有一个误差。x%1 1x例7.2第三节第三节 离散变量优化问题离散变量优化问题 前面研究的优化方法都是针对连续变量而言的。在工程优化问题中，经常会遇到非连续变量的一

21、些参数，它们是整数变量或离散变量。整数变量的如齿轮的齿数，加强肋的数目，冷凝器管子的数目，行星轮的个数等。离散变量如齿轮的模数，型钢尺寸以及大量的标准表格、数据等。整数亦可视为是离散数的一种特殊情形。综上所述，离散变量是指在规定的变量界限内，只能从有限个离散值或整数值中取值的一种变量。离散变量中有等间隔离散变量和非均匀间隔离散变量两种。由于离散变量在工程中大量存在，故研究离散变量的优化方法是非常必要的。处理离散变量的一种最简易方法是先将这种设计变量视为连续变量来处理，在得出优化解后，圆整成最近的值。这种方法虽简单易行，但有很大盲目性，主要是圆整后的值不在可行域以内的可能性很大。因为很多约束条件

22、是用“小于”及“等于”某一界限来表示。通常优化解多半只满足于“等于”条件，也就是说，优化解一般是在某一条等值线与可行域边界的切点上，即在可行域的边界上。圆整后的优化解，可能落于非可行域中，从而破坏了约束条件，不能作为整数优化解。纠正这个缺点的方法是校核未取整前优化解附近的所有整数点或离散点，以保证不出现上述圆整后违反约束条件的情况。但这样做需较长的计算时间。此外在多维空间中，未取整前优化解的附近有多少个整数点也较难确定，并且不能排除在离未取整前优化解较远的整数点恰恰是真正优化解的可能性。另外，有些设计变量是不允许最后取整的。如设计变为齿轮传动，优化结果是非整数的齿数、非标准的模数及变位系数，如

23、果将齿数圆整，模数取标准以后，原优化结果的变位系数就不变得毫无意义了。为此，需对离散变量优化问题作为专门的课题予以研究讨论。第四节第四节 离散变量优化方法离散变量优化方法 常见的离散变量优化方法有混合整数优化方法、约束非线性混合离散变量优化方法等。约束非线性混合离散变量优化设计问题的数学模型可表达为 minmaxmin.01,2,1,2,jiiifst gjmxxximxxLL其中1212DCnTDDpTCCppnRxxxRxxxRxxxxxLLnDCRRR 为离散变量的子集合，为全连续变量的子集合。DxCx 为空集时，为全连续变量型问题；反之，为空集时，为全离散型问题；二者均为非空集时为混合

24、型问题。DxCx 若将整数视为离散数的一种特殊情况，则混合离散变量优化问题实际上已包含了混合整数变量的优化问题。解决工程问题离散变量的优化的方法需要有与一般处理连续变量优化技术不完全相同的一种理论和方法。离散最优化是数学规划和运筹学中最有意义，但也是较困难的领域之一。约束非线性离散变量的优化方法有以下四类：1）以连续变量优化方法为基础的方法；如圆整法、拟离散法、离散型惩罚函数法。2）离散变量的随机型优化方法；如离散变量随机试验法、随机离散搜索法。3）离散变量搜索优化方法；如启发式组合优化方法、整数梯度法、离散复合形法。4）其它离散变量优化方法；如非线性隐枚举法、分支定界法、离散型网格与离散型正

25、交网格法、离散变量的组合型法。这些方法的解题能力与数学模型的函数性态和变量多少有很大关系。一、以连续变量优化方法为基础的方法一、以连续变量优化方法为基础的方法1.1.整型化、离散化法（圆整法，凑整法）整型化、离散化法（圆整法，凑整法）该方法是先按连续变量方法求得优化解，然后再进一步寻找整型量或离散量优化解。这一过程称为整型化或离散化。设有n维优化问题，其实型最优点为 ，它的n个实型分量为 ，则 的整数部分 （或它的偏下一个标准量）和整数部分加1即 （或它的偏上一个标准量）便是最接近 的两个整型（或离散型）分量。*nRx*ix*ix*ix*1ix*ix 由这些整型分量的不同组合便构成了最邻近与实

26、型最优点的两个整型分量及相应的一组整型点群 （），该整型点群包含有 个设计点。在整型点群中，可能有些不在可行域内，应将它们剔除；在其余可行域内的若干整型点中选取一个目标函数值最小的点作为最优的整型点给与输出。*tix1,2,2nt L2n 这样做有时不一定行得通，因为连续变量的最优点通常处于约束边界上，在连续变量最优点附近凑整所得的设计点有可能均不在可行域内。显然在这种情况下，采用连续变化量优化点附近凑整法就可能得不到一个可行设计方案。另一方面，这种简单的凑整法是基于一种假设，即假设离散变量的最优点是在连续变量最优点附近。然而这种假设并非总能成立。该问题离散变量最优点应是离 较远的P点，而且如

27、果目标函数与约束函数的非线性越严重，这种情况越易出现。*x 这些情况表明，凑整法虽然简便，但不一定能得到理想的结果。由以上分析可知，离散优化点不一定落在某个约束面上，因此对连续变量约束最优解的K-T条件不再成立。与连续变量优化解一样，离散变量优化解通常也是指局部优化解。所谓局部离散优化解，是指在此点单位领域 内查点未搜索到优于 点的离散点，所得的解即为局部离散优化解 。UN x*x*x 当目标函数为凸函数、约束集合为凸集时，此点也是全域的约束离散优化解。2.2.拟离散法拟离散法 该法是在求得连续变量优化解 后，不是用简单的圆整方法来寻优，而是在 点附近按一定方法进行搜索来求得优化离散解的。*x

28、*x 该法虽然比前述圆整法前进了一步，但因仍是在连续变量优化解附近领域进行搜索，往往也不可能取得正确的离散优化解。（1）交替查点法（Luns法）该法适用于全整数变量优化问题，其优化离散解的搜索方法为：1）先按连续变量求得优化解 ，并将它圆整到满足约束条件的整数解上。*x2）依次将每个圆整后的优化分量 加1，检查该点是否为可行点，然后仅保留目标函数值为最小的 点；重复此过程，直到可行的 不再增大为止。*ixixix 3）将一个分量加1，其余n-1个分量依次减1。如将 增加到 ，再将 减到 ，如此下去，直到 减到 为止，最后选择目标函数值为最小的点去替换旧点。1x11x 2x21x nx1nx 再

29、依次增大 、，重复上述循环。最终比较目标函数值的大小，找到优化解，即认为是该问题的整数优化解。2x3xnx（2）离散分量取整，连续分量优化法（Pappas法）该法是针对混合离散变量问题（即变量中既含有离散分量，也含有连续分量）提出来的。其计算步骤为：1）先将连续变量优化解 圆整到最近的一个离散点 上。*x*x2）将 的离散分量固定，对其余的连续分量进行优化。*x3）若得到的新优化点可行，且满足收敛准则，则输出优化结果，结束。否则把离散分量转移到 邻近的其它离散点上，再对连续分量进行优化，即转2）。如此重复，直到 附近离散点全部轮换到为止。*x*x 该法实际上只能从上述几个方案中选出一个较好的可

30、行解作为近似优化解。由于离散变量移动后得到的离散点可能已在可行域外，故要求连续变量所用优化程序应选择其始点可以是外点的一种算法。该算法可适用于设计变量较多但连续变量显著多于离散变量的情形，且计算工作量增加不大。对离散变量较多，而变量维数又较低（少于6个）的混合离散变量问题Pappas又提出了另一种算法。其步骤为：1）求出连续变量优化解 ，取整到最靠近 的离散值上。*x*x2）令变量的灵敏度为 ，它是目标函数的增量与自变量增量的比值。即iS iiiSfxfxxx 它反映了变量对目标函数的影响程度。计算各离散变量的灵敏度 ，并将离散变量按灵敏度从大到小的顺序排队：、。iS1x2xkx1kn 3）相

31、对灵敏度最小的离散变量 作离散一维搜索，并使其它离散变量 、固定不变。每当搜索到一个较好的离散点时，便需要对所有连续变量优化一次。然后再对 作一维离散搜索，此时将其余的离散变量 、保持不变，但对分量 还要再作一次搜索。找到好的离散点后仍需对所有的连续变量再进行优化。如此重复，直到 为止。kx1x2x1kx1kx1x2x2kxkx1x 4）由3）所得终点重新计算灵敏度并进行排队。若与第2）步结果相近，则停止计算，其终点即为优化解。否则转3）继续搜索。该法可采用连续变量优化程序对初始点是外点的一种算法。拟离散法是目前求解离散变量优化的一种常用方法，但这类算法都是基于离散优化解一定在连续优化解附近的

32、这样一种观点的基础之上。而实际情况又往往不一定是这样的，而且这类算法工作量较大，因此具有一定的局限性。3.3.离散惩罚函数法离散惩罚函数法 若将设计变量的离散性视为对该变量的一种约束条件，则可用连续变量的优化方法来计算离散变量问题的优化解。按此思路可以Lagrange乘子法或SUMT法等连续变量优化方法为基础作些变换后，再用来求解离散变量的优化问题。下面介绍一种离散惩罚函数法。1）构造一个具有下列性质的离散惩罚函数项00DDDkDDRQRxxx Marcal定义的离散惩罚函数项为 1dijijDkj d iijxZQZx 设计空间离散点的集合 Gisvold定义了另一种形式的离散惩罚函数项：4

33、1Dkiikj dQqqx minmaxminminmaxiiiiiiiiqxxxxxxx2）将离散惩罚函数项加到内点法SUMT的惩罚项中，可得离散惩罚函数 11,mDkkkuuSfS Qgxxxx原目标函数 参数（或称罚因子）不等式约束条件 离散项罚因子 ，而 ，当 时有 ，此时 1kk1kkSSk 0k min,min01,2,0uDkSfgumQxxxxL例例7.37.3 离散惩罚函数法的缺点是函数容易出现病态，给优化搜索造成较大困难，因此它不能算是一种成功有效的方法。二、二、离散变量型网格法离散变量型网格法 1.1.离散变量型普通网格法离散变量型普通网格法 离散变量型普通网格法就是以一

34、定的变量增量为间隔，把设计空间划分为若干个网格，计算在域内的每个网格节点上的目标函数值，比较其大小，再以目标函数值最小的节点为中心，在其附近空间划分更小的网格，再计算在域内各节点上的目标函数值。重复进行下去，直到网格小到满足精度为止。此法对低维变量较有效，对多维变量因其要计算的网格节点数目成指数幂增加，故很少用它。为提高网格搜索效率，通常可先把设计空间划分成为较稀疏的网格，如先按50个离散增量划分网格。找到最好点后，再在该点附近空间以10个离散增量为间隔划分网格，在这个范围缩小、但密度增大的网格空间中进一步搜索最好的节点。如此重复，直至网格节点的密度与离散点的密度相等，即按1个离散增量划分网格

35、节点为止。这时将搜索到的最好点作为离散优化点。2.2.离散变量型正交网格法离散变量型正交网格法 由前述网格法的分析可知，只要约束优化点包含在寻优区间中，且网格点又布置得足够密，则约束优化解就不会被漏网。但当变量数增加时，网格点数将成幂指数增加。设变量数为n，每个变量分点数均为T，则总的网格点数为 。可见在变量维数较高时要细分网格，将大大增加计算工作量，这是网格法的主要缺点。nT 正交网格法的基本思想相当于正交试验法，它是利用正交表，均匀的选取网格法中的一部分有代表性的网格点作为计算点，又称随机正交网格法，或叫正交计算设计法。正交网格法只计算了网格法中一部分网格点的目标函数值，工作量明显减少。对

36、n维变量每个变量分点数均为T的优化问题，正交网格法只需算 个网格点，计算点数与变量维数无关。2T 计算点虽少，但它们在整个寻优区间均匀分布，具有很好的代表性，它们以相当高的可信度代表了全部网格点的计算结果。用正交网格法寻优时，可按正交表的列安排变量，使第 个变量 与正交表中第 列相对应，然后按正交表中的行取点，每一行表示一个试验方案。jjxj 为了体现正交设计的概率特征，提高计算效果，用正交表取定的点为球心，以单位离散变量增量的某一整倍数为半径的球域内随机的取定计算点。该法可称为球域内随机点法。若计算点在可行域内，则计算其目标函数值，并比较各试验点的目标函数值，取目标函数值为最小的点作为较优点

37、，继续寻优，直到达到精度为止。该法的计算步骤如下：1）确定各变量的取值范围 按单位离散变量的增量整数倍选择变量的分点数。即选择水平数 ，为素数；令区间分段数为 ，单位离散变量的增量为 。minmax,1,2,jjxxjnL1TnT1Tj 2）计算各变量分段步长，即网格点的间隔。对等间隔的离散量可取 。或取 ，为正整数；开始时 取大值，以后逐步取小值。令行号 ，中间变量 ，极差分析用数组 ，并以 表示数组 中的第 行第 列元素。minmax1,2,jjjhxxjnLjjh jjhEEE1I FA 0FK,FK i jFKij 3）确定第 个计算点。正交表中的第 行元素 代入下式确定计算点II P

38、 jx minjjjaxP j h令121,2,jjjjjjAhhbxaAhBAhjnL 是区间 上的随机数，取小数后的位数比 的位数少1或相等；是大于1的整数，一般可取 ，若 时 ，这时即将终止计算。注意 此时应取整数或取离散值。B0,1E1b1210b:1bE1E jjh jx 的含义 jx 由上述关系可产生由正交表中第 行的各列元素生成的第 个计算点 。II12TnxxxxL 4）验证点 是否在可行域内，若在可行域内，则转5），否则转6）。x5）计算 ,1,2,FFFK P jjFK P jjFjnxL若 ，则令 ，；否则 、保持原值。FFAFAFpxxFApx6）若 ，则 ，转3）；否

39、则输出 、。2IT1IIFApx 7）极差分析：对数组 按列求出每列的最大值 ，最小值 及对应于 的水平号 ，称为第 个变量 的最好水平。第 个变量 的极差为：FKjmjnjnjWjWjjxjjx1,2,jjjRmnjnL 将 从小到大排列，并与对应的变量号一起输出，以便分析各变量对目标函数的影响程度。jR8）计算最好水平点的目标函数值。令 min1,2,jjijxxhWjnL 则最好水平点 ，若 在可行域内，则计算 ，当 时，令 ，。12TnxxxxLx FFxFFAFAFpxx 因为 为单位离散量步长或单位整型量步长的整数倍，这一做法可使变量优化解为所需的整型量或离散量，因此该法可适用于整

40、型量或离散量的优化问题。jh 9）对 为在可行域内的优化解检验迭代是否可以终止。如可检验步长 （为单位离散变量的增量值）是否满足？若已满足或总的迭代次数已足够则输出 、，停机。若 不满足或优化解 在可行域外或 ，则转10）。xjjh jFApxjjh xFFA 10）寻优区间的收缩或扩张，计算重新开始。令 maxmin2minmax1,2,jjjjpjjpuxxcxxjuxxjjnL 式中，是 的第 个分量；，为正整数，当取 时，寻优区间收缩；当取 时，寻优区间扩张，转2）。pxjpxj22c 22c 22c 这里扩张与收缩应视具体情况决定。一般规律是先扩张，以后逐步缩小寻优区间，使 逐步减小

41、到单位离散变量的增量 为止。分析所得结果是否是所要求的优化解。如果出现伪优化解，这时可以采用将各变量在正交表中的列号互换位置，其实质即使原正交表改变形状，使 ，jhj1nxx12,3,jjxxjnL 如此错位后再按正交表重新寻优，亦即转2），计算重新开始。经验证明，这样交换三次左右往往可以走出伪优化解的死区，找到真正优化解。三、离散变量的组合型法三、离散变量的组合型法 离散变量的组合型优化方法，又称MDCP法。这种方法是以离散复合形思想为主体，具有离散搜索策略，且备有多种功能的组合型算法。本法是一种有效的求解约束非线性离散变量问题的方法，具有较好的解题可靠性。组合型方法的含义是指将两种单一性算

42、法组合在一起形成的第三种算法。在计算过程中，除了方法本身按计算过程中产生的信息不断自动调用各种辅助功能外，使用者还可按计算机输出的信息进行分析判断加以人工干涉改变计算策略，使两者灵活运用，以期较好较快的求得离散变量的优化解。该法可用于求解约束非线性混合离散变量优化设计问题。其数学模型为：minmaxmin.01,2,1,2,jiiifst gjmxxximxxLL式中1212DCnTDDpTCCppnRxxxRxxxRxxxxxLLnDCRRR 为离散变量的子集合，为全连续变量的子集合。DxCx 离散变量复合形优化的基本思想与连续变量复合形优化思想是一致的。该法属于在离散空间直接查点的一类方法

43、，对高维问题，计算工作量相对较大。但由于离散空间仅仅是一些离散点集，搜索的点比连续空间要少，故可用于维数的 场合，此时计算效率还是较好的。20n计算步骤：1）产生 的初始离散复合形顶点；2）利用复合形顶点目标函数值大小，判断目标函数下降方向，产生新的较好的顶点；3）用新顶点代替原复合形中最坏的顶点；4）重复计算，使复合形不断向最优点方向搜索、移动；5）当满足收敛条件时结束，以其中最好顶点作为离散优化解。1kn 由以上步骤可以看出，它和连续变量复合形优化的步骤是一致的。但离散变量和连续变量是有区别的，因此在形成初始复合形及搜索产生新点时都有其特点，下面针对这些特点分别予以讨论。1.1.初始复合形

44、顶点的形成初始复合形顶点的形成 给定一个初始离散点 ，其各分量必须满足变量边界条件，即 0 x 0minmax1,2,iiixxxinL 初始离散点各分量只满足边界条件，但不一定全部满足其它约束条件。初始复合形顶点可用下述方法形成：设初始复合形顶点数 个，标记的上标为点号数，下标为该点的分量号值。取21kn 10101min101max1,2,1,2,;1,2,1,2,1,2,;1,2,1,2,iijiijjjnjiinjjjxxinxxin ij jnxxjnxxin ij jnxxjn LLLLLLL这些顶点可能有些是可行点，有些是不可行点 2.2.离散一维搜索产生新点离散一维搜索产生新点

45、 由上一步产生的离散复合形顶点，可计算各顶点的目标函数值。令目标函数值最大的为最坏点，反之为最好点。按连续变量复合形产生新点的方法是以最坏点向其余各顶点的几何中心连线方向进行反射，再根据反射点目标函数值进行延伸或收缩，找出比最坏点要好的可行点，完成一次寻优运算，形成新的复合形。如此反复进行使复合形向最优点逼近。而离散组合型算法与连续变量不同点在于希望产生的新点落在离散空间的离散点上，或者说希望落在离散空间值域矩阵 的元素 上。Qijq 若把最坏顶点作为一维搜索初始点 ，以最坏顶点向其余各顶点的几何中心 ，即点集中心的连续方向作为离散一维搜索的方向 。bx exS 这时可把反射、延伸或收缩几个步

46、骤统一用该离散一维搜索来替代。搜索方向 的各分量值 计算式为SiS 1,2,ebiiiSxxinL 除最坏点 外的其它各顶点的几何中心 的各分量值 计算式为 bx ex eix 111,2,;1,2,1ejiijjj bxsin jknLL设离散一维搜索得到的新点为 ，其各分量值为 tx 1,2,tbiiixxTSinL取 1,2,ttiixxipnL 3.3.约束条件的处理约束条件的处理 在上面讨论的初始离散复合形的形成及离散一维搜索产生新点中，均未考虑约束条件，这一点与连续变量复合形法是不同的。这样做完全是为了降低搜索离散可行顶点的难度，否则其搜索工作量相当大。下面用一种新的技巧来处理约束

47、条件，避开寻找初始离散可行点的困难。使离散复合形顶点自动在寻优迭代中由非可行域向可行域内移动，直至进入可行域，最后求得可行的离散优化解。该法称为自动进入可行域寻优技巧。自动进入可行域寻优技巧可用下述方法来实现：定义一有效目标函数 ，令 EF x fDEFMSUMDxxxxSUM为一特殊函数，其值与所有违反约束量的总和成正比，可由下式求出：01,2,jj PjSUMCgPj gjmxxL 当初始离散复合形顶点中存在不可行顶点时，最坏的顶点总是不可行离散点之一。以最坏顶点 为离散一维搜索的基点，则其有效目标函数值应为 bx bEFMSUMx 由此可知，从不可行离散顶点出发的离散一维搜索，实际上就是

48、沿 方向搜索求 的极小值。当 为零时，求得的新点满足所有的约束条件，即进入可行域内。这时 ，即有效目标函数等于原目标函数。此时若继续进行离散一维搜索，即为对 求极小值。可见引入有效目标函数 来处理约束条件后，即能自动的从不可行离散点进入可行离散点，直到找到离散优化点。把寻找离散可行点和求解离散优化点结合起来统一进行了。SSUMSUM EFfxx fx EF x4.4.重新启动技术重新启动技术 由上所述沿方向进行离散一维搜索只是目标函数可能的下降方向，只能表明其下降概率较大，但不一定能保证是下降方向，也就不一定能求得好的离散点。当出现这种情形时，须要采用重新启动技术，它属于算法的一个辅助功能。但

49、它与离散复合形产生合适的新点关系十分密切。重新启动技术可以有两种方法：一是改变搜索基点和搜索方向；二是离散复合形的各顶点向最好顶点搜索。5.5.组合型算法终止总则组合型算法终止总则令 max1,2,min1,2,1,2,jiijiiiiiaxjkbxjkLabinLLL 取连续变量的精度值（或称拟增量）为 ，其值由实际设计变量的含义事先选定。如可取为 ；离散变量的增量可取为 ；取变量中期望满足精度的分量个数为 ，为一取定的正整数。通常取 。并设 （或 ）的个数为 。则当 时，离散复合形寻优迭代运算结束，这时表明离散复合形各顶点坐标值不再产生有意义的变化。i410iENEN2nENniiL iR

50、NRNEN 6.6.组合型算法的辅助功能组合型算法的辅助功能 上述离散复合形运算中，加入了重新启动技术，这一辅助功能可使产生新点寻优迭代工作比较顺利地进行下去，直至迭代满足精度要求结束运算。但此时不能保证迭代的高效率，也不能保证迭代能找到离散优化解。为此，该算法中还需要加入其它辅助功能，以提高求解效率及可靠性。通常其辅助功能除了上述的重新启动技术外，还有加速技巧、变量分解策略、网格搜索技术、贴界搜索技术、离散复合形最终反射技术和离散复合形重构技术等6种辅助功能。第五节第五节 工程设计应用工程设计应用一、机械刨床的优化设计一、机械刨床的优化设计1.1.设计问题设计问题 已知刨床的行程速比系数 、