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

机械优化设计机械优化设计第六章约束优化方法×第六章约束优化方法×6.1概述6.2随机方向法

6.3复合形方法

6.4可行方向法

6.5惩罚函数法

6.6增广乘子法

6.11遗传算法简述6.10结构优化法简述

6.9二次规划法

6.8广义简约梯度法

6.7非线性规划问题的线性化解法—线性逼近法6.1概述6.2随机方向法6.3复合形方法6

机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为§第一节

概述机械优化设计中的问题，大多数属于约束优化设计问题，其数学§第一节

概述

直接解法：随机方向搜索法、复合形法、可行方向法

间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法一.有约束问题解法分类：二.直接解法的基本思想：

合理选择初始点，确定搜索方向，在可行域中寻优，经过若干次迭代，收敛至最优点。

xk+1=xk+αkdkdk::

可行搜索方向。即设计点沿该方向作微量移动时,目标函数值将下降,且不会超出可行域直接解法通常适用于仅含不等式约束的问题§第一节概述直接解法：随机方向搜索法、复合形法、可行§第一节

概述特点：①由于求解过程在可行域内进行；无论迭代计算何时终止,都可以获得一个比初始点好的设计点;②若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。凸可行域非凸可行域§第一节概述特点：①由于求解过程在可行域内进行；无论迭§第一节

概述原理：将有约束优化问题转化为无约束优化问题来解决。方法：以原目标函数和加权的约束函数共同构成一个新的

目标函数Φ(x,r1,r2)，成为无约束优化问题。通

过不断调整加权因子，产生一系列Φ函数的极小点

序列x(k)*(r1(k),r2(k))k=0,1,2…，逐渐收敛到原目标

函数的约束最优解。其中：新目标函数：三.间接解法的基本思想：

惩罚因子：r1,r2§第一节概述原理：将有约束优化问题转化为无约束优化问题来§第二节随机方向法一.基本思想：随机产生初始点，随机产生若干个搜索方向dk，并从中选择一个能使目标函数值下降最快的方向作为可行搜索方向进行搜索。确保：①新迭代点在可行域中②目标函数值的下降性。x(0)x(L)x(1)x*§第二节随机方向法一.基本思想：随机产生初始点，随机二.初始点的选择

随机方向法的初始点x0必须是一个可行点，既满足全部

不等式约束条件。初始点可以通过随机选择的方法产生。1）输入设计变量的下限值和上限值，即2）在区间（0，1）内产生n个伪随机数3）计算随机点x的各分量4）判别随机点x是否可行，若随机点可行，用x0←x

为初始点；若非可行点，转到步骤2）重新产生随

机点，直到可行为止。§第二节随机方向法二.初始点的选择随机方向法的初始点x0必须是一个可行点三.可行搜索方向的产生从k个随机方向中，选取一个较好的方向。1）在(-1,1)区间内产生伪随机数，得随机单位向量2)取一试验步长a0，按下式计算k个随机点§第二节随机方向法三.可行搜索方向的产生从k个随机方向中，选取一个较好的方向3）检验k个随机点是否为可行点，除去非可行点，计算余下的可行点的目标函数值，比较其大小，选出目标

函数最小的点xL

。4)比较xL

和x0两点的目标函数值:①若f(xL)<f(x0)，则取xL

和x0连线方向为可行搜索方向；

②若f(xL)≥f(x0)，则缩小步长α0

，转步骤1）重新计算，

直至f(xL)<f(x0)为止。③α0

缩小到很小仍然找不到一个xL，使f(xL)<f(x0),则

说明x0是一个局部极小点，更换初始点转步骤1）。§第二节随机方向法3）检验k个随机点是否为可行点，除去非可行点，计算4)比较产生可行搜索方向的条件为：则可行搜索方向为：四、搜索步长的确定步长由加速步长法确定：τ为步长加速系数，一般取1.3§第二节随机方向法产生可行搜索方向的条件为：则可行搜索方向为：四、搜索步长的确五.计算步骤1)选择一个可行的初始点x0;2)产生k个n维随机单位向量ej(j=1,2,…,k);3)取试验步长0，计算出k个随机点xj;4)在k个随机点中，找出可行的的随机点xL,产生可行搜索方向d=xLx0.5)从初始点x0出发，沿可行搜索方向d以步长进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点x。6)若收敛条件满足，停止迭代。否则，令x0x转步骤2五.计算步骤例6-1求下列约束优化问题的最优解

解：用随机方向法程序，在计算机上运行，迭代13次，求得约束最优解：x*=[0.00273.0]T,f(x*)=3

例6-1求下列约束优化问题的最优解一.单纯形法：基本思想：以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，不断地迭代，逐渐逼近最优点。

二维空间中映射法比较单纯形x(1)x(2)x(3)的顶点，f(x(1))>f(x(2))>f(x(3)),

x(1)为最坏点，称为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))<f(x(H));

a>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维空间中，由k≥n+1个点组成的多面体称为复合形。基本思想：

以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。说明：

