机械优化设计第6章约束优化方法课件.ppt

《机械优化设计第6章约束优化方法课件.ppt》由会员分享，可在线阅读，更多相关《机械优化设计第6章约束优化方法课件.ppt（138页珍藏版）》请在三一办公上搜索。

1、机械优化设计,第六章 约束优化方法,6.1 概 述,6.2 随机方向法,6.3 复合形方法,6.4 可行方向法,6.5 惩罚函数法,6.6 增广乘子法,6.11遗传算 法简述,6.10结构优化法简述,6.9 二次规划法,6.8广义简约梯度法,6.7 非线性规划问题的线性化解法线性逼近法,机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为,第一节 概述,第一节 概述,直接解法：随机方向搜索法、复合形法、可行方向法 间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法,一. 有约束问题解法分类：,二. 直接解法的基本思想：,合理选择初始点，确定搜索方向，在可行域中寻优，经过若干次迭

2、代，收敛至最优点。 xk+1= xk+kdkdk: 可行搜索方向。即设计点沿该方向作微量移动时,目标函数值将下 降,且不会超出可行域直接解法通常适用于仅含不等式约束的问题,第一节 概述,特点：由于求解过程在可行域内进行；无论迭代计算何时终止, 都可以获得一个比初始点好的设计点; 若可行域是凸集，目标函数是定义在凸集上的凸函数， 则收敛到全局最优点；否则，结果与初始点有关。,凸可行域,非凸可行域,第一节 概述,原理：将有约束优化问题转化为无约束优化问题来解决。方法：以原目标函数和加权的约束函数共同构成一个新的 目标函数 ( x, r1 ,r2 )，成为无约束优化问题 。通 过不断调整加权因子，产

3、生一系列函数的极小点 序列 x(k)* (r1(k),r2(k) k= 0,1,2 ，逐渐收敛到原目标 函数的约束最优解。,其中：新目标函数：,三. 间接解法的基本思想：,惩罚因子： r1 , r2,第二节 随机方向法,一. 基本思想：,随机产生初始点，随机产生若干个搜索方向dk，并从中选择一个能使目标函数值下降最快的方向作为可行搜索方向进行搜索。确保： 新迭代点在可行域中 目标函数值的下降性。,x(0),x(L),x(1),x*,二.初始点的选择,随机方向法的初始点x0必须是一个可行点，既满足全部 不等式约束条件。,初始点可以通过随机选择的方法产生。,1）输入设计变量的下限值和上限值，即,2

4、）在区间（0，1）内产生n个伪随机数,3）计算随机点x的各分量,4）判别随机点x是否可行，若随机点可行，用x0 x 为初始点；若非可行点，转到步骤2）重新产生随 机点，直到可行为止。,第二节 随机方向法,三.可行搜索方向的产生,从k个随机方向中， 选取一个较好的方向。,2) 取一试验步长a0，按下式计算k个随机点,第二节 随机方向法,3）检验k个随机点是否为可行点，除去非可行点，计算 余下的可行点的目标函数值，比较其大小，选出目标 函数最小的点xL 。,4) 比较xL 和x0两点的目标函数值: 若f(xL) f(x0)，则 取xL 和x0连线方向为可行搜索方向； 若f(xL) f(x0)，则缩

5、小步长0 ，转步骤1）重新计算， 直至f(xL) f(x0)为止。 0 缩小到很小仍然找不到一个xL，使 f(xL) f(x0),则 说明x0是一个局部极小点，更换初始点转步骤1）。,第二节 随机方向法,产生可行搜索方向的条件为：,则可行搜索方向为：,四、搜索步长的确定,步长由加速步长法确定：,为步长加速系数，一般取1.3,第二节 随机方向法,五. 计算步骤 1) 选择一个可行的初始点x0; 2) 产生k个n维随机单位向量e j ( j = 1, 2, , k); 3) 取试验步长0，计算出k个随机点x j ; 4) 在k个随机点中，找出可行的的随机点xL, 产生可行搜索 方向d= xLx0.

