机械优化设计方法第六章约束最优化方法

6-1概述约束最优化问题是：求n维设计变量X=[x1,x2,…,xn]T，受约束于gu(X)≥0(u=1,2,…,m)，hv(X)=0(v=1,2,…,pn)，使目标函数为minf(X)=f(X*)，则称X*为最优点，f(X*)为最优值。机械优化设计问题和一般工程实际优化问题绝大多数属于约束非线性规划问题。约束最优化问题的解法很多，归纳起来可分为两大类。一类是直接方法，即直接用原来的目标函数限定在可行域内进行搜索，且在搜索过程中一步一步地降低目标函数值，直到求出在可行域内的一个最优解，属于直接方法的有约束变量轮换法、随机试验法、随机方向搜索法、复合形法、可行方向法等。另一类是间接方法，即将约束最优化问题，通过变换转成为无约束最优化问题．然后采用无约束最优化方法得出最优解．属于间接方法的有消元法、拉格朗日乘子法、惩罚函数法等。约束最优化问题算法收效速率的判断比无约束最优化问题困难，约束最优化问题的研究和进展情况远不如无约束优化问题。6-2约束随机方向搜索法一、基本原理基本原理可用图6-1所示二维最优化问题进行说明。在约束可行区域D内，任意选择一个初始点X(0)，以给定的初始步长α=α0沿着随机方向S(1)取得探索点X=X(0)+αS(1)若该点同时符合下降性(即f(X)f(X(0))和可行性(即X∈D)要求，则表示X点探索成功。并以它作为新的起始点，即X→X(0)，继续按上面的迭代公式在S(1)方向上获取新的探索成功点。重复上述步骤，迭代点可沿S(1)方向前进，直至到达某搜索点不能同时符合下降性和可行性要求时停止。此时废弃该搜索点并退回到前一个搜索成功点作为S(1)方向搜索中的最终成功点，记作X(1)。此后，将X(1)点置为新的始点X(1)→X(0)，再产生另一随机方向S(2)，以步长α重复以上过程，得到沿S(2)方向的最终成功点X(2)。经若干循环，点列{X(k)(k=1,2,…)}必最后逼近约束最优点X*。若在初始点X(0)或某个换向转折点处(如图中的X(1)点)，沿某随机方向的探索点目标函数值增大(如图中的A点、C点)或者越出可行域(如图中的B点、D点),则应相应弃去该随机方向,重新产生另一随机方向进行探索。探索成功继续前进,探索失败再重新产生随机方向。当在某个转折点处(如图中的X(2)点)，沿Nmax(预先限定在某个转折点处产生随机方向所允许的最大数目)个随机方向以步长α进行探索均失败，可以反映以此点为中心、α为半径的圆周上各点均难同时符合下降性和可行性条件。此时可将步长α缩半后继续试探，直到α已缩减到预定精度ε以下(即α≤ε)，且沿Nmax个随机方向都探索失败时，则以最后一个成功点(如图中的X(3)点)作为达到预定精度要求的约束最优点，结束迭代。Nmax一般可在50~500范围内选取，对目标函数性态不好的应取较大的值，以提高解题成功率。二、初始点的选择随机方向搜索法的初始点X(0)必须是一个可行点，即必须满足全部约束条件gu(X)≥0(u=1,2,…,m)通常有两种方法：(一)人为给定：即在设计的可行区域D内人为地确定一个可行的初始点。(二)随机选定：即利用电子计算机产生的伪随机数来选择一个可行的初始点X(0)。此时需要送入设计变量估计的上限和下限，以图6-2所示二维情况为例，X=[x1,x2]T，a1≤x1≤b1，a2≤x2≤b2。在[0，1]区间内产生两个随机数r1和r2，0r11，0r21，以x1(0)=a1+r1(b1―a1),x2(0)=a2+r2(b2―a2)作分量获得随机初始点X=[x1(0),x2(0)]T。同理，若对n维变量估计其上限和下限：ai≤xi≤bi(i=1,2,…,n)(6-1)在[0，1]区间内产生n个随机数ri，0＜ri＜1(i=1,2,…,n)这样随机产生的初始点X(0)的各分量为xi(0)=ai+ri(bi―ai)(i=1,2,…,n)(6-2)ri—[0,1]区间内服从均匀分布的伪随机数列。许多计算机本身就有发生随机数的功能，可直接调用。需要指出，这样产生的初始点X(0)=[x1(0),x2(0),…,xn(0)]T虽能满足设计变量的边界条件，但不一定能满足所有约束条件(如点)。因此这样产生的初始点还须经过可行性条件的检验，如能满足，才可作为一个可行的初始点。否则，应重新随机选初始点，直到满足所有的约束条件。三、随机搜索方向的产生以图6-3所示二维情况说明随机向量的产生。设y1，y2是在区间(-1，+1)上的两个随机数。将它们分别作为x1，x2坐标轴上的分量所构成的向量即为相应的二维随机向量。其单位向量如y1′,y2′区间(-1，+1)上的另外两个随机数，同样相应构成另一个二维随机向量，其单位向量为S′。这些二维随机单位向量的端点分布于半径为单位长的圆周上。TyyyyS212221,1同理类推，对于一个n维优化问题，随机方向单位向量可按下式计算：yi(i=1,2,…,n)是在n个坐标轴上随机向量的分量，它由规定在(-1，+1)区间的随机数取得。有些计算机具有直接调用的功能，但有些计算机则无此功能，需要另编程序。如可获得(0，1)区间内服从均匀分布的随机数数列ri(i=1,2,…,n)，则可通过下式yi=ai+ri(bi-ai)(i=1,2,…,n)转化成在(ai，bi)区间内服从均匀分布的随机数数列。以ai＝-1，bi＝1代入上式，可得(-1，+1)区间内服从均匀分布的随机数数列yi=2ri-1由于yi在区间(-1，+1)内产生，因此所构成的随机方向单位向量端点一定位于n维的超球面上。TnniiyyyyS,,,12112四、迭代过程及算法框图(1)给定设计变量数目n,初始变量估计的上下限ai,bi(i=1,2,…,n)，初始步长α0，步长收敛精度ε，产生随机方向最大次数Nmax。(2)随机产生初始点。(3)X(0)→X，f(X)→f0，α0→α。(4)置1→k，0→jj。(5)在(-1,+1)区间产生随机数yi(i=1,2,…,n)，获得单位随机向量，沿S方向迭代得迭代新点X=X(0)+αS。(6)检验新点X的可行性。若满足gu(X)≥0(u=1,2,…,m)，则进行第(7)步；否则转向第(9)步。(7)检验新点X的下降性。计算f(X)→f，若ff0则进行第(8)步，否则转向第(9)步。(8)X→X(0)，f→f0，置jj=1，继续沿S方向迭代得迭代新点X＝X(0)+αS，返回第(6)步。(9)若jj＝0，则k+1→k，进行第(10)步；否则返回第(4)步。(10)若kNmax，则进行第(11)步；否则返回第(5)步。(11)若α≤ε，则输出最优解：X→X*，f(X)→f(X*)，可终止迭代；否则,将步长减半,即0.5α→α,返回第(4)步，继续迭代。随机方向搜索法的算法框图如图6-4所示。6-3复合形法一、基本原理复合形法的基本思路在n维空间的可行域中选取K个设计点(通常取n+1≤K≤2n)作为初始复合形(多面体)的顶点。然后比较复合形各顶点目标函数值的大小，其中目标函数值最大的点为坏点以坏点之外其余各点的中心为映射中心，寻找坏点的映射点，一般说来此映射点的目标函数值总是小于坏点的，也就是说映射点优于坏点。这时，以映射点替换坏点与原复合形除坏点之外其余各点构成K个顶点的新的复合形。如此反复迭代计算，在可行域中不断以目标函数值低的新点代替目标函数值最大的坏点从而构成新复合形，使复合形个断向最优点移动和收缩，直至收缩到复合形的各顶点与其形心非常接近、满足迭代精度要求时为止。输出复合形各顶点中的目标函数值最小的顶点作为近似最优点。现以图6-5所示二维不等式约束优化问题来作进—步说明。其数学模型为2minRDXXfD：g1(X)≥0g2(X)≥0a1≤x1≤b1a2≤x2≤b2其中，g1(X)≥0，g2(X)≥0可称为隐式约束条件，而边界约束a1≤x1≤b1，a2≤x2≤b2可称为显式约束条件。在可行域内先选定X(1)、X(2)、X(3)、X(4)四个点(这里取K=2n=2×2=4)作为初始复合形的顶点，计算这四个点的目标函数值，并作比较，得出坏点X(H)和好点X(L)：X(H)：f(X(H))=max{f(X(j))j=1,2,…K}（6-7）X(L)：f(X(L))=min{f(X(j))j=1,2,…K}（6-8）由图6-5，可以看出点X(4)为好点，点X(1)为坏点，即X(4)→X(L)，X(1)→X(H)。以X(2)、X(3)、X(4)三点的中心X(C)为映射中心，寻找坏点X(H)的映射点X(R)：X(R)＝X(C)+α(X(C)-X(H))(6-9)α为映射系数，通常取α＝1.3。计算映射点X(R)处目标函数f(X(R))与坏点目标函数值f(X(H))相比是否下降。并同时检查X(R)是否在可行域内。如果下降性、可行性这两方面都得到满足，则以X(R)点替换X(H)点，由X(R)与X(2)、X(3)、X(4)共四个点构成一个新复合形〔如图6-5出虚线所示)，这个新复合形肯定优于原复合形；如果上述两个条件不能同时满足，则可将映射系数缩半，即0.5α→α，仍按式(6-9)迭代。重新取得新的映射点X(R)，使其同时满足下降性、可行性条件。有时甚至要经过多次缩减映射系数才能使回缩的映射点X(R)最后满足这两个条件。这时以回缩成功的映射点X(R)和X(2)、X(3)、X(4)构成新复合形。构成新复合形就完成了一轮迭代。再按上述方法进行迭代搜索，不断地使复合形向着目标函数减小的方向移动和收缩，直到逼近最优解。通过以上说明，复合形寻优可以归为两大步骤：第一步是在可行域内构成初始复合形，第二步是通过复合形的收缩和移动不断调优，逐步逼近最优点。二、初始复合形的产生初始复合形的全部K个顶点都必须在可行域内。对于维数较低、不很复杂的优化问题，可以人为地预先按实际情况决定K个可行设计点作为初始复合形的顶点；对于维数较高的优化问题则多采用随机方法产生初始复合形。现将随机方法产生初始复合形的过程阐述如下：(一)确定一个可行点X(1)作为初始复合形的第一个顶点在(ai，bi)区间给定一点X(1)=[x1(1),x2(1),…,xn(1)]T或调用(0，1)区间内服从均匀分布的随机数列ri(j)在(ai，bi)区间产生第一个随机点X(1)，的分量：xi(j)＝ai+ri(j)(bi-ai)(j=1；i=1,2,…,n)(6-10)检验X(1)是否可行。若非可行点，则调用随机数，重新产生随机点X(1)，直到X(1)为可行点。(二)产生其他(K-1)个随机点继续调用随机数ri(j)，在(ai，bi)区间产生其他(K-1)个随机点：X(2)=[x1(2),x2(2),…,xn(2)]T，X(3)=[x1(3),x2(3),…,xn(3)]T，…，X(K)=[x1(K),x2(K),…,xn(K)]T其分量为xi(j)＝ai+ri(j)(bi-ai)(j=2,3,…,K；i=1,2,…,n)(6-11)(三)将非可行点调入可行域构成初始复合形用上述方法产生的K个点，除第一点X(1)已在可行域内，其他(K-1)个随机点未必都在可行域内。因此应设法将不在可行域的所有随机点逐一调入可行域。这就需要依次检查X(2)，X(3)，…，X(K)是否在可行域内。检查过程中如X(2)，X(3)，…，X(q)依次都在可行域内，它们均作为初始复合形的顶点；至第X(q+1)点不在可行域内，则应首先将X(q+1)点调入可行域。其步骤为：1．求出已在可行域的q个点的点集的中心X(D)qjjDXqX112．将点X(q+1)向X(D)点的方向推进，移至X(q+1)与X(D)的中点，即按下式产生新的X(q+1)点X(q+1)＝X(D)+0.5(X(q+1)-X(D))(6-13)如果推移后的X(q+1)点已