单纯形是无约束优化方法，复合形用于约束优化的方法。因为顶点数较多，所以比单纯形更灵活易变。复合形只能解决不等式约束问题。因为迭代过程始终在可行域内进行，运行结果可靠。二.复合形法：定义：基本思想：以一个较好的新点，三.迭代方法：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，建议先取1.3。若求得的x(R)在可行域内，且f(x(R))<f(x(H))，则以x(R)代替x(H)组成新复合形，再进行下轮迭代。●X(S)X(R)X(H)三.迭代方法：1.映射法：例：二维空间中，k变形法一

——扩张：若f(x(R))<f(x(L))，则可沿此方向扩张取若f(x(E))<f(x(L))，则扩张成功，以x(E)代替x(H)组成新复合形若f(x(E))>f(x(L))，则扩张失败，以x(R)代替x(H)组成新复合形●X(S)X(R)X(H)X(E)变形法一——扩张：●X(S)X(R)X(H)变形法二

——收缩：若在映射法中f(x(R))>f(x(H)),则以a＝0.5a重复采用映射法若直至a<10-5仍不成功，考虑采用收缩法

取

若f(x(K))<f(x(H)),则成功，以x(K)代替x(H)组成新复合形。●X(S)X(R)X(H)X(K)变形法二——收缩：●X(S)X(R)X(H)4.变形法三

——压缩：如采用上述方法均无效，还可以将复合形各顶点向最好点

x(L)靠拢，即采用压缩的方法改变复合形的形状。

取

X(L)4.变形法三——压缩：X(L)四.初始复合形的形成：人工选择初始复合形2.随机产生初始复合形：

①先在可行域内确定一个初始顶点；②确定xi的上下界：ai、bi；③产生区间[0,1]中的k-1组伪随机数ri(j)；④产生k-1个顶点，xi(j)=αi+ri(j)

(bi-ai)⑤检查k-1个顶点的可行性，若有q个顶点满足约束，求q个顶点的几何中心：

⑥以x(q+1)=x(t)+α(x(q+1)-x(t)),a=0.5将不满足约束的顶点移向可行域若可行域是非凸集，可能失败，需减小上、下界再进行。四.初始复合形的形成：人工选择初始复合形若可行域是非凸集步骤：

1.形成初始复合形

2.计算各顶点的函数值,找到最坏点x(H)

、次坏点x(G)和最好点x(L)

3.计算除最坏点外，其余顶点的形心:

检查形心是否在可行域内

4.则可行域为非凸集，取ai＝min[ai

(L),

ai(S)],

bi＝max[ai

(L),

ai(S)]作为上下界；计算xi(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,重新计算反射点步骤：是，a=1.3,转步骤5是，转步骤66.计算f(x(R))，若

7.若a>

:

检查终止准则

若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＊否，则以重构的复合形转步骤2f(x(R))<f(x(H))，以x(R)代替x(H)六.方法评价：

计算简单，不必求导，占内存小；随着维数的增加，效率大大下降；不能解含等式约束的问题；建议：①初始α取1.3。②n+1≤k≤2n，当n≤5时，k取值接近2n；当n>5时，k取值可小些。六.方法评价：计算简单，不必求导，占内存小；建议：一.基本思想：在可行域内选择一个初始点x(0)，确定了一个可行方向和适当的步长后，按照下式进行迭代计算：

x(k+1)=x(k)+ad通过不断的调整可行方向，使迭代点逐步逼近约束最优点。§第四节可行方向法一.基本思想：在可行域内选择一个初始点x(0)，确定了一二.搜索策略：

根据目标函数和约束函数的不同性态，选择不同的搜索策略。

①边界反弹法：第一次搜索为负梯度方向，终止于边

界。以后各次搜索方向均为适用可行方向，以最大

步长从一个边界反弹到另一个边界，直至满足收敛

条件。x(1)x(2)x(3)x*x(0)§第四节可行方向法二.搜索策略：根据目标函数和约束函数的不同性态，选择不同

②最优步长法：第一次搜索为负梯度方向，终止于边

界。第二次搜索沿适用可行方向作一维搜索以最优

步长因子求得最优点。反复以上两步，直至得到最

优点x*。x(1)x(2)x(3)x*x(0)§第四节可行方向法②最优步长法：第一次搜索为负梯度方向，终止于边x(1)

③贴边搜索法：第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个约束面，经过有限的几步就可以收敛到最优点。x(1)x(2)x*x(0)§第四节可行方向法③贴边搜索法：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)§第四节可行方向法若约束面是非线性时，从x(k)点沿切线（面）方调整步长因子α1

：

x(k+1)=x’-a1▽g(x’)将g(x)在x’点泰勒展开，取一阶近似式：

g(x)≈g(x’)+[▽g(x’)]T(x-x’)进而得到：

g(x(k+1))≈g(x’)+[▽g(x’)]T[-a1▽g(x’)]为了让x(k+1)到达约束面，令g(x(k+1))=0得:§第四节可行方向法调整步长因子α1：§第四节可行方向法三.可行方向的确定可行方向应该满足设计点可行及目标函数值下降两个条件

