机械优化设计第六章约束优化方法.ppt

,第六章约束优化方法,一、概述二、随机方向法三、复合形法四、惩罚函数法,一、概述,1、数学模型,求解上式的方法称为约束优化方法,2、求解方法,（1）直接解法：将迭代点限制在可行域内（可行性），步步降低目标函数值（下降性），直至到达最优点。如随机方向法、复合形法、可行方向法、广义简约梯度法。,根据求解方式不同，约束优化设计问题可分为直接解法和间接解法。,（2）间接解法：通过变换，将约束优化问题转化为无约束优化问题求解。如惩罚函数法、增广乘子法等。,（1）直接解法,适用于仅含不等式约束的问题，基本思路是：,在不等式确定的可行域内选择一个初始点，然后决定可行搜索方向，且以适当的步长进行搜索，得到一个使目标函数值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上述搜索过程，满足收敛条件后，迭代终止。,-步长,-可行搜索方向,可行搜索方向：当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域。,直接解法的搜索路线,迭代计算无论何时终止，都可获得一个比初始点好的设计点；若目标函数是凸函数，可行域是凸集，则可保证获得全域最优解。否则，将由于所选择的初始点的不同，而探测到不同的局部最优解上，在这种情况下，探索结果经常与初始点的选择有关系，为了能得到全局最优解，在探索过程中最好能改变初始点，或选择几个差别较大的初始点分别计算，以便从多个局部最优解中 选择更好的最优解；要求可行域为有界的非空集，即在有界可行域内存在满足全部约束条件的点，且目标函数有定义。,2）直接解法的特点,a)可行域是凸集；b)可行域是非凸集,（2）间接解法,1)基本思路 将约束优化问题中的约束函数进行特殊的加权处理后，和目标函数结合起来，构成新的目标函数，即将原约束优化问题转化成一个或一系列的无约束优化问题。再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束问题的最优解。,新目标函数,加权因子,2)间接解法的特点计算效率和数值计算的稳定性有较大提高；可以有效地处理具有约束等式约束的约束优化问题；选择加权因子困难，如果选择不当，不但影响收敛速度和计算精度，甚至会导致计算失败。,由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。,二、随机方向法,基本思路：在可行域内选择一个初始点，利用随机数的概率特性，产生若干个随机方向，并从中选择一个能使目标函数值下降最快的随机方向作为可行搜索方向。从初始点 出发，沿搜索方向 以一定的步长进行搜索，得到新点，新点应该满足一定的条件（约束条件即在可行域内，且保证目标函数值的下降性），至此完成第一次迭代。然后将起始点移至，重复以上过程，经过若干次迭代计算后，最终取得约束最优解。,1）在可行域内选择一个初始点；2）沿该点周围不同的方向进行若干次搜索，计算各方向上等距离点的函数值，找出其中最小值 及点；3）如果 则以两点连线方向作为搜索方向以适当的步长向前搜索，得到新点。若，则将新的起点移至，重复前面过程；否则应缩短步长，直至取得较好点。4）如此循环下去，当满足计算精度，则可结束迭代计算,1随机数的产生,首先令,取,然后按以下步骤计算：,令,若,，则,若,则,若,则,则,即为 区间内的伪随机数。,利用,容易求得任意区间,内的伪随机数，,其计算公式为,2初始点的选择,（1）输入设计变量的下限值和上限值，即,（2）在区间,内产生,个伪随机数,（3）计算随机点,的各分量,（4）判别随机点,是否可行，若随机点,可行，,则取初始点,；若随机点,为非可行点，,则转步骤（2）重新计算，直到产生的随机点是可行点为止。,3可行搜索方向的产生,（1）在,区间内产生伪随机数,，并计算随机单位向量。,（2）取一维试验步长,，按下式计算,个随机点,则可行搜索方向为,（3）检验 个随机点是否为可行点，除去非可行点，计算余下可行点的目标函数值，比较大小，选出目标函数值最小的点；,（4）比较两点 和 的函数值，当点 满足,产生可行搜索方向的条件,4搜索步长的确定,所用的步长一般按加速步长法来确定。所谓加速步长法是指依次迭代的步长按一定的比例递增的方法。各次迭代的步长按下式计算：,5随机方法的计算步骤,（1）选择一个可行的初始点,（2）产生,个,维随机单位向量,（3）取试验步长,，计算出,个随机点,加速步长系数,（4）找出满足条件的随机点,产生可行搜索方向,（5）从初始点 出发，沿可行搜索方向以加速步长,进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点。,（6）若收敛条件,得到满足，迭代终止。约束最优解为,否则，,转步骤（2）。,随机方向法的特点,对目标函数的性态无特殊要求，程序设计简单，使用方便；由于可行搜索方向的选择能保证目标函数下降最快，加之步长可以灵活变动，使得算法的收敛速度较快；初始点的选择对于收敛迭代次数影响较大。,对于求解小型的机械优化问题，随机方向法是一种比较有效的算法。,三、复合形法,基本思路：在可行域内构造一个具有 个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，找到目标函数值最大的顶点（称最坏点），然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状每改变一次，就向最优点移动一步，直至逼近最优点。,1初始复合形的形成,（1）由设计者决定 个可行点，构成初始复合形。,适用于设计变量少，约束条件简单的情况。,（2）由设计者选定一个可行点，其余的,个可行点用随机法产生。各顶点按下式计算：,式中：,复合形中的第j个顶点。,设计变量的上限和下限；,在,区间内的伪随机数。,随机点不一定在可行域内，可采用的方法是：,求出已知在可行域内的,个顶点的中心,将非可行点向中心移动，即,若 仍是不可行点，则继续移动，直到成为可行点为止。,这种方法可保证移动后的点一定会在可行域内，且不会与原来的可行点重合。,完全适用于可行域是凸集的情况，如为非凸集，中心点可能不在可行域内，可以通过改变设计变量的上限和下限值，重新产生各顶点来解决。经过多次计算，有可能在可行域内生成初始复合形。,（3）由计算机自动生成初始复合形的全部顶点。首先随机产生一个可行点，然后按第二种方法生成其余的可行点。,2、复合形法的搜索方法,（1）反射,1）计算复合形各顶点的目标函数值，并比较其大小，求出最好点,和最坏点,及次坏点,2）计算除去最坏点外的,个顶点的中心,3）以点 为中心，将最坏点,按一定比例进行反射，找到一个函数值小的新点（一般可以认为最坏点与中心点的连线方向可能为目标函数下降的方向）,4）判别反射点 的位置:,若 为可行点，则比较 和 点的目标函数值，如果，则用 取代，构成新的复合形，完成一次迭代；如果，则将 缩小0.7倍重新计算新的反射点，若仍不可行，继续缩小直至 为止；若为 不可行点，可缩小反射系数直至为可行点，并按上述方法确定合适的新点。,反射成功的条件：,（2）扩张,当求得的反射点为可行点，且目标函数值下降较多，则沿反射方向继续移动，即采用扩张的方法，可能找到更好的新点,若扩张点为可行点，且,则扩张,成功，构成新的复合形。否则，放弃扩张，仍用原反射点构成新的复合形。,XR,XE,（3）收缩,在中心点以外找不到好的反射点，可以在中心点以内，即采用收缩的方法寻找较好的新点，其计算公式为：,则收缩成功，用收缩点构成新的复合形。,（4）压缩 若采用上述方法均无效，可采取复合形各顶点向最好点 靠拢，即采用压缩的方法来改变复合形的形状。压缩后的各顶点的计算公式为：,然后再对压缩后的复合形采用反射、扩张或收缩等方法，继续改变复合形的形状。,3、复合形法的计算步骤（只含反射）,（1）选择复合形的顶点数，在可行域内构造初始复合形。,（2）计算复合形各顶点的目标函数值，比较其大小，找出最好点，最坏点和次坏点。,（3）计算除去最坏点以外的各顶点的中心，判别中心是否可行，若行转步骤（4）；若不可行，则重新确定设计变量,的下限和上限值，令,，然后由转步骤（1），,重新构造初始复合形。,（4）计算反射点，必要时改变反射系数的值，直至反射,成功。然后，构成新的复合形。,（5）若收敛条件,得到满足，计算终值，约束最优解为,，否则转步骤（2）。,四、惩罚函数法,1、基本思想,通过构造惩罚函数把约束优化问题转化为一些列无约束优化问题，进而用无约束最优化方法求解。,转化求解的前提：是不能破坏约束问题的约束条件；是使它归结到原约束问题的同一最优解上去。,将约束优化问题,中的不等式和等式约束函数经过加权转化后，和原目标函数结合形成新的目标函数惩罚函数,加权转化项,障碍项,惩罚项,障碍项的作用是当迭代点在可行域内时，在迭代过程中将阻止迭代点越出可行域；,惩罚项的作用是当迭代点在非可行域或不满足等式约束条件时，在迭代过程将迫使迭代点逼近约束边界或等式约束曲面。,惩罚项和障碍项用约束条件构造;到达最优点时,惩罚项和障碍项的值为0;当约束不满足或未到达最优点时,惩罚项和障碍项的值大于0.,构造惩罚函数的基本要求:,求解该新目标函数的无约束极小值，以期得到原问题的约束最优解。为此，按一定的法则改变加权因子 的值，构成一系列无约束优化问题,求得一系列无约束最优解，并不断的逼近原约束优化问题的最优解。因此惩罚函数法又称为序列无约束极小化方法，常称SUMT法，即(Sequential Unconstrained Minimization Technique)。,障碍项和惩罚项必须具有以下极限性质：,从而有,2惩罚函数方法,内点惩罚函数法 外点惩罚函数法 混合惩罚函数法,根据约束形式以及惩罚因子的递推方法的不同，惩罚函数方法可分为：,（1）内点惩罚函数法（内点法）,基本思想：内点法将新目标函数定义于可行域内，这样它的初始点及后面的迭代点序列必定在可行域内，并逐步逼近最优点。,采用内点法只能求解具有不等式约束的优化问题。,转化后的惩罚函数形式为,或,或,障碍项。,对于只具有不等式约束的优化问题,是惩罚因子，它是由大到小，且趋近于0的数列，即,由于内点法的迭代过程在可行域内进行，障碍项的作用是阻止迭代点越出可行域。由障碍项的函数形式可知，当迭代点靠近某一约束边界时，其值趋近0，而障碍项的值陡然增加，并趋近于无穷大，好像在可行域的边界上筑起了一道“高墙”，使迭代点始终不能越出可行域，显然，只有当惩罚因子趋于0时，才能求得在约束边界上的最优解。,惩罚因子的作用：由于内点法只能在可行域内迭代，而最优解很可能在可行域内靠边界处或就在边界上，此时尽管泛函的值很大，但由于惩罚因子是不断递减的正值，经过多次迭代，接近最优解时，惩罚项已是很小的正值。,例:用内点法求问题,约束最优解。,解:用内点法求该问题，首先构造内点惩罚函数：,用解析法求函数的极小值，运用极值条件：,联立求得：,当 时不满足约束条件，应舍去,则无约束极值点为,初始点 的选取,应选择一个离约束边界较远的可行点。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难。计算机自动生成可行初始点的常用方法是利用随机数生成设计点。,惩罚因子初值 的选取,惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。无一般有效方法，对于不同问题，都要经过多次试算，才能决定一个适当的初值。,A取,，根据计算结果再决定增加或减小,的值。,B按经验公式,参考方法：,惩罚因子的缩减系数 的选取,相邻两次迭代的惩罚因子的关系为,为惩罚因子的缩减系数，其为小于1的正数，通常取值范围在 之间。,收敛条件,内点法的计算步骤,选取可行的初始点,，惩罚因子的初始值,，缩减系数,以及收敛精度,。令迭代次数,构造惩罚函数,，选择适当的无约束优化,方法，,求函数,的无约束极值，得,点。,用收敛条件判别迭代是否收敛，若满足收敛条件，迭代终止。约束最优解为,；否则令,，转步骤2。,内点法程序框图,（2）外点惩罚函数法（外点法）,基本思想：与内点法将惩罚函数定义于可行域内不同，外点法是将惩罚函数定义于可行区域的外部。序列迭代点从可行域外部逐渐逼近约束边界上的最优点。,外点法可以用来求解含不等式和等式约束的优化问题。,对于约束优化问题,转化后的外点惩罚函数的形式为,式中：,惩罚因子，它是由小到大，且趋近于,外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面。由惩罚项的形式可知，当迭代点不可行时，惩罚项的值大于0。,递增系数c的选取可按经验公式选取（参见教材）,例:用外点法求解下列有约束优化问题,解:惩罚函数为：,用解析法求函数的极小值，运用极值条件：,注意：应舍去在可行域的点。,则无约束极值点为,当惩罚因子渐增时，由下表可看出收敛情况。,外点法的特点：1初始点可以任选，但应使各函数有定义；2对等式约束和不等式约束均可适用；3仅最优解为可行设计方案；4一般收敛较快；5初始罚因子要选择得当；6惩罚因子为递增，递增率c有c1。,内点法的特点：1初始点必须为严格内点；2不适于具有等式约束的数学模型；3迭代过程中各个点均为可行设计方案；4一般收敛较慢；5初始罚因子要选择得当；6罚因子为递减，递减率c有0c1。,（3）混合惩罚函数法,对于约束优化问题,转化后的混合惩罚函数的形式为：,障碍项，惩罚因子按内点法选取。,惩罚项，惩罚因子为,