现代优化方法综述

1、1. 引言优化设计英文名是optimization design，从多种方案中选择最佳方案的设计方法。它以数学中的最优化理论为基础，以计算机为手段，根据设计所追求的性能目标，建立目标函数，在满足给定的各种约束条件下，寻求最优的设计方案。第二次世界大战期间，在军事上首先应用了优化技术。1967年，美国的R.L.福克斯等发表了第一篇机构最优化论文。1970年，C.S.贝特勒等用几何规划解决了液体动压轴承的优化设计问题后，优化设计在机械设计中得到应用和发展。随着数学理论和电子计算机技术的进一步发展，优化设计已逐步形成为一门新兴的独立的工程学科，并在生产实践中得到了广泛的应用。通常设计方案可以用一组参

2、数来表示，这些参数有些已经给定，有些没有给定，需要在设计中优选，称为设计变量。如何找到一组最合适的设计变量，在允许的范围内，能使所设计的产品结构最合理、性能最好、质量最高、成本最低（即技术经济指标最佳），有市场竞争能力，同时设计的时间又不要太长，这就是优化设计所要解决的问题。一般来说，优化设计有以下几个步骤：建立数学模型。选择最优化算法。程序设计。制定目标要求。计算机自动筛选最优设计方案等。2. 数学模型优化设计的数学模型是对优化设计工程问题的数学描述，它包含设计变量、目标函数和设计约束三个基本要素。2.1设计变量基本参数a、定义：在设计过程中进行选择变化并最终确定的各项独立参数称为设计变量。

3、b、说明：在设计选择过程中，这些设计变量是变量，但它们一旦被确定后，设计对象也就完全确定了。最优化设计是研究怎样合理地优选这些设计变量的一种现代设计方法。在设计过程中，凡根据设计要求事先给定的，不是设计变量而是设计常量。设计方案的表现形式a、设计空间：由n个设计变量为坐标所组成的时空间称作设计空间。b、设计变量的表示法（1）坐标表示法：一维问题一个设计变量数轴上的一个点 二维问题两个设计变量平面直角坐标系上的向量 三维问题三个设计变量空间直角坐标系的向量n维问题n个设计变量n维超越空间的向量一个“设计”方案，可用设计空间中的一点表示，此点可看成是设计变量向量的端点（始点取在坐标原点），称作设计

4、点。也即：在设计空间中的一个点，对应于一组设计变量的值，代表一个设计方案。设计空间包含了该项设计所有可能的设计方案。（2）向量表示法：二维问题二维向量 三维问题三维向量 n维问题n维向量设计变量的选取a、维数：设计变量的数目称为最优化问题的维数。如有n个设计变量则称为n维问题。b、常选用的设计变量（1）结构的总体布置尺寸，如中心距。（2）元件的几何尺寸：长度，截面尺寸，某些点的坐标值。（3）材料的力学和物理特性：重量、惯性矩、力或力矩等。通常选择的设计变量都是构件的几个尺寸，因为这不仅可使问题相对简单些，而且由于很多实际结构的几个关系和材料特性已决定的缘故。决定结构布置情况的设计变量的选取要复

5、杂些。较困难的是选取表示材料特性的变量，因为通常所用材料的特性是离散值，选择这些变量时出现了设计变量不连续变化的这一特殊问题。c、设计变量的选择原则（1）对设计影响较大的参数选为设计变量（2）尽量减少设计变量的个数2.2设计约束设计约束的种类a、定义：设计空间是所有设计方案的集合，但这些设计方案有些是工程上所不能接受的（例如面积取负等）。如果一个设计满足所有对它提出的要求，就称为可行（或可接受）设计。反之则称为不可行（或不可接受）设计。在设计过程中，为了得到可行的设计方案，必须根据实际要求，对设计变量的取值加以种种限制，这种限制条件称为约束条件。即：一个可行设计必须满足的限制条件称为约束条件。

6、b、分类法一 性能约束：针对性能要求而提出的限制条件称为性能约束。例如：强度条件、刚度或稳定性条件等等。边界约束：对设计变量的取值范围加以限制的约束。例如允许选择的尺寸范围。法二 等式约束：h（x）=0要求设计点在n维设计空间的约束曲面上不等式约束：g（x）0要求设计点在约束曲面一侧2.2.2可行域与非可行域设计可行域：凡满足所有约束条件的设计点，它在设计空间中的活动范围称作可行域。2.3目标函数2.3.1目标函数的定义：a、定义在设计中，设计者总是希望所设计的产品或工程设施具有最好的使用性能，最小的质量或最紧凑的体积和最小的制造成本及最大的经济效益。在最优设计中，可将所追求的设计目标（最优指