①可行条件:

[▽gj(xk)]T

dk≤0

j=1,2,…J(起作用约束的个数)▽g(xk)dk▽g1(xk)▽g2(xk)dk§第四节可行方向法三.可行方向的确定可行方向应该满足设计点可行及目标函数值下降三.可行方向的确定

②目标函数值下降条件:

[▽f(xk)]T

dk<0

▽f(xk)dk§第四节可行方向法三.可行方向的确定▽f(xk)dk§第四节可行方三.可行方向的确定[▽gj(xk)]T

dk≤0

保证在可行域内[▽f(xk)]T

dk<0

保证目标函数值下降

可行方向§第四节可行方向法三.可行方向的确定[▽gj(xk)]Tdk≤0保①优选方向法四.可行方向产生方法式中：d为求解变量，▽gj(xk)]T

、[▽f(xk)]T为定值，可用线性规划方法求解§第四节可行方向法①优选方向法四.可行方向产生方法式中：d为求解变量，▽②梯度投影法：可行方向:

其中:p为投影算子J-起作用的约束个数§第四节可行方向法②梯度投影法：J-起作用的约束个数§第四节可行方向法①取最优步长五.步长的确定若x(k+1)为可行点，a＊作为本次迭代步长

x(k+1)=x(k)+a＊da＊dx(k+1)

§第四节可行方向法①取最优步长五.步长的确定若x(k+1)为可行点，a②取最大步长aM五.步长的确定a＊daMdx(k+1)

x(k+1)=x(k)+a＊d§第四节可行方向法②取最大步长aM五.步长的确定a＊daMdx(k+收敛条件2）设计点xk满足库恩-塔克条件1）设计点xk及约束允差满足收敛条件2）设计点xk满足库恩-塔克条件1）设计点x例用可行方向法求约束优化问题的约束最优解。Minf(x1,x2)=x12+2x22-10x1-x1x2-4x2+60s.t.g1(x)=x10

g2(x)=x20g3(x)=x160g4(x)=x280g5(x)=x1+x2110解：取初始点x0=[01]T，为约束边界g1(x)=0上的一点。第一次迭代用优选方向法确定可行方向。首先计算x0点的目标函数f(x0)和约束函数g1(x0)的梯度例用可行方向法求约束优化问题的约束最优解。为在可行下降扇形区内寻找最优方向，需求解一个以可行方向d=[d1d2]T为设计变量的线性规划问题，其数学模型为：为在可行下降扇形区内寻找最优方向，需求解一个以可行方向d=[最优方向是d*=[0.9840.179]T，它是目标函数等值线（直线束）和约束函数d12+d22=1（半径为1的圆）的切点。第一次迭代的可行方向为d0=d*。最优方向是d*=[0.9840.179]T，它是目标函第一次迭代的可行方向为d0=d*。若步长取0=6.098，则

可见第一次迭代点x1

在约束边界g3(x1)=0上。

第一次迭代的可行方向为d0=d*。若步长取0=6.第二次迭代用梯度投影法来确定可行方向。迭代点x1的目标函数负梯度-f(x1)=[0.0925.818]T，不满足方向的可行条件。现将f(x1)投影到约束边界g3(x)=0上，

计算投影算子P本次迭代的可行方向为第二次迭代用梯度投影法来确定可行方向。迭代点x1的目标函数负显然，d1为沿约束边界g3(x)=0的方向。若取1=2.909，则本次迭代点即为该问题的约束最优点x*则得约束最优解

显然，d1为沿约束边界g3(x)=0的方向。若取1=2.9将有约束的优化问题转化为无约束优化问题来求解。前提：一是不能破坏约束问题的约束条件，二是使它归结到原约束问题的同一最优解上去。

构成一个新的目标函数：§第五节

惩罚函数法惩罚项惩罚因子惩罚函数将有约束的优化问题转化为无约束优化问题来求解。前提：一是不能从而保证惩罚项必须具有以下极限性质：根据惩罚项的不同构成形式，惩罚函数法又可分为内点惩罚函数法、外点惩罚函数法和混合惩罚函数法§第五节

惩罚函数法从而保证惩罚项必须具有以下极限性质：根据惩罚项的不同构成一.内点惩罚函数法基本思想内点法将新目标函数Φ(x,r)构筑在可行域D内，随着惩罚因子r(k)的不断递减，生成一系列新目标函数Φ(xk,

r(k))，在可行域内逐步迭代，产生的极值点xk*(r(k))序列从可行域内部趋向原目标函数的约束最优点x*。例：min.f(x)=x

s.t.g(x)=1-x≤0X1*X2*X*一.内点惩罚函数法基本思想例：min.f(x)=2.惩罚函数的形式

①

②其中：惩罚（加权）因子

降低系数c：0<c<1当x在可行域内远离约束边界时：当x由可行城内靠近约束边界时：障碍项2.惩罚函数的形式其中：惩罚（加权）因子当x在可行域内远离3.几个参数的选择惩罚因子初始值r(0)

的选择：

过大、过小均不好，建议考虑选择r(0)=1或者：2.降低系数c的选择：c的典型值为0.1～0.7。3.初始点x(0)

的选择：要求：①在可行域内；②不要离约束边界太近。方法：①人工估算，需要校核可行性；②计算机随机产生，也需校核可行性。3.几个参数的选择惩罚因子初始值r(0)的选择：过大

③搜索方法：

任意给出一个初始点；判断其可行性，若违反了S个约束，求出不满足约束中的最大值：

应用优化方法减少违反约束：

以求得的设计点作为新初始点，继续其判断可行性，若仍有不满足的约束，则重复上述过程，直至初始点可行。任意给出一个初始点；应用优化方法减少违反④

判断是否收敛：4.步骤：①选取合适的初始点x(0)

，以及r(0)、c、计算精度ε1、ε2

，令k=0；

②

构造惩罚（新目标）函数；③调用无约束优化方法，求新目标函数的最优解xk*和

Φ(xk,r(k))；若均满足，停止迭代，有约束优化问题的最优点为x*=xk*；若有一个准则不满足，则令并转入第3步，继续计算。④判断是否收敛：4.步骤：①选取合适的初始点x(0例：用内点法求下列问题的最优解：构造惩罚函数例：用内点法求下列问题的最优解：构造惩罚函数机械优化设计第6章约束优化方法课件112112二.外点惩罚函数法1.基本原理外点法将新目标函数Φ(x,r)构筑在可行域D外，随着惩罚因子r(k)的不断递增，生成一系列新目标函数Φ(xk,r(k))，在可行域外逐步迭代，产生的极值点xk*(r(k))序列从可行域外部趋向原目标函数的约束最优点x*。新目标函数：例：求下述约束优化问题的最优点。

min.f(X)=x

x∈R1s.tg(X)=1-x≤0二.外点惩罚函数法1.基本原理新目标函数：例：求下述惩罚函数可取为2)惩罚因子1)当设计点在可行域内时,惩罚项为0,不惩罚;当设计点在可行域外

时,惩罚项大于0,有惩罚作用.外点法可以用来求解含不等式和等式约束的优化问题。衰减项惩罚函数可取为2)惩罚因子1)当设计点在可行域内时,惩3.几个参数的选择①r(0)

