《的加減法》課件

機械優(yōu)化設計太原科技大學張學良2021/7/231機械優(yōu)化設計太原科技大學2021/7/231第六章約束優(yōu)化的直接搜索法數(shù)學模型：minf(X

)X∈Rn

s.t.gj(X

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

hk(X

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

概述根據(jù)對約束函數(shù)處理方法的不同，約束優(yōu)化方法可以分為：直接法和間接法。2021/7/232第六章約束優(yōu)化的直接搜索法數(shù)學模型：§6直接法通常適用于僅含不等式約束的優(yōu)化問題，當有等式約束時，該等式約束函數(shù)不能是復雜的隱函數(shù)，而且容易實現(xiàn)消元過程。直接法的基本思想在m個不等式約束條件所確定的可行域內(nèi)，選擇一個初始點X(0)，然后決定可行搜索方向S(0)，且以適當?shù)牟介L

(0)，沿S(0)方向進行搜索，得到一個使目標函數(shù)值下降的可行的新點X(1)，即完成一次迭代，再以新點為起點，重復上述搜索過程，滿足收斂條件后，迭代終止。2021/7/233直接法通常適用于僅含不等式約束的優(yōu)化問題，當有等式約束迭代公式為一般公式：X(k+1)=X(k)+

(k)

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

(k)為步長。

可行搜索方向是指：當設計點沿該方向作微量移動時，目標函數(shù)值將下降，且不會超出可行域。直接法的特點是：原理簡單、方法實用，但計算量大，收斂慢、效率低。適于維數(shù)低、精度要求不高但目標函數(shù)較復雜的問題。2021/7/234迭代公式為一般公式：可行搜索方向是指：當設計間接法的基本思想將約束優(yōu)化問題中的約束函數(shù)進行特殊的加權處理后，和目標函數(shù)結(jié)合起來，構成一個新的目標函數(shù)，即將約束優(yōu)化問題轉(zhuǎn)化成為一個或一系列的無約束優(yōu)化問題，再對新的目標函數(shù)進行無約束優(yōu)化計算，從而間接地搜索到原約束優(yōu)化問題的最優(yōu)解。常用的直接法有：網(wǎng)格法、約束隨機方向搜索法和復合形法。2021/7/235間接法的基本思想將約束優(yōu)化問題中的約束§6.2

網(wǎng)格法

網(wǎng)格法的基本思想適于解決如下數(shù)學模型：minf(X

)X∈Rn

s.t.gj(X

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

ai≤x

i≤bi(i=1,2,…,n)其基本思想是：在設計變量的界限區(qū)域內(nèi)作出網(wǎng)格，逐個計算各個網(wǎng)格點上的約束函數(shù)值和目標函數(shù)值，然后舍去不滿足約束條件的網(wǎng)格點，對滿足約束條件的網(wǎng)格點，2021/7/236§6.2網(wǎng)格法網(wǎng)格法的基本思想比較其目標函數(shù)值的大小，從中找出目標函數(shù)值最小的網(wǎng)格點。若此網(wǎng)格點之間的距離hj均小于給定的控制精度

j(通常取

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

，則該網(wǎng)格點就是所要求的最優(yōu)點的近似點X*。否則，以該點為中心縮小尋優(yōu)區(qū)間，即在該點附近作較密的網(wǎng)格，繼續(xù)求目標函數(shù)值最小的網(wǎng)格點。如此循環(huán)往復，直至找到滿足精度要求的最優(yōu)點的近似點X*。網(wǎng)格的劃分可以是等間距的，也可以是非等間距的。2021/7/237比較其目標函數(shù)值的大小，從中找出目標函數(shù)值最小的網(wǎng)格點。若此計算步驟及算法框圖（略）2021/7/238計算步驟及算法框圖（略）2021/7/238§6.3約束隨機方向搜索法基本思想它是約束優(yōu)化問題中經(jīng)常采用的一種直接求解方法。它適于解決如下數(shù)學模型：minf(X

)X∈Rn

s.t.gj(X

)≤0(j=1,2,…,m)其基本思想是：在不破壞約束條件的前提下，從選定的初始可行點X(0)出發(fā)，相繼沿著n個隨機產(chǎn)生的搜索方向e(k)(k=1,2,…,n)，2021/7/239§6.3約束隨機方向搜索法基本思想以定步長

0搜索得到n個試驗點Xk(k=1,2,…,n)，然后計算比較n個試驗點處的函數(shù)值f(Xk)，找出其中的最小點XL。若f(XL)≥f(X(0))，則縮短步長

0，或重新產(chǎn)生n個隨機方向，重復前面的過程。若f(XL)<f(X(0))，則繼續(xù)沿方向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)，則應縮短步長

，直至取得一個好的可行點作為新一輪搜索的起始點。如此周而復始，當?shù)介L

已經(jīng)很小時，說明搜索已逼近約束最優(yōu)點。達到精度要求時，即可終止迭代計算。方法1）決定性方法當問題的約束條件比較簡單，可憑判斷人為地在可行域內(nèi)選定一個初始點。確定初始可行點方法2）隨機投點方法當問題的約束條件較為復雜時，靠判斷選擇初始可行點較困難，這時可借助計算機中的隨機數(shù)發(fā)生器，產(chǎn)生隨機但可行的初始點。2021/7/2311若f(X(1))>f(XL)，則應設給定設計變量的上下限值為：ai≤xi≤bi(i=1,2,…,n)則產(chǎn)生的隨機點的各分量為xi(0)=ai+ri(bi-ai)(i=1,2,…,n)其中，ri為[0，1]區(qū)間上的隨機數(shù)。還需對點X(0)進行可行性檢驗，即是否滿足gj(X(0))≤0(j=1,2,…,m)若滿足，X(0)可作為初始點；否則，則應另取隨機數(shù)重新產(chǎn)生隨機點，直到得到一個可行的隨機點為止。2021/7/2312設給定設計變量的上下限值為：2021/7/2構造隨機搜索方向利用計算機中的隨機數(shù)發(fā)生器，在區(qū)間[-1,1]上產(chǎn)生一組隨機數(shù)方法r1、r2、…、rn(n為變量的維數(shù))，則隨機搜索方向為e=[e1

e2…en]T=[r1

r2…rn]T/(∑ri)0.5||e||=1,e是一個單位向量。要產(chǎn)生N個隨機搜索方向e(k)(k=1,2,…,N),需要產(chǎn)生N組隨機數(shù)ri(k)(i=1,2,…,n;k=1,2,…,N)。2021/7/2313構造隨機搜索方向利用計算機中的隨機數(shù)發(fā)生器，

0X(0)XLSXLS計算步驟及算法框圖（略）2021/7/23140X(0)XLSXLS計算步驟及算法框圖（略）202基本思想

§6.4

復合形法它是約束優(yōu)化問題中經(jīng)常采用的一種重要的直接求解方法。它適于解決如下數(shù)學模型：minf(X

)X∈Rn

s.t.gj(X

)≤0(j=1,2,…,m)ai≤xi≤bi(i=1,2,…,n)其基本思想是：在可行域內(nèi)構造一個具有K1個頂點的初始復合形（n+1≤K1≤2n），2021/7/2315基本思想§6.4復合形法它是或叫多面體，對該復合形各頂點的目標函數(shù)值進行比較，去掉目標函數(shù)值最大的頂點（或稱最壞點），然后按一定的法則求出目標函數(shù)值有下降的可行的新點，并用此點代替最壞點，構成新的復合形。復合形的形狀每改變一次，就向最優(yōu)點移動一步，直到逼近最優(yōu)點。初始復合形的形成

復合形法是一種在可行域內(nèi)搜索最優(yōu)點的直接解法，要求初始復合形必須在可行域內(nèi)生成，即初始復合形的K1個頂點都必須是可行點。2021/7/2316或叫多面體，對該復合形各頂點的目標函數(shù)值進行比較，去掉目標函構造初始復合形是復合形法的關鍵內(nèi)容之一，其方法和步驟如下：1）給定K1值，n+1≤K1≤2n；2）生成初始復合形，有兩種方法：①由設計者試選K1個可行點，構成初始復合形。當設計變量較多或約束函數(shù)較復雜時，由設計者決定K1個可行點常常很困難。只有在設計變量少，約束函數(shù)簡單的情況下，才用這種方法。2021/7/2317構造初始復合形是復合形法的關鍵內(nèi)容之一，其方②記K=1，由設計者選定一個可行點X1或用隨機投點法確定X1，其余的(K1-1)個可行點用隨機法產(chǎn)生。各頂點按下式計算：XK=a+rK(b–a)(K=1,2,…,K1)其中，rK—(0，1)區(qū)間上的隨機數(shù);

a、b—設計變量的上下限；

XK—復合形中的第K個頂點。由上式計算得到的(K1-1)個隨機點不一定都在可行域內(nèi)，因此要設法將不可行點移到可行域內(nèi)。2021/7/2318②記K=1，由設計者選定一個可行點X1或在隨機產(chǎn)生每個隨機點時，要檢查其可行性，若可行轉(zhuǎn)3）；否則計算前(K-1)個可行點所成復合形的中心（或形心）點XF：XF

=(∑Xj)/(K-1)然后將非可行點XK向中心點XF移動，即

XK

=XF

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

退縮得到的，再檢查是否為可行點，若仍為非可行點，則繼續(xù)按上式使XK向XF

退縮，直到成為可行點。如果目標函數(shù)是凸函數(shù)，可行域是凸集，則。2021/7/2319在隨機產(chǎn)生每個隨機點時，要檢查其可行性，若可XF總是可行的，故由XK向XF

退縮，總可以找到可行點XK。若XF

不可行，則可行域必為非凸集。這種情況下為保證初始復合形在可行域內(nèi)，應縮小隨機投點的邊界域，重新產(chǎn)生初始復合形的各頂點。3）判斷K=K1否，如果K≠K1，則令KK+1并轉(zhuǎn)2）的②，直至產(chǎn)生K1個可行點，構成初始復合形X1X2…XK1。2021/7/2320XF總是可行的，故由XK向XF退縮，總可以找到可行點XK復合形法的計算步驟及算法框圖

1）構造初始復合形2）計算并比較復合形各頂點的目標函數(shù)值f(XK)，找出最壞點XH、最優(yōu)點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個頂點的函數(shù)值的平均值fm。fm=(∑f(XK))/K1計算容差DF，并判別是否滿足DF={∑[f(XK)-fm]2/K1}1/2≤？若滿足，迭代計算終止，并輸出最優(yōu)解：X*

=XL，f*

=f(XL);否則，轉(zhuǎn)下一步。2021/7/23223）檢驗迭代終止條件，計算復合形K1個頂點的函數(shù)值的4）計算除去最壞點XH以外的(K1-1)個頂點的中心XC:XC

=(∑Xj)/(K1-1)判別XC是否可行，若XC為可行點，則轉(zhuǎn)5）；若XC為非可行點，則重新確定設計變量的下限和上限值，即令

a=XL，b=XC或a=XC，b=XL然后轉(zhuǎn)1），重新構造初始復合形。5）計算反射點XRXR=XC+

(XC-XH)—反射系數(shù)，一般取

=1～1.3。2021/7/23234）計算除去最壞點XH以外的(K1-1)個頂點的中6）檢驗反射點XR的可行性，若可行，轉(zhuǎn)下一步；若不可行，則令0.5，轉(zhuǎn)5）再求反射點（此時又稱退縮點），直至XR可行，再轉(zhuǎn)下一步。7）計算f(XR)，若f(XR)<f(XH)，反射成功，則以反射點XR點替換最壞點XH，構成新的復合形，并比較f(XR)、f(XL)、f(XG