机械优化设计课件第六章-约束优化的直接搜索法-.ppt

1、机械优化设计机械优化设计太原科技大学张学良第六章 约束优化的直接搜索法 数学模型：数学模型：min f(X)X Rn s.t.gj(X)0 (j=1,2,m)hk(X)=0 (k=1,2,p)6.1 概述概述 根据对约束函数处理方法的不同，约束根据对约束函数处理方法的不同，约束优化方法可以分为：直接法和间接法。优化方法可以分为：直接法和间接法。直接法通常适用于仅含不等式约束的优化直接法通常适用于仅含不等式约束的优化问题，当有等式约束时，该等式约束函数不问题，当有等式约束时，该等式约束函数不能是复杂的隐函数，而且容易实现消元过程。能是复杂的隐函数，而且容易实现消元过程。直接法的基本思想直接法的基

2、本思想 在在m个不等式约束条件所确定的可行域个不等式约束条件所确定的可行域内，选择一个初始点内，选择一个初始点X(0)，然后决定，然后决定可行搜可行搜索方向索方向S(0)，且以适当的步长，且以适当的步长(0)，沿，沿S(0)方向进行搜索，得到一个使目标函数值下方向进行搜索，得到一个使目标函数值下降的可行的新点降的可行的新点X(1)，即完成一次迭代，再，即完成一次迭代，再以新点为起点，重复上述搜索过程，满足以新点为起点，重复上述搜索过程，满足收敛条件后，迭代终止。收敛条件后，迭代终止。迭代公式为一般公式：迭代公式为一般公式：X(k+1)=X(k)+(k)S(k)(k=0,1,2,)S(k)为为可

3、行搜索方向可行搜索方向，(k)为步长。为步长。可行搜索方向可行搜索方向是指：当设计点沿该方向是指：当设计点沿该方向作微量移动时，目标函数值将下降，且不会作微量移动时，目标函数值将下降，且不会超出可行域。超出可行域。直接法的特点是：直接法的特点是：原理简单、方法实用，但计算量大，收敛原理简单、方法实用，但计算量大，收敛慢、效率低。适于维数低、精度要求不高但目慢、效率低。适于维数低、精度要求不高但目标函数较复杂的问题。标函数较复杂的问题。间接法的基本思想间接法的基本思想 将约束优化问题中的约束函数进行特将约束优化问题中的约束函数进行特殊的加权处理后，和目标函数结合起来，殊的加权处理后，和目标函数结

4、合起来，构成一个新的目标函数，即将约束优化问构成一个新的目标函数，即将约束优化问题转化成为一个或一系列的无约束优化问题转化成为一个或一系列的无约束优化问题，再对新的目标函数进行无约束优化计题，再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束优化问题的算，从而间接地搜索到原约束优化问题的最优解。最优解。常用的直接法有：常用的直接法有：网格法、约束随机方向搜索法和复合形网格法、约束随机方向搜索法和复合形法。法。6.2 网格法网格法 网格法网格法的基本思想的基本思想 适于解决如下数学模型：适于解决如下数学模型：min f(X)X Rn s.t.gj(X)0 (j=1,2,m)ai x i

5、bi (i =1,2,n)其基本思想是：在设计变量的界限区域内其基本思想是：在设计变量的界限区域内作出网格，逐个计算各个网格点上的约束函作出网格，逐个计算各个网格点上的约束函数值和目标函数值，然后舍去不满足约束条数值和目标函数值，然后舍去不满足约束条件的网格点，对满足约束条件的网格点，件的网格点，对满足约束条件的网格点，比较其目标函数值的大小，从中找出目标函数比较其目标函数值的大小，从中找出目标函数值最小的网格点。若此网格点之间的距离值最小的网格点。若此网格点之间的距离hj均均小于给定的控制精度小于给定的控制精度 j(通常取通常取 j=，i=1,2,n)，则该网格点就是所要求的最优点的近似点则

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

