优化理论与最优控制

1、优化理论与最优控制优化理论与最优控制“优化优化”与与“最优化最优化” 优化优化 “化化”加在名词或形容词后构成动词加在名词或形容词后构成动词, ,表示表示转变成某种性质或状态。比如：绿化、转变成某种性质或状态。比如：绿化、美化、丑化，自动化，优化美化、丑化，自动化，优化 最最优化（值）优化（值） 指在指在一定条件影响下一定条件影响下所能得到的最佳值。它所能得到的最佳值。它是一个相对的概念；不同于数学上的极值，是一个相对的概念；不同于数学上的极值，但在很多情况下可以用但在很多情况下可以用最大值最大值或或最小值最小值来表来表示。示。最优化问题的控制方程最优化问题的控制方程 调整（设计、策略、决策）

2、变量调整（设计、策略、决策）变量 设计变量的数目称为最优化设计的维数。设计变量的数目称为最优化设计的维数。 目标函数目标函数 在最优化设计中，可将所追求的设计目标（最优在最优化设计中，可将所追求的设计目标（最优指标）用设计变量的函数（解析或隐含）形式表指标）用设计变量的函数（解析或隐含）形式表达出来，这一过程称为建立目标函数。达出来，这一过程称为建立目标函数。 约束条件约束条件 在很多实际问题中，设计变量的取值范围是有限在很多实际问题中，设计变量的取值范围是有限制的或必须满足一定的条件。以及其他方面的限制的或必须满足一定的条件。以及其他方面的限制。制。最优化问题的控制方程为：最优化问题的控制方

3、程为：最优化问题的数学模型调整参数：调整参数：目标函数目标函数:约束条件：约束条件：X=x1 x2 x3 xnT, X Dymin或 ymax= f(X)hv(X)=0, v=1,2,pgu(X) 0, u=1,2,m几点说明 调整（决策、策略）变量调整（决策、策略）变量 原则应选择对目标函数影响大且独立的变量；通常情况原则应选择对目标函数影响大且独立的变量；通常情况下，调整变量越多，优化潜力越大，但优化过程也越复杂。下，调整变量越多，优化潜力越大，但优化过程也越复杂。 目标函数目标函数 单目标函数：只有一个目标函数；单目标函数：只有一个目标函数； 多目标函数：有多个目标函数。多目标函数：有多

4、个目标函数。 约束条件约束条件 显约束显约束vs 隐约束隐约束、等式约束等式约束vs不等式约束不等式约束和和边界约束边界约束vs 性态约束性态约束。 控制方程的解控制方程的解 调整（设计、策略、决策）变量组合调整（设计、策略、决策）变量组合 vs 目标函数；目标函数； 最优值的相对性与动态性等。最优值的相对性与动态性等。约束条件约束条件 目标函数取决于调整变量目标函数取决于调整变量, ,而在工程实际问而在工程实际问题中调整变量的取值范围是有限制的或必题中调整变量的取值范围是有限制的或必须满足一定的条件。须满足一定的条件。 等式约束：对调整变量的约束严格，起着降等式约束：对调整变量的约束严格，起

5、着降低设计自由度的作用。低设计自由度的作用。 不等式约束不等式约束 边界约束（显约束）：对调整变量的直接限制约束的形式隐约束（性能约束）：对调整变量的间接限制分类分类p 线性规划线性规划：若若 都是调整变量都是调整变量 X的线性函数的线性函数 ；(X),(X)(X)vufhg和p非线性规划非线性规划：若它们不全是调整变量若它们不全是调整变量X的线的线 性函数；性函数；0,0(1,2, ;1,2,)pmvp ump无约束规划无约束规划： 若若 。 参考书目参考书目刘惟信，刘惟信，机械最优化设计机械最优化设计，清华大学出版，清华大学出版社，社，1994年年9月，第月，第2版。版。p常规控制回路的优

6、化调整：参数整定常规控制回路的优化调整：参数整定320( , ,)xaxbxca b cRp方程求解方程求解： 思考题思考题p人工神经元网络的学习算法人工神经元网络的学习算法p 工业过程的优化调整，比如电站锅炉的燃烧工业过程的优化调整，比如电站锅炉的燃烧优化优化举例说明（举例说明（） 小朋友算数小朋友算数 1) 2堆苹果，每堆有堆苹果，每堆有3个，问个，问2堆加起来一堆加起来一 共有几个苹果？若有共有几个苹果？若有3堆，堆，1000堆这样堆这样 的苹果呢？的苹果呢？ 2）9个苹果，个苹果，3个小朋友分，问每人分几个个小朋友分，问每人分几个 苹果？若有苹果？若有18个，个，3000个苹果呢？个苹

7、果呢？观察到什么现象？观察到什么现象？发现什么问题？发现什么问题？得到什么结论？得到什么结论？举例说明（举例说明（） 一简单的仅有两个输入变量一简单的仅有两个输入变量x1、x2，一个输出，一个输出变量变量 y 的工业过程，即的工业过程，即 。在工程中，在工程中，输入变量即运行（工艺）参数输入变量即运行（工艺）参数x1、x2一般都有一般都有一定的取值范围一定的取值范围。不妨设其允许取值范围分不妨设其允许取值范围分别为别为a,b、c,d。那么，图中蓝色方框中所有那么，图中蓝色方框中所有的的x1、x2组合都能满足系统正常运行的要求。组合都能满足系统正常运行的要求。12( ,)yf x x 简单的工业

