《的加减法》课件

机械优化设计太原科技大学张学良2021/7/231机械优化设计太原科技大学2021/7/231第六章约束优化的直接搜索法数学模型：minf(X

)X∈Rn

s.t.gj(X

)≤0(j=1,2,…,m)

hk(X

)=0(k=1,2,…,p)§6.1

概述根据对约束函数处理方法的不同，约束优化方法可以分为：直接法和间接法。2021/7/232第六章约束优化的直接搜索法数学模型：§6直接法通常适用于仅含不等式约束的优化问题，当有等式约束时，该等式约束函数不能是复杂的隐函数，而且容易实现消元过程。直接法的基本思想在m个不等式约束条件所确定的可行域内，选择一个初始点X(0)，然后决定可行搜索方向S(0)，且以适当的步长

(0)，沿S(0)方向进行搜索，得到一个使目标函数值下降的可行的新点X(1)，即完成一次迭代，再以新点为起点，重复上述搜索过程，满足收敛条件后，迭代终止。2021/7/233直接法通常适用于仅含不等式约束的优化问题，当有等式约束迭代公式为一般公式：X(k+1)=X(k)+

(k)

S(k)(k=0,1,2,…)S(k)为可行搜索方向，

(k)为步长。

可行搜索方向是指：当设计点沿该方向作微量移动时，目标函数值将下降，且不会超出可行域。直接法的特点是：原理简单、方法实用，但计算量大，收敛慢、效率低。适于维数低、精度要求不高但目标函数较复杂的问题。2021/7/234迭代公式为一般公式：可行搜索方向是指：当设计间接法的基本思想将约束优化问题中的约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将约束优化问题转化成为一个或一系列的无约束优化问题，再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束优化问题的最优解。常用的直接法有：网格法、约束随机方向搜索法和复合形法。2021/7/235间接法的基本思想将约束优化问题中的约束§6.2

网格法

网格法的基本思想适于解决如下数学模型：minf(X

)X∈Rn

s.t.gj(X

)≤0(j=1,2,…,m)

ai≤x

i≤bi(i=1,2,…,n)其基本思想是：在设计变量的界限区域内作出网格，逐个计算各个网格点上的约束函数值和目标函数值，然后舍去不满足约束条件的网格点，对满足约束条件的网格点，2021/7/236§6.2网格法网格法的基本思想比较其目标函数值的大小，从中找出目标函数值最小的网格点。若此网格点之间的距离hj均小于给定的控制精度

j(通常取

j=，i=1,2,…,n)

，则该网格点就是所要求的最优点的近似点X*。否则，以该点为中心缩小寻优区间，即在该点附近作较密的网格，继续求目标函数值最小的网格点。如此循环往复，直至找到满足精度要求的最优点的近似点X*。网格的划分可以是等间距的，也可以是非等间距的。2021/7/237比较其目标函数值的大小，从中找出目标函数值最小的网格点。若此计算步骤及算法框图（略）2021/7/238计算步骤及算法框图（略）2021/7/238§6.3约束随机方向搜索法基本思想它是约束优化问题中经常采用的一种直接求解方法。它适于解决如下数学模型：minf(X

)X∈Rn

s.t.gj(X

)≤0(j=1,2,…,m)其基本思想是：在不破坏约束条件的前提下，从选定的初始可行点X(0)出发，相继沿着n个随机产生的搜索方向e(k)(k=1,2,…,n)，2021/7/239§6.3约束随机方向搜索法基本思想以定步长

0搜索得到n个试验点Xk(k=1,2,…,n)，然后计算比较n个试验点处的函数值f(Xk)，找出其中的最小点XL。若f(XL)≥f(X(0))，则缩短步长

0，或重新产生n个随机方向，重复前面的过程。若f(XL)<f(X(0))，则继续沿方向S=XL-X(0)，并令X(0)=XL，以适当步长向前跨步，得到新点X(1)=X(0)+