7、方法。它适于解决如下数学模型：直接求解方法。它适于解决如下数学模型：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。若若f(XL)f(X(0)，则缩短步长，则缩短步长

8、0，或重，或重新产生新产生n个随机方向，重复前面的过程。个随机方向，重复前面的过程。若若f(XL)f(X(0)，则继续沿方向，则继续沿方向S=XL-X(0)，并令，并令X(0)=XL，以适当步长，以适当步长 向前跨步，向前跨步，得到新点得到新点 X(1)=X(0)+S。若若f(X(1)f(XL)，则应缩短步长，则应缩短步长 ，直，直至取得一个好的可行点作为新一轮搜索的起至取得一个好的可行点作为新一轮搜索的起始点。如此周而复始，当迭代步长始点。如此周而复始，当迭代步长 已经很已经很小时，说明搜索已逼近约束最优点。达到精小时，说明搜索已逼近约束最优点。达到精度要求时，即可终止迭代计算。度要求时，即

9、可终止迭代计算。方法方法1）决定性方法）决定性方法 当问题的约束条件当问题的约束条件比较简单，可凭判断人为地在可行域内选定比较简单，可凭判断人为地在可行域内选定一个初始点。一个初始点。确定初始可行点确定初始可行点 方法方法2）随机投点方法随机投点方法 当问题的约束条当问题的约束条件较为复杂时，靠判断选择初始可行点较困件较为复杂时，靠判断选择初始可行点较困难，这时可借助计算机中的随机数发生器，难，这时可借助计算机中的随机数发生器，产生随机但可行的初始点。产生随机但可行的初始点。设给定设计变量的上下限值为：设给定设计变量的上下限值为：ai xi bi (i=1,2,n)则产生的随机点的各分量为则产

10、生的随机点的各分量为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

11、为为变量的维数变量的维数)，则随机搜索方向为，则随机搜索方向为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)。0X(0)XLSXLS 计算步骤及算法框图（略）计算步骤及算法框图（略）基本思想基本思想 6.4 复合形法复合形法 它是约束优化问题中经常采用的一种它是约束优化问题中经常采用的一种重要的直接求解方法。它适于解决如下数重要的直接求解方法。它适于解决如下数学模型：学模型：min f

12、(X)X Rn s.t.gj(X)0 (j=1,2,m)ai xi bi (i=1,2,n)其基本思想是：在可行域内构造一个具有其基本思想是：在可行域内构造一个具有K1个顶点的初始复合形（个顶点的初始复合形（n+1 K12n），），或叫多面体，对该复合形各顶点的目标函或叫多面体，对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶数值进行比较，去掉目标函数值最大的顶点（或称最坏点），然后按一定的法则求点（或称最坏点），然后按一定的法则求出出目标函数值有下降的可行的新点，目标函数值有下降的可行的新点，并用并用此点代替最坏点，构成新的复合形。复合此点代替最坏点，构成新的复合形。复合形的形状

13、每改变一次，就向最优点移动一形的形状每改变一次，就向最优点移动一步，直到逼近最优点。步，直到逼近最优点。初始复合形的形成初始复合形的形成 复合形法是一种在可行域内搜索最优点复合形法是一种在可行域内搜索最优点的直接解法，要求初始复合形必须在可行域的直接解法，要求初始复合形必须在可行域内生成，即初始复合形的内生成，即初始复合形的K1个顶点都必须是个顶点都必须是可行点。可行点。构造初始复合形是复合形法的关键内容构造初始复合形是复合形法的关键内容之一，其方法和步骤如下：之一，其方法和步骤如下：1）给定）给定K1值，值，n+1 K12n；2）生成初始复合形，有两种方法：）生成初始复合形，有两种方法：由设

14、计者试选由设计者试选K1个可行点，构成初始个可行点，构成初始复合形。当设计变量较多或约束函数较复杂时，复合形。当设计变量较多或约束函数较复杂时，由设计者决定由设计者决定K1个可行点常常很困难。只有在个可行点常常很困难。只有在设计变量少，约束函数简单的情况下，才用这设计变量少，约束函数简单的情况下，才用这种方法。种方法。记记K=1，由设计者选定一个可行点，由设计者选定一个可行点X1 或用随机投点法确定或用随机投点法确定X1，其余的，其余的(K1-1)个可行个可行点用随机法产生。各顶点按下式计算：点用随机法产生。各顶点按下式计算：XK=a+rK(b a)(K=1,2,K1)其中，其中，rK (0，

15、1)区间上的随机数区间上的随机数;a、b 设计变量的上下限；设计变量的上下限；XK 复合形中的第复合形中的第K个顶点。个顶点。由上式计算得到的由上式计算得到的(K1-1)个随机点不一定个随机点不一定都在可行域内，因此要设法将不可行点移到都在可行域内，因此要设法将不可行点移到可行域内。可行域内。在随机产生每个随机点时，要检查其可在随机产生每个随机点时，要检查其可行性，若可行转行性，若可行转 3）；否则计算前）；否则计算前(K-1)个可个可行点所成复合形的中心（或形心）点行点所成复合形的中心（或形心）点 XF：XF=(Xj)/(K-1)然后将非可行点然后将非可行点XK向中心点向中心点XF移动，即移

16、动，即 XK =XF+0.5(XK -XF)新的新的XK是由原是由原XK向向XF 退缩得到的，再退缩得到的，再检查是否为可行点，若仍为非可行点，则继检查是否为可行点，若仍为非可行点，则继续按上式使续按上式使XK向向XF 退缩，直到成为可行点。退缩，直到成为可行点。如果目标函数是凸函数，可行域是凸集，则。如果目标函数是凸函数，可行域是凸集，则。XF总是可行的，故由总是可行的，故由XK向向XF 退缩，总可以退缩，总可以找到可行点找到可行点XK。若。若XF 不可行，则可行域必不可行，则可行域必为非凸集。这种情况下为保证初始复合形在为非凸集。这种情况下为保证初始复合形在可行域内，应缩小随机投点的边界域

17、，重新可行域内，应缩小随机投点的边界域，重新产生初始复合形的各顶点。产生初始复合形的各顶点。3）判断）判断K=K1否，如果否，如果K K1，则令，则令K K+1 并转并转 2）的）的 ，直至产生，直至产生K1个可个可行点，构成初始复合形行点，构成初始复合形X1 X2 XK1。复合形法的计算步骤及算法框图复合形法的计算步骤及算法框图 1）构造初始复合形）构造初始复合形 2）计算并比较复合形各顶点的目标函数值）计算并比较复合形各顶点的目标函数值f(XK)，找出最坏点，找出最坏点XH、最优点、最优点XL、次坏点、次坏点 XG。f(XH)=max f(XK)，K=1,2,K1 f(XL)=min f(

18、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 是否可行，若

19、是否可行，若XC 为可行点，则为可行点，则转转 5）；若）；若XC 为非可行点，则重新确定设计为非可行点，则重新确定设计变量的下限和上限值，即令变量的下限和上限值，即令 a=XL，b=XC 或或 a=XC，b=XL 然后转然后转 1），重新构造初始复合形。），重新构造初始复合形。5）计算反射点）计算反射点XRXR=XC+(XC-XH)反射系数，一般取反射系数，一般取 =11.3。6）检验反射点）检验反射点XR的可行性，若可行，转下的可行性，若可行，转下一步；若不可行，则令一步；若不可行，则令 0.5 ，转转 5）再求反射点（此时又称退缩点），直至再求反射点（此时又称退缩点），直至XR可可行，再

20、转下一步。行，再转下一步。7）计算）计算f(XR)，若，若f(XR)f(XH)，则转下，则转下一步。一步。8）检验反射系数是否满足）检验反射系数是否满足 ，为一小为一小的正数。的正数。若满足，则转下一步；若不满足，若满足，则转下一步；若不满足，则令则令 0.5 ，转转 5）。）。9）改变反射方向，即改求次坏点）改变反射方向，即改求次坏点 XG的反的反射点射点XR，公式为，公式为XR=XC+(XC-XG)并转并转 6），直至找到新的复合形（此时上式），直至找到新的复合形（此时上式中的反射系数中的反射系数 应重新赋值）。应重新赋值）。XRX4X1=XHX2=XGX3=XLXC 举例：举例：用复合形法求用复合形法求 min f(X)=x12+2x22-4x1-8x2 12 s.t.1x1 3 0.5x2 3的最优解，的最优解，给定精度给定精度 =0.2。