的选择:r(0)

过大，会使惩罚函数的等值线变形或偏心，求极

值困难。r(0)

过小，迭代次数太多。r(0)

＝1或者②x(0)

的选择：基本上可以在可行域内外，任意选择。③递增系数c的选择：通常选择5～10，可根据具体题目，进行试算调整。3.几个参数的选择①r(0)的选择:②x(0)的选内点法特点：

（1）初始点必须为严格的可行点

（2）不适于具有等式约束的数学模型

（3）迭代过程中各个点均为可行设计方案

（4）一般收敛较慢

（5）初始惩罚因子要选择得当

（6）惩罚因子为递减，递减率c有0<c<1

外点法特点：

（1）初始点可以任选

（2）对等式约束和不等式约束均可适用

（3）仅最优解为可行设计方案

（4）一般收敛较快

（5）初始罚因子要选择得当

（6）罚因子为递增，递增率c有c>1内点法特点： 三.

混合惩罚函数法1.基本思想采用内点法和外点法相结合的混合惩罚函数法，以发挥内点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。2.惩罚函数的形式一般既包括障碍项，也包括衰减项。三.混合惩罚函数法1.基本思想采用内点法和外点法相结合惩罚函数法优点：原理简单，算法易行，适应范围广，可利用无约束最优化方法资源。缺点：（1）初始惩罚因子r(0)取值不当可导致惩罚函数变得病态，

使无约束优化计算困难。（2）理论上讲，只有惩罚因子r

(k)

0（内点法）或

r(k)

趋于无穷（外点法）时，算法才收敛，因此序

列迭代过程收敛速度慢。增广乘子法外点惩罚函数＋拉格朗日函数

计算过程稳定，计算效率超过惩罚函数法惩罚函数法拉格朗日函数一、拉格朗日乘子法（升维法）§第六节

增广乘子法l+n个方程l+n个未知变量具有相同的最优解X*拉格朗日函数一、拉格朗日乘子法（升维法）§第六节增广乘子例:用拉格朗日乘子法求下列问题的最优解解构造拉格朗日函数令▽L=0,得到求解得：例:用拉格朗日乘子法求下列问题的最优解解构造拉格朗日函数令构造拉格朗日函数构造外点惩罚函数构造拉格朗日函数构造外点惩罚函数二.等式约束的增广乘子法

采用拉格朗日乘子法时求解有难度,而罚函数法当迭代点接近边界时函数常有病态,此法的思路是把两者结合起来。其增广拉格朗日函数为:二.等式约束的增广乘子法采用拉格朗日乘子法时求解有难等式约束增广乘子法不论r(k)取何值，增广乘子函数与原函数具有相同的约束极值点X*，与拉格朗日函数有相同的拉格朗日乘子向量。等式约束增广乘子法不论r(k)取何值，增广乘子函数与原函数具等式约束增广乘子法等式约束增广乘子法等式约束增广乘子法增广乘子法中的乘子迭代等式约束增广乘子法增广乘子法中的乘子迭代等式约束增广乘子法参数选取没有其它信息情况下，初始乘子向量