8、问题简单的工业问题举例说明（举例说明（）请问在这无穷多个组合中，哪个组合请问在这无穷多个组合中，哪个组合y能能取得最大值或最小值呢？取得最大值或最小值呢？1234567891011 1312x1x2ab cd无约束目标函数的极值点存在条件无约束目标函数的极值点存在条件1 一元函数一元函数 任何一个单值、连续、可微分的不受任何约任何一个单值、连续、可微分的不受任何约束的一元函数束的一元函数 点处有极值的点处有极值的充分必要条件是：充分必要条件是： 0( )yf xxx在000()0;()0fxfx极小值极大值2 二元函数二元函数 若二元函数若二元函数 点的某个领域内有点的某个领域内有连续二阶偏导

9、数，则在该点存在极值的充连续二阶偏导数，则在该点存在极值的充分必要条件是：分必要条件是：00( , ),)zf x yP x y0在 (000000(,)0(,)0( , )( , )0( , )( , )xyxyxxx xyyyxy yfxyfxyfx yfx yfx yfx y00000000(,)0,)(,)0,)xxxxfxyP xyfxyP xy00时， (为极大点时， (为极小点且3 多元函数多元函数 n元函数元函数 在点在点M处存在极值处存在极值的充分必要条件是：的充分必要条件是：12(X)(,)nff x xx(M)(M)(M)(M)12(X)(X)(X)(X)0000nfff

10、fxxx在点在点M处函数的梯度为零向量：处函数的梯度为零向量：Hessian矩阵为正定或负定：矩阵为正定或负定：2(M)(M)M2(M)2(M)2(M)211212(M)2(M)2(M)221222(M)2(M)2(M)212(X)H(X)H(X)(X)(X)(X)(X)(X)(X)(X)(X)nnnnnffffxx xx xfffx xxx xfffx xx xx MMMHMHMHM为正定时，为极小点；为负定时，为极大点；既非正定也非负定时，为鞍点。且当且当最优化问题求解的数值计算方法最优化问题求解的数值计算方法1 解析法解析法间接寻优方法 利用数学分析的方法利用数学分析的方法, ,根据目标

11、函数的变化规根据目标函数的变化规律与函数极值的关系律与函数极值的关系, ,求目标函数的极值点求目标函数的极值点. . 寻找极值点寻找极值点 需要求解由目标函数的偏导数需要求解由目标函数的偏导数所组成的方程组或梯度所组成的方程组或梯度 。(X)0f然后用然后用Hessian矩阵对所找到的稳定点进行矩阵对所找到的稳定点进行判断，看它是否是最优点。判断，看它是否是最优点。当目标函数比较简单时，求解上述方程组且当目标函数比较简单时，求解上述方程组且用用Hessian矩阵进行判断并不困难。但当目矩阵进行判断并不困难。但当目标函数比较复杂时，就会遇到麻烦，甚至很标函数比较复杂时，就会遇到麻烦，甚至很难求解

12、各项偏导数所组成的方程组，更不用难求解各项偏导数所组成的方程组，更不用说对说对Hessian矩阵进行判断时将遇到的困难。矩阵进行判断时将遇到的困难。p 此外，对目标函数还有连续、可微分等大此外，对目标函数还有连续、可微分等大前提条件前提条件数值计算方法数值计算方法直接寻优方法直接寻优方法 它是根据目标函数的变化规律，以适当的步它是根据目标函数的变化规律，以适当的步长沿着能使目标函数值下降的方向，逐步长沿着能使目标函数值下降的方向，逐步向目标函数值的最优点进行探索，逐步逼向目标函数值的最优点进行探索，逐步逼近到目标函数的最优点。近到目标函数的最优点。 步骤：步骤：(0)X初选一个可能靠近最优点的

13、初始初选一个可能靠近最优点的初始点点 ，从，从 出发按照一定的原则寻找可行方向和出发按照一定的原则寻找可行方向和初始步长，向前跨出一步达到初始步长，向前跨出一步达到 点；点；(0)X(1)X(1)X得到新点得到新点 后再选择一个新的使函数值迅速后再选择一个新的使函数值迅速下降的方向及适当的步长，从下降的方向及适当的步长，从 点出发再点出发再跨出一步，达到跨出一步，达到 点。依此类推，一步一步点。依此类推，一步一步地向前探索并重复数值计算，最终逼近目标地向前探索并重复数值计算，最终逼近目标函数的最优点。函数的最优点。(2)X(1)X 中间过程中每一步的迭代形式为：中间过程中每一步的迭代形式为：

14、式式中：中：(1)( )( )( )(1)( )XXS(X)(X)0,1,2,kkkkkkffk使 - -第第k 步迭代计算所得到的点；步迭代计算所得到的点；( )Xk - -第第k 步迭代计算的步长；步迭代计算的步长；( )k - -第第k 步迭代计算的探索方向。步迭代计算的探索方向。( )Sk以最小以最小值为例值为例每向前跨完一步，都应检查所得到的新点每向前跨完一步，都应检查所得到的新点能否满足预定的计算精度，即能否满足预定的计算精度，即(1)( )(X)- (X)kkff(1)Xk 如满足，则认为如满足，则认为 为局部最小点；为局部最小点；(1)Xk 否则，应以否则，应以 为新的初始点，

15、按上述方法为新的初始点，按上述方法继续跨步探索。继续跨步探索。根本目的在于设根本目的在于设置迭代终止判据置迭代终止判据几点讨论 迭代过程中探索方向迭代过程中探索方向S的选择的选择 保证沿此方向进行探索时，目标函数值是不断下保证沿此方向进行探索时，目标函数值是不断下 降的；降的； 应尽可能地使其指向最优点，以缩短探索的路程应尽可能地使其指向最优点，以缩短探索的路程 和时间，提高求优过程的效率。和时间，提高求优过程的效率。 迭代的收敛性迭代的收敛性否则，迭代是发散的。否则，迭代是发散的。 根据任意一个迭代式进行计算，不一定都能得到逼根据任意一个迭代式进行计算，不一定都能得到逼近精确解的近似解。近精

16、确解的近似解。( ),1,2,kixin( )*lim,(1,2, )kiikxxin如果能够计算出逼近精确解的近似解，即近似解如果能够计算出逼近精确解的近似解，即近似解序列序列 有极限有极限 ，则迭代是收敛的。，则迭代是收敛的。 对于实际工程问题有时很难判断其目标函数对于实际工程问题有时很难判断其目标函数的最小值，而只能根据计算中的具体情况的最小值，而只能根据计算中的具体情况来进行判断。来进行判断。依迭代过程真实逼近最优点所呈现的特征来依迭代过程真实逼近最优点所呈现的特征来构建判据构建判据 判断是否应终止迭代的依据有三种形式判断是否应终止迭代的依据有三种形式 当调整变量在相邻两点之间的移动距

17、离已当调整变量在相邻两点之间的移动距离已 充分小时，可用相邻两点的向量差的模作为充分小时，可用相邻两点的向量差的模作为终止迭代的判据：终止迭代的判据：(1)( )1X-Xkk终止迭代的判断依据终止迭代的判断依据 或用向量或用向量 的所有坐标分量之差表示：的所有坐标分量之差表示：(1)( )X,Xkk(1)( )-,(1,2, )kkiiixxin 当相邻两点目标函数值之差已达充分小时，当相邻两点目标函数值之差已达充分小时，即移动该步后目标函数值的下降量已充分小即移动该步后目标函数值的下降量已充分小时，可用两次迭代的目标函数值之差作为终时，可用两次迭代的目标函数值之差作为终止迭代的判据：止迭代的

18、判据：(1)( )2(X)- (X)kkff 上述上述3种任何一种得到满足，则认为目标函数种任何一种得到满足，则认为目标函数值已收敛于该函数的最优值。值已收敛于该函数的最优值。 当迭代点逼近极值点时，目标函数在该点当迭代点逼近极值点时，目标函数在该点的梯度将变得充分小，故目标函数在迭代点的梯度将变得充分小，故目标函数在迭代点处的梯度达到充分小时，也可作为终止迭代处的梯度达到充分小时，也可作为终止迭代的判据：的判据：(1)3(X)kf？几点讨论 （2种特殊情况种特殊情况） 函数变化剧烈函数变化剧烈 函数变化缓慢函数变化缓慢(1)Xk*X 为了防止当函数变化缓慢时，判据虽已得到满为了防止当函数变化

19、缓慢时，判据虽已得到满足，而所求得的最优点足，而所求得的最优点 与真正最优点与真正最优点 仍仍相距较远，往往将判据、结合起来使用。相距较远，往往将判据、结合起来使用。 (1)(X)kf*(X )f 为了防止当函数变化剧烈时，判据虽已得到满为了防止当函数变化剧烈时，判据虽已得到满足，而所求得的最优值足，而所求得的最优值 与真正最优值与真正最优值 仍相差较大；仍相差较大；无约束最优化方法的特点及应用范围无约束最优化方法的特点及应用范围最优化方法特点及应用范围坐标轮换法(变量轮换法或降维法)不需求导数，方法易懂，程序设计容易，但迭代过程较长，收敛速度较慢，且问题的维数n愈多求解效率愈低，适用于n10

20、的小型无约束最优化问题，当函数的等值线为圆或为长短轴都平行于坐标轴的椭圆时此法很有效。最速下降法(一阶梯度法) 效率高于上法，尤其最初几步迭代函数值下降很快，但愈靠近极值点愈慢。迭代计算简单，占用计算机单元少，对初始点的选择要求低。常与其它方法混用。 牛顿法(Newton-Raphson法或二阶梯度法)当初始点选得合适时是目前算法中收敛得最快的一种(尤其对二次函数)，但当初始点选择不当会影响到能否收敛或导致失败。计算较繁且要求Hessian矩阵是非奇异的。计算量和存贮量都以维数n的平方 (n2)比例增加，故当函数变量较多和因次较高时不宜采用此法。修正牛顿法(广义牛顿法)即使初始点选择不当，此法

21、亦会成功，其它特点与牛顿法相同。共轭梯度法是对最速下降法在收敛速度上的重大改进，其收敛速度比最速下降法大为加快，而计算又比牛顿法大为简化。计算简单，所需的存储量少，收敛速度快，常用于多变量的最优化设计。共轭方向法及其改进Powell法 不需求导数只需计算函数值，适用于中、小型问题的无约束最优化问题。Powell法是一种求无约束最优化问题较为有效的方法，适用于中小型无约束最优化问题，但对于多维问题收敛速度较慢。无约束最优化方法的特点及应用范围无约束最优化方法的特点及应用范围(续表续表)最优化方法特点及应用范围变尺度法(DFP法及BFGS法)为求解无约束极值问题最有效的算法之一，可以用到维数n10

22、0的问题。对于高维的大型问题，(n100)，由于收敛快，效果好，被认为是最好的优化方法之一，但计算A(k)的程序较复杂，且需要较大的存贮量。DFP法也存在数值稳定性不够理想等情况，而BFGS法则有较好的数值稳定性。单纯形法单纯形法不需求导数，只需计算函数值。属直接求优法，这类不需求导数，只需计算函数值。属直接求优法，这类方法甚至适用于未知目标函数的数学表达式而只知道方法甚至适用于未知目标函数的数学表达式而只知道它的具体算法的情况、程序简单、收敛快、效果好，它的具体算法的情况、程序简单、收敛快、效果好，适用于中小型设计问题。适用于中小型设计问题。Hooke-Jeeves法程序简单，当变量较少时比

23、较有效，适应性较强，收敛速度比坐标轮换法有所改善但仍较慢，不适于高维数的问题。Rosenbrock法可看成是对Hooke-Jeeves法的进一步改善与发展，比坐标轮换法显著地提高了迭代效率和解题效能，同样不适用于高维数的问题。Marquardt法集中了最速下降法及牛顿法的优点，且算法简单，接近极小点时收敛得非常快，不需要一维探索。常用于求函数平方和的极小值的问题。最小二乘法(Gauss-Newton法)常用于求函数平方和的极小值问题，且不必计算二阶偏导数矩阵，为线性收敛速度。单纯形法单纯形法基本思想：基本思想： 不需要计算目标函数的导数；不需要计算目标函数的导数； 实际的最优化工程中，目标函数

24、的导数往实际的最优化工程中，目标函数的导数往往很难求出甚至根本无法求出。往很难求出甚至根本无法求出。在在n维空间中由维空间中由n+1+1个线性独立的点构成一个凸个线性独立的点构成一个凸 多面体；多面体；求出这些顶点处的目标函数值并加以比较，确定求出这些顶点处的目标函数值并加以比较，确定它们当中有最大值的点以及函数值的下降方向，它们当中有最大值的点以及函数值的下降方向，再设法找到一个新的比较好的点替换那个最差点，再设法找到一个新的比较好的点替换那个最差点，从而构成新的单纯形；从而构成新的单纯形；随着这种取代过程的不断进行，新的单纯随着这种取代过程的不断进行，新的单纯形将向着极小点收缩。经过一定次

25、数的迭形将向着极小点收缩。经过一定次数的迭代，即可得到满足收敛准则的近似解。代，即可得到满足收敛准则的近似解。 设有一个二维目标函数设有一个二维目标函数 ，在平面中，在平面中 为线性独立（不在同一直线上）的三个为线性独立（不在同一直线上）的三个 点，并以它们为顶点构造单纯形（三角形）。点，并以它们为顶点构造单纯形（三角形）。 计算这三个顶点处的函数值计算这三个顶点处的函数值 并作比并作比 较：若较：若 ，则说明，则说明 点最差，点最差， 最最 好。故应该抛弃好。故应该抛弃 点并形成新的单纯形。点并形成新的单纯形。12(X)( ,)yff x xX ,X ,Xhlg(X )(X )(X )hgl

26、fff(X ),(X ),(X )hglfffXhXlXh算法思路算法思路：（3 3种类型的步骤种类型的步骤反射、扩张和压缩）反射、扩张和压缩） 为此要找出除为此要找出除 以外的所有顶点的形心点以外的所有顶点的形心点 ，并在，并在 和和 连线的延长线上取一点连线的延长线上取一点 ，使，使XhXhXcXcXrXX(XX )(1)rcch最差点的反射点最差点的反射点反射系数，一般取为反射系数，一般取为1.0关于反射点的选取：关于反射点的选取：若反射点的函数值若反射点的函数值 小于最好点的函数值小于最好点的函数值 ，即，即 时，则表明所取的探索时，则表明所取的探索 方向正确，可进一步扩大效果，继续沿

27、方向正确，可进一步扩大效果，继续沿 向向 前进行扩张，在更远处取一点前进行扩张，在更远处取一点 ，并使，并使(X )(X )rlffXX(XX )(2)ecrcXeX Xhr(X )lf(X )rf扩展系数，大小一般在扩展系数，大小一般在1.22.0之间之间图示图示 若若 ，说明扩张有利，就用，说明扩张有利，就用 代替最代替最 差点差点 ，构造新的单纯形，构造新的单纯形 ； 若若 不成立，则不能扩张。此时，如果不成立，则不能扩张。此时，如果 则用反射点则用反射点 替换最差点替换最差点 而形成新的单纯形而形成新的单纯形 。 (X )(X )elffXeXhXhXrX ,X ,Xgle(X )(X

28、 )rlff(X )(X )(3)rgffX ,X ,Xglr若下式成立，即若下式成立，即 则表示则表示 点走得太远，应该缩回一些，需要进点走得太远，应该缩回一些，需要进 行压缩，且得到的压缩点应为：行压缩，且得到的压缩点应为：(X )(X )(X )(4)grhfffXrXX(XX )(5)scrc压缩系数，常取压缩系数，常取0.5图示图示 若若 则用压缩点则用压缩点 代替代替 ，形成新的单纯形，形成新的单纯形(X )(X )(6)shffXsX ,X ,XglsXh若反射点的函数值若反射点的函数值 大于最差点的函数值，大于最差点的函数值， 即即 时，应该压缩得更多些，即将新点压缩至时，应该

29、压缩得更多些，即将新点压缩至 与与 之间，这时所得的压缩点应为：之间，这时所得的压缩点应为：Xh(X )rf(X )(X )(7)rhffXcXX(XX )X(XX )(8)scchchc(X )hf如果在如果在 方向上所有点的函数值方向上所有点的函数值 都大于都大于 ，或式（，或式（6）不成立，则不能沿此方向探索。）不成立，则不能沿此方向探索。 这时应使单纯形向最好点进行收缩，即最好点这时应使单纯形向最好点进行收缩，即最好点 不动，其余各顶点不动，其余各顶点 ， 皆向皆向 移近为原距离的移近为原距离的 一半，由原单纯形一半，由原单纯形 收缩成新单纯形收缩成新单纯形 。X XhcX ,X ,X

30、hgl(X)f(X )hfXlXgXhXlX ,X ,Xhgl 从以上各步得到新的单纯形后，再重新开始从以上各步得到新的单纯形后，再重新开始各步，逐渐缩小单纯形直至满足精度要求为止。各步，逐渐缩小单纯形直至满足精度要求为止。0 x1x2XhXgXlXcXrXeXsXs返回返回返回返回单纯形法的计算步骤单纯形法的计算步骤 设目标函数设目标函数 为为n元函数，即元函数，即X为为n维向量，因此单维向量，因此单纯形应有纯形应有n+1个顶点个顶点 。(X)f121X ,X ,Xn(0)(0)1XXejih一般取值范围为一般取值范围为0.515.0; 构成初试单纯形时构成初试单纯形时,h=1.61.7.

31、构造初始单纯形时，先在构造初始单纯形时，先在n维空间中选取初始点维空间中选取初始点 （尽量靠近最优点），然后从（尽量靠近最优点），然后从 出发沿各坐标轴出发沿各坐标轴方向方向 ，以步长，以步长h找到其余找到其余n个顶点个顶点 ；(0)1X(0)1X(0)X(2,3,1)jjnei0 x1x2XhXgXlXgXh 表示第表示第k轮探索时的最好点轮探索时的最好点, ,即即并令并令: : 为第为第k轮探索的第轮探索的第j顶点顶点, ,其函数值为其函数值为 ; ; 表示第表示第k轮探索时所有顶点中函数值最大的轮探索时所有顶点中函数值最大的 顶点顶点, ,即最差点即最差点: : 为次差点为次差点, ,即

32、即 比比 小小, ,但比其余但比其余 各顶点的函数值各顶点的函数值 都大都大; ; 为除最差点外为除最差点外, ,其余所有顶点的形心其余所有顶点的形心, ,其坐其坐标标 可以按下式计算可以按下式计算: :( )(X)kjf( )Xkj( )Xkh( )Xkg( )(X)kgf( )(X)kjf( )2Xkn( )Xkl( )( )( )( )121(X)max(X),(X),(X)kkkkhnffff1( )( )( )2,11nkkknijihijxxxn( )( )( )( )121(X)min(X),(X),(X)kkkklnffff( )(X)khf1( )( )( )211XXXnk

33、kknjhjn( )( )( )( )322XXXXkkkknnnh式中，式中，i=1,2,n为各坐标方向的序号；为各坐标方向的序号；j为顶点为顶点号，或号，或构成初始单纯形后，即可进行以下步骤构成初始单纯形后，即可进行以下步骤：计算各顶点的函数值并进行比较，找出最好点计算各顶点的函数值并进行比较，找出最好点 ，最差点，最差点 ，次差点，次差点 ，以及除最差点，以及除最差点 以外其余各顶点的形心以外其余各顶点的形心 。求。求 对形心对形心 的反射点：的反射点：( )Xkl( )Xkh( )Xkg( )2Xkn( )2Xkn( )Xkh( )( )( )( )4232XXXXkkkknnnn比较

34、比较 和和 ，如果反射点，如果反射点 比最好点比最好点 还要好，即还要好，即 时，则进行扩张，得时，则进行扩张，得 扩张点为（按式扩张点为（按式（2）：）：( )Xkl( )3Xkn( )3Xkn( )Xkl( )( )3(X)(X)kknlff将反射点将反射点 与次差点与次差点 比较，若比较，若 ，则用，则用 代替最差点代替最差点 ，并转入步骤；，并转入步骤； 若若 ，则用，则用 代替代替 后后 进行压缩进行压缩, ,否则直接进行压缩，得压缩点为否则直接进行压缩，得压缩点为：( )Xkg( )Xkh( )3Xkn( )( )3(X)(X)kkngff( )3Xkn( )( )( )3(X)(

35、X)(X)kkkgnhfff( )3Xkn( )Xkh 得到扩张点得到扩张点 后，如果后，如果 ，则用，则用 代替代替 后转入。后转入。否则用否则用 代替转入。代替转入。( )Xkh( )4Xkn( )( )4(X)(X)kknlff( )4Xkn 若若 ，即反射点比最好点差，则转，即反射点比最好点差，则转 下一步。下一步。( )( )3(X)(X)kknlff( )3Xkn( )( )( )( )522XXXXkkkknnhn( )( )( )( )XX0.5 XX1,2,1kkkkjljljn进行收敛性检验进行收敛性检验. .若若则停止迭代并输出则停止迭代并输出 及及 , ,否则否则 后转

36、后转第步。第步。( )Xklf1kk1122( )( )211XX1nkkjnjffn( )Xkl将压缩点将压缩点 与最差点与最差点 比较，若比较，若 ，则用，则用 代替最差点代替最差点 以后转入下一步以后转入下一步; ;否否 则使单纯形向最好点则使单纯形向最好点 收缩收缩, ,收缩后的单纯形收缩后的单纯形 顶点为顶点为: :( )Xkl( )Xkh( )5Xkn( )( )5(X)(X)kknhff( )5Xkn( )Xkh逐渐缩小单纯形直逐渐缩小单纯形直至至满足精度要求为止。满足精度要求为止。单纯形程序框图单纯形程序框图思考题思考题基于单纯形算法的基本框架，设计其具体的寻优思基于单纯形算法

37、的基本框架，设计其具体的寻优思路（请以程序框图的形式描述）。路（请以程序框图的形式描述）。如何设计单纯形算法的收敛准则？在程序调试过程如何设计单纯形算法的收敛准则？在程序调试过程中，应该如何观察、判定其寻优过程是否已收敛？中，应该如何观察、判定其寻优过程是否已收敛？单纯形算法有哪些控制参数，它们对算法有何种影单纯形算法有哪些控制参数，它们对算法有何种影响？响？复合形法复合形法 复合形法是求解约束非线性最优化问题的一种重复合形法是求解约束非线性最优化问题的一种重 要的直接方法。要的直接方法。 它来源于用于求解约束非线性最优化问题的单纯它来源于用于求解约束非线性最优化问题的单纯形法，实际上是单纯形

38、法在约束问题中的发展。形法，实际上是单纯形法在约束问题中的发展。 初始复合形的产生方法：初始复合形的产生方法：(0)=-jiijiiixarba 设在可行域内先给定复合形的一个初始顶点设在可行域内先给定复合形的一个初始顶点 ，则，则其余其余n个顶点个顶点 由下式确定：由下式确定：(0)1X(0)X(2,3,1)jjn 调整变量调整变量 的解域或上下界；的解域或上下界；其中其中: : 为复合形顶点的标号为复合形顶点的标号 ; ; 为调整变量的标号为调整变量的标号 ； 为为 区间内服从均匀分布的伪随机数。区间内服从均匀分布的伪随机数。2,3,1jnjijir0,1,iia b(0)(0)111,2

39、,qijijxxinq1,2,in1,2,ix in这样产生的顶点虽能满足调整变量的边界约束条这样产生的顶点虽能满足调整变量的边界约束条件，但不一定能满足性能约束条件。假定其中件，但不一定能满足性能约束条件。假定其中 等等q个点个点 满足全部约束条件，满足全部约束条件，而其余点而其余点 不满足，为了使它们也能满不满足，为了使它们也能满足，则可先求出所有满足点的形心点：足，则可先求出所有满足点的形心点： (0)(0)(0)12X,X,Xq(1)qn(0)(0)11X,Xqn(0)(0)(0)(0)11(0)(0)(0)(0)11XXXXXXXXqqnn然后将然后将 这些不满足约束条件的点向形这些

40、不满足约束条件的点向形心点心点 靠拢，得新点：靠拢，得新点：(0)X(0)(0)11X,Xqn(0)1(0)1X01,2,X0uqungumg只要系数只要系数 选择得当（一般取选择得当（一般取 ），总可以使），总可以使新点新点 满足全部约束条件，即满足全部约束条件，即(0)(0)11X,Xqn0.5这样就可求得另外这样就可求得另外n-q+1 个满足全部约束条件个满足全部约束条件的初始顶点。的初始顶点。取得取得n+1个顶点后便可构成一个有个顶点后便可构成一个有n+1顶点的多顶点的多面体面体复合形。然后如下进行迭代计算：复合形。然后如下进行迭代计算：计算复合形各顶点的目标函数值，找出其中的计算复合

41、形各顶点的目标函数值，找出其中的 最差点最差点 ： 找出次差点找出次差点 : : 找出最好点找出最好点 : :XlXgX=maxX1,2,1hjffjnXhX=maxX1,2,1,gjffjnjh但X=minX1,2,1ljffjn计算除最差点计算除最差点 外其它各顶点的形心外其它各顶点的形心 : : 或或 检查检查 点的可行性点的可行性。cXXc11X =XncjjjhnXh11=1,2, ;ncijijxxin jhn如果如果 点在可行域内，则沿点在可行域内，则沿 方向求反射方向求反射 点点: : 式中式中 ，可取，可取 ，若，若 为非可行点，则为非可行点，则 应将应将 值减半，继续计算，

42、直至值减半，继续计算，直至 满足全部满足全部 约束条件为止。约束条件为止。XXchXcX =X +XXrcch11.3XrXr如果如果 点不在可行域内，为了将点不在可行域内，为了将 点移进可行点移进可行 域内，可在以域内，可在以 点和点和 点为界，重新利用伪随点为界，重新利用伪随 机数产生机数产生n+1个新的顶点，构成新的复合形。此个新的顶点，构成新的复合形。此 时变量的上下界改为：时变量的上下界改为： 若若 ，则取，则取 否则相反。重复步骤、，直至否则相反。重复步骤、，直至 点进入可点进入可 行域为止。行域为止。XcXc1,2,iliiciaxinbx1,2,licixxinXcXcXl计算

43、计算 点的目标函数值，如果点的目标函数值，如果 时，时， 则用反射点则用反射点 替换最差点替换最差点 组成新的复合形，组成新的复合形， 完成一次迭代并转入步骤，否则转入步骤。完成一次迭代并转入步骤，否则转入步骤。 XrXXrhffXrXh如果如果 则将则将 值减半，重新计算反射值减半，重新计算反射 点点 ，这时若，这时若 且且 为可行点，则转向为可行点，则转向 步骤；否则应再将步骤；否则应再将 值减半，如此反复。如果值减半，如此反复。如果 经过若干次减半经过若干次减半 值的计算并使值的计算并使 值已缩小到给值已缩小到给 定的一个很小的正数定的一个很小的正数 （例如（例如 ）以下仍无）以下仍无

44、效，则可使复合形向最好点效，则可使复合形向最好点 收缩，还可在收缩，还可在 三点所决定的平面中，将三点所决定的平面中，将 点绕点绕 点旋转某一角度点旋转某一角度 ，并向最好点，并向最好点 靠拢，得靠拢，得 到新的到新的 点后构成新的复合形并转入步骤，重点后构成新的复合形并转入步骤，重 新进行迭代计算，直到满足计算精度为止。新进行迭代计算，直到满足计算精度为止。 XrXrXXrhffXXrhff( )Xkh05010( )Xkl( )( )( )X,X,Xkkkhcl( )Xkl( )Xkl( )Xkh若同时满足收敛准则若同时满足收敛准则、时，则停止迭代，并时，则停止迭代，并 取复合形的最小函数

45、值的顶点作为最优解。取复合形的最小函数值的顶点作为最优解。复合形程序复合形程序框图框图复合形程序框图复合形程序框图思考题思考题基于复合形算法的基本框架，设计其具体的寻优思基于复合形算法的基本框架，设计其具体的寻优思路（请以程序框图的形式描述）。路（请以程序框图的形式描述）。如何设计复合形算法的收敛准则？在程序调试过程如何设计复合形算法的收敛准则？在程序调试过程中，应该如何观察、判定其寻优过程是否已收敛？中，应该如何观察、判定其寻优过程是否已收敛？复合形算法有哪些控制参数，它们对算法有何种影复合形算法有哪些控制参数，它们对算法有何种影响？响？编程实现编程实现 Generalized Rosen

46、brocks valley Function Generalized Rastrigins Function Schaffers Function122211max( )100 ()(1)2.0482.048niiiiifxxxxx21min( )(10 cos(2)+10)5.125.12niiiifxxxx2221212222120.5min0.5sin,10.010.01 0.001ifxxx xxxx Rosen Brocks valley Function Rastrigins Function Schaffers Function它有无限个局部极大点，只有一个全局最大值点它有无限个

47、局部极大点，只有一个全局最大值点 f(0,0)=1，此，此函数最大值峰周围有一圈脊，它们的取值均为函数最大值峰周围有一圈脊，它们的取值均为0.990283.Schaffers Function-1-0.500.511.522.533.54-3-2.5-2-1.5-1-0.500.51寻优过程中复合寻优过程中复合形的演变轨迹形的演变轨迹Rosen brocks valley Function寻优过程中一些重要信息的显示寻优过程中一些重要信息的显示多目标函数的最优化方法前面介绍的最优化方法，可直接用于前面介绍的最优化方法，可直接用于仅含一个目标函数的所谓仅含一个目标函数的所谓“单目标函单目标函数的

48、最优化问题数的最优化问题”。但在许多实际工程问题中，常常期望但在许多实际工程问题中，常常期望同时有几项指标同时有几项指标整体整体达到最优值，这达到最优值，这就是所谓就是所谓“多目标函数的最优化问多目标函数的最优化问题题”，其数学模型的一般表达式为，其数学模型的一般表达式为:各个分目标各个分目标f1(X)，f2(X)，fn(X)的优化的优化往往是互相矛盾的，即不能期望同时实现它往往是互相矛盾的，即不能期望同时实现它们的最优解；们的最优解；甚至有时还会产生完全对立的情况，即对一甚至有时还会产生完全对立的情况，即对一个目标函数是最优点，对另一目标函数却是个目标函数是最优点，对另一目标函数却是最劣点。

49、最劣点。这就需要在各个分目标的最优解之间进行协这就需要在各个分目标的最优解之间进行协调，相互间作出适当调，相互间作出适当“让步让步”，以便取得，以便取得整整体体最优方案。由此也可以看出多目标函数的最优方案。由此也可以看出多目标函数的最优化问题要比单目标函数的最优化问题复最优化问题要比单目标函数的最优化问题复杂得多，求解难度也更大。杂得多，求解难度也更大。统一目标法统一目标法的实质就是将控制方程中的各个统一目标法的实质就是将控制方程中的各个目标函数目标函数( (或称分目标函数或称分目标函数) ) f1(X)，f2(X)，fn(X) 统一到一个总的统一到一个总的“统一目标函数统一目标函数” f(X

50、)中，即令中，即令从而把多目标函数的最优化问题转变为单目从而把多目标函数的最优化问题转变为单目标函数的最优化问题。标函数的最优化问题。 12(X)(X),(X),(X)qfffff 在极小化在极小化“统一目标函数统一目标函数”f(X) 的过程中，为的过程中，为了使各个分目标函数能均匀一致地趋向各自的了使各个分目标函数能均匀一致地趋向各自的最优值，可采用如下的一些方法：最优值，可采用如下的一些方法：加权组合法加权组合法目标规划法目标规划法功效系数法功效系数法(1)乘除法乘除法加权组合法又称线性组合法或加权因子法，即在将各个又称线性组合法或加权因子法，即在将各个分目标函数组合为总的分目标函数组合为

51、总的“统一目标函数统一目标函数”的的过程中，引入加权因子，以考虑各个分目标过程中，引入加权因子，以考虑各个分目标函数在相对重要程度方面的差异以及在量级函数在相对重要程度方面的差异以及在量级和量纲上的差异。如和量纲上的差异。如1(X)(X)qiiifw f 第第i项分目标函数项分目标函数fi(X)的加权因子，的加权因子，是一个大于零的数。是一个大于零的数。在将各个分目标函数加权组合成总的统一目标在将各个分目标函数加权组合成总的统一目标函数的过程中，加权组合法又分为函数的过程中，加权组合法又分为: : 直接加权法直接加权法(X)(1,2, )iiifiq 采用直接加权法来建立总的统一目标函数时，采

52、用直接加权法来建立总的统一目标函数时，其加权因子其加权因子wi的选取方法如下：的选取方法如下： 若已知某分目标函数若已知某分目标函数fi(X)的变动范围为的变动范围为直接加权法直接加权法; ; 转化设计指标法。转化设计指标法。则称则称为该指标的的容限，于是可取该项指标的加为该指标的的容限，于是可取该项指标的加权因子为权因子为(X)0.5()(1,2, )iiifiq 21/(X)(1,2, )iiwfiq这种取法是基于要求在统一目标函数中的各项这种取法是基于要求在统一目标函数中的各项指标指标(分目标函数分目标函数)趋于在数量级上达到统一平趋于在数量级上达到统一平衡。因此，当某项指标的数值变化范

53、围愈宽时，衡。因此，当某项指标的数值变化范围愈宽时，其目标的容限就愈大，加权因子就取较小值；其目标的容限就愈大，加权因子就取较小值；而数值变化范围愈窄时，目标的容限就愈小，而数值变化范围愈窄时，目标的容限就愈小，加权因子就取大值，以达到平衡各分目标函数加权因子就取大值，以达到平衡各分目标函数量级的作用。量级的作用。直接加权方法应该把加权因子分为两部分，即直接加权方法应该把加权因子分为两部分，即第第i项设计指标的加权因子项设计指标的加权因子wi为为式中式中 wi1反映第反映第i项目标项目标( (设计指标设计指标) )相对重要性的加相对重要性的加 权因子，称作本征权因子；权因子，称作本征权因子；

54、wi2第第i项目标的校正权因子，用于调整各目标项目标的校正权因子，用于调整各目标 间在量级差别方面的影响、并在迭代过程间在量级差别方面的影响、并在迭代过程 中逐步加以校正的加权因子。中逐步加以校正的加权因子。12(1,2, )iiiwwwiq 若用梯度若用梯度 来反映各个分目标函数来反映各个分目标函数fi(X)随随设计变量变化而有不同函数值的情况，设计变量变化而有不同函数值的情况，则其校正权因子可取则其校正权因子可取即：即： fi(X)的函数值变化愈快，加权值愈应取的函数值变化愈快，加权值愈应取小些；反之则应取大些。这样就可使变小些；反之则应取大些。这样就可使变化快慢不等的目标一起调整好。化快

55、慢不等的目标一起调整好。(X)if 221/(X)(1,2, )iiwfiq 转化设计指标法先将各项设计指标都转化为统一的无量纲值，先将各项设计指标都转化为统一的无量纲值，并且将量级也限于某一规定范围之内，使目并且将量级也限于某一规定范围之内，使目标规格化，然后再根据各个目标标规格化，然后再根据各个目标( (设计指标设计指标) )的重要性用加权因子来组合的重要性用加权因子来组合“统一目标函统一目标函数数”。(X)(1,2, )iiifiq 例如，若能预计各项设计指标的变动范围，即已知例如，若能预计各项设计指标的变动范围，即已知则可用右图所示的正弦函则可用右图所示的正弦函数将各项设计指标数将各项

56、设计指标( (分目标分目标函数函数) )都转换到在都转换到在01的范的范围内取值，使各目标规格围内取值，使各目标规格化。当然也可以用其它合化。当然也可以用其它合适的函数作为转换函数。适的函数作为转换函数。(X)2(1,2, )iiiiifxiq 转换函数中自变量的上下界应与原设计指转换函数中自变量的上下界应与原设计指标的上下界相对应。即标的上下界相对应。即0与与2应分别对应于应分别对应于i及及i，则相应于，则相应于fi(X)值转换函数的自变量值转换函数的自变量值为值为令设计指标令设计指标fi(X)在转化后为在转化后为fiT(X) ，则，则 因此，因此，“统一目标函数统一目标函数”为为 式中的加

57、权因子式中的加权因子wi (i=1,2,q)，是根据该是根据该项项( (第第i项项) )设计指标在最优化设计中所占的设计指标在最优化设计中所占的 重要程度来确定。重要程度来确定。(X)sin(1,2, )2iiTixfxiq 1(X)(X)qiiTifw f 通过上述换算，可使各项设计指标都转化通过上述换算，可使各项设计指标都转化为无量纲且等量级的一个数。为无量纲且等量级的一个数。(2)目标规划法先分别求出各个分目标函数的最优值先分别求出各个分目标函数的最优值fi(X*)，然后根据多目标函数最优化设计的总体要求，然后根据多目标函数最优化设计的总体要求，作适当调整，制定出理想的最优值作适当调整，

58、制定出理想的最优值fi(o) 。则统。则统一目标函数可按如下的平方和法来构成：一目标函数可按如下的平方和法来构成：2(o)(o)1(X)(X)qiiiiffff 这意味着当各项分目标函数分别达到各自的理这意味着当各项分目标函数分别达到各自的理想最优值时，统一目标函数想最优值时，统一目标函数 f(X) 为最小。此为最小。此法的关键在于选择恰当的法的关键在于选择恰当的fi(o) (i=1,2,q)值。值。(3)功效系数法如果每个分目标函数如果每个分目标函数fi(X) 都用一个称为功效系都用一个称为功效系数数i (i=1,2,q)并定义于并定义于0i1间的函数来表间的函数来表示该项设计指标的好坏示该

59、项设计指标的好坏(当当i=1时表示最好，时表示最好，i=0时表示最坏时表示最坏)，那么被称作总功效系数，那么被称作总功效系数的的这些系数这些系数(1,2,q)的几何平均值的几何平均值12qq 12maxqq 即表示该设计方案的好坏。因此，最优设计方即表示该设计方案的好坏。因此，最优设计方案应是案应是这样，当这样，当=1时，表示取得最理想的设计方案；时，表示取得最理想的设计方案；反之，当反之，当= 0时则表明这种设计方案不能接时则表明这种设计方案不能接受，这时必有某项分目标函数的功效系数受，这时必有某项分目标函数的功效系数i= 0 。fi(X)ii01.0ifi(X)ii01.0ii1.0fi(

60、X)i0i功效系数的函数曲线功效系数的函数曲线用总功效系数用总功效系数作为作为“统一目标函数统一目标函数” f(X) ：12(X)maxqqf 这样，虽然计算稍繁，但方法较为有效。因这样，虽然计算稍繁，但方法较为有效。因为它比较直观且调整容易；其次是不论各个为它比较直观且调整容易；其次是不论各个分目标的量级及量纲如何，最终都转化为分目标的量级及量纲如何，最终都转化为01间的数值，而且一旦有一项分目标函数值不间的数值，而且一旦有一项分目标函数值不理想理想(i= 0 )时，其总功效系数时，其总功效系数必为零，表明必为零，表明设计方案不可接受，需重新调整约束条件或设计方案不可接受，需重新调整约束条件