7、标）用设计变量的函数形式表达出来。l 目标函数是设计中预期要达到的目标，表达为各设计变量的函数表达式：l 在优化设计中，用目标函数的大小来衡量设计方案的优劣，故目标函数又叫评价函数。 l 优化设计中，通常对目标函数求极小值。b、常用的目标函数（1）以成本最低构造目标函数。（2）按最小重量构造目标函数。（3）按几何要求：如最小体积，最小尺寸构造目标函数。（4）按机构的工作精度要求构造（5）按机构的运动轨迹最准确（6）满足应力要求（材料利用最好）（7）振动或噪声最小（齿轮振动，由侧隙产生，寻找一周期内啮合点加速度平方根值最小）。（8）平均寿命最长（轴承的寿命计算）。（9）冷却效果最好（轴承的热平衡

8、计算）。（10）可靠性最高。2.4 优化设计数学模型的几何意义 优化设计数学模型的一般形式a、模型形式选取设计变量，列出目标函数，给定约束条件后，便可构造最优化设计的数学模型。任何一个最优化问题均可归结为如下描述：在给定的约束条件下，选取适当的设计变量X，使其目标函数f（X）达到最优值，其数学表达式（数学模型）为： b、模型分类：（1）法一 有约束 无约束（2）法二 线性：目标函数和约束函数都是线性的。 非线性：目标函数和约束函数至少有一个为非线性最优化问题的几何描述a、约束条件与可行域b、目标函数等值线（1）定义：目标函数是n为变量的函数，它的图象只能在n+1维空间中描述出来。给定一组设计变

9、量的值就相应有一个函数值（并相应在设计空间对应于一个设计点），具有相同函数值的点集在设计空间内形成一个曲线或曲面，就是目标函数的等值面或等值线。（c、无约束最优解和约束最优解（1）无约束优化问题：在没有限制条件下，对设计变量求目标函数的极小点，即求等值面中心。（2）约束优化问题：在设计可行域内寻求目标函数的极小点。局部最优解和全局最优解一、单谷函数和多股函数只有一个极值点的函数称为单谷函数；具有两个以上局部极值点的函数称为多谷函数。二、局部最优解和全局最优解2.5优化设计数学模型大小的分类: n50大型 10n50中型n10小型 3. 经典优化算法小结：3.1无约束优化方法 工程优化问题通常都

10、是多维有约束优化问题，但需从一维无约束问题到多维无约束优化问题再到多维约束优化问题的由简单到复杂的循序渐进的研究过程。 无约束优化问题数学模型： 分类，从是否利用目标函数的导数信息，分直接法和间接法直接法：坐标轮换法、共轭方向法、鲍威尔法(略)间接法：梯度法、牛顿法(略)、变尺度法(略)3.1.1 坐标轮换法.1 坐标轮换法基本原理将多维无约束优化问题分解、转化为一系列一维优化问题，轮换沿各个坐标轴一维搜索，直到求得最优点。在每次迭代内部，要依次沿各坐标轴进行N次（N为优化问题的维数）一维搜索。这种一维搜索是固定其它N-1维变量，视为常量，然后进行一维搜索，对于第k轮迭代，须重复N次该式的一维

11、搜索，搜索的参数为ajk（即要优化的参数是ajk），为相对第j维变量的搜索步长，搜索方向为第j维空间坐标的方向。当k轮迭代结束后，本轮搜索的重点作为下一轮的起点，即，然后投入下一轮迭代。.2 该方法特点 不考虑目标函数本身的变化情况（函数特点），简单、效率低、收敛速度慢。3.1.2 共轭方向法.1 共轭方向对于N维正定二次函数 (当N=2，为同心椭圆族)，H为函数f的黑塞矩阵(正定对称阵)。若存在两个方向向量，满足，则称与为共轭方向。如何构造共轭方向（二维）？对于某两点，沿方向（不平行）一维搜索得到两个最优点，构成方向，则可以证明与为共轭方向，即当然，这个结论可以从2维推广到N维。同样，说明对

