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