S。若f(X(1))<f(XL)，则将新的起始点移到X(1)，重复前面的过程进行新一轮搜索。2021/7/2310以定步长0搜索得到n个试验点Xk(k=1,2,若f(X(1))>f(XL)，则应缩短步长

，直至取得一个好的可行点作为新一轮搜索的起始点。如此周而复始，当迭代步长

已经很小时，说明搜索已逼近约束最优点。达到精度要求时，即可终止迭代计算。方法1）决定性方法当问题的约束条件比较简单，可凭判断人为地在可行域内选定一个初始点。确定初始可行点方法2）随机投点方法当问题的约束条件较为复杂时，靠判断选择初始可行点较困难，这时可借助计算机中的随机数发生器，产生随机但可行的初始点。2021/7/2311若f(X(1))>f(XL)，则应设给定设计变量的上下限值为：ai≤xi≤bi(i=1,2,…,n)则产生的随机点的各分量为xi(0)=ai+ri(bi-ai)(i=1,2,…,n)其中，ri为[0，1]区间上的随机数。还需对点X(0)进行可行性检验，即是否满足gj(X(0))≤0(j=1,2,…,m)若满足，X(0)可作为初始点；否则，则应另取随机数重新产生随机点，直到得到一个可行的随机点为止。2021/7/2312设给定设计变量的上下限值为：2021/7/2构造随机搜索方向利用计算机中的随机数发生器，在区间[-1,1]上产生一组随机数方法r1、r2、…、rn(n为变量的维数)，则随机搜索方向为e=[e1

e2…en]T=[r1

r2…rn]T/(∑ri)0.5||e||=1,e是一个单位向量。要产生N个随机搜索方向e(k)(k=1,2,…,N),需要产生N组随机数ri(k)(i=1,2,…,n;k=1,2,…,N)。2021/7/2313构造随机搜索方向利用计算机中的随机数发生器，

0X(0)XLSXLS计算步骤及算法框图（略）2021/7/23140X(0)XLSXLS计算步骤及算法框图（略）202基本思想

§6.4

复合形法它是约束优化问题中经常采用的一种重要的直接求解方法。它适于解决如下数学模型：minf(X

)X∈Rn

s.t.gj(X

)≤0(j=1,2,…,m)ai≤xi≤bi(i=1,2,…,n)其基本思想是：在可行域内构造一个具有K1个顶点的初始复合形（n+1≤K1≤2n），2021/7/2315基本思想§6.4复合形法它是或叫多面体，对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（或称最坏点），然后按一定的法则求出目标函数值有下降的可行的新点，并用此点代替最坏点，构成新的复合形。复合形的形状每改变一次，就向最优点移动一步，直到逼近最优点。初始复合形的形成

复合形法是一种在可行域内搜索最优点的直接解法，要求初始复合形必须在可行域内生成，即初始复合形的K1个顶点都必须是可行点。2021/7/2316或叫多面体，对该复合形各顶点的目标函数值进行比较，去掉目标函构造初始复合形是复合形法的关键内容之一，其方法和步骤如下：1）给定K1值，n+1≤K1≤2n；2）生成初始复合形，有两种方法：①由设计者试选K1个可行点，构成初始复合形。当设计变量较多或约束函数较复杂时，由设计者决定K1个可行点常常很困难。只有在设计变量少，约束函数简单的情况下，才用这种方法。2021/7/2317构造初始复合形是复合形法的关键内容之一，其方②记K=1，由设计者选定一个可行点X1或用随机投点法确定X1，其余的(K1-1)个可行点用随机法产生。各顶点按下式计算：XK=a+rK(b–a)(K=1,2,…,K1)其中，rK—(0，1)区间上的随机数;

a、b—设计变量的上下限；

XK—复合形中的第K个顶点。由上式计算得到的(K1-1)个随机点不一定都在可行域内，因此要设法将不可行点移到可行域内。2021/7/2318②记K=1，由设计者选定一个可行点X1或在随机产生每个随机点时，要检查其可行性，若可行转3）；否则计算前(K-1)个可行点所成复合形的中心（或形心）点XF：XF

=(∑Xj)/(K-1)然后将非可行点XK向中心点XF移动，即

XK

=XF

+0.5(XK-XF)新的XK是由原XK向XF

退缩得到的，再检查是否为可行点，若仍为非可行点，则继续按上式使XK向XF

退缩，直到成为可行点。如果目标函数是凸函数，可行域是凸集，则。2021/7/2319在随机产生每个随机点时，要检查其可行性，若可XF总是可行的，故由XK向XF

退缩，总可以找到可行点XK。若XF

不可行，则可行域必为非凸集。这种情况下为保证初始复合形在可行域内，应缩小随机投点的边界域，重新产生初始复合形的各顶点。3）判断K=K1否，如果K≠K1，则令KK+1并转2）的②，直至产生K1个可行点，构成初始复合形X1X2…XK1。2021/7/2320XF总是可行的，故由XK向XF退缩，总可以找到可行点XK复合形法的计算步骤及算法框图

1）构造初始复合形2）计算并比较复合形各顶点的目标函数值f(XK)，找出最坏点XH、最优点XL、次坏点

XG。f(XH)=max{f(XK)，K=1,2,…,K1}f(XL)=min{f(XK)，K=1,2,…,K1}f(XG)=max{f(XK)，K=1,2,…,K1，K≠H}2021/7/2321复合形法的计算步骤及算法框图1）构造初始复3）检验迭代终止条件，计算复合形K1个顶点的函数值的平均值fm。fm=(∑f(XK))/K1计算容差DF，并判别是否满足DF={∑[f(XK)-fm]2/K1}1/2≤？若满足，迭代计算终止，并输出最优解：X*

=XL，f*

=f(XL);否则，转下一步。2021/7/23223）检验迭代终止条件，计算复合形K1个顶点的函数值的4）计算除去最坏点XH以外的(K1-1)个顶点的中心XC:XC

=(∑Xj)/(K1-1)判别XC是否可行，若XC为可行点，则转5）；若XC为非可行点，则重新确定设计变量的下限和上限值，即令

a=XL，b=XC或a=XC，b=XL然后转1），重新构造初始复合形。5）计算反射点XRXR=XC+

(XC-XH)—反射系数，一般取

=1～1.3。2021/7/23234）计算除去最坏点XH以外的(K1-1)个顶点的中6）检验反射点XR的可行性，若可行，转下一步；若不可行，则令0.5，转5）再求反射点（此时又称退缩点），直至XR可行，再转下一步。7）计算f(XR)，若f(XR)<f(XH)，反射成功，则以反射点XR点替换最坏点XH，构成新的复合形，并比较f(XR)、f(XL)、f(XG