12、于N维函数，有N个共轭方向。对于二次函数，只要经过N个一维搜索即可到达最优点（即N维空间内完成一轮迭代）。对于大于二次的函数，则可能需要将上一轮迭代的终点作为新一轮迭代的起点。在构造迭代方程式时，可以用二次泰勒展开式来近似目标函数的等值面。.2 共轭方向法基本原理第一轮迭代与坐标轮换法相同。将起点和N次一维搜索的末点组成一个新的方向，沿这个方向一维搜索，得到本轮迭代的终点。从第二轮起，舍去前一轮的第一个一维搜索方向，将前一轮的后N个一维搜索方向作为本轮迭代的前N个方向，这N个方向的一维搜索终点与本轮搜索的起点构成第N+1个一维搜索方向，沿这个方向做一维搜索，得到本轮搜索的终点。若不满足精度要求

13、，则重复迭代。.3 共轭方向法的特点收敛速度比坐标轮换法有明显的提高，但前提是每次迭代所产生的新的方向与原来的N-1个方向之间要保持线性无关，若这些方向之间线性相关，则降低了搜索空间的维数，导致不能完全穷尽对设计空间每个方向的搜索，从而不能收敛于真正的最优解。3.1.3 梯度法（最速下降法）.1 梯度法基本原理无约束优化的直接法（坐标轮换法和共轭方向法、鲍威尔法）没有考虑无约束优化最优解存在的必要条件（梯度为零），使用这一条件，可以设计出更为高效的算法，所谓间接法（梯度法、牛顿法、变尺度法）。梯度方向是函数值变化最快的方向，那么负梯度方向便是函数值下降最快的方向。从这一点受启发，可以使迭代方向

14、沿梯度方向进行一维搜索来再多维空间寻优。即搜索方向为梯度方向：，或，则迭代公式为。.2 梯度法的特点前提是梯度存在。优点是算法简单。相邻两次迭代的搜索方向垂直。即证明：，即k轮迭代经过一次一维搜索由k点到达k+1点，那么，对于一维优化有，所以可见，相邻两轮迭代的搜索方向并不一致，为相互垂直的锯齿形过程。剃度法对于迭代出发点目标函数等值面偏心率为零时很有效，但对于有偏心的其效率就低了，随偏心率的增加，迭代终止的难度也在增加。可见这种搜索在接近目标时的收敛是比较慢（缺点）的，效率也就不会高了。剃度法一般并不作为工程中实际应用的方法，常用于其他方法的初始迭代（类似于坐标轮换法）。3.2约束优化方法实

15、际工程优化问题大多数为设计空间多维且带有约束条件的非线性优化问题。其数学模型为根据对约束条件处理方法的不同：直接法（约束坐标轮换法、随机方向法、复合形法、可行方向法）间接法（简约梯度法、惩罚函数法等）。直接法可以直接从可行域中找到最优解；将问题分解为一系列比较简单的子问题，用子问题的解逼近原问题的解。直接法简单直观、对目标函数要求不高；计算量大、收敛慢，因此效率低。 约束随机方向搜索法（随机方向法）3.2.1.1 基本原理从可行域内某一点出发，沿某一给定步长，并随机产生搜索方向，直到该方向同时满足可行性和下降性要求，沿着这个方向以该步长继续搜索，直到不满足可行性及下降性条件为止。把上述满足要求

16、的终点作为新的起点，重新产生随机方向，如果能够找到一个合适的方向，同时满足条件，则沿该方向以原步长继续搜索；如若找不到适合的方向，则将步长减半，仍以该点为起点随机搜索，如果能找到新的方向，则沿该方向继续，如果不能，步长再减半。直到找不到新的搜索方向，且步长满足精度要求，则以该起点为最优点。一个需要说明的问题：从某一点出发，如何判断沿某一给定步长找不到可行的方向呢？如果不靠目标函数和约束条件中隐含的指引信息，那么只有对搜索空间进行机械的排查，对随机方向搜索法而言，就是在产生并搜索了足够多方向之后，认为可以近似的得出这个结论。那么，到底随机搜索了多少个方向才能得出结论呢？一般取50500个方向，当

17、然，如果不考虑计算的速度和效率，这个最大的方向数大一些更好，而且设计空间维数越大，这个数也应越大。3.2.1.2 初始点的选取其中ri为随机数，对C语言，有函数rand()产生一个0到RAND_MAX的伪随机整数，则3.2.1.3随机搜索方向的产生。通过该变换，使搜索方向的每个分量为-1到1之间的随机值，从而确保对每个坐标方向的正负两方向的搜索。之后可以进行标准化处理3.2.1.4 随机法的特点算法简单，对目标函数要求不高；由于随机搜索带有盲目性，效率低，速度慢，可能不收敛。 复合形法3.2.2.1 基本原理（1） 在设计空间找到K个可行点构成多面体（复合形），一般N+1K2N。（2） 不断使