增广乘子函数和外点惩罚函数形式相同；从第二次迭代开始，乘子向量按式子进行校正。惩罚因子初始值r(0)按照外点法取。从第二次迭代开始，惩罚因子按下式递增：惩罚因子递增系数，C=10判别数，通常取0.25等式约束增广乘子法参数选取没有其它信息情况下，初始乘子向量机械优化设计第6章约束优化方法课件等式约束增广乘子法计算步骤：

选取设计变量的初始点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等式约束增广乘子法计算步骤：例:用拉格朗日乘子法求下列问题的最优解解构造增广乘子函数确定初始参数：

C＝2,

λ0=0,

r0=0.1，例:用拉格朗日乘子法求下列问题的最优解解构造增广乘子函数确利用解析法求min

M(X,λ,r)，令▽M(X,λ,r)＝0，可得最优解：

利用解析法求minM(X,λ,r)，令▽M(X,λ,r迭代6次得到最优解,迭代结果如下:精确解:

X*=[0.25,0.75],

f(X*)=0.125迭代6次得到最优解,迭代结果如下:精确解:X*=[0.25不等式约束增广乘子法用于求解不等式约束优化问题。引入松弛变量Z＝[z1,

z2

,

…,

zm]T,并且令则不等式约束优化问题转化为等式优化问题不等式约束增广乘子法用于求解不等式约束优化问题。引入松弛变量不等式约束增广乘子法构造增广乘子函数由于引入松弛变量Z，使原有的n维极值问题扩充为n+m维问题，计算工作量和求解难度增大，可简化。不等式约束增广乘子法构造增广乘子函数由于引入松弛变量Z，使原不等式约束增广乘子法不等式约束增广乘子法同时具有等式和不等式约束的增广乘子法同时具有等式和不等式约束的增广乘子法第七节非线性规划问题的线性化解法——线性逼近法一、序列线性规划法这个方法的基本思想：在某个近似解处将约束函数和目标函数进行泰勒展开，只保留一次项，从而将非线性规划问题变成线性规划问题。求解此线性规划，并将其最优解作为原来问题新的近似解，再展开成新的线性规划问题，再求解。如此重复下去，一直到相邻两次最优解足够接近时为止。缺点：序列线性规划法收敛较慢，且最后的近似解不满足非线性约束，有时还会出现不收敛的情况。为了获得较好的收敛性而采用一些改进的方法，如割平面法、小步梯度法等。第七节非线性规划问题的线性化解法——线性逼近法第七节非线性规划问题的线性化解法——线性逼近法二、割平面法割平面法主要用于不等式约束的非线性规划问题。若问题是凸规划问题，则这种方法将收敛于问题的最优解。对于非凸规划问题，某些约束的线性近似可能把原问题可行域切掉一些，可能最优点恰好就在这些被切去的区域里。因为这种方法实际上是用线性近似约束把原问题可行域切掉一部分，所以称为“割平面法”。第七节非线性规划问题的线性化解法——线性逼近法第七节非线性规划问题的线性化解法——线性逼近法三、小步梯度法线性逼近法求解是指按下面的迭代公式对设计点进行修改，从而获得新的设计点的方法。当把上式写成而是一个小数值时，可把此式作为一个约束列入原问题中去求解。当用梯度法求解时，这种方法就是用一个小数值限制各寻优方向步长的方法，可称为小步梯度法。只有当是可行解时，此法收敛较快，否则过程收敛较慢。第七节非线性规划问题的线性化解法——线性逼近法第七节非线性规划问题的线性化解法——线性逼近法四、非线性规划法对于灯饰和不等式约束的给线性规划问题，有一种解法是把最速下降法（梯度法）和线性规划法结合起来求解。它的解法步骤如下：第一步，当是不可行点时，用最速下降法把它拉到满足约束集内。此时的函数形式取为：第二步，再用线性规划法。每次线性规划阶段移步后，要进行一次判别，看是否满足此法的使用效果好于前两种方法。第七节非线性规划问题的线性化解法——线性逼近法第七节非线性规划问题的线性化解法——线性逼近法四、非线性规划法对于线性规划问题，也可以通过泰勒级数展开的方法把约束取成线性的，目标函数取成二次函数。这种约束为线性而目标函数是二次函数的最优问题。有多种求解二次规划问题的方法，其中一种实际上可以看成是线性规划问题中单纯形法的推广。因此，用这样的处理办法来解决非线性规划问题可以称为二次规划问题的线性规划解法。第七节非线性规划问题的线性化解法——线性逼近法第八节广义简约梯度法广义简约梯度法也称GRG法。它是简约梯度法推广到求解具有非线性约束的优化问题的一种方法。这种方法是目前求解一般非线性优化问题的最有效的算法之一。一、简约梯度法简约梯度法仅用来求解具有线性等式约束的优化问题。算法的基本思想是设法处理约束函数，将原问题转化成仅具有变量边界约束的优化问题，然后求解。第八节广义简约梯度法第八节广义简约梯度法二、广义简约梯度法广义简约梯度法可以用来求解具有非线性等式约束和变量界限约束的优化问题，其数学模型为式中的为变量的下界和上界值。第八节广义简约梯度法第八节广义简约梯度法三、不等式约束函数的处理和换基问题1.不等式简约梯度法求解的处理方法用广义简约梯度法求解具有不等式约束函数的优化问题时，需引进新变量，将不等式约束函数转化成等式约束函数，即将该问题转化成与式（6-107）相同的形式，然后按前述方法求解。第八节广义简约梯度法第八节广义简约梯度法三、不等式约束函数的处理和换基问题2.基变量的选择和换基问题按广义简约梯度法原理，首先应将涉及变量分成基变量和非基变量，对于只具有等式函数的问题，应在n设计变量中选择m个变量作为基变量，对于具有不等式约束函数的问题，应在n+l个变量中选择m+l个变量作为基变量（l为松弛变量数），其余的变量为非基变量。为了使基变量的变化尽量少，应选择远离其边界的变量为基变量。同时，为了保证基矩阵非奇异及求逆计算的稳定，要求基矩阵的主元不能太小以及同列中的其他元素与主元之比不能太大。在迭代过程中，若某一基变量等于0，或等于边界值时，应换基变量，即选择一非基变量来代替该基变量。第八节广义简约梯度法第九节二次规划法二次规划法的基本原理是将元问题转化为一系列二次规划的子问题。求解子问题，得到本次迭代的搜索方向，沿搜索方向寻优，最终逼近问题的最优点，因此，这种方法又称为序列二次规划法。另外，算法是利用拟牛顿法（变尺度法）来近似构造海塞矩阵，以建立二次规划子问题，故又可称为约束变尺度法，这种方法被认为是目前最先进的非线性规划计算方法。第九节二次规划法第九节二次规划法二次规划法的迭代步骤如下：1.给定初始值，令（单位矩阵）。2.计算原问题的函数值、梯度值，构造二次规划子问题。3.求解二次规划子问题，确定新的乘子矢量和搜索方向。4.沿进行一维搜索，确定步长，得到新的近似极小点。5.若满足收敛精度则停止计算，否则转至下步。6.采用拟牛顿公式（如BFGS公式）对进行修正，得到，返回步骤2.第九节二次规划法第十节结构优化简述在工程结构设计中，通常要在保证性能约束条件下，满足结构体积尽量小以减轻重量或节约材料。在进行结构设计时，性能约束一般是取结构固有频率禁区约束、振型约束、结构变形或许用应力约束。以准则法思想为基础的优化准则法，对于结构优化来说，它是一种收敛速度快、求解目标函数和约束函数次数少的一种方法。准则法思想是由“满应力设计”和“同步失效准则”原则，且主要是针对桁架结构的最轻设计发展起来的。第十节结构优化简述第十节结构优化简述一、准则方程二、迭代乘子C三、优化准则法和数学规划法的相似性质四、形状优化和拓扑布局优化五、小结第十节结构优化简述第十节结构优化简述一、准则方程任何一个设计方案是否是最优的基本检验方法就是看它是否满足K-T条件。优化问题的准则方程是由所讨论的优化问题的最优解应满足K-T条件推导出来的。这时的迭代公式用来寻求满足K-T条件的极小值点（设计点）。第十节结构优化简述第十节结构优化简述二、迭代乘子C考虑到结构性能约束函数常是隐含设计变量的非线性方程，对式（6-127）的准则方程的求解可采用线性迭代的方法。这种求解从某个初始设计变量开始，按迭代公式反复进行线性迭代，直到求出满足准则方的设计变量。这种优化准则就具有数学规划法的性质，是准则思想和数学规划的结合，故称为优化准则法。第十节结构优化简述第十节结构优化简述三、优化准则法和数学规划法的相似性质虽然在满应力设计的一类准则设计中，不考虑目标函数值，因而其解不是最优解。这反映了它和数学规划法的不同，这是它的特点。但是，在优化准则法中，由于准则方程是目标函数梯度换和诸约束梯度的线性组合，所以已经失去了原来的满应力类设计与目标函数无关的特点，而具有数学规划法的性质。它实际上已经把准则法和数学规划法结合起来了。第十节结构优化简述第十节结构优化简述四、形状优化和拓扑布局优化一种以极大值原理为基础——把优化问题表示为泛函极值形式的求解结构形式的理论和方法的应用，实现了从有限维的参数优化向无限维的形状优化和拓扑及布局优化的跨越。这种无限维的优化方法是一种连续型的分析方法，它是基于结构的弹性力学模型和泛函极值的求解方法。连续体的形状和拓扑及布局优化设计需要建立研究对象的几何和分析模型，这既涉及用相应的优化设计变量对边界形状和布局进行有效的描述，也需要处理与有限元分析相关的敏度分析和网络生成等问题。第十节结构优化简述第十节结构优化简述五、小结求解非线性规划问题可概括为如下三种迭代格式：1）（搜索格式）2）（替代格式）3）（收敛格式）前两种属于数学规划类方法，后一种属于优化准则方法。第十节结构优化简述第十节结构优化简述五、小结总得策略：一是在可行域内直接搜索最优设计点；二是把非线性问题转化为线性问题，采用线性规划方法求解；三是把约束问题转化为无约束问题，采用无约束方法求解。具体方法是：1）直接方法——以约束条件为界面，形成一个解的可行域，在可行域范围内直接采用无约束优化方法求解。2）线性逼近法——把非线性函数在现行点线性化，采用较成熟的线性规划方法。3）简接方法——先把约束问题转化为无约束问题，再采用无约束优化方法求解。这种方法可以分为两类，即降维方法和升维方法。第十节结构优化简述Powell法、梯度法随机方向法、复合形法、惩罚函数法常规优化算法启发式算法(现代优化计算方法)

适于求解高非线性、多约束、多极值问题遗传算法（Geneticalgorithms）神经网络优化算法（Neuralnetworksoptimization）混合优化算法（Hybridoptimization）§第十一节

遗传算法简述Powell法、梯度法常规优化算法启发式算法(现代优化计算方一.背景：生物进化基本循环图

依据生物进化论的“适者生存”规律而提出：§第十一节

遗传算法简述一.背景：生物进化基本循环图依据生物进化论的

遗传算法的主要生物进化特征体现在：（1）进化发生在解的编码（染色体）上。（2）自然选择规律决定优秀的染色体产生超过平均数的后代。遗传算法通过优化目标构造适应函数以达到好的染色体超过平均数的后代。（3）染色体结合时，双亲的遗传基因结合使得子女保持父母的特征。（4）当染色体结合后，随机变异会造成子代与父代不同。§第十一节

遗传算法简述遗传算法的主要生物进化特征体现在：§第十一节二.基本思想：

遗传算法在求解优化问题时首先对求解空间的各个解进行编码。在寻优过程中，通过对染色体

进行结合（选择、交配和变异），不断产生新的解，进而根据适应函数在新解中选择部分染色体继续进行结合，直至最终找到最好的解。§第十一节

遗传算法简述二.基本思想：遗传算法在求解优化问题时首先对

例用遗传算法求minf(x1,x2)=x1+x2

，当x1和x2为整数时的整数解，且解：若用4位二进制编码表示一个设计变量xi，则一个解(x1,x2)需用8位二进制编码表示：例用遗传算法求minf(x1,x2)=x1遗传算法4个组成部分：编码和解码、适应函数、遗传算子和控制参数若以这4个个体为群体，按求解的要求，适应函数值小的染色体的生存概率较大，则能竞争上的是N1、N3和N4点，其交配方式如下：通过分别交换基因，实现了交配，得到了4个新个体N1’、N2’、N3’和N4’。若对某个个体（例如N2’）进行基因变异（1→0），可得N2”:00100001(=3)遗传算法4个组成部分：若以这4个个体为群体，按求解的要求，适三.算法的基本步骤：S.1选择优化问题求解的一种编码；S.2随机产生N个染色体的初始群体{pop(k),k=0}；S.3对群体中的每个染色体popi(k)计算适应函数

fi=fitness(popi(k))S.4若满足终止规则，则转向S.9，否则计算概率S.5以概率pi从pop

(k)中随机选一些染色体构成一个新群体（其中可以重复选pop

(k)中的元素）

newpop(k+1)={popi(k),i=1,2,···,N}§第十一节

遗传算法简述三.算法的基本步骤：S.1选择优化问题求解的一种编码三.算法的基本步骤：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终止计算，输出最优结果。§第十一节

遗传算法简述三.算法的基本步骤：S.6通过交配，按交配概率pc四.算法实现的几个技术问题——编码和解码编码——由设计空间向编码空间的映射。将设计解用字符串表示的过程。编码的选择是影响算法性能和效率的重要因素。解码——由编码空间向设计空间的映射。§第十一节

遗传算法简述四.算法实现的几个技术问题——编码和解码几种常见的编码方式四.算法实现的几个技术问题——编码和解码

§第十一节

遗传算法简述几种常见的编码方式四.算法实现的几个技术问题——编码对于求极大化的目标函数（max

f(x)），可通过下面转换建立与fitness(x)的映射关系:四.算法实现的几个技术问题——适应函数fitness(x)

对于求极小化的目标函数（min

f(x)），可通过下面转换建立与fitness(x)的映射关系:Cmin和Cmax为可调参数，所取的值应使适应函数fitness(x)恒大于0。适应函数——用于对个体进行评价，即反映个体对环境适应能力。是优化进程发展的依据。其值必须大于等于零§第十一节

遗传算法简述对于求极大化的目标函数（maxf(x)），可通过下面群体规模N——是影响算法性能和效率的因素之一。规模太小，不能提供足够多的采样点；规模太大，计算量大，耗时长。通常取N介于n（编码长度）和2n之间，或依据经验在范围内取值。四.算法实现的几个技术问题——算法参数

交配概率pc

——用于控制交配操作的频率，通常取0.4~0.9之间。概率太大，种群更新过快，会使高适应函数值的个体过快被破坏；概率太小，交配操作很少进行，搜索速度慢，耗时长。变异概率pm

——加大种群多样性的重要因素，通常取0.001~0.1之间。概率太大，则使遗传算法退化成随机搜索算法；概率太小，产生新个体的机会太小。§第十一节

遗传算法简述群体规模N——是影响算法性能和效率的因素之一。四.复制、交配、变异四.算法实现的几个技术问题——遗传算子

复制(选择)

—选择用于繁殖后代的双亲。体现“适者生存”，适应度高，生存概率大。依据选择概率pi=fi/Σfi进行。交配(交叉)

—两个相互配对的染色体（双亲）按某种方式相互交换其部分基因而生成两个新的个体。§第十一节

遗传算法简述复制、交配、变异四.算法实现的几个技术问题——遗传算四.算法实现的几个技术问题——遗传算子

一点交配（二进制）：多点交配（二进制）：§第十一节

遗传算法简述四.算法实现的几个技术问题——遗传算子四.算法实现的几个技术问题——遗传算子

变异

—在交配之后进行。将个体染色体编码字符中的某些基因用其他等位基因替换，从而生成新的染色体。作用：保持群体中个体的多样性，有效地防止算法早熟收敛。方法：按位进行，以概率pm改变字符串上某一位基因。例：变异（二进制）§第十一节

遗传算法简述四.算法实现的几个技术问题——遗传算子四.算法实现的几个技术问题——算法终止准则

事先规定出一个最大的进化步数，到达此步数时终止(一般取100-500代)。判断当前最好的解已连续若干步没有变化。算法已找到了一个可接受的最好解。§第十一节

遗传算法简述四.算法实现的几个技术问题——算法终止准则

遗传算法应用举例

例1:利用遗传算法求解区间［0,31］上的二次函数y=x2最大时的整数解。y=x2

31

xy遗传算法应用举例例1:利用遗传算法求解区间［0,31］上解:

(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=01101,s2=11000s3=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=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361首先计算种群S1中各个体的适应度f(si)再计算种群S1中各个体的选择概率。选择概率的计算公式为

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31再计算种群S1中各个体的选择概率。选择概率的计算公式为由此

赌轮选择示意s40.31s20.49s10.14s30.06

赌轮选择法赌轮选择示意s4s2s1s30.06赌轮选择法

在算法中赌轮选择法可用下面的子过程来模拟:①在［0,1］区间内产生一个均匀分布的随机数r。②若r≤q1,则染色体x1被选中。③

若qk-1<r≤qk(2≤k≤N),则染色体xk被选中。其

中的qi称为染色体xi(i=1,2,…,n)的积累概

率,其计算公式为在算法中赌轮选择法可用下面的子过程来模拟:①在［选择-复制

设从区间［0,1］中产生4个随机数如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

选择-复制设从区间［0,1］中产生4个随机数如交配(交叉)设交叉率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中共有

5×4×0.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。于是，得到第二代种群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）变异:变异率pm=0.001。于是，得到第二代种群S2：

第二代种群S2中各染色体的情况第二代种群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）

这一轮仍然不会发生变异。

假设这一轮选择-复制操作中，种群S2中的s1’=11

第三代种群S3中各染色体的情况于是，得第三代种群S3：

s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第三代种群S3中各染色体的情况于是，得第三代种群S3

设这一轮的选择-复制结果为：

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交配(交叉)运算，让s1’与s4’，s2’与s3’

分别交换后两位基因，得s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

这一轮仍然不会发生变异。设这一轮的选择-复制结果为：做交配(交叉显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。

于是，得第四代种群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）显然，在这一代种群中已经出现了适应度最高的染色体s1=YYy=x2

8131924

X第一代种群y=x2

12162527

XY第二代种群y=x2

9192428

XY第三代种群y=x2

16242831

X第四代种群YYy=x28131924例2:求下列函数的最大值。

maxf(x1,

x2)=100(x12-x22)2+(1-x1)2s.t.-2.048≤xi

≤2.048(i=1,2)该函数有两个局部极大点，分别是:

f(2.048,-2.048)=3897.7342

和

f(-2.048,-2.048)=3905.9262其中后者为全局最大点。例2:求下列函数的最大值。该函数有两个局部极大点，分别解：第一步：确定编码方法。用长度为l0位的二进制(最大可表示1023)表示一个变量。从离散点-2.048到离散点2.048，依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。再将分别表示x1和x2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。例如

X：00001

101111101110001就表示一个个体。解：第二步：确定解码方法。

解码时先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。依据前述个体编码方法相对定义域的离散化方法可知，将代码yi

转换为变量xi的解码公式为：例如，对前述个体

X：0000110111110111000