第二章 优化设计.doc

第2章 优化设计优化设计是在满足一定的约束前提下寻求目标函数极大值或极小值的过程。实际上，自然界中很多现象都是以优化的方式存在的，如在金属和合金中，原子占据能量最小的位置以形成晶胞，这些晶胞决定了材料的晶体结构；在零重力条件下一滴液体的形状是一个完美的球，因为在体积一定的条件下，球的表面积最小；树的支干在根部变粗以抗弯，蜂巢结构是最紧凑的包装排列方式之一等，而遗传和变异对生存来讲是自然界优化过程的又一实例。和自然界一样，社会和企业中的许多问题也在追求最优化状态，然而这些问题的解多数情况下都基于判断和经验。随着企业之间的竞争加剧和用户要求的不断提高，要求得到最优解而不仅仅是可行解，在大规模零件生产中的很小的节约也会企业带来可观的效益。在车辆设计中，质量的最小化可以影响到燃油效率，提高载重量和性能。优化设计是应用数学的方法寻求最优设计的过程，所以首先要根据实际的设计问题建立相应的数学模型，即用数学形式来描述实际设计问题。在建立数学模型时需要应用专业知识确定设计的限制条件和所追求的目标，确定设计变量之间的相互关系等。数学模型一旦建立，优化设计问题就变成一个数学求解问题，应用优化理论，根据数学模型的特点，以计算机作为工具，设计优化程序，可求得最佳设计参数。2.1 优化设计的基本概念 (1) 优化设计的数学模型优化设计的数学模型，就是描述优化问题的设计内容、变量关系、有关设计条件和优化意图的数学表达式。 建立数学模型是优化设计的基础，数学模型能否严密而准确地反映优化问题的实质，是优化设计成败的关键。 优化设计的数学模型包括设计变量、目标函数和约束条件三个要素。 (2) 设计变量所谓产品设计，其核心就是要寻找并确定最佳的结构参数。这些参数中，有的可根据标准、规定等选定，在优化设计中可认为是设计常量，有的必须通过设计确定，这些参数称为设计变量。例如在齿轮设计中，可以把静摩擦系数、系列化齿轮传动的中心距等作为设计常量，而把齿数、模数、齿宽等作为设计变量。 设计变量可分为连续变量和离散变量两种。大多数机械优化问题中的设计变量都是连续变量，可用常规的优化方法进行求解。若变量只能取跳跃式的值才有意义，则称为离散变量，如齿轮的齿数、模数等。对于离散变量的优化问题既可以用离散优化方法求解，亦可先将其视为连续变量，用常规的优化方法求得优化结果后，再进行圆整或标难化处理，以求得最优解。 设计变量的个数称为优化问题的维数，如有个设计变量，则称为维优化设计问题。设计变量可写为这种以个设计变量为坐标轴组成的实空间称为维实空间，用表示。这样，具有个分量的一个设计变量对应着维设计空间中的一个设计点，用符号表示，它代表具有个设计变量的一个设计方案。当维数时，如图2-1(a)所示，设计变量、组成二维设计空间。当维数时，如图2-1 (b)所示，设计变量、组成三维设计空间。当3时，设计空间无法用图形表示，称为超越空间。a二维设计空间 (b) 三维设计空间图2-1 优化设计空间 (3) 目标函数为了对设计进行定量评价，必须构造包含设计变量的评价函数，它是优化的目标，称为目标函数，用表示。建立目标函数，是整个优化设计中比较重要的问题，它既要反映用户的要求，又要敏感地、直接地反映设计变量的变化。一般情况下，目标函数与设计变量应有明显的函数关系。由于目标函数可以直接用来评价设计方案的好坏，所以又称目标函数为评价函数。在机械产品设计中，目标函数主要按设计准则要求来建立。在零件和部件设计问题中，可以用重量、体积、效率、可靠性、承载能力等表示；在机构优化设计问题中，这种准则可以是运动学和动力学的性质；对于产品设计，也可以将成本、价格、寿命等作为所追求的目标。在某些设计中，可能存在两个或两个以上的优化设计目标，如设计一台机器时，期望得到最低的造价和最小的维护费用等。具有两个或两个以上的设计目标的优化设计，称为多目标优化设计。 优化问题一般统一用极小化来描述。即 （2-1）实际工程设计问题中有追求极大化的，如效率最高、容积最大、承载能力最高等。这时可转化为其负值的最小问题来处理。即： （2-2） (4) 约束条件任何设计，都有各种各样的限制条件，例如强度、刚度等。每个限制条件都可写成包含设计变量的函数，称为约束条件。 函数约束的形式有不等式约束和等式约束两种：（1）不等式约束 （2）等式约束 对设计变量的可能取值范围的限制： ，其中：和分别为设计变量的下界和上界。确定约束函数时应注意，不能有矛盾约束，可行域不能无界，尽量避免等价约束，也不能遗漏必须的约束。带有设计约束条件的优化问题称为约束优化问题，反之则称为无约束优化问题。在机械设计中绝大多数属于约束优化问题。所有的约束优化问题都可以转化为无约束优化问题，为方便起见，本书介绍的方法基本上以无约束优化问题为基础。为了让大家对优化设计的基本概念和数学模型的一般形式有一个全面的了解，下面用几个简单的优化设计实例加以说明。它们虽然简单，但都有一定的代表性。例2.1 某工厂生产甲、乙两种产品。生产每种产品所需的材料、工时、电力和可获得的利润，以及能够提供的材料、工时和电力见表2-1。试确定两种产品每天的产量，使得每天可能获得的利润最大。表2-1生产条件与供给数据产品材料kg工时h电力(kWh)利润元甲93460乙4105120供应量360300200这是一个生产计划问题，可归结为既满足各项生产条件，又使每天所能获得的利润达到最大的优化设计问题。设每天生产甲产品件，乙产品件，每天获得的利润可用函数表示，即每天实际消耗的材料、工时和电力可分别用函数、和表示，即 于是上述生产计划问题可归结为 求变量 ， 使函数 极大化 满足条件 这就是该设计问题的数学模型，其中代表设计目标，称为目标函数。代表5个已知的生产指标，称为约束函数。5个不等式代表5个生产条件，称为约束条件。由于目标函数和所有约束函数均为设计变量的线性函数，故此问题属线性约束优化问题。图2-2 空心传动轴简图例2.2 一种承受纯扭矩的空心传动轴，已知传递的转矩为T，见图2-2。试确定此传动轴的内、外径，以使其用料最省。当传动轴的长度一定时，轴的体积与截面积成正比。因此，该传动轴的设计可归结为在满足强度和刚度条件的前提下，合理确定轴的内、外径，以使其截面积最小的优化设计问题。由机械设计资料知, 空心传动轴的截面积:扭转强度条件 扭转刚度条件 式中，和分别为最大扭剪应力和许用扭剪应力；和分别为扭转角和许用扭转角；G为剪切弹性模量。分别用,代表外径D和内径d，则上述设计问题可归结为如下数学模型：求设计变量 ,使函数 极小化满足条件 这是一个含有4个约束条件的二元非线性约束优化问题。2.2 基于导数的优化算法2.2.1梯度法 函数的梯度方向是函数值增加量最快的方向，而负梯度方向是函数值下降最快的方向。梯度法就是采用负梯度方向作为搜索方向，其迭代式可由基本迭代公式导出。一般基本迭代公式： （2-3）取 ，则有 （2-4） 为使目标函数值沿搜索方向能获得最大的下降值，其步长因子应取一维搜索的最优步长。即 (1)梯度法求优的步骤梯度法求优的步骤如下。任选初始点，选定迭代精度，。确定点的梯度计算梯度的模： 判断终止迭代条件若满足，则迭代终止，得最优解：，不满足，转下一步。寻求下一个迭代点式中，步长因子为最优步长。由一维搜索求得。令，返回第步。按照上述迭代方法进行若干次一维搜索，每次迭代的初始点取上次迭代的终点，即可使迭代点逐渐逼近目标函数的极小点。图2-3描述了用梯度法优化二维问题时逼近极小点的过程。其中，为初始点，为极小点。 (a) 等值线是椭圆 (b)等值线是圆图2-3 梯度法迭代过程 从图2-3可以看到，对于等值线为圆的优化问题，梯度法一次迭代就可达到极小点；当等值线不是圆时，负梯度方向不再指向圆心(实线)，迭代次数增加。实际上，偏心越严重，迭代次数越多，形成“锯齿现象”。而且，在搜索开始时步长较大，愈接近极小点步长愈小，最后收敛的速度极其缓慢。 (2) 梯度法的特点梯度法的特点是，初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。 梯度法每次迭代都是沿迭代点函数值下降最快的方向搜索，因而梯度法又称为最速下降法。其实，这种方法搜索路线常常很曲折，收敛速度较慢。因此，对于比较复杂的优化问题，梯度法不具有实用价值。但由于梯度法在迭代开始时函数值下降得较快，因而常用于其他方法中作初始迭代法。2.2.2牛顿法 (1) 牛顿法的基本思想 牛顿法是梯度法的进一步发展，其基本思想是在求目标函数的极小值时，先将在点附近作泰勒(Taylor)展开，取其二次近似函数式，然后求出这个二次函数的极小点，并以该极小点作为原目标函数的近似极小点；若此值不满足精度要求，则以此近似极小点作为下一次迭代的初始点，继续以上过程，迭代下去，直至所求出的近似极小点满足精度要求为止。 (2) 牛顿法的迭代公式 对目标函数在点取二阶泰勒展开，即这里，是函数的二阶偏导数矩阵(即Hession矩阵)。求二次近似函数的极小点，令，得若是二次函数，则就是的极小点；否则只是一个近似点，需进一步迭代。 牛顿法的迭代公式为 （2-5）比较图2-3(a)与(b)可知，当的等值线是圆时，负梯度方向直接指向极小点；而当是正定二次函数，其等值线是椭圆时，牛顿方向(图中，的连线方向)也可直接指向极小点，只经一步就收敛到。其原因就在于牛顿法改变了设计空间的度量尺度。对于偏心率为零的二次函数，其等值面(线)是一组超球面(圆)，在设计空间中，任意点的负梯度方向总是指向球(圆)心的；然而对于偏心率不为零的二次函数，其负梯度方向就不指向中心了。这些结论是在欧氏尺度即的条件下成立的。而牛顿法的实质是对原坐标引入新的尺度，即。在新尺度坐标系条件下，牛顿法对目标函数进行了交换，使其偏心率减少。如果目标函数是二次函数，总可以得到偏心率为零的结果，即变换后的目标函数的等值面(线)已成为超球面(圆)了，变换后的目标函数的负梯度方向就是牛顿方向。因而，牛顿法可以看作是在新尺度下的梯度法。 由于牛顿法迭代公式中没有步长因子，或者说是一种定步长的迭代（），这对于非二次型目标函数，有时会出现函数值上升即的情况。这表明牛顿法不能保证函数值的稳定下降，在严重的情况下甚至可能造成迭代点的发散而导致计算失败。为克服上述弊病，对其加以改进，提出了“阻尼牛顿法”或“修正牛顿法”。 (3) 阻尼牛顿法阻尼牛顿法迭代公式为 （2-6）式中 阻尼因子，或称最优步长因子；牛顿方向，。阻尼牛顿法的算法步骤归纳如下。任选初始点，选定迭代精度，。确定点的梯度，计算梯度的模： 判断终止迭代条件若满足，则迭代终止，得最优解：，不满足，转下一步。 计算点的并求其逆矩阵。 确定牛顿方向，沿牛顿方向作一维搜索，求出在方向上的最优步长。寻求下一个迭代点令，返回第步。阻尼牛顿法的算法流程如图2-4所示。 图2-4 阻尼牛顿法的算法流程图牛顿法不仅利用了函数的一阶导数信息，还利用了函数的二阶导数信息，故其收敛速度较梯度法快得多。但是牛顿法要计算Hession矩阵及其逆矩阵，计算量存储量均很大，且都以维数比例增加，维数高时这个问题更加突出。此外，若Hession矩阵是奇异矩阵时，其逆矩阵不存在，这种方法就根本不能应用，所以牛顿法的应用是有限度的。2.2.3共轭梯度法 (1) 共轭方向法的概念 设为一正定对称矩阵，若有一组非零向量满足=0（）则称这组向量关于矩阵共轭。当为单位矩阵时，有（）此时称向量（）相互正交。 可以证明，对于一般函数，共轭方向具有以下性质。 若（）是以共轭的个向量，对于正定二次函数从任意初始点出发，依次沿这个方向进行一维搜索，最多次即可达到极小点。从任意两个点和出发，分别沿同一方向进行一维搜索，得到两个一维极小点和，则连接此两点构成的向量与原方向关于该函数的二阶导数矩阵相共轭。(2) 共轭方向的形成共轭方向有两种形成方法，它们是平行搜索法和基向量组合法。图 2-5二次函数平行搜索法产生共轭方向1）平行搜索法平行搜索法是由上述共轭方向的性质构造出来的，从不同的两点出发，沿同一方向进行两次一维搜索，或者说进行两次平行搜索，所得两个极小点的连线方向便是与原方向共轭的另一方向。沿该方向作两次平行搜索，又可得到第三个共轭方向，如此继续下去，便可得到一个包含(维数)个共轭方向的方向组。二次函数平行搜索法产生共轭方向如图2-5所示。2）基向量组合法取个基向量(单位坐标向量)()和另一个独立向量，令向量为和的线性组合，即式中 待定常数。 欲使和关于相共轭，则必有下式成立。 联立以上两式，可解得 所以可求得的共轭向量为 同理，令为和、的线性组合，可求得与、共轭的另一个向量，依次类推，有 （2-7） (3) 共轭梯度方向从任意点出发，沿负梯度方向作一维搜索得 设与（）共轭的下个方向由和点的负梯度的线性组合构成，即 根据共轭条件有 联立以上三式，可解得 令为函数的泰勒二次展开式，则点和的梯度可写作 两式相减并联立，得 将和上式的两边分别相乘，并注意式共轭条件，得将上式展开，并注意到相邻两点梯度间的正交关系，整理后得所以可求得 （2-8）上式为共轭梯度法的基本迭代算式，式中，。可见，只需利用相邻两点的梯度就可以构造一个共轭方向。 (4) 共轭梯度法的迭代步骤共轭梯度法的迭代步骤总结如下。给定初始点和收敛精度。取的负梯度方向作为搜索方向，即，置。沿方向作一维搜索得。 收敛判断：若满足，则令，结束迭代；否则，转。 若，则令，转开始新的一轮迭代，否则，转。 构造新的共轭方向，令，转。共轭梯度法的程序框图如图2-6所示。 图2-6 共轭梯度法的程序框图2.3 非导数优化算法2.3.1随机方向法图2-7随机方向法 随机方向法是直接解法的一种，这种向法既可以用于求解约束优化问题，也可以用于求解无约束优化问题。 (1) 随机方向法的基本思想如图2-7所示，随机方向法的基本思想为，在约束可行域内，选取一个初始点，以一初始走步长沿随机方向(以某种形式产生的随机方向)，求得探索点，检验该点是否同时满足下降性(即和可行性(即)要求。若不能同时满足，则应弃去该方向，重新产生另一随机方向进行探索；若能同时满足，则表示点探索成功，然后以它为新的起始点，即，在方向上继续探索新的成功点，直到所探索的点不能同时满足下降性和可行性要求时停止。这时放弃该点，并将前一个成功点作为方向的最终成功点，记为。而后以为新的起点，即，然后再产生另随机方向，以原定步长，重复上述过程，得成功点。依此类推，经若干次循环，点列，必最终逼近约束最优点。 当在某个转折点处(如图2-7中的点)，沿(预先给定的某个转折点处产生随机方向的最大数目)个随机方向以步长进行探索均失败时(即不能同时满足下降性和可行性要求)，可将步长缩半，以进行探索，直至已缩减到指定精度(即)，且沿个随机方向都探索失败时，则以最后一个成功点(如图2-7中的点)为所求的最优约束点。一般选取50500，对目标函数性态不好的应取较大的值，以提高解题成功率。即算法的终止迭代条件为；，式中，为随机方向数，为预先规定的在某转折点处产生随机方向所允许的最大数目。 (2) 随机方向的产生和可行搜索方向的形成随机方向按以下方式产生，将区间内的随机数(伪随机数)按下式转换成为另一个在区间之间的随机数，即式中 按一定的数学模型产生的区间均匀分布的随机数。然后由随机数构成下面的随机方向 （2-9） 由于随机数在区间内产生。因此，所构成的随机方向矢量一定是在超球面空间里均匀分布且模等于l的单位矢量（） 可行搜索方向按以下方法形成，根据基本迭代公式，可计算个随机点。检验个随机点()是否为可行点，并计算可行随机点的目标函数值，比较其大小，选出目标函数值最小点，比较与两点的目标函数值，若，则取和的连线方向作为可行搜索方向。若，则将步长缩小，重新产生随机方向并计算随机点，直至为止。 (3) 约束随机方向法流程综合上述约束随机方向搜索方法，给出如下约束随机方向法的流程图如图2-8所示。图2-8 约束随机方向法的流程图2.3.2 复合形法 (1) 复合形法的基本原理 复合形法的基本思路是在维空间的可行域中选取个设计点(通常取)作为初始复合形(多面体)的顶点，然后比较复合形各顶点目标函数值的大小，其中目标函数值最大的点为坏点，以坏点之外其余各点的中心(即形心)为映射中心，寻找坏点的映射点，一般来说此映射点的目标函数值总是小于坏点的，也就是说映射点优于坏点。这时，以映射点替换坏点，并与原复合形其余各点（除坏点之外）构成个顶点的新的复合形。如此反复迭代计算，在可行域中不断以目标函数值最小的新点代替目标函数值最大的坏点，构成新复合形，从而使复合形不断向最优点移动和收缩，直至收缩到复合形的各顶点与形心非常接近、满足迭代精度要求时为止。最后输出复合形各顶点中的目标函数值最小的顶点作为近似最优点。图2-9 复合形法的基本原理 现以图2-9所示的二维约束优化问题为例进一步说明复合形法的基本原理。图2-9中，在可行域内，先选定义、和共4个点(这里)作为初始复合形的顶点，计算这4个点的目标函数值，并作比较，可以确定函数值最大的坏点，函数值最小的好点，以、和3点的形心为映射中心，寻找坏点的映射点：式中，称为映射系数，一般1，通常取1.3。检查的可行性和下降性。若在可行域之内，且时，则用点替换点，并组成新的复合形，完成一次迭代。若上述两条件得不到满足，应将映射系数减半。即，仍按以上方式迭代，重新取新的，再检查是否满足上述条件，若已满足，则用替换构成新的复合形；反之，则继续将减半，当减至很少(例如时)仍然达不到上式要求时，则更改映射方向，可用次坏点代替进行映射，组成新的迭代过程。这样可使复合形向着目标函数值减小的方向移动和收缩，直至逼近最优解。 (2) 初始复合形的产生初始复合形的全部个顶点都必须在可行域内。对于维数较低，不很复杂的优化问题，可以人为地预先按实际情况决定个可行设计点作为初始复合形的顶点；对于维数较高的复杂优化问题，人为选定这些顶点几乎是不可能的，可以采用伪随机数，由计算机自动确定。 1)随机方法产生初始复合形确定一个可行点作为初始复合形的第一个顶点。在区间上给定一个点，或调用区间内服从均匀分布的随机数列在 区间产生第一个随机点的分量： （2-10）检验是否可行。若非可行点，则调用随机数，重新产生随机点，直到为可行点,继续调用随机数产生其他(-1)个随机点。2）非可行点调入可行域如图2-10所示，非可行点可按下述方法将其调入可行域。首先按下式求可行点点集中心： （2-11） 式中，为可行点数目，然后调入迭代公式 （2-12）图2-10非可行点调入可行域示意图例如图2-10中，为可行点、3点中心，为非可行点，调入可行域，应有。以上调入方法应逐点分别进行，直到全部个点都成为可行点为止，构成个顶点的初始复合形。3）计算形心X0并检查它的可行性以函数值的大小为标准，在复合形各个顶点中选出好点（复合形中函数值最小的顶点）和坏点（复合形中函数值最大的顶点），计算除坏点外其余各顶点之中心：，。 如图2-11所示，若不在可行域内，则以最好点为起点，形心为端点的超立方体(对二维优化问题应为矩形)中重新利用随机数产生新的复合形。即：当然，此时的边界条件已变换为，。 (3) 复合形法的迭代步骤1)按前文介绍的方法构成初始复合形；2)计算各顶点的函数值，按前文介绍的方法选出好点与坏点；3)按前文介绍的方法计算除坏点外其余各顶点之中心；4)计算映射点，计算方法同前；5)构造新的复合形，按以下方式处理。映射点优于坏点，即，用点替换点，组成新的复合形。映射点次于坏点，即，应将映射系数逐次减半，即，当出现时，则转化为情况。如果经过多次将减半，当减至很少，比如小于预先给定的很小正数(例如时)仍然不能使映射点优于坏点时，则说明该映射方向不利。此时，应改换映射方向，取对次坏点的映射。确定不包括在内的复合形顶点中心，并以此为映射轴心，计算的映射点再转回本步骤开始处，直到构成新的复合形。6)判别终止条件当一个新的复合形构成时，可用下列条件判别其是否终止：、判别式中，（）为待判别复合形的顶点，为各顶点中最好点。如果不满足判别终止条件，则返回步骤2）继续进行下一次迭代，否则，可将最后复合形的好点及其函数值作为最优解输出，结束运行。复合形法的流程图如图2-11所示。图2-11 复合形法流程图从上面的讨论可知，复合形法具有如下特点：由于复合形的形状不必保持规则的图形，对于目标函数及约束函数的性状又无特殊要求，因此该法的适用性较强，在机械优化设计中得到了广泛应用。复合形法仅仅依靠复合形顶点的目标函数值和约束函数值的信息，不必计算目标函数的一阶导数和二阶导数，程序较简单。当设计变量和约束函数较多时，复合形法搜索效率较低。2.3.3遗传算法遗传算法（GA, Genetic Algorithm）是一种宏观意义下的仿生算法，它模仿生命与智能的产生与进化过程。遗传算法的基本思想源于达尔文的进化论和孟德尔的遗传学说，它通过模拟达尔文“优胜劣汰、适者生存”的原理产生好的结构，通过模仿孟德尔遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。遗传算法从代表问题可能潜在解集的一个种群开始，借助选择、复制、交叉、变异等遗传操作，依据“适者生存”原则，指导在不断改进的解区域中进行搜索，最后以末代种群的最优个体作为问题的近似最优解。遗传算法作为一种随机优化与搜索方法，有如下特点： 遗传算法具有固有的并行特点，通过对种群的遗传处理可处理大量的模式。遗传算法的操作对象是一组可行解，而非单个可行解；搜索轨道有多条，而非单条，因而具有并行性。 遗传算法只需利用目标函数的取值信息，而无需梯度等高价信息，因而适用于大规模、高度非线性的不连续多峰函数的优化以及无解析表达式的目标函数的优化，具有很强的通用性。 遗传算法的搜索过程是从问题解的一个集合开始的，算法进行全空间并行搜索，并将搜索的重点集中于性能高的部分，正是这一点使得遗传算法有可能得到全局最优解。 遗传算法的处理对象通常不是参数本身，而是对参数进行了编码的个体，目标函数可解释为编码化个体(可行解)的适应值，这使遗传算法不受函数连续性、可导性等约束条件的限制，具有良好的可操作性与简单性。 (1) 遗传算法的基本流程遗传算法虽然是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量的状态。标准遗传算法的主要步骤可描述如下： 随机产生一组初始个体构成初始种群，并评价每一个体的适配值(fitness value)； 判断算法收敛准则是否满足。若满足则输出搜索结果，否则执行以下步骤； 根据适配值大小以一定方式执行复制操作； 按交叉概率执行交叉操作； 按变异概率执行变异操作； 返回步骤。上述算法中，适配值是对染色体(个体)进行评价的一种指标，是GA进行优化所用的主要信息，它与个体的目标值存在一种对应关系；复制操作通常采用比例复制，即复制概率正比于个体的适配值，如此意味着适配值高的个体在下一代中复制自身的概率大，从而提高了种群的平均适配值；交叉操作通过交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，从而有助于产生优良个体；变异操作通过随机改变个体中某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛。 标准遗传算法的流程图如图2-12所示：图2-12 标准遗传算法的优化框图 (2) 算法关键参数与操作的设计通常，遗传算法的设计是按以下步骤进行的。1)确定问题的编码方案 编码就是将问题的解用一种码来表示，从而将问题的状态空间与GA的码空间相对应，编码在很大程度上依赖于问题的性质，并将影响遗传操作的设计。由于GA的优化过程不是直接作用在问题参数本身，而是在一定编码机制对应的码空间上进行的，因此编码的选择是影响算法性能与效率的重要因素。 二进制编码方法是遗传算法中最常用的一种编码方法。它使用的编码符号集是由二进制符号O和1所组成的二值符号集0，l，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是，我们用长度为的二进翻编码符号串来表示该参数，则它总共能够产生种不同的编码，若使参数编码时的对应关系如下： 0000000000000000=0 00000000O0000001=l l111111111111111= 则二进制编码的编码精度为：假设某一个体的编码是：则对应的解码公式为：十进制编码将问题的解用一个十进制串来表示，类似于二进制编码，显然码长也影响算法的精度，而且算法将付出较大的存储量。实数编码将问题的解用一个实数来表示，解决了编码对算法精度和存储量的影响，也便利于优化中引入问题的相关信息，它在高维复杂优化问题中得到广泛应用。组合优化中，由于问题本身的性质，编码方式需要特殊设计，如TSP问题中基于置换排列的路径编码、0-l矩阵编码等。2)确定适配值函数 适配值函数用于对个体进行评价，也是优化过程发展的依据。在简单问题的优化时，通常可以直接利用目标函数变换成适配值函数，譬如将个体的适配值定义为或，其中为一足够大正数，为个体的目标值，。在复杂问题的优化时往往需要构造合适的评价函数，使其适应GA进行优化。 3)算法参数的选取种群数目是影响算法优化性能和效率的因素之一。通常，种群太小则不能提供足够的采样点，以致算法性能很差甚至得不到问题的可行解；种群太大时尽管可增加优化信息以阻止早熟收敛的发生，但无疑会增加计算量，从而使收敛时间太长。当然，在优化过程中种群数目是允许变化的。 交叉概率用于控制交叉操作的频率。概率太大时，种群中串的更新很快，进而会使高适配值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前。变异概率是加大种群多样性的重要因素。基于二进制编码的GA中，通常一个较低的变异率足以防止整个群体中任一位置的基因一直保持不变。但是，概率太小则不会产生新个体，概率太大则使GA成为随机搜索。由此可见，确定最优参数是一个极其复杂的优化问题，要从理论上严格解决这个问题是十分困难的，它依赖于GA理论研究的进展。4)遗传算子的设计优胜劣汰是设计GA的基本思想，它应在选择、交叉、变异等遗传算子中得以体现，并考虑到对算法效率与性能的影响。 复制操作是为了避免有效基因的损失，使高性能的个体得以更大的概率生存，从而提高全局收敛性和计算效率。最常用的方法是比例复制和基于排名的复制，前者以正比于个体适配值的概率来选择相应的个体，后者则基于个体在种群中的排名来选择相应的个体。至于种群的替换，采纳的方案可以是部分个体的替换，也可以是整个群体的替换。交叉操作用于组合出新的个体，在解空间中进行有效搜索，同时降低对有效模式的破坏概率。二进制编码中，单点交叉随机确定一个交叉位置，然后对换相应的子串；多点交叉随机确定多个交叉位置，然后对换相应的子串。譬如，父串为(1 0 1 1 0 0 1)，(O 0 1 0 1 1 0)，若单点交叉位置为4，则后代为(1 0 1 1 1 1 O)，(0 0 1 0 0 0 1)；若多点交叉位置为2，5，则后代为(1 0 1 0 1 0 1)，(O 0 1 1 0 1 0)。十进制编码也类似。实数编码则可采用算术交叉，即，其中，、为父代个体，、为后代个体。组合优化中，交叉操作有部分映射交叉、次序交叉、循环交叉等。当交叉操作产生的后代适配值不再进化且没有达到最优时，就意味着算法的早熟收敛。这种现象的根源在于有效基因的缺损，变异操作一定程度上克服了这种情况，有利于增加种群的多样性。二进制或十进制编码中通常采用替换式变异，即用另一种基因替换某位置原先的基因；实数编码中通常采用扰动式变异，即对原先个体附加一定机制的扰动来实现变异；组合优化问题中通常采用互换式、逆序式、插入式变异。5)确定算法的终止条件 GA的收敛理论说明了GA以概率1收敛的极限性质，因此我们要追寻的是提高算法的收敛速度，这与算法操作设计和参数选取有关。然而，实际应用GA时是不允许让它无停止地发展下去的，而且通常问题的最优解也未必知道，因此需要有一定的条件来终止算法的进程。最常用的终止条件就是事先给定一个最大进化步数，或者是判断最佳优化值是否连续若干步没有明显变化等。应该认识到，GA并非一个简单的系统，而是一种复杂的非线性智能计算模型，纯粹用数学方法来预测其运算结果是很难的，而且这方面的工作也远远不够。目前，为兼顾GA的优化质量与效率，实际应用GA时许多环节一般还只是凭经验解决，这方面还有待更深入的研究与发展。2.3.4模拟退火算法模拟退火算法(simulated annealing,简称SA)的思想最早是由Metropolis等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。模拟退火算法是基于Mente Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题的相似性。当孤立粒子系统的温度以足够慢的速度下降时，系统近似处于热力学平衡状态，最后系统将达到本身的最低能量状态，即基态，这相当于能量函数的全局极小点。简单而言，物理退火过程由以下三部分组成：1)加温过程 加温过程的目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔解为液体，从而消除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。熔解过程与系统的熵增过程相联系，系统能量也随温度的升高而增大。2)等温过程物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。3)冷却过程冷却过程的目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，因而计算量很大。鉴于物理系统