6、 5) 从初始点x0出发，沿可行搜索方向d以步长进行迭代计 算，直到搜索到一个满足全部约束条件，且目标函数值 不再下降的新点x。 6) 若收敛条件满足，停止迭代。否则， 令x0 x转步骤2,例6-1 求下列约束优化问题的最优解 解：用随机方向法程序，在计算机上运行， 迭代13次， 求得约束最优解：x* = 0.0027 3.0T, f(x*) = 3,一. 单纯形法：,基本思想：以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，不断地迭代，逐渐逼近最优点。,二维空间中映射法比较单纯形x(1)x(2)x(3)的顶点，f(x(1)f(x(2)f(x(3), x(1)为

7、最坏点，称为x(H)，通过映射得到新点x(R)，x(R)x(S)a(x(S)-x(H) 以x(R)来代替x(H)，组成新的单纯形x(R)x(2)x(3)。其中f(x(R)1；称为映射因子；,X(1)=X(H),X(2),X(3),X(S),X(R)=X(4),X(5),X(6),定义：在n维空间中，由n+1个点组成的图形称单纯形。,X*,除x(H)外，其它顶点的几何中心,第三节 复合形法,二. 复合形法：,定义： 在n维空间中，由 kn+1 个点组成的多面体称为复合形。,基本思想：,以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。,说明：,单纯

8、形是无约束优化方法，复合形用于约束优化的方法。 因为顶点数较多，所以比单纯形更灵活易变。 复合形只能解决不等式约束问题。 因为迭代过程始终在可行域内进行，运行结果可靠。,三. 迭代方法：,1. 映射法：,例：二维空间中，k=4，复合形是四面体 x(1)x(2)x(3)x(4)，计算得： f(x(1)f(x(2)f(x(3)f(x(4),确定最坏点 x(H)= x(4) ，次坏点 x(G)=x(3)，最好点x(L)=x(1)。x(S)为除x(H)以外，各点的几何中心。,映射迭代公式： x(R)=x(S)+(x(S)-x(H)搜 索 方 向：沿x(H)x(S)的方向。步长因子（映射系数）： 1，建

9、议先取1.3。若求得的x(R)在可行域内，且f(x(R)f(x(H)，则以x(R)代替x(H)组成新复合形，再进行下轮迭代。, X(S),X(R),X(H),变形法一 扩张： 若f(x(R) f(x(L)，则扩张失败，以x(R)代替x(H)组成新复合形, X(S),X(R),X(H),X(E),变形法二 收缩： 若在映射法中f(x(R) f (x(H),则以a0.5a重复采用映射法 若直至a10-5仍不成功，考虑采用收缩法 取 若f(x(K) f(x(H),则成功，以x(K)代替x(H)组成新复合形。, X(S),X(R),X(H),X(K),4. 变形法三 压缩： 如采用上述方法均无效，还可

10、以将复合形各顶点向最好点 x(L)靠拢，即采用压缩的方法改变复合形的形状。 取,X(L),四. 初始复合形的形成：,人工选择初始复合形2. 随机产生初始复合形： 先在可行域内确定一个初始顶点； 确定xi的上下界：ai、bi ； 产生区间0,1中的k-1组伪随机数ri(j) ； 产生k-1个顶点，x i(j) = i + ri(j) (bi- ai ) 检查k-1个顶点的可行性，若有q个顶点满足 约束，求q个顶点的几何中心： 以x(q+1) = x(t) + (x(q+1) - x(t) ), a=0.5 将不满足 约束的顶点移向可行域,若可行域是非凸集，可能失败，需减小上、下界再进行。,步骤：

11、 1. 形成初始复合形 2. 计算各顶点的函数值,找到最坏点x(H) 、次坏点x(G)和最好点x(L) 3. 计算除最坏点外，其余顶点的形心: 检查形心是否在可行域内 4. 则可行域为非凸集，取 aiminai (L), ai(S), bimaxai (L), ai(S) 作为上下界；计算x i(j) = i+ri(j)(bi-ai)，重新构成复合形，转 步骤2 5. 计算映射点： x (R) =x (S)+a(x (S)-x (H) 检查是否在可行域内,是，a=1.3,转步骤5否，转步骤4,是，转步骤6否， a=0.5a,重新计算反射点,6. 计算f(x(R)，若 7. 若a : 检查终止准

12、则 若,f(x(R) f(x(H) ，以x(R)代替x(H) 重构复合形后转步骤2f(x(R) f(x(H) ，转步骤7,是，则a=0.5a，转步骤5否，则调用收缩法或压缩法，重构复合形后转步骤2,是，则迭代结束，以此复合形的x(L)为x否，则以重构的复合形转步骤2,六. 方法评价：,计算简单，不必求导，占内存小； 随着维数的增加，效率大大下降； 不能解含等式约束的问题；,建议： 初始取1.3。 n+1 k 2n ，当 n 5 时，k取值接近 2n ； 当 n 5 时，k 取值可小些。,一. 基本思想：,在可行域内选择一个初始点x(0)，确定了一个可行方向和适当的步长后，按照下式进行迭代计算：

13、 x(k+1) =x(k)+ad 通过不断的调整可行方向，使迭代点逐步逼近约束最优点。,第四节 可行方向法,二. 搜索策略：,根据目标函数和约束函数的不同性态，选择不同的搜索策略。, 边界反弹法：第一次搜索为负梯度方向，终止于边 界。以后各次搜索方向均为适用可行方向，以最大 步长从一个边界反弹到另一个边界，直至满足收敛 条件。,x(1),x(2),x(3),x*,x(0),第四节 可行方向法, 最优步长法：第一次搜索为负梯度方向，终止于边 界。第二次搜索沿适用可行方向作一维搜索以最优 步长因子求得最优点。反复以上两步，直至得到最 优点x*。,x(1),x(2),x(3),x*,x(0),第四节

14、 可行方向法,贴边搜索法： 第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。 若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个约束面，经过有限的几步就可以收敛到最优点。,x(1),x(2),x*,x(0),第四节 可行方向法,若约束面是非线性时，从x(k)点沿切线（面）方向d(k) 搜索，会进入非可行域。,容差带：,建立约束面的容差带 +， 从 x(k) 出发，沿d(k)方向搜索到 d(k) 方向与g(x) +=0 的交点x后，再沿适时约束的负梯度方向返回约束面的x(k+1)点。,x(k),x(k+1),g(x),g(x)+ ,x,-g(x),d(k),第四节

15、可行方向法,调整步长因子1 ： x (k+1) =x-a1g(x)将g(x)在x点泰勒展开，取一阶近似式： g(x) g(x)+g(x) T(x-x )进而得到： g(x (k+1) ) g(x)+g(x) T-a1g(x)为了让x (k+1)到达约束面，令g(x (k+1) ) =0得:,第四节 可行方向法,三.可行方向的确定,可行方向应该满足设计点可行及目标函数值下降两个条件 可行条件: gj(xk)T dk 0 j=1,2, J(起作用约束的个数),g(xk),dk,g1(xk),g2(xk),dk,第四节 可行方向法,三.可行方向的确定, 目标函数值下降条件: f(xk)T dk 0,

16、f(xk),dk,第四节 可行方向法,三.可行方向的确定,gj(xk)T dk 0 保证在可行域内f(xk)T dk 0 保证目标函数值下降,可行方向,第四节 可行方向法, 优选方向法,四. 可行方向产生方法,式中：d为求解变量，gj(xk)T 、f(xk)T为定值， 可用线性规划方法求解,第四节 可行方向法, 梯度投影法： 可行方向: 其中:p为投影算子,J-起作用的约束个数,第四节 可行方向法, 取最优步长,五. 步长的确定,若x(k+1)为可行点， a作为本次迭代步长,x(k+1) =x(k)+ad,ad,x(k+1),第四节 可行方向法, 取最大步长aM,五. 步长的确定,ad,aMd

17、,x(k+1),x(k+1) =x(k)+ad,第四节 可行方向法,收敛条件,2）设计点xk满足库恩-塔克条件,1）设计点xk及约束允差 满足,例 用可行方向法求约束优化问题的约束最优解。 Min f(x1, x2) = x12 + 2x22 - 10 x1 - x1x2 - 4x2 +60 s.t. g1(x) = x1 0 g2(x) = x2 0 g3(x) = x1 6 0 g4(x) = x2 8 0 g5(x) = x1 + x2 11 0 解：取初始点x0 = 0 1T，为约束 边界g1(x) = 0上的一点。第一次迭代用优选方向法确定可行方向。首先计算x0点的目标函数f(x0)

18、和约束函数g1(x0)的梯度,为在可行下降扇形区内寻找最优方向，需求解一个以可行方向d=d1 d2T为设计变量的线性规划问题，其数学模型为：,最优方向是d*=0.984 0.179T，它是目标函数等值线（直线束）和约束函数d12+d22=1（半径为1的圆）的切点。第一次迭代的可行方向为d0=d*。,第一次迭代的可行方向为d0=d*。若步长取0=6.098，则 可见第一次迭代点x1 在约束边界g3(x1)=0上。,第二次迭代用梯度投影法来确定可行方向。迭代点x1的目标函数负梯度-f(x1)=0.092 5.818T，不满足方向的可行条件。现将f(x1)投影到约束边界g3(x)=0上， 计算投影算

19、子P本次迭代的可行方向为,显然，d1为沿约束边界g3(x)=0的方向。若取1=2.909，则本次迭代点即为该问题的约束最优点x*则得约束最优解,将有约束的优化问题转化为无约束优化问题来求解。前提：一是不能破坏约束问题的约束条件，二是使它归结到原约束问题的同一最优解上去。,构成一个新的目标函数：,第五节 惩罚函数法,惩罚项,惩罚因子,惩罚函数,从而保证,惩罚项必须具有以下极限性质：,根据惩罚项的不同构成形式，惩罚函数法又可分为内点惩罚函数法、外点惩罚函数法和混合惩罚函数法,第五节 惩罚函数法,一. 内点惩罚函数法,基本思想内点法将新目标函数( x , r ) 构筑在可行域D内，随着惩罚因子r(k

20、)的不断递减，生成一系列新目标函数(xk, r(k)，在可行域内逐步迭代，产生的极值点xk*(r(k)序列从可行域内部趋向原目标函数的约束最优点 x* 。,例：min. f(x)=x s.t. g (x) =1-x 0,X1*,X2*,X*,2. 惩罚函数的形式 ,其中：惩罚（加权）因子 降低系数 c： 0 c 1,当x在可行域内远离约束边界时：,当x由可行城内靠近约束边界时：,障碍项,3. 几个参数的选择,惩罚因子初始值 r(0) 的选择：,过大、过小均不好，建议考虑选择r(0) =1或者：,2. 降低系数 c 的选择：,c 的典型值为0.10.7。,3. 初始点 x (0) 的选择：,要求

21、： 在可行域内； 不要离约束边界太近。,方法： 人工估算，需要校核可行性； 计算机随机产生，也需校核可行性。, 搜索方法：,任意给出一个初始点； 判断其可行性，若违反了S个约束，求出不满足约束中的最大值：,应用优化方法减少违反约束：,以求得的设计点作为新初始点，继续其判断可行性，若仍有不 满足的约束，则重复上述过程，直至初始点可行。, 判断是否收敛：,4. 步骤：, 选取合适的初始点 x(0) ，以及 r(0)、c、计算精度 1、2 ，令 k=0；, 构造惩罚（新目标）函数；, 调用无约束优化方法，求新目标函数的最优解 xk* 和 (xk , r(k) ) ；,若均满足，停止迭代，有约束优化问

22、题的最优点为 x*=xk*；若有一个准则不满足，则令 并转入第 3 步，继续计算。,例：用内点法求下列问题的最优解：,构造惩罚函数,1,1,2,二.外点惩罚函数法,1. 基本原理外点法将新目标函数( x , r ) 构筑在可行域 D 外，随着惩罚因子 r(k) 的不断递增，生成一系列新目标函数 (xk ,r(k)，在可行域外逐步迭代，产生的极值点 xk*(r(k) 序列从可行域外部趋向原目标函数的约束最优点 x* 。,新目标函数：,例：求下述约束优化问题的最优点。 min. f (X) = x x R1 s.t g (X) = 1-x 0,惩罚函数可取为,2) 惩罚因子,1) 当设计点在可行域

23、内时,惩罚项为0, 不惩罚; 当设 计点在可行域外 时, 惩罚项大于0, 有惩罚作用.,外点法可以用来求解含不等式和等式约束的优化问题。,衰减项,3. 几个参数的选择,r (0) 的选择: r (0) 过大，会使惩罚函数的等值线变形或偏心，求极 值困难。r (0) 过小，迭代次数太多。 r (0) 1或者,x(0) 的选择： 基本上可以在可行域内外，任意选择。,递增系数c的选择： 通常选择 5 10，可根据具体题目，进行试算调整。,内点法特点： （1）初始点必须为严格的可行点 （2）不适于具有等式约束的数学模型 （3）迭代过程中各个点均为可行设计方案 （4）一般收敛较慢 （5）初始惩罚因子要选

24、择得当 （6）惩罚因子为递减，递减率c有01,三. 混合惩罚函数法,1. 基本思想,采用内点法和外点法相结合的混合惩罚函数法，以发挥内点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。,2. 惩罚函数的形式,一般既包括障碍项，也包括衰减项。,惩罚函数法优点：原理简单，算法易行，适应范围广，可利用无约束最 优化方法资源。缺点：（1）初始惩罚因子r(0)取值不当可导致惩罚函数变得病态， 使无约束优化计算困难。（2）理论上讲，只有惩罚因子 r (k) 0 （内点法）或 r (k) 趋于无穷 （外点法）时，算法才收敛，因此序 列迭代过程收敛速度慢。增广乘子法 外点惩罚函数拉格朗日函数

25、 计算过程稳定，计算效率超过惩罚函数法,拉格朗日函数,一、 拉格朗日乘子法（升维法）,第六节 增广乘子法,l+n个方程l+n个未知变量,具有相同的最优解X*,例:用拉格朗日乘子法求下列问题的最优解,解 构造拉格朗日函数,令L=0,得到,求解得：,构造拉格朗日函数,构造外点惩罚函数,二.等式约束的增广乘子法,采用拉格朗日乘子法时求解有难度,而罚函数法当迭代点接近边界时函数常有病态, 此法的思路是把两者结合起来。其增广拉格朗日函数为:,等式约束增广乘子法,不论r(k)取何值，增广乘子函数与原函数具有相同的约束极值点X*，与拉格朗日函数有相同的拉格朗日乘子向量。,等式约束增广乘子法,等式约束增广乘子

26、法,增广乘子法中的乘子迭代,等式约束增广乘子法,参数选取,惩罚因子初始值r(0)按照外点法取。,从第二次迭代开始，惩罚因子按下式递增：,惩罚因子递增系数，C=10,判别数，通常取0.25,等式约束增广乘子法计算步骤： 选取设计变量的初始点x0，惩罚因子初值r0，增长系数，判别数，收敛精度，乘子向量p0=0 (p=1,2, l), 迭代次数k=0；构造增广乘子函数M(x,r)，并用无约束方法求 min M(x,r) ，得无约束最优解xk=x*(k,rk)计算校正乘子向量如果 ，迭代终止，约束最优解为x*=xk， *= k+1; 否则转步骤6计算惩罚因子 再令k=k+1，转步骤2,例:用拉格朗日乘

27、子法求下列问题的最优解,解 构造增广乘子函数,确定初始参数： C2, 0=0, r0=0.1 ，,利用解析法求min M(X,r) ，令 M(X,r)0 ，可得最优解：,迭代6次得到最优解,迭代结果如下:,精确解: X*=0.25,0.75, f(X*)=0.125,不等式约束增广乘子法,用于求解不等式约束优化问题。,引入松弛变量Zz1, z2 , , zmT,并且令,则不等式约束优化问题转化为等式优化问题,不等式约束增广乘子法,构造增广乘子函数,由于引入松弛变量Z，使原有的n维极值问题扩充为n+m维问题，计算工作量和求解难度增大，可简化。,不等式约束增广乘子法,同时具有等式和不等式约束的增广

28、乘子法,第七节 非线性规划问题的线性化解法线性逼近法一、序列线性规划法 这个方法的基本思想：在某个近似解处将约束函数和目标函数进行泰勒展开，只保留一次项，从而将非线性规划问题变成线性规划问题。求解此线性规划，并将其最优解作为原来问题新的近似解，再展开成新的线性规划问题，再求解。如此重复下去，一直到相邻两次最优解足够接近时为止。缺点： 序列线性规划法收敛较慢，且最后的近似解不满足非线性约束，有时还会出现不收敛的情况。为了获得较好的收敛性而采用一些改进的方法，如割平面法、小步梯度法等。,第七节 非线性规划问题的线性化解法线性逼近法二、割平面法 割平面法主要用于不等式约束的非线性规划问题。若问题是凸

29、规划问题，则这种方法将收敛于问题的最优解。对于非凸规划问题，某些约束的线性近似可能把原问题可行域切掉一些，可能最优点恰好就在这些被切去的区域里。因为这种方法实际上是用线性近似约束把原问题可行域切掉一部分，所以称为“割平面法”。,第七节 非线性规划问题的线性化解法线性逼近法三、小步梯度法 线性逼近法求解是指按下面的迭代公式对设计点 进行修改，从而获得新的设计点 的方法。当把上式写成而 是一个小数值时，可把此式作为一个约束列入原问题中去求解。当用梯度法求解时，这种方法就是用一个小数值 限制各寻优方向步长的方法，可称为小步梯度法。只有当 是可行解时，此法收敛较快，否则过程收敛较慢。,第七节 非线性规

30、划问题的线性化解法线性逼近法四、非线性规划法对于灯饰和不等式约束的给线性规划问题，有一种解法是把最速下降法（梯度法）和线性规划法结合起来求解。它的解法步骤如下：第一步，当是 不可行点时，用最速下降法把它拉到满足约束集内。此时的函数形式取为：第二步，再用线性规划法。每次线性规划阶段移步后，要进行一次判别，看是否满足此法的使用效果好于前两种方法。,第七节 非线性规划问题的线性化解法线性逼近法四、非线性规划法对于线性规划问题，也可以通过泰勒级数展开的方法把约束取成线性的，目标函数取成二次函数。这种约束为线性而目标函数是二次函数的最优问题。有多种求解二次规划问题的方法，其中一种实际上可以看成是线性规划

31、问题中单纯形法的推广。因此，用这样的处理办法来解决非线性规划问题可以称为二次规划问题的线性规划解法。,第八节 广义简约梯度法广义简约梯度法也称GRG法。它是简约梯度法推广到求解具有非线性约束的优化问题的一种方法。这种方法是目前求解一般非线性优化问题的最有效的算法之一。一、简约梯度法简约梯度法仅用来求解具有线性等式约束的优化问题。算法的基本思想是设法处理约束函数，将原问题转化成仅具有变量边界约束的优化问题，然后求解。,第八节 广义简约梯度法二、广义简约梯度法广义简约梯度法可以用来求解具有非线性等式约束和变量界限约束的优化问题，其数学模型为式中的 为变量的下界和上界值。,第八节 广义简约梯度法三、

32、不等式约束函数的处理和换基问题1.不等式简约梯度法求解的处理方法 用广义简约梯度法求解具有不等式约束函数的优化问题时，需引进新变量，将不等式约束函数转化成等式约束函数，即将该问题转化成与式（6-107）相同的形式，然后按前述方法求解。,第八节 广义简约梯度法三、不等式约束函数的处理和换基问题2.基变量的选择和换基问题按广义简约梯度法原理，首先应将涉及变量分成基变量和非基变量，对于只具有等式函数的问题，应在n设计变量中选择m个变量作为基变量，对于具有不等式约束函数的问题，应在n+l个变量中选择m+l个变量作为基变量（l为松弛变量数），其余的变量为非基变量。为了使基变量的变化尽量少，应选择远离其边

33、界的变量为基变量。同时，为了保证基矩阵非奇异及求逆计算的稳定，要求基矩阵的主元不能太小以及同列中的其他元素与主元之比不能太大。在迭代过程中，若某一基变量等于0，或等于边界值时，应换基变量，即选择一非基变量来代替该基变量。,第九节 二次规划法二次规划法的基本原理是将元问题转化为一系列二次规划的子问题。求解子问题，得到本次迭代的搜索方向，沿搜索方向寻优，最终逼近问题的最优点，因此，这种方法又称为序列二次规划法。另外，算法是利用拟牛顿法（变尺度法）来近似构造海塞矩阵，以建立二次规划子问题，故又可称为约束变尺度法，这种方法被认为是目前最先进的非线性规划计算方法。,第九节 二次规划法二次规划法的迭代步骤

34、如下：1.给定初始值 ，令 （单位矩阵）。2.计算原问题的函数值、梯度值，构造二次规划子问题。3.求解二次规划子问题，确定新的乘子矢量 和搜索方向 。4.沿 进行一维搜索，确定步长，得到新的近似极小点 。5.若满足收敛精度则停止计算，否则转至下步。6.采用拟牛顿公式（如BFGS公式）对进行修正，得到，返回步骤2.,第十节 结构优化简述在工程结构设计中，通常要在保证性能约束条件下，满足结构体积尽量小以减轻重量或节约材料。在进行结构设计时，性能约束一般是取结构固有频率禁区约束、振型约束、结构变形或许用应力约束。以准则法思想为基础的优化准则法，对于结构优化来说，它是一种收敛速度快、求解目标函数和约束

35、函数次数少的一种方法。准则法思想是由“满应力设计”和“同步失效准则”原则，且主要是针对桁架结构的最轻设计发展起来的。,第十节 结构优化简述一、准则方程二、迭代乘子C三、优化准则法和数学规划法的相似性质四、形状优化和拓扑布局优化五、小结,第十节 结构优化简述一、准则方程任何一个设计方案是否是最优的基本检验方法就是看它是否满足K-T条件。优化问题的准则方程是由所讨论的优化问题的最优解应满足K-T条件推导出来的。这时的迭代公式用来寻求满足K-T条件的极小值点（设计点）。,第十节 结构优化简述二、迭代乘子C考虑到结构性能约束函数常是隐含设计变量 的非线性方程，对式（6-127）的准则方程的求解可采用线

36、性迭代的方法。这种求解从某个初始设计变量开始，按迭代公式反复进行线性迭代，直到求出满足准则方的设计变量。这种优化准则就具有数学规划法的性质，是准则思想和数学规划的结合，故称为优化准则法。,第十节 结构优化简述三、优化准则法和数学规划法的相似性质虽然在满应力设计的一类准则设计中，不考虑目标函数值，因而其解不是最优解。这反映了它和数学规划法的不同，这是它的特点。但是，在优化准则法中，由于准则方程是目标函数梯度换和诸约束梯度的线性组合，所以已经失去了原来的满应力类设计与目标函数无关的特点，而具有数学规划法的性质。它实际上已经把准则法和数学规划法结合起来了。,第十节 结构优化简述四、形状优化和拓扑布局

37、优化一种以极大值原理为基础把优化问题表示为泛函极值形式的求解结构形式的理论和方法的应用，实现了从有限维的参数优化向无限维的形状优化和拓扑及布局优化的跨越。这种无限维的优化方法是一种连续型的分析方法，它是基于结构的弹性力学模型和泛函极值的求解方法。连续体的形状和拓扑及布局优化设计需要建立研究对象的几何和分析模型，这既涉及用相应的优化设计变量对边界形状和布局进行有效的描述，也需要处理与有限元分析相关的敏度分析和网络生成等问题。,第十节 结构优化简述五、小结求解非线性规划问题可概括为如下三种迭代格式：1） （搜索格式）2） （替代格式）3） （收敛格式）前两种属于数学规划类方法，后一种属于优化准则方

38、法。,第十节 结构优化简述五、小结总得策略：一是在可行域内直接搜索最优设计点；二是把非线性问题转化为线性问题，采用线性规划方法求解；三是把约束问题转化为无约束问题，采用无约束方法求解。具体方法是：1）直接方法以约束条件为界面，形成一个解的可行域，在可行域范围内直接采用无约束优化方法求解。2）线性逼近法把非线性函数在现行点线性化，采用较成熟的线性规划方法。3）简接方法先把约束问题转化为无约束问题，再采用无约束优化方法求解。这种方法可以分为两类，即降维方法和升维方法。,Powell法、梯度法随机方向法、复合形法、惩罚函数法,常规优化算法,启发式算法(现代优化计算方法),适于求解高非线性、多约束、多

39、极值问题,遗传算法（Genetic algorithms） 神经网络优化算法（Neural networks optimization） 混合优化算法（Hybrid optimization）,第十一节 遗传算法简述,一. 背景：,生物进化基本循环图,依据生物进化论的“适者生存”规律而提出：,第十一节 遗传算法简述,遗传算法的主要生物进化特征体现在：（1）进化发生在解的编码（染色体）上。 （2）自然选择规律决定优秀的染色体产生超过平均数的后代。 遗传算法通过优化目标构造适应函数以达到好的染色 体超过平均数的后代。（3）染色体结合时，双亲的遗传基因结合使得子女保持父母 的特征。（4）当染色体结合

40、后，随机变异会造成子代与父代不同。,第十一节 遗传算法简述,二. 基本思想：,遗传算法在求解优化问题时首先对求解空间的各个解进行编码。在寻优过程中，通过对染色体 进行结合（选择、交配和变异），不断产生新的解，进而根据适应函数在新解中选择部分染色体继续进行结合，直至最终找到最好的解。,第十一节 遗传算法简述,例 用遗传算法求min f (x1,x2)= x1 + x2 ，当x1和x2为整数时 的整数解，且,解：若用4位二进制编码表示一个设计变量 xi，则一个 解(x1, x2)需用8位二进制编码表示：,遗传算法4个组成部分： 编码和解码、适应函数、遗传算子和控制参数,若以这4个个体为群体，按求解

41、的要求，适应函数值小的染色体的生存概率较大，则能竞争上的是N1、 N3和N4点，其交配方式如下：,通过分别交换基因，实现了交配，得到了4个新个体N1、 N2、 N3和N4 。,若对某个个体（例如N2 ）进行基因变异（10），可得N2”: 0 0 1 0 0 0 0 1 (=3),三. 算法的基本步骤：,S.1 选择优化问题求解的一种编码；S.2 随机产生N个染色体的初始群体 pop(k) , k=0 ；S.3 对群体中的每个染色体popi(k)计算适应函数 f i=fitness(popi(k)S.4 若满足终止规则，则转向S.9，否则计算概率S.5 以概率 pi 从 pop (k) 中随机选

42、一些染色体构成一个新群体（其中可以重复选 pop (k) 中的元素） newpop(k+1)= popi(k) , i=1,2,N ,第十一节 遗传算法简述,三. 算法的基本步骤：,S.6 通过交配，按交配概率 pc 得到一个有 N 个染色体的交配群体crosspop (k+1)；S.7 以一个较小的变异概率 pm ，使得一个染色体的基因发生变异，形成变异群体mutpop (k+1) ；S.8 令 k= k+1 和 popi(k) = mutpop (k+1) ，返回S.3；S.9 终止计算，输出最优结果。,第十一节 遗传算法简述,四. 算法实现的几个技术问题 编码和解码,编码由设计空间向编码

43、空间的映射。将设计解用字符串表示的过程。编码的选择是影响算法性能和效率的重要因素。解码由编码空间向设计空间的映射。,第十一节 遗传算法简述,几种常见的编码方式,四. 算法实现的几个技术问题 编码和解码,第十一节 遗传算法简述,对于求极大化的目标函数（max f (x) ），可通过下面转换建立与fitness(x)的映射关系:,四. 算法实现的几个技术问题 适应函数 fitness(x),对于求极小化的目标函数（min f (x) ），可通过下面转换建立与fitness(x)的映射关系:,Cmin和Cmax为可调参数，所取的值应使适应函数fitness(x)恒大于0。,适应函数用于对个体进行评价

44、，即反映个体对环境适应能力。 是优化进程发展的依据。其值必须大于等于零,第十一节 遗传算法简述,群体规模 N 是影响算法性能和效率的因素之一。规模太小，不能提供足够多的采样点；规模太大，计算量大，耗时长。通常取N介于n（编码长度）和2n之间，或依据经验在范围内取值。,四. 算法实现的几个技术问题 算法参数,交配概率 pc 用于控制交配操作的频率，通常取0.40.9之间。概率太大，种群更新过快，会使高适应函数值的个体过快被破坏；概率太小，交配操作很少进行，搜索速度慢，耗时长。,变异概率 pm 加大种群多样性的重要因素，通常取0.0010.1之间。概率太大，则使遗传算法退化成随机搜索算法；概率太小

45、，产生新个体的机会太小。,第十一节 遗传算法简述,复制、交配、变异,四. 算法实现的几个技术问题 遗传算子,复制(选择) 选择用于繁殖后代的双亲。体现“适者生存”，适应 度高，生存概率大。依据选择概率 pi= fi / fi 进行。,交配(交叉) 两个相互配对的染色体（双亲）按某种方式相互交换其 部分基因而生成两个新的个体。,第十一节 遗传算法简述,四. 算法实现的几个技术问题 遗传算子,一点交配（二进制）：,多点交配（二进制）：,第十一节 遗传算法简述,四. 算法实现的几个技术问题 遗传算子,变异 在交配之后进行。将个体染色体编码字符中的某些基因 用其他等位基因替换，从而生成新的染色体。作用

46、：保持群体中个体的多样性，有效地防止算法早熟收敛。方法：按位进行，以概率 pm 改变字符串上某一位基因。,例：变异（二进制）,第十一节 遗传算法简述,四. 算法实现的几个技术问题 算法终止准则,事先规定出一个最大的进化步数，到达此步数时终止(一般取100-500代)。判断当前最好的解已连续若干步没有变化。算法已找到了一个可接受的最好解。,第十一节 遗传算法简述,遗传算法应用举例,例1:利用遗传算法求解区间0,31上的二 次函数y=x2最大时的整数解。,解:(1) 设定种群规模, 编码染色体，产生初始种群。 将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1: s1= 01

47、101, s2= 11000 s3= 01000, s4= 10011 (2) 定义适应度函数: f (x)=x2 (3) 计算各代种群中每个个体的适应度值, 并相应对其染色体进行遗传操作。,首先计算种群S1中各个体的适应度f (si) 。 s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 361,再计算种群S1中

48、各个体的选择概率。,选择概率的计算公式为,由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31,赌轮选择示意,赌轮选择法,在算法中赌轮选择法可用下面的子过程来模拟: 在0, 1区间内产生一个均匀分布的随机 数r。 若rq1,则染色体x1被选中。 若qk-1rqk(2kN), 则染色体xk被选中。其 中的qi称为染色体xi (i=1, 2, , n)的积累概 率, 其计算公式为,选择-复制,设从区间0, 1中产生4个随机数如下: r1 = 0.450126, r2 = 0.

49、110347 r3 = 0.572496, r4 = 0.98503,交配(交叉) 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。 设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）,于是，经复制得新群体： s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19）,变异:变异率pm=0.001。 这样，群体S1中共有 540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做

50、变异。,于是，得到第二代种群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）,第二代种群S2中各染色体的情况,假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体：,s1=11001（25）, s2= 01100（12） s3=11011（27）, s4= 10000（16）,做交配(交叉) 运算，让s1与s2，s3与s4 分别交换后三位基因，得,s1 =11100（28）, s2 = 01001（9） s3 =11000（24）, s4 = 10011（19）,这一轮仍然不会发生变异。,第三代种群S3中各染色