18、复合形向着约束内最优点移动和收缩。更具体一些，根据目标函数值的大小找出这K个点中的最坏点（函数值最大），除最坏点之外的其它K-1个点的形心为映射中点，找到最坏点的映射点（对称点），最坏点之外其余K-1个点以及这个映射点构成新的复合形。（3） 检验复合形中各个点与最好点是否满足重合,或这些点收敛于某个精度构成的最好点的临域之内。若满足，则算法成功结束；否则，重复(2)。3.2.2.2 几个关键问题（一）初始复合形的产生1 确定第一个可行点作为复合形的第一个顶点。如果不满足可行性，反复进行随机搜索，直到找到可行点。公式2 再随机产生其余K-1个顶点。3 对2.中产生的K-1个点逐一检验可行性，并将

19、不满足的点调入可行域。具体的方法：1） 从第一个点起，找到满足可行性的q个点，第q+1个点不满足。求前q个点的形心。2） 将q+1点向这个形心按两点长度的一半移动，如此反复，直到将该点移入可行域。3） 之后其它不可行的点按1）、2）的步骤重复，直到K个点均满足可行性。（二） 映射点不满足可行性和下降性的处理1） 如果映射点不满足可行性和下降性，将映射系数减半，产生新的映射点，如此反复，直到满足；否则2）2） 以次坏点取代最坏点，求新的形心和形心的映射点。（三） 可行域为非凸集的处理如果除最坏点外其它K-1个点的形心不在可行域内，则可行域可能是非凸集。这时在以最好点和该形心构成的超立方体中重新构

20、造复合形。如果，则（四）迭代终止条件：各顶点与最好点目标函数值之差的均方根小于设计精度3.2.2.3 复合形法的特点搜索具有方向性，收敛速度较快 惩罚函数法罚函数法基本思想：约束条件构造罚函数项，并入目标函数，化为无约束优化问题。所谓“惩罚”，既是给不满足约束条件的惩罚项以很大的值，使目标函数的总值增大（就是惩罚），那么无约束优化方法就会使搜索向着总值减小的方向前进，从而使不满足的约束的点（或远离约束边界的点）向满足约束的方向靠拢。4. 现代优化算法小结遗传算法遗传算法简称GA（Genetic Algorithm），最早由美国Michigan大学的J. Holland教授提出（于上世纪60-7

21、0年代，以1975年出版的一本著作为代表）,模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。 遗传算法是以达尔文的自然选择学说为基础发展起来的。自然选择学说包括以下三个方面：（1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。（2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。（3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐与祖先有所不同，演变为新的物种。遗

22、传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的选择、交叉及变异对个体进行筛选，使适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。4.1 遗传算法的基本操作（算子）有（1）选择（Selection Operator） 选择是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。 选择操作可以通过随机方法来实现。首先产生01之间均匀分

23、布的随机数，若某串的选择概率为40%，则当产生的随机数在0.401.0之间时，该串被选择，否则被淘汰。（2）交叉（Crossover Operator） 选择操作能从旧种群中选择出优秀者，但不能创造新的染色体。而交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种。 交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。交叉体现了自然界中信息交换的思想。交叉有单点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。单点交叉是最基本的方法，应用较广。它是指染色体切断点有一处。（3）变异 (Mu

24、tation Operator) 变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变为0，或由0变为1。若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。4.2 遗传算法的特点 （1）遗传算法是对参数的编码进行操作，而非对参数本身，这就是使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自

25、然界中生物的遗传和进化等机理（2）遗传算法同时使用多个搜索点的搜索信息。传统的优化方法往往是从解空间的单个初始点开始最优解的迭代搜索过程，单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜索过程局限于局部最优解而停滞不前。遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高（3）遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，

26、无需目标函数的导数值等其他一些辅助信息。遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以及组合优化问题等（4）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体（5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索（6）遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广（7）遗传算法具有并行计算的特点，因

27、而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化。 4.3 遗传算法的应用领域（1）函数优化 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果。（2）组合优化 随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。（3）生产调度问题 在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。（4）自动控制 在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在其中得