《机械优化设计ppt课件第六章约束优化的直接搜索法.ppt》由会员分享，可在线阅读，更多相关《机械优化设计ppt课件第六章约束优化的直接搜索法.ppt（27页珍藏版）》请在三一办公上搜索。
1、机械优化设计,太原科技大学张学良,第六章 约束优化的直接搜索法,数学模型：min f(X)X Rn s.t.gj(X)0(j=1,2,m)hk(X)=0(k=1,2,p),6.1 概述,根据对约束函数处理方法的不同，约束优化方法可以分为：直接法和间接法。,直接法通常适用于仅含不等式约束的优化问题，当有等式约束时，该等式约束函数不能是复杂的隐函数，而且容易实现消元过程。,直接法的基本思想,在m个不等式约束条件所确定的可行域内，选择一个初始点X(0)，然后决定可行搜索方向S(0)，且以适当的步长(0)，沿S(0)方向进行搜索，得到一个使目标函数值下降的可行的新点X(1)，即完成一次迭代，再以新点为
2、起点，重复上述搜索过程，满足收敛条件后，迭代终止。,迭代公式为一般公式：X(k+1)=X(k)+(k)S(k)(k=0,1,2,)S(k)为可行搜索方向，(k)为步长。,可行搜索方向是指：当设计点沿该方向作微量移动时，目标函数值将下降，且不会超出可行域。,直接法的特点是：,原理简单、方法实用，但计算量大，收敛慢、效率低。适于维数低、精度要求不高但目标函数较复杂的问题。,间接法的基本思想,将约束优化问题中的约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将约束优化问题转化成为一个或一系列的无约束优化问题，再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束优化问题
3、的最优解。,常用的直接法有：,网格法、约束随机方向搜索法和复合形法。,6.2 网格法,网格法的基本思想,适于解决如下数学模型：min f(X)X Rn s.t.gj(X)0(j=1,2,m)ai x i bi(i=1,2,n),其基本思想是：在设计变量的界限区域内作出网格，逐个计算各个网格点上的约束函数值和目标函数值，然后舍去不满足约束条件的网格点，对满足约束条件的网格点，,比较其目标函数值的大小，从中找出目标函数值最小的网格点。若此网格点之间的距离hj均小于给定的控制精度j(通常取j=，i=1,2,n)，则该网格点就是所要求的最优点的近似点X*。否则，以该点为中心缩小寻优区间，即在该点附近作
4、较密的网格，继续求目标函数值最小的网格点。如此循环往复，直至找到满足精度要求的最优点的近似点X*。网格的划分可以是等间距的，也可以是非等间距的。,计算步骤及算法框图（略）,6.3 约束随机方向搜索法,基本思想,它是约束优化问题中经常采用的一种直接求解方法。它适于解决如下数学模型：min f(X)X Rn s.t.gj(X)0(j=1,2,m),其基本思想是：在不破坏约束条件的前提下，从选定的初始可行点X(0)出发，相继沿着n个随机产生的搜索方向e(k)(k=1,2,n)，,以定步长 0 搜索得到n个试验点Xk(k=1,2,n)，然后计算比较n个试验点处的函数值f(Xk)，找出其中的最小点XL。
5、若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)，重复前面的过程进行新一轮搜索。,若f(X(1)f(XL)，则应缩短步长，直至取得一个好的可行点作为新一轮搜索的起始点。如此周而复始，当迭代步长 已经很小时，说明搜索已逼近约束最优点。达到精度要求时，即可终止迭代计算。,方法1）决定性方法 当问题的约束条件比较简单，可凭判断人为地在可行域内选定一个初始点。,确定初始可行点,方法2）随机
6、投点方法 当问题的约束条件较为复杂时，靠判断选择初始可行点较困难，这时可借助计算机中的随机数发生器，产生随机但可行的初始点。,设给定设计变量的上下限值为：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)可作为初始点；否则，则应另取随机数重新产生随机点，直到得到一个可行的随机点为止。,构造随机搜索方向,利用计算机中的随机数发生器，在区间-1,1上产生一组随机数方法r1、r2、rn(n 为变量的维数)，则随机搜
7、索方向为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)。,计算步骤及算法框图（略）,基本思想,6.4 复合形法,它是约束优化问题中经常采用的一种重要的直接求解方法。它适于解决如下数学模型：min f(X)X Rn s.t.gj(X)0(j=1,2,m)ai xi bi(i=1,2,n),其基本思想是：在可行域内构造一个具有K1个顶点的初始复合形（n+1 K12n），,或叫多面体，对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的
8、顶点（或称最坏点），然后按一定的法则求出目标函数值有下降的可行的新点，并用此点代替最坏点，构成新的复合形。复合形的形状每改变一次，就向最优点移动一步，直到逼近最优点。,初始复合形的形成,复合形法是一种在可行域内搜索最优点的直接解法，要求初始复合形必须在可行域内生成，即初始复合形的K1个顶点都必须是可行点。,构造初始复合形是复合形法的关键内容之一，其方法和步骤如下：,1）给定K1值，n+1 K12n；,2）生成初始复合形，有两种方法：,由设计者试选K1个可行点，构成初始复合形。当设计变量较多或约束函数较复杂时，由设计者决定K1个可行点常常很困难。只有在设计变量少，约束函数简单的情况下，才用这种方
9、法。,记K=1，由设计者选定一个可行点X1 或用随机投点法确定X1，其余的(K1-1)个可行点用随机法产生。各顶点按下式计算：XK=a+rK(b a)(K=1,2,K1)其中，rK(0，1)区间上的随机数;a、b 设计变量的上下限；XK 复合形中的第K个顶点。,由上式计算得到的(K1-1)个随机点不一定都在可行域内，因此要设法将不可行点移到可行域内。,在随机产生每个随机点时，要检查其可行性，若可行转 3）；否则计算前(K-1)个可行点所成复合形的中心（或形心）点 XF：XF=(Xj)/(K-1)然后将非可行点XK向中心点XF移动，即 XK=XF+0.5(XK-XF),新的XK是由原XK向XF
10、退缩得到的，再检查是否为可行点，若仍为非可行点，则继续按上式使XK向XF 退缩，直到成为可行点。如果目标函数是凸函数，可行域是凸集，则。,XF总是可行的，故由XK向XF 退缩，总可以找到可行点XK。若XF 不可行，则可行域必为非凸集。这种情况下为保证初始复合形在可行域内，应缩小随机投点的边界域，重新产生初始复合形的各顶点。,3）判断K=K1否，如果K K1，则令K K+1 并转 2）的，直至产生K1个可行点，构成初始复合形X1 X2 XK1。,复合形法的计算步骤及算法框图,1）构造初始复合形,2）计算并比较复合形各顶点的目标函数值f(XK)，找出最坏点XH、最优点XL、次坏点 XG。f(XH)
11、=max f(XK)，K=1,2,K1 f(XL)=min f(XK)，K=1,2,K1 f(XG)=maxf(XK)，K=1,2,K1，K H,3）检验迭代终止条件，计算复合形K1个顶点的函数值的平均值 fm。fm=(f(XK)/K1计算容差DF，并判别是否满足DF=f(XK)-fm 2/K1 1/2？若满足，迭代计算终止，并输出最优解：X*=XL，f*=f(XL);否则，转下一步。,4）计算除去最坏点XH以外的(K1-1)个顶点的中心XC:XC=(Xj)/(K1-1)判别 XC 是否可行，若XC 为可行点，则转 5）；若XC 为非可行点，则重新确定设计变量的下限和上限值，即令 a=XL，b
12、=XC 或 a=XC，b=XL 然后转 1），重新构造初始复合形。,5）计算反射点XRXR=XC+(XC-XH)反射系数，一般取=11.3。,6）检验反射点XR的可行性，若可行，转下一步；若不可行，则令 0.5，转 5）再求反射点（此时又称退缩点），直至XR可行，再转下一步。,7）计算f(XR)，若f(XR)f(XH)，则转下一步。,8）检验反射系数是否满足，为一小的正数。若满足，则转下一步；若不满足，则令 0.5，转 5）。,9）改变反射方向，即改求次坏点 XG的反射点XR，公式为XR=XC+(XC-XG)并转 6），直至找到新的复合形（此时上式中的反射系数 应重新赋值）。,XR,举例：用复合形法求 min f(X)=x12+2x22-4x1-8x2 12 s.t.1x1 3 0.5x2 3的最优解，给定精度=0.2。,
