機(jī)械優(yōu)化設(shè)計(jì)第6章約束優(yōu)化方法課件

機(jī)械優(yōu)化設(shè)計(jì)機(jī)械優(yōu)化設(shè)計(jì)第六章約束優(yōu)化方法×第六章約束優(yōu)化方法×6.1概述6.2隨機(jī)方向法

6.3復(fù)合形方法

6.4可行方向法

6.5懲罰函數(shù)法

6.6增廣乘子法

6.11遺傳算法簡(jiǎn)述6.10結(jié)構(gòu)優(yōu)化法簡(jiǎn)述

6.9二次規(guī)劃法

6.8廣義簡(jiǎn)約梯度法

6.7非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法—線(xiàn)性逼近法6.1概述6.2隨機(jī)方向法6.3復(fù)合形方法6

機(jī)械優(yōu)化設(shè)計(jì)中的問(wèn)題，大多數(shù)屬于約束優(yōu)化設(shè)計(jì)問(wèn)題，其數(shù)學(xué)模型為§第一節(jié)

概述機(jī)械優(yōu)化設(shè)計(jì)中的問(wèn)題，大多數(shù)屬于約束優(yōu)化設(shè)計(jì)問(wèn)題，其數(shù)學(xué)§第一節(jié)

概述

直接解法：隨機(jī)方向搜索法、復(fù)合形法、可行方向法

間接解法：內(nèi)點(diǎn)懲罰函數(shù)法、外點(diǎn)懲罰函數(shù)法、混合懲罰函數(shù)法一.有約束問(wèn)題解法分類(lèi)：二.直接解法的基本思想：

合理選擇初始點(diǎn)，確定搜索方向，在可行域中尋優(yōu)，經(jīng)過(guò)若干次迭代，收斂至最優(yōu)點(diǎn)。

xk+1=xk+αkdkdk::

可行搜索方向。即設(shè)計(jì)點(diǎn)沿該方向作微量移動(dòng)時(shí),目標(biāo)函數(shù)值將下降,且不會(huì)超出可行域直接解法通常適用于僅含不等式約束的問(wèn)題§第一節(jié)概述直接解法：隨機(jī)方向搜索法、復(fù)合形法、可行§第一節(jié)

概述特點(diǎn)：①由于求解過(guò)程在可行域內(nèi)進(jìn)行；無(wú)論迭代計(jì)算何時(shí)終止,都可以獲得一個(gè)比初始點(diǎn)好的設(shè)計(jì)點(diǎn);②若可行域是凸集，目標(biāo)函數(shù)是定義在凸集上的凸函數(shù)，則收斂到全局最優(yōu)點(diǎn)；否則，結(jié)果與初始點(diǎn)有關(guān)。凸可行域非凸可行域§第一節(jié)概述特點(diǎn)：①由于求解過(guò)程在可行域內(nèi)進(jìn)行；無(wú)論迭§第一節(jié)

概述原理：將有約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題來(lái)解決。方法：以原目標(biāo)函數(shù)和加權(quán)的約束函數(shù)共同構(gòu)成一個(gè)新的

目標(biāo)函數(shù)Φ(x,r1,r2)，成為無(wú)約束優(yōu)化問(wèn)題。通

過(guò)不斷調(diào)整加權(quán)因子，產(chǎn)生一系列Φ函數(shù)的極小點(diǎn)

序列x(k)*(r1(k),r2(k))k=0,1,2…，逐漸收斂到原目標(biāo)

函數(shù)的約束最優(yōu)解。其中：新目標(biāo)函數(shù)：三.間接解法的基本思想：

懲罰因子：r1,r2§第一節(jié)概述原理：將有約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題來(lái)§第二節(jié)隨機(jī)方向法一.基本思想：隨機(jī)產(chǎn)生初始點(diǎn)，隨機(jī)產(chǎn)生若干個(gè)搜索方向dk，并從中選擇一個(gè)能使目標(biāo)函數(shù)值下降最快的方向作為可行搜索方向進(jìn)行搜索。確保：①新迭代點(diǎn)在可行域中②目標(biāo)函數(shù)值的下降性。x(0)x(L)x(1)x*§第二節(jié)隨機(jī)方向法一.基本思想：隨機(jī)產(chǎn)生初始點(diǎn)，隨機(jī)二.初始點(diǎn)的選擇

隨機(jī)方向法的初始點(diǎn)x0必須是一個(gè)可行點(diǎn)，既滿(mǎn)足全部

不等式約束條件。初始點(diǎn)可以通過(guò)隨機(jī)選擇的方法產(chǎn)生。1）輸入設(shè)計(jì)變量的下限值和上限值，即2）在區(qū)間（0，1）內(nèi)產(chǎn)生n個(gè)偽隨機(jī)數(shù)3）計(jì)算隨機(jī)點(diǎn)x的各分量4）判別隨機(jī)點(diǎn)x是否可行，若隨機(jī)點(diǎn)可行，用x0←x

為初始點(diǎn)；若非可行點(diǎn)，轉(zhuǎn)到步驟2）重新產(chǎn)生隨

機(jī)點(diǎn)，直到可行為止。§第二節(jié)隨機(jī)方向法二.初始點(diǎn)的選擇隨機(jī)方向法的初始點(diǎn)x0必須是一個(gè)可行點(diǎn)三.可行搜索方向的產(chǎn)生從k個(gè)隨機(jī)方向中，選取一個(gè)較好的方向。1）在(-1,1)區(qū)間內(nèi)產(chǎn)生偽隨機(jī)數(shù)，得隨機(jī)單位向量2)取一試驗(yàn)步長(zhǎng)a0，按下式計(jì)算k個(gè)隨機(jī)點(diǎn)§第二節(jié)隨機(jī)方向法三.可行搜索方向的產(chǎn)生從k個(gè)隨機(jī)方向中，選取一個(gè)較好的方向3）檢驗(yàn)k個(gè)隨機(jī)點(diǎn)是否為可行點(diǎn)，除去非可行點(diǎn)，計(jì)算余下的可行點(diǎn)的目標(biāo)函數(shù)值，比較其大小，選出目標(biāo)

函數(shù)最小的點(diǎn)xL

。4)比較xL

和x0兩點(diǎn)的目標(biāo)函數(shù)值:①若f(xL)<f(x0)，則取xL

和x0連線(xiàn)方向?yàn)榭尚兴阉鞣较颍?/p>

②若f(xL)≥f(x0)，則縮小步長(zhǎng)α0

，轉(zhuǎn)步驟1）重新計(jì)算，

直至f(xL)<f(x0)為止。③α0

縮小到很小仍然找不到一個(gè)xL，使f(xL)<f(x0),則

說(shuō)明x0是一個(gè)局部極小點(diǎn)，更換初始點(diǎn)轉(zhuǎn)步驟1）?！斓诙?jié)隨機(jī)方向法3）檢驗(yàn)k個(gè)隨機(jī)點(diǎn)是否為可行點(diǎn)，除去非可行點(diǎn)，計(jì)算4)比較產(chǎn)生可行搜索方向的條件為：則可行搜索方向?yàn)椋核?、搜索步長(zhǎng)的確定步長(zhǎng)由加速步長(zhǎng)法確定：τ為步長(zhǎng)加速系數(shù)，一般取1.3§第二節(jié)隨機(jī)方向法產(chǎn)生可行搜索方向的條件為：則可行搜索方向?yàn)椋核?、搜索步長(zhǎng)的確五.計(jì)算步驟1)選擇一個(gè)可行的初始點(diǎn)x0;2)產(chǎn)生k個(gè)n維隨機(jī)單位向量ej(j=1,2,…,k);3)取試驗(yàn)步長(zhǎng)0，計(jì)算出k個(gè)隨機(jī)點(diǎn)xj;4)在k個(gè)隨機(jī)點(diǎn)中，找出可行的的隨機(jī)點(diǎn)xL,產(chǎn)生可行搜索方向d=xLx0.5)從初始點(diǎn)x0出發(fā)，沿可行搜索方向d以步長(zhǎng)進(jìn)行迭代計(jì)算，直到搜索到一個(gè)滿(mǎn)足全部約束條件，且目標(biāo)函數(shù)值不再下降的新點(diǎn)x。6)若收斂條件滿(mǎn)足，停止迭代。否則，令x0x轉(zhuǎn)步驟2五.計(jì)算步驟例6-1求下列約束優(yōu)化問(wèn)題的最優(yōu)解

解：用隨機(jī)方向法程序，在計(jì)算機(jī)上運(yùn)行，迭代13次，求得約束最優(yōu)解：x*=[0.00273.0]T,f(x*)=3

例6-1求下列約束優(yōu)化問(wèn)題的最優(yōu)解一.單純形法：基本思想：以一個(gè)目標(biāo)函數(shù)值較小的新點(diǎn)，代替原單純形中目標(biāo)函數(shù)值最大的頂點(diǎn)，組成新的單純形，不斷地迭代，逐漸逼近最優(yōu)點(diǎn)。

二維空間中映射法比較單純形x(1)x(2)x(3)的頂點(diǎn)，f(x(1))>f(x(2))>f(x(3)),

x(1)為最壞點(diǎn)，稱(chēng)為x(H)，通過(guò)映射得到新點(diǎn)x(R)，x(R)＝x(S)＋a(x(S)-x(H))以x(R)來(lái)代替x(H)，組成新的單純形x(R)x(2)x(3)。其中f(x(R))<f(x(H));

a>1；稱(chēng)為映射因子；X(1)=X(H)X(2)X(3)X(S)X(R)=X(4)X(5)X(6)定義：在n維空間中，由n+1個(gè)點(diǎn)組成的圖形稱(chēng)單純形。X*除x(H)外，其它頂點(diǎn)的幾何中心§第三節(jié)復(fù)合形法一.單純形法：基本思想：以一個(gè)目標(biāo)函數(shù)值較小的新點(diǎn)，代替二.復(fù)合形法：定義：在n維空間中，由k≥n+1個(gè)點(diǎn)組成的多面體稱(chēng)為復(fù)合形。基本思想：

以一個(gè)較好的新點(diǎn)，代替原復(fù)合形中的最壞點(diǎn)，組成新的復(fù)合形，以不斷的迭代，使新復(fù)合形逐漸逼近最優(yōu)點(diǎn)。說(shuō)明：

單純形是無(wú)約束優(yōu)化方法，復(fù)合形用于約束優(yōu)化的方法。因?yàn)轫旤c(diǎn)數(shù)較多，所以比單純形更靈活易變。復(fù)合形只能解決不等式約束問(wèn)題。因?yàn)榈^(guò)程始終在可行域內(nèi)進(jìn)行，運(yùn)行結(jié)果可靠。二.復(fù)合形法：定義：基本思想：以一個(gè)較好的新點(diǎn)，三.迭代方法：1.映射法：

例：二維空間中，k=4，復(fù)合形是四面體x(1)x(2)x(3)x(4)，計(jì)算得：f(x(1))<f(x(2))<f(x(3))<f(x(4)),確定最壞點(diǎn)x(H)=x(4)，次壞點(diǎn)x(G)=x(3)，最好點(diǎn)x(L)=x(1)。x(S)為除x(H)以外，各點(diǎn)的幾何中心。映射迭代公式：x(R)=x(S)+α(x(S)-x(H))搜索方向：沿x(H)→x(S)的方向。步長(zhǎng)因子（映射系數(shù)）α：α>1，建議先取1.3。若求得的x(R)在可行域內(nèi)，且f(x(R))<f(x(H))，則以x(R)代替x(H)組成新復(fù)合形，再進(jìn)行下輪迭代。●X(S)X(R)X(H)三.迭代方法：1.映射法：例：二維空間中，k變形法一

——擴(kuò)張：若f(x(R))<f(x(L))，則可沿此方向擴(kuò)張取若f(x(E))<f(x(L))，則擴(kuò)張成功，以x(E)代替x(H)組成新復(fù)合形若f(x(E))>f(x(L))，則擴(kuò)張失敗，以x(R)代替x(H)組成新復(fù)合形●X(S)X(R)X(H)X(E)變形法一——擴(kuò)張：●X(S)X(R)X(H)變形法二

——收縮：若在映射法中f(x(R))>f(x(H)),則以a＝0.5a重復(fù)采用映射法若直至a<10-5仍不成功，考慮采用收縮法

取

若f(x(K))<f(x(H)),則成功，以x(K)代替x(H)組成新復(fù)合形。●X(S)X(R)X(H)X(K)變形法二——收縮：●X(S)X(R)X(H)4.變形法三

——壓縮：如采用上述方法均無(wú)效，還可以將復(fù)合形各頂點(diǎn)向最好點(diǎn)

x(L)靠攏，即采用壓縮的方法改變復(fù)合形的形狀。

取

X(L)4.變形法三——壓縮：X(L)四.初始復(fù)合形的形成：人工選擇初始復(fù)合形2.隨機(jī)產(chǎn)生初始復(fù)合形：

①先在可行域內(nèi)確定一個(gè)初始頂點(diǎn)；②確定xi的上下界：ai、bi；③產(chǎn)生區(qū)間[0,1]中的k-1組偽隨機(jī)數(shù)ri(j)；④產(chǎn)生k-1個(gè)頂點(diǎn)，xi(j)=αi+ri(j)

(bi-ai)⑤檢查k-1個(gè)頂點(diǎn)的可行性，若有q個(gè)頂點(diǎn)滿(mǎn)足約束，求q個(gè)頂點(diǎn)的幾何中心：

⑥以x(q+1)=x(t)+α(x(q+1)-x(t)),a=0.5將不滿(mǎn)足約束的頂點(diǎn)移向可行域若可行域是非凸集，可能失敗，需減小上、下界再進(jìn)行。四.初始復(fù)合形的形成：人工選擇初始復(fù)合形若可行域是非凸集步驟：

1.形成初始復(fù)合形

2.計(jì)算各頂點(diǎn)的函數(shù)值,找到最壞點(diǎn)x(H)

、次壞點(diǎn)x(G)和最好點(diǎn)x(L)

3.計(jì)算除最壞點(diǎn)外，其余頂點(diǎn)的形心:

檢查形心是否在可行域內(nèi)

4.則可行域?yàn)榉峭辜?，取ai＝min[ai

(L),

ai(S)],

bi＝max[ai

(L),

ai(S)]作為上下界；計(jì)算xi(j)=αi+ri(j)(bi-ai)，重新構(gòu)成復(fù)合形，轉(zhuǎn)步驟2

5.計(jì)算映射點(diǎn)：

x(R)=x(S)+a(x(S)-x(H))

檢查是否在可行域內(nèi)是，a=1.3,轉(zhuǎn)步驟5否，轉(zhuǎn)步驟4是，轉(zhuǎn)步驟6否，a=0.5a,重新計(jì)算反射點(diǎn)步驟：是，a=1.3,轉(zhuǎn)步驟5是，轉(zhuǎn)步驟66.計(jì)算f(x(R))，若

7.若a>

:

檢查終止準(zhǔn)則

若f(x(R))<f(x(H))，以x(R)代替x(H)重構(gòu)復(fù)合形后轉(zhuǎn)步驟2f(x(R))≥f(x(H))，轉(zhuǎn)步驟7是，則a=0.5a，轉(zhuǎn)步驟5否，則調(diào)用收縮法或壓縮法，重構(gòu)復(fù)合形后轉(zhuǎn)步驟2是，則迭代結(jié)束，以此復(fù)合形的x(L)為x＊否，則以重構(gòu)的復(fù)合形轉(zhuǎn)步驟2f(x(R))<f(x(H))，以x(R)代替x(H)六.方法評(píng)價(jià)：

計(jì)算簡(jiǎn)單，不必求導(dǎo)，占內(nèi)存?。浑S著維數(shù)的增加，效率大大下降；不能解含等式約束的問(wèn)題；建議：①初始α取1.3。②n+1≤k≤2n，當(dāng)n≤5時(shí)，k取值接近2n；當(dāng)n>5時(shí)，k取值可小些。六.方法評(píng)價(jià)：計(jì)算簡(jiǎn)單，不必求導(dǎo)，占內(nèi)存??；建議：一.基本思想：在可行域內(nèi)選擇一個(gè)初始點(diǎn)x(0)，確定了一個(gè)可行方向和適當(dāng)?shù)牟介L(zhǎng)后，按照下式進(jìn)行迭代計(jì)算：

x(k+1)=x(k)+ad通過(guò)不斷的調(diào)整可行方向，使迭代點(diǎn)逐步逼近約束最優(yōu)點(diǎn)?！斓谒墓?jié)可行方向法一.基本思想：在可行域內(nèi)選擇一個(gè)初始點(diǎn)x(0)，確定了一二.搜索策略：

根據(jù)目標(biāo)函數(shù)和約束函數(shù)的不同性態(tài)，選擇不同的搜索策略。

①邊界反彈法：第一次搜索為負(fù)梯度方向，終止于邊

界。以后各次搜索方向均為適用可行方向，以最大

步長(zhǎng)從一個(gè)邊界反彈到另一個(gè)邊界，直至滿(mǎn)足收斂

條件。x(1)x(2)x(3)x*x(0)§第四節(jié)可行方向法二.搜索策略：根據(jù)目標(biāo)函數(shù)和約束函數(shù)的不同性態(tài)，選擇不同

②最優(yōu)步長(zhǎng)法：第一次搜索為負(fù)梯度方向，終止于邊

界。第二次搜索沿適用可行方向作一維搜索以最優(yōu)

步長(zhǎng)因子求得最優(yōu)點(diǎn)。反復(fù)以上兩步，直至得到最

優(yōu)點(diǎn)x*。x(1)x(2)x(3)x*x(0)§第四節(jié)可行方向法②最優(yōu)步長(zhǎng)法：第一次搜索為負(fù)梯度方向，終止于邊x(1)

③貼邊搜索法：第一次搜索為負(fù)梯度方向，終止于邊界。以后各次搜索貼邊（約束面）進(jìn)行。若適時(shí)約束面是線(xiàn)性約束，每次搜索到約束面的交集時(shí)，移至另一個(gè)約束面，經(jīng)過(guò)有限的幾步就可以收斂到最優(yōu)點(diǎn)。x(1)x(2)x*x(0)§第四節(jié)可行方向法③貼邊搜索法：x(1)x(2)x*x(0)§第四

若約束面是非線(xiàn)性時(shí)，從x(k)點(diǎn)沿切線(xiàn)（面）方向d(k)

搜索，會(huì)進(jìn)入非可行域。容差帶δ：

建立約束面的容差帶+δ，從x(k)

出發(fā)，沿d(k)方向搜索到d(k)方向與g(x)+δ=0的交點(diǎn)x’后，再沿適時(shí)約束的負(fù)梯度方向返回約束面的x(k+1)點(diǎn)。x(k)x(k+1)g(x)g(x)+

δx’-▽g(x)d(k)§第四節(jié)可行方向法若約束面是非線(xiàn)性時(shí)，從x(k)點(diǎn)沿切線(xiàn)（面）方調(diào)整步長(zhǎng)因子α1

：

x(k+1)=x’-a1▽g(x’)將g(x)在x’點(diǎn)泰勒展開(kāi)，取一階近似式：

g(x)≈g(x’)+[▽g(x’)]T(x-x’)進(jìn)而得到：

g(x(k+1))≈g(x’)+[▽g(x’)]T[-a1▽g(x’)]為了讓x(k+1)到達(dá)約束面，令g(x(k+1))=0得:§第四節(jié)可行方向法調(diào)整步長(zhǎng)因子α1：§第四節(jié)可行方向法三.可行方向的確定可行方向應(yīng)該滿(mǎn)足設(shè)計(jì)點(diǎn)可行及目標(biāo)函數(shù)值下降兩個(gè)條件

①可行條件:

[▽gj(xk)]T

dk≤0

j=1,2,…J(起作用約束的個(gè)數(shù))▽g(xk)dk▽g1(xk)▽g2(xk)dk§第四節(jié)可行方向法三.可行方向的確定可行方向應(yīng)該滿(mǎn)足設(shè)計(jì)點(diǎn)可行及目標(biāo)函數(shù)值下降三.可行方向的確定

②目標(biāo)函數(shù)值下降條件:

[▽f(xk)]T

dk<0

▽f(xk)dk§第四節(jié)可行方向法三.可行方向的確定▽f(xk)dk§第四節(jié)可行方三.可行方向的確定[▽gj(xk)]T

dk≤0

保證在可行域內(nèi)[▽f(xk)]T

dk<0

保證目標(biāo)函數(shù)值下降

可行方向§第四節(jié)可行方向法三.可行方向的確定[▽gj(xk)]Tdk≤0保①優(yōu)選方向法四.可行方向產(chǎn)生方法式中：d為求解變量，▽gj(xk)]T

、[▽f(xk)]T為定值，可用線(xiàn)性規(guī)劃方法求解§第四節(jié)可行方向法①優(yōu)選方向法四.可行方向產(chǎn)生方法式中：d為求解變量，▽②梯度投影法：可行方向:

其中:p為投影算子J-起作用的約束個(gè)數(shù)§第四節(jié)可行方向法②梯度投影法：J-起作用的約束個(gè)數(shù)§第四節(jié)可行方向法①取最優(yōu)步長(zhǎng)五.步長(zhǎng)的確定若x(k+1)為可行點(diǎn)，a＊作為本次迭代步長(zhǎng)

x(k+1)=x(k)+a＊da＊dx(k+1)

§第四節(jié)可行方向法①取最優(yōu)步長(zhǎng)五.步長(zhǎng)的確定若x(k+1)為可行點(diǎn)，a②取最大步長(zhǎng)aM五.步長(zhǎng)的確定a＊daMdx(k+1)

x(k+1)=x(k)+a＊d§第四節(jié)可行方向法②取最大步長(zhǎng)aM五.步長(zhǎng)的確定a＊daMdx(k+收斂條件2）設(shè)計(jì)點(diǎn)xk滿(mǎn)足庫(kù)恩-塔克條件1）設(shè)計(jì)點(diǎn)xk及約束允差滿(mǎn)足收斂條件2）設(shè)計(jì)點(diǎn)xk滿(mǎn)足庫(kù)恩-塔克條件1）設(shè)計(jì)點(diǎn)x例用可行方向法求約束優(yōu)化問(wèn)題的約束最優(yōu)解。Minf(x1,x2)=x12+2x22-10x1-x1x2-4x2+60s.t.g1(x)=x10

g2(x)=x20g3(x)=x160g4(x)=x280g5(x)=x1+x2110解：取初始點(diǎn)x0=[01]T，為約束邊界g1(x)=0上的一點(diǎn)。第一次迭代用優(yōu)選方向法確定可行方向。首先計(jì)算x0點(diǎn)的目標(biāo)函數(shù)f(x0)和約束函數(shù)g1(x0)的梯度例用可行方向法求約束優(yōu)化問(wèn)題的約束最優(yōu)解。為在可行下降扇形區(qū)內(nèi)尋找最優(yōu)方向，需求解一個(gè)以可行方向d=[d1d2]T為設(shè)計(jì)變量的線(xiàn)性規(guī)劃問(wèn)題，其數(shù)學(xué)模型為：為在可行下降扇形區(qū)內(nèi)尋找最優(yōu)方向，需求解一個(gè)以可行方向d=[最優(yōu)方向是d*=[0.9840.179]T，它是目標(biāo)函數(shù)等值線(xiàn)（直線(xiàn)束）和約束函數(shù)d12+d22=1（半徑為1的圓）的切點(diǎn)。第一次迭代的可行方向?yàn)閐0=d*。最優(yōu)方向是d*=[0.9840.179]T，它是目標(biāo)函第一次迭代的可行方向?yàn)閐0=d*。若步長(zhǎng)取0=6.098，則

可見(jiàn)第一次迭代點(diǎn)x1

在約束邊界g3(x1)=0上。

第一次迭代的可行方向?yàn)閐0=d*。若步長(zhǎng)取0=6.第二次迭代用梯度投影法來(lái)確定可行方向。迭代點(diǎn)x1的目標(biāo)函數(shù)負(fù)梯度-f(x1)=[0.0925.818]T，不滿(mǎn)足方向的可行條件?，F(xiàn)將f(x1)投影到約束邊界g3(x)=0上，

計(jì)算投影算子P本次迭代的可行方向?yàn)榈诙蔚锰荻韧队胺▉?lái)確定可行方向。迭代點(diǎn)x1的目標(biāo)函數(shù)負(fù)顯然，d1為沿約束邊界g3(x)=0的方向。若取1=2.909，則本次迭代點(diǎn)即為該問(wèn)題的約束最優(yōu)點(diǎn)x*則得約束最優(yōu)解

顯然，d1為沿約束邊界g3(x)=0的方向。若取1=2.9將有約束的優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題來(lái)求解。前提：一是不能破壞約束問(wèn)題的約束條件，二是使它歸結(jié)到原約束問(wèn)題的同一最優(yōu)解上去。

構(gòu)成一個(gè)新的目標(biāo)函數(shù)：§第五節(jié)

懲罰函數(shù)法懲罰項(xiàng)懲罰因子懲罰函數(shù)將有約束的優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題來(lái)求解。前提：一是不能從而保證懲罰項(xiàng)必須具有以下極限性質(zhì)：根據(jù)懲罰項(xiàng)的不同構(gòu)成形式，懲罰函數(shù)法又可分為內(nèi)點(diǎn)懲罰函數(shù)法、外點(diǎn)懲罰函數(shù)法和混合懲罰函數(shù)法§第五節(jié)

懲罰函數(shù)法從而保證懲罰項(xiàng)必須具有以下極限性質(zhì)：根據(jù)懲罰項(xiàng)的不同構(gòu)成一.內(nèi)點(diǎn)懲罰函數(shù)法基本思想內(nèi)點(diǎn)法將新目標(biāo)函數(shù)Φ(x,r)構(gòu)筑在可行域D內(nèi)，隨著懲罰因子r(k)的不斷遞減，生成一系列新目標(biāo)函數(shù)Φ(xk,

r(k))，在可行域內(nèi)逐步迭代，產(chǎn)生的極值點(diǎn)xk*(r(k))序列從可行域內(nèi)部趨向原目標(biāo)函數(shù)的約束最優(yōu)點(diǎn)x*。例：min.f(x)=x

s.t.g(x)=1-x≤0X1*X2*X*一.內(nèi)點(diǎn)懲罰函數(shù)法基本思想例：min.f(x)=2.懲罰函數(shù)的形式

①

②其中：懲罰（加權(quán)）因子

降低系數(shù)c：0<c<1當(dāng)x在可行域內(nèi)遠(yuǎn)離約束邊界時(shí)：當(dāng)x由可行城內(nèi)靠近約束邊界時(shí)：障礙項(xiàng)2.懲罰函數(shù)的形式其中：懲罰（加權(quán)）因子當(dāng)x在可行域內(nèi)遠(yuǎn)離3.幾個(gè)參數(shù)的選擇懲罰因子初始值r(0)

的選擇：

過(guò)大、過(guò)小均不好，建議考慮選擇r(0)=1或者：2.降低系數(shù)c的選擇：c的典型值為0.1～0.7。3.初始點(diǎn)x(0)

的選擇：要求：①在可行域內(nèi)；②不要離約束邊界太近。方法：①人工估算，需要校核可行性；②計(jì)算機(jī)隨機(jī)產(chǎn)生，也需校核可行性。3.幾個(gè)參數(shù)的選擇懲罰因子初始值r(0)的選擇：過(guò)大

③搜索方法：

任意給出一個(gè)初始點(diǎn)；判斷其可行性，若違反了S個(gè)約束，求出不滿(mǎn)足約束中的最大值：

應(yīng)用優(yōu)化方法減少違反約束：

以求得的設(shè)計(jì)點(diǎn)作為新初始點(diǎn)，繼續(xù)其判斷可行性，若仍有不滿(mǎn)足的約束，則重復(fù)上述過(guò)程，直至初始點(diǎn)可行。任意給出一個(gè)初始點(diǎn)；應(yīng)用優(yōu)化方法減少違反④

判斷是否收斂：4.步驟：①選取合適的初始點(diǎn)x(0)

，以及r(0)、c、計(jì)算精度ε1、ε2

，令k=0；

②

構(gòu)造懲罰（新目標(biāo)）函數(shù)；③調(diào)用無(wú)約束優(yōu)化方法，求新目標(biāo)函數(shù)的最優(yōu)解xk*和

Φ(xk,r(k))；若均滿(mǎn)足，停止迭代，有約束優(yōu)化問(wèn)題的最優(yōu)點(diǎn)為x*=xk*；若有一個(gè)準(zhǔn)則不滿(mǎn)足，則令并轉(zhuǎn)入第3步，繼續(xù)計(jì)算。④判斷是否收斂：4.步驟：①選取合適的初始點(diǎn)x(0例：用內(nèi)點(diǎn)法求下列問(wèn)題的最優(yōu)解：構(gòu)造懲罰函數(shù)例：用內(nèi)點(diǎn)法求下列問(wèn)題的最優(yōu)解：構(gòu)造懲罰函數(shù)機(jī)械優(yōu)化設(shè)計(jì)第6章約束優(yōu)化方法課件112112二.外點(diǎn)懲罰函數(shù)法1.基本原理外點(diǎn)法將新目標(biāo)函數(shù)Φ(x,r)構(gòu)筑在可行域D外，隨著懲罰因子r(k)的不斷遞增，生成一系列新目標(biāo)函數(shù)Φ(xk,r(k))，在可行域外逐步迭代，產(chǎn)生的極值點(diǎn)xk*(r(k))序列從可行域外部趨向原目標(biāo)函數(shù)的約束最優(yōu)點(diǎn)x*。新目標(biāo)函數(shù)：例：求下述約束優(yōu)化問(wèn)題的最優(yōu)點(diǎn)。

min.f(X)=x

x∈R1s.tg(X)=1-x≤0二.外點(diǎn)懲罰函數(shù)法1.基本原理新目標(biāo)函數(shù)：例：求下述懲罰函數(shù)可取為2)懲罰因子1)當(dāng)設(shè)計(jì)點(diǎn)在可行域內(nèi)時(shí),懲罰項(xiàng)為0,不懲罰;當(dāng)設(shè)計(jì)點(diǎn)在可行域外

時(shí),懲罰項(xiàng)大于0,有懲罰作用.外點(diǎn)法可以用來(lái)求解含不等式和等式約束的優(yōu)化問(wèn)題。衰減項(xiàng)懲罰函數(shù)可取為2)懲罰因子1)當(dāng)設(shè)計(jì)點(diǎn)在可行域內(nèi)時(shí),懲3.幾個(gè)參數(shù)的選擇①r(0)

的選擇:r(0)

過(guò)大，會(huì)使懲罰函數(shù)的等值線(xiàn)變形或偏心，求極

值困難。r(0)

過(guò)小，迭代次數(shù)太多。r(0)

＝1或者②x(0)

的選擇：基本上可以在可行域內(nèi)外，任意選擇。③遞增系數(shù)c的選擇：通常選擇5～10，可根據(jù)具體題目，進(jìn)行試算調(diào)整。3.幾個(gè)參數(shù)的選擇①r(0)的選擇:②x(0)的選內(nèi)點(diǎn)法特點(diǎn)：

（1）初始點(diǎn)必須為嚴(yán)格的可行點(diǎn)

（2）不適于具有等式約束的數(shù)學(xué)模型

（3）迭代過(guò)程中各個(gè)點(diǎn)均為可行設(shè)計(jì)方案

（4）一般收斂較慢

（5）初始懲罰因子要選擇得當(dāng)

（6）懲罰因子為遞減，遞減率c有0<c<1

外點(diǎn)法特點(diǎn)：

（1）初始點(diǎn)可以任選

（2）對(duì)等式約束和不等式約束均可適用

（3）僅最優(yōu)解為可行設(shè)計(jì)方案

（4）一般收斂較快

（5）初始罰因子要選擇得當(dāng)

（6）罰因子為遞增，遞增率c有c>1內(nèi)點(diǎn)法特點(diǎn)： 三.

混合懲罰函數(shù)法1.基本思想采用內(nèi)點(diǎn)法和外點(diǎn)法相結(jié)合的混合懲罰函數(shù)法，以發(fā)揮內(nèi)點(diǎn)法和外點(diǎn)法的特點(diǎn)，處理既有等式約束，又有不等式約束的優(yōu)化設(shè)計(jì)問(wèn)題。2.懲罰函數(shù)的形式一般既包括障礙項(xiàng)，也包括衰減項(xiàng)。三.混合懲罰函數(shù)法1.基本思想采用內(nèi)點(diǎn)法和外點(diǎn)法相結(jié)合懲罰函數(shù)法優(yōu)點(diǎn)：原理簡(jiǎn)單，算法易行，適應(yīng)范圍廣，可利用無(wú)約束最優(yōu)化方法資源。缺點(diǎn)：（1）初始懲罰因子r(0)取值不當(dāng)可導(dǎo)致懲罰函數(shù)變得病態(tài)，

使無(wú)約束優(yōu)化計(jì)算困難。（2）理論上講，只有懲罰因子r

(k)

0（內(nèi)點(diǎn)法）或

r(k)

趨于無(wú)窮（外點(diǎn)法）時(shí)，算法才收斂，因此序

列迭代過(guò)程收斂速度慢。增廣乘子法外點(diǎn)懲罰函數(shù)＋拉格朗日函數(shù)

計(jì)算過(guò)程穩(wěn)定，計(jì)算效率超過(guò)懲罰函數(shù)法懲罰函數(shù)法拉格朗日函數(shù)一、拉格朗日乘子法（升維法）§第六節(jié)

增廣乘子法l+n個(gè)方程l+n個(gè)未知變量具有相同的最優(yōu)解X*拉格朗日函數(shù)一、拉格朗日乘子法（升維法）§第六節(jié)增廣乘子例:用拉格朗日乘子法求下列問(wèn)題的最優(yōu)解解構(gòu)造拉格朗日函數(shù)令▽L=0,得到求解得：例:用拉格朗日乘子法求下列問(wèn)題的最優(yōu)解解構(gòu)造拉格朗日函數(shù)令構(gòu)造拉格朗日函數(shù)構(gòu)造外點(diǎn)懲罰函數(shù)構(gòu)造拉格朗日函數(shù)構(gòu)造外點(diǎn)懲罰函數(shù)二.等式約束的增廣乘子法

采用拉格朗日乘子法時(shí)求解有難度,而罰函數(shù)法當(dāng)?shù)c(diǎn)接近邊界時(shí)函數(shù)常有病態(tài),此法的思路是把兩者結(jié)合起來(lái)。其增廣拉格朗日函數(shù)為:二.等式約束的增廣乘子法采用拉格朗日乘子法時(shí)求解有難等式約束增廣乘子法不論r(k)取何值，增廣乘子函數(shù)與原函數(shù)具有相同的約束極值點(diǎn)X*，與拉格朗日函數(shù)有相同的拉格朗日乘子向量。等式約束增廣乘子法不論r(k)取何值，增廣乘子函數(shù)與原函數(shù)具等式約束增廣乘子法等式約束增廣乘子法等式約束增廣乘子法增廣乘子法中的乘子迭代等式約束增廣乘子法增廣乘子法中的乘子迭代等式約束增廣乘子法參數(shù)選取沒(méi)有其它信息情況下，初始乘子向量

增廣乘子函數(shù)和外點(diǎn)懲罰函數(shù)形式相同；從第二次迭代開(kāi)始，乘子向量按式子進(jìn)行校正。懲罰因子初始值r(0)按照外點(diǎn)法取。從第二次迭代開(kāi)始，懲罰因子按下式遞增：懲罰因子遞增系數(shù)，C=10判別數(shù)，通常取0.25等式約束增廣乘子法參數(shù)選取沒(méi)有其它信息情況下，初始乘子向量機(jī)械優(yōu)化設(shè)計(jì)第6章約束優(yōu)化方法課件等式約束增廣乘子法計(jì)算步驟：

選取設(shè)計(jì)變量的初始點(diǎn)x0，懲罰因子初值r0，增長(zhǎng)系數(shù)β，判別數(shù)δ，收斂精度ε，乘子向量λp0=0

(p=1,2,…l),迭代次數(shù)k=0；構(gòu)造增廣乘子函數(shù)M(x,λ,r)，并用無(wú)約束方法求

min

M(x,λ,r)，得無(wú)約束最優(yōu)解xk=x*(λk,rk)計(jì)算校正乘子向量如果，迭代終止，約束最優(yōu)解為x*=xk，λ*=λk+1;否則轉(zhuǎn)步驟6計(jì)算懲罰因子再令k=k+1，轉(zhuǎn)步驟2等式約束增廣乘子法計(jì)算步驟：例:用拉格朗日乘子法求下列問(wèn)題的最優(yōu)解解構(gòu)造增廣乘子函數(shù)確定初始參數(shù)：

C＝2,

λ0=0,

r0=0.1，例:用拉格朗日乘子法求下列問(wèn)題的最優(yōu)解解構(gòu)造增廣乘子函數(shù)確利用解析法求min

M(X,λ,r)，令▽M(X,λ,r)＝0，可得最優(yōu)解：

利用解析法求minM(X,λ,r)，令▽M(X,λ,r迭代6次得到最優(yōu)解,迭代結(jié)果如下:精確解:

X*=[0.25,0.75],

f(X*)=0.125迭代6次得到最優(yōu)解,迭代結(jié)果如下:精確解:X*=[0.25不等式約束增廣乘子法用于求解不等式約束優(yōu)化問(wèn)題。引入松弛變量Z＝[z1,

z2

,

…,

zm]T,并且令則不等式約束優(yōu)化問(wèn)題轉(zhuǎn)化為等式優(yōu)化問(wèn)題不等式約束增廣乘子法用于求解不等式約束優(yōu)化問(wèn)題。引入松弛變量不等式約束增廣乘子法構(gòu)造增廣乘子函數(shù)由于引入松弛變量Z，使原有的n維極值問(wèn)題擴(kuò)充為n+m維問(wèn)題，計(jì)算工作量和求解難度增大，可簡(jiǎn)化。不等式約束增廣乘子法構(gòu)造增廣乘子函數(shù)由于引入松弛變量Z，使原不等式約束增廣乘子法不等式約束增廣乘子法同時(shí)具有等式和不等式約束的增廣乘子法同時(shí)具有等式和不等式約束的增廣乘子法第七節(jié)非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法——線(xiàn)性逼近法一、序列線(xiàn)性規(guī)劃法這個(gè)方法的基本思想：在某個(gè)近似解處將約束函數(shù)和目標(biāo)函數(shù)進(jìn)行泰勒展開(kāi)，只保留一次項(xiàng)，從而將非線(xiàn)性規(guī)劃問(wèn)題變成線(xiàn)性規(guī)劃問(wèn)題。求解此線(xiàn)性規(guī)劃，并將其最優(yōu)解作為原來(lái)問(wèn)題新的近似解，再展開(kāi)成新的線(xiàn)性規(guī)劃問(wèn)題，再求解。如此重復(fù)下去，一直到相鄰兩次最優(yōu)解足夠接近時(shí)為止。缺點(diǎn)：序列線(xiàn)性規(guī)劃法收斂較慢，且最后的近似解不滿(mǎn)足非線(xiàn)性約束，有時(shí)還會(huì)出現(xiàn)不收斂的情況。為了獲得較好的收斂性而采用一些改進(jìn)的方法，如割平面法、小步梯度法等。第七節(jié)非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法——線(xiàn)性逼近法第七節(jié)非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法——線(xiàn)性逼近法二、割平面法割平面法主要用于不等式約束的非線(xiàn)性規(guī)劃問(wèn)題。若問(wèn)題是凸規(guī)劃問(wèn)題，則這種方法將收斂于問(wèn)題的最優(yōu)解。對(duì)于非凸規(guī)劃問(wèn)題，某些約束的線(xiàn)性近似可能把原問(wèn)題可行域切掉一些，可能最優(yōu)點(diǎn)恰好就在這些被切去的區(qū)域里。因?yàn)檫@種方法實(shí)際上是用線(xiàn)性近似約束把原問(wèn)題可行域切掉一部分，所以稱(chēng)為“割平面法”。第七節(jié)非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法——線(xiàn)性逼近法第七節(jié)非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法——線(xiàn)性逼近法三、小步梯度法線(xiàn)性逼近法求解是指按下面的迭代公式對(duì)設(shè)計(jì)點(diǎn)進(jìn)行修改，從而獲得新的設(shè)計(jì)點(diǎn)的方法。當(dāng)把上式寫(xiě)成而是一個(gè)小數(shù)值時(shí)，可把此式作為一個(gè)約束列入原問(wèn)題中去求解。當(dāng)用梯度法求解時(shí)，這種方法就是用一個(gè)小數(shù)值限制各尋優(yōu)方向步長(zhǎng)的方法，可稱(chēng)為小步梯度法。只有當(dāng)是可行解時(shí)，此法收斂較快，否則過(guò)程收斂較慢。第七節(jié)非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法——線(xiàn)性逼近法第七節(jié)非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法——線(xiàn)性逼近法四、非線(xiàn)性規(guī)劃法對(duì)于燈飾和不等式約束的給線(xiàn)性規(guī)劃問(wèn)題，有一種解法是把最速下降法（梯度法）和線(xiàn)性規(guī)劃法結(jié)合起來(lái)求解。它的解法步驟如下：第一步，當(dāng)是不可行點(diǎn)時(shí)，用最速下降法把它拉到滿(mǎn)足約束集內(nèi)。此時(shí)的函數(shù)形式取為：第二步，再用線(xiàn)性規(guī)劃法。每次線(xiàn)性規(guī)劃階段移步后，要進(jìn)行一次判別，看是否滿(mǎn)足此法的使用效果好于前兩種方法。第七節(jié)非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法——線(xiàn)性逼近法第七節(jié)非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法——線(xiàn)性逼近法四、非線(xiàn)性規(guī)劃法對(duì)于線(xiàn)性規(guī)劃問(wèn)題，也可以通過(guò)泰勒級(jí)數(shù)展開(kāi)的方法把約束取成線(xiàn)性的，目標(biāo)函數(shù)取成二次函數(shù)。這種約束為線(xiàn)性而目標(biāo)函數(shù)是二次函數(shù)的最優(yōu)問(wèn)題。有多種求解二次規(guī)劃問(wèn)題的方法，其中一種實(shí)際上可以看成是線(xiàn)性規(guī)劃問(wèn)題中單純形法的推廣。因此，用這樣的處理辦法來(lái)解決非線(xiàn)性規(guī)劃問(wèn)題可以稱(chēng)為二次規(guī)劃問(wèn)題的線(xiàn)性規(guī)劃解法。第七節(jié)非線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性化解法——線(xiàn)性逼近法第八節(jié)廣義簡(jiǎn)約梯度法廣義簡(jiǎn)約梯度法也稱(chēng)GRG法。它是簡(jiǎn)約梯度法推廣到求解具有非線(xiàn)性約束的優(yōu)化問(wèn)題的一種方法。這種方法是目前求解一般非線(xiàn)性?xún)?yōu)化問(wèn)題的最有效的算法之一。一、簡(jiǎn)約梯度法簡(jiǎn)約梯度法僅用來(lái)求解具有線(xiàn)性等式約束的優(yōu)化問(wèn)題。算法的基本思想是設(shè)法處理約束函數(shù)，將原問(wèn)題轉(zhuǎn)化成僅具有變量邊界約束的優(yōu)化問(wèn)題，然后求解。第八節(jié)廣義簡(jiǎn)約梯度法第八節(jié)廣義簡(jiǎn)約梯度法二、廣義簡(jiǎn)約梯度法廣義簡(jiǎn)約梯度法可以用來(lái)求解具有非線(xiàn)性等式約束和變量界限約束的優(yōu)化問(wèn)題，其數(shù)學(xué)模型為式中的為變量的下界和上界值。第八節(jié)廣義簡(jiǎn)約梯度法第八節(jié)廣義簡(jiǎn)約梯度法三、不等式約束函數(shù)的處理和換基問(wèn)題1.不等式簡(jiǎn)約梯度法求解的處理方法用廣義簡(jiǎn)約梯度法求解具有不等式約束函數(shù)的優(yōu)化問(wèn)題時(shí)，需引進(jìn)新變量，將不等式約束函數(shù)轉(zhuǎn)化成等式約束函數(shù)，即將該問(wèn)題轉(zhuǎn)化成與式（6-107）相同的形式，然后按前述方法求解。第八節(jié)廣義簡(jiǎn)約梯度法第八節(jié)廣義簡(jiǎn)約梯度法三、不等式約束函數(shù)的處理和換基問(wèn)題2.基變量的選擇和換基問(wèn)題按廣義簡(jiǎn)約梯度法原理，首先應(yīng)將涉及變量分成基變量和非基變量，對(duì)于只具有等式函數(shù)的問(wèn)題，應(yīng)在n設(shè)計(jì)變量中選擇m個(gè)變量作為基變量，對(duì)于具有不等式約束函數(shù)的問(wèn)題，應(yīng)在n+l個(gè)變量中選擇m+l個(gè)變量作為基變量（l為松弛變量數(shù)），其余的變量為非基變量。為了使基變量的變化盡量少，應(yīng)選擇遠(yuǎn)離其邊界的變量為基變量。同時(shí)，為了保證基矩陣非奇異及求逆計(jì)算的穩(wěn)定，要求基矩陣的主元不能太小以及同列中的其他元素與主元之比不能太大。在迭代過(guò)程中，若某一基變量等于0，或等于邊界值時(shí)，應(yīng)換基變量，即選擇一非基變量來(lái)代替該基變量。第八節(jié)廣義簡(jiǎn)約梯度法第九節(jié)二次規(guī)劃法二次規(guī)劃法的基本原理是將元問(wèn)題轉(zhuǎn)化為一系列二次規(guī)劃的子問(wèn)題。求解子問(wèn)題，得到本次迭代的搜索方向，沿搜索方向?qū)?yōu)，最終逼近問(wèn)題的最優(yōu)點(diǎn)，因此，這種方法又稱(chēng)為序列二次規(guī)劃法。另外，算法是利用擬牛頓法（變尺度法）來(lái)近似構(gòu)造海塞矩陣，以建立二次規(guī)劃子問(wèn)題，故又可稱(chēng)為約束變尺度法，這種方法被認(rèn)為是目前最先進(jìn)的非線(xiàn)性規(guī)劃計(jì)算方法。第九節(jié)二次規(guī)劃法第九節(jié)二次規(guī)劃法二次規(guī)劃法的迭代步驟如下：1.給定初始值，令（單位矩陣）。2.計(jì)算原問(wèn)題的函數(shù)值、梯度值，構(gòu)造二次規(guī)劃子問(wèn)題。3.求解二次規(guī)劃子問(wèn)題，確定新的乘子矢量和搜索方向。4.沿進(jìn)行一維搜索，確定步長(zhǎng)，得到新的近似極小點(diǎn)。5.若滿(mǎn)足收斂精度則停止計(jì)算，否則轉(zhuǎn)至下步。6.采用擬牛頓公式（如BFGS公式）對(duì)進(jìn)行修正，得到，返回步驟2.第九節(jié)二次規(guī)劃法第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述在工程結(jié)構(gòu)設(shè)計(jì)中，通常要在保證性能約束條件下，滿(mǎn)足結(jié)構(gòu)體積盡量小以減輕重量或節(jié)約材料。在進(jìn)行結(jié)構(gòu)設(shè)計(jì)時(shí)，性能約束一般是取結(jié)構(gòu)固有頻率禁區(qū)約束、振型約束、結(jié)構(gòu)變形或許用應(yīng)力約束。以準(zhǔn)則法思想為基礎(chǔ)的優(yōu)化準(zhǔn)則法，對(duì)于結(jié)構(gòu)優(yōu)化來(lái)說(shuō)，它是一種收斂速度快、求解目標(biāo)函數(shù)和約束函數(shù)次數(shù)少的一種方法。準(zhǔn)則法思想是由“滿(mǎn)應(yīng)力設(shè)計(jì)”和“同步失效準(zhǔn)則”原則，且主要是針對(duì)桁架結(jié)構(gòu)的最輕設(shè)計(jì)發(fā)展起來(lái)的。第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述一、準(zhǔn)則方程二、迭代乘子C三、優(yōu)化準(zhǔn)則法和數(shù)學(xué)規(guī)劃法的相似性質(zhì)四、形狀優(yōu)化和拓?fù)洳季謨?yōu)化五、小結(jié)第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述一、準(zhǔn)則方程任何一個(gè)設(shè)計(jì)方案是否是最優(yōu)的基本檢驗(yàn)方法就是看它是否滿(mǎn)足K-T條件。優(yōu)化問(wèn)題的準(zhǔn)則方程是由所討論的優(yōu)化問(wèn)題的最優(yōu)解應(yīng)滿(mǎn)足K-T條件推導(dǎo)出來(lái)的。這時(shí)的迭代公式用來(lái)尋求滿(mǎn)足K-T條件的極小值點(diǎn)（設(shè)計(jì)點(diǎn)）。第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述二、迭代乘子C考慮到結(jié)構(gòu)性能約束函數(shù)常是隱含設(shè)計(jì)變量的非線(xiàn)性方程，對(duì)式（6-127）的準(zhǔn)則方程的求解可采用線(xiàn)性迭代的方法。這種求解從某個(gè)初始設(shè)計(jì)變量開(kāi)始，按迭代公式反復(fù)進(jìn)行線(xiàn)性迭代，直到求出滿(mǎn)足準(zhǔn)則方的設(shè)計(jì)變量。這種優(yōu)化準(zhǔn)則就具有數(shù)學(xué)規(guī)劃法的性質(zhì)，是準(zhǔn)則思想和數(shù)學(xué)規(guī)劃的結(jié)合，故稱(chēng)為優(yōu)化準(zhǔn)則法。第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述三、優(yōu)化準(zhǔn)則法和數(shù)學(xué)規(guī)劃法的相似性質(zhì)雖然在滿(mǎn)應(yīng)力設(shè)計(jì)的一類(lèi)準(zhǔn)則設(shè)計(jì)中，不考慮目標(biāo)函數(shù)值，因而其解不是最優(yōu)解。這反映了它和數(shù)學(xué)規(guī)劃法的不同，這是它的特點(diǎn)。但是，在優(yōu)化準(zhǔn)則法中，由于準(zhǔn)則方程是目標(biāo)函數(shù)梯度換和諸約束梯度的線(xiàn)性組合，所以已經(jīng)失去了原來(lái)的滿(mǎn)應(yīng)力類(lèi)設(shè)計(jì)與目標(biāo)函數(shù)無(wú)關(guān)的特點(diǎn)，而具有數(shù)學(xué)規(guī)劃法的性質(zhì)。它實(shí)際上已經(jīng)把準(zhǔn)則法和數(shù)學(xué)規(guī)劃法結(jié)合起來(lái)了。第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述四、形狀優(yōu)化和拓?fù)洳季謨?yōu)化一種以極大值原理為基礎(chǔ)——把優(yōu)化問(wèn)題表示為泛函極值形式的求解結(jié)構(gòu)形式的理論和方法的應(yīng)用，實(shí)現(xiàn)了從有限維的參數(shù)優(yōu)化向無(wú)限維的形狀優(yōu)化和拓?fù)浼安季謨?yōu)化的跨越。這種無(wú)限維的優(yōu)化方法是一種連續(xù)型的分析方法，它是基于結(jié)構(gòu)的彈性力學(xué)模型和泛函極值的求解方法。連續(xù)體的形狀和拓?fù)浼安季謨?yōu)化設(shè)計(jì)需要建立研究對(duì)象的幾何和分析模型，這既涉及用相應(yīng)的優(yōu)化設(shè)計(jì)變量對(duì)邊界形狀和布局進(jìn)行有效的描述，也需要處理與有限元分析相關(guān)的敏度分析和網(wǎng)絡(luò)生成等問(wèn)題。第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述五、小結(jié)求解非線(xiàn)性規(guī)劃問(wèn)題可概括為如下三種迭代格式：1）（搜索格式）2）（替代格式）3）（收斂格式）前兩種屬于數(shù)學(xué)規(guī)劃類(lèi)方法，后一種屬于優(yōu)化準(zhǔn)則方法。第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述五、小結(jié)總得策略：一是在可行域內(nèi)直接搜索最優(yōu)設(shè)計(jì)點(diǎn)；二是把非線(xiàn)性問(wèn)題轉(zhuǎn)化為線(xiàn)性問(wèn)題，采用線(xiàn)性規(guī)劃方法求解；三是把約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題，采用無(wú)約束方法求解。具體方法是：1）直接方法——以約束條件為界面，形成一個(gè)解的可行域，在可行域范圍內(nèi)直接采用無(wú)約束優(yōu)化方法求解。2）線(xiàn)性逼近法——把非線(xiàn)性函數(shù)在現(xiàn)行點(diǎn)線(xiàn)性化，采用較成熟的線(xiàn)性規(guī)劃方法。3）簡(jiǎn)接方法——先把約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題，再采用無(wú)約束優(yōu)化方法求解。這種方法可以分為兩類(lèi)，即降維方法和升維方法。第十節(jié)結(jié)構(gòu)優(yōu)化簡(jiǎn)述Powell法、梯度法隨機(jī)方向法、復(fù)合形法、懲罰函數(shù)法常規(guī)優(yōu)化算法啟發(fā)式算法(現(xiàn)代優(yōu)化計(jì)算方法)

適于求解高非線(xiàn)性、多約束、多極值問(wèn)題遺傳算法（Geneticalgorithms）神經(jīng)網(wǎng)絡(luò)優(yōu)化算法（Neuralnetworksoptimization）混合優(yōu)化算法（Hybridoptimization）§第十一節(jié)

遺傳算法簡(jiǎn)述Powell法、梯度法常規(guī)優(yōu)化算法啟發(fā)式算法(現(xiàn)代優(yōu)化計(jì)算方一.背景：生物進(jìn)化基本循環(huán)圖

依據(jù)生物進(jìn)化論的“適者生存”規(guī)律而提出：§第十一節(jié)

遺傳算法簡(jiǎn)述一.背景：生物進(jìn)化基本循環(huán)圖依據(jù)生物進(jìn)化論的

遺傳算法的主要生物進(jìn)化特征體現(xiàn)在：（1）進(jìn)化發(fā)生在解的編碼（染色體）上。（2）自然選擇規(guī)律決定優(yōu)秀的染色體產(chǎn)生超過(guò)平均數(shù)的后代。遺傳算法通過(guò)優(yōu)化目標(biāo)構(gòu)造適應(yīng)函數(shù)以達(dá)到好的染色體超過(guò)平均數(shù)的后代。（3）染色體結(jié)合時(shí)，雙親的遺傳基因結(jié)合使得子女保持父母的特征。（4）當(dāng)染色體結(jié)合后，隨機(jī)變異會(huì)造成子代與父代不同?！斓谑还?jié)

遺傳算法簡(jiǎn)述遺傳算法的主要生物進(jìn)化特征體現(xiàn)在：§第十一節(jié)二.基本思想：

遺傳算法在求解優(yōu)化問(wèn)題時(shí)首先對(duì)求解空間的各個(gè)解進(jìn)行編碼。在尋優(yōu)過(guò)程中，通過(guò)對(duì)染色體

進(jìn)行結(jié)合（選擇、交配和變異），不斷產(chǎn)生新的解，進(jìn)而根據(jù)適應(yīng)函數(shù)在新解中選擇部分染色體繼續(xù)進(jìn)行結(jié)合，直至最終找到最好的解?！斓谑还?jié)

遺傳算法簡(jiǎn)述二.基本思想：遺傳算法在求解優(yōu)化問(wèn)題時(shí)首先對(duì)

例用遺傳算法求minf(x1,x2)=x1+x2

，當(dāng)x1和x2為整數(shù)時(shí)的整數(shù)解，且解：若用4位二進(jìn)制編碼表示一個(gè)設(shè)計(jì)變量xi，則一個(gè)解(x1,x2)需用8位二進(jìn)制編碼表示：例用遺傳算法求minf(x1,x2)=x1遺傳算法4個(gè)組成部分：編碼和解碼、適應(yīng)函數(shù)、遺傳算子和控制參數(shù)若以這4個(gè)個(gè)體為群體，按求解的要求，適應(yīng)函數(shù)值小的染色體的生存概率較大，則能競(jìng)爭(zhēng)上的是N1、N3和N4點(diǎn)，其交配方式如下：通過(guò)分別交換基因，實(shí)現(xiàn)了交配，得到了4個(gè)新個(gè)體N1’、N2’、N3’和N4’。若對(duì)某個(gè)個(gè)體（例如N2’）進(jìn)行基因變異（1→0），可得N2”:00100001(=3)遺傳算法4個(gè)組成部分：若以這4個(gè)個(gè)體為群體，按求解的要求，適三.算法的基本步驟：S.1選擇優(yōu)化問(wèn)題求解的一種編碼；S.2隨機(jī)產(chǎn)生N個(gè)染色體的初始群體{pop(k),k=0}；S.3對(duì)群體中的每個(gè)染色體popi(k)計(jì)算適應(yīng)函數(shù)

fi=fitness(popi(k))S.4若滿(mǎn)足終止規(guī)則，則轉(zhuǎn)向S.9，否則計(jì)算概率S.5以概率pi從pop

(k)中隨機(jī)選一些染色體構(gòu)成一個(gè)新群體（其中可以重復(fù)選pop

(k)中的元素）

newpop(k+1)={popi(k),i=1,2,···,N}§第十一節(jié)

遺傳算法簡(jiǎn)述三.算法的基本步驟：S.1選擇優(yōu)化問(wèn)題求解的一種編碼三.算法的基本步驟：S.6通過(guò)交配，按交配概率pc得到一個(gè)有N個(gè)染色體的交配群體crosspop(k+1)；S.7以一個(gè)較小的變異概率pm，使得一個(gè)染色體的基因發(fā)生變異，形成變異群體mutpop(k+1)；S.8令k=k+1和popi(k)=mutpop(k+1)，返回S.3；S.9終止計(jì)算，輸出最優(yōu)結(jié)果。§第十一節(jié)

遺傳算法簡(jiǎn)述三.算法的基本步驟：S.6通過(guò)交配，按交配概率pc四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——編碼和解碼編碼——由設(shè)計(jì)空間向編碼空間的映射。將設(shè)計(jì)解用字符串表示的過(guò)程。編碼的選擇是影響算法性能和效率的重要因素。解碼——由編碼空間向設(shè)計(jì)空間的映射?！斓谑还?jié)

遺傳算法簡(jiǎn)述四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——編碼和解碼幾種常見(jiàn)的編碼方式四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——編碼和解碼

§第十一節(jié)

遺傳算法簡(jiǎn)述幾種常見(jiàn)的編碼方式四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——編碼對(duì)于求極大化的目標(biāo)函數(shù)（max

f(x)），可通過(guò)下面轉(zhuǎn)換建立與fitness(x)的映射關(guān)系:四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——適應(yīng)函數(shù)fitness(x)

對(duì)于求極小化的目標(biāo)函數(shù)（min

f(x)），可通過(guò)下面轉(zhuǎn)換建立與fitness(x)的映射關(guān)系:Cmin和Cmax為可調(diào)參數(shù)，所取的值應(yīng)使適應(yīng)函數(shù)fitness(x)恒大于0。適應(yīng)函數(shù)——用于對(duì)個(gè)體進(jìn)行評(píng)價(jià)，即反映個(gè)體對(duì)環(huán)境適應(yīng)能力。是優(yōu)化進(jìn)程發(fā)展的依據(jù)。其值必須大于等于零§第十一節(jié)

遺傳算法簡(jiǎn)述對(duì)于求極大化的目標(biāo)函數(shù)（maxf(x)），可通過(guò)下面群體規(guī)模N——是影響算法性能和效率的因素之一。規(guī)模太小，不能提供足夠多的采樣點(diǎn)；規(guī)模太大，計(jì)算量大，耗時(shí)長(zhǎng)。通常取N介于n（編碼長(zhǎng)度）和2n之間，或依據(jù)經(jīng)驗(yàn)在范圍內(nèi)取值。四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——算法參數(shù)

交配概率pc

——用于控制交配操作的頻率，通常取0.4~0.9之間。概率太大，種群更新過(guò)快，會(huì)使高適應(yīng)函數(shù)值的個(gè)體過(guò)快被破壞；概率太小，交配操作很少進(jìn)行，搜索速度慢，耗時(shí)長(zhǎng)。變異概率pm

——加大種群多樣性的重要因素，通常取0.001~0.1之間。概率太大，則使遺傳算法退化成隨機(jī)搜索算法；概率太小，產(chǎn)生新個(gè)體的機(jī)會(huì)太小?！斓谑还?jié)

遺傳算法簡(jiǎn)述群體規(guī)模N——是影響算法性能和效率的因素之一。四.復(fù)制、交配、變異四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——遺傳算子

復(fù)制(選擇)

—選擇用于繁殖后代的雙親。體現(xiàn)“適者生存”，適應(yīng)度高，生存概率大。依據(jù)選擇概率pi=fi/Σfi進(jìn)行。交配(交叉)

—兩個(gè)相互配對(duì)的染色體（雙親）按某種方式相互交換其部分基因而生成兩個(gè)新的個(gè)體。§第十一節(jié)

遺傳算法簡(jiǎn)述復(fù)制、交配、變異四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——遺傳算四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——遺傳算子

一點(diǎn)交配（二進(jìn)制）：多點(diǎn)交配（二進(jìn)制）：§第十一節(jié)

遺傳算法簡(jiǎn)述四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——遺傳算子四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——遺傳算子

變異

—在交配之后進(jìn)行。將個(gè)體染色體編碼字符中的某些基因用其他等位基因替換，從而生成新的染色體。作用：保持群體中個(gè)體的多樣性，有效地防止算法早熟收斂。方法：按位進(jìn)行，以概率pm改變字符串上某一位基因。例：變異（二進(jìn)制）§第十一節(jié)

遺傳算法簡(jiǎn)述四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——遺傳算子四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——算法終止準(zhǔn)則

事先規(guī)定出一個(gè)最大的進(jìn)化步數(shù)，到達(dá)此步數(shù)時(shí)終止(一般取100-500代)。判斷當(dāng)前最好的解已連續(xù)若干步?jīng)]有變化。算法已找到了一個(gè)可接受的最好解?！斓谑还?jié)

遺傳算法簡(jiǎn)述四.算法實(shí)現(xiàn)的幾個(gè)技術(shù)問(wèn)題——算法終止準(zhǔn)則

遺傳算法應(yīng)用舉例

例1:利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2最大時(shí)的整數(shù)解。y=x2

31

xy遺傳算法應(yīng)用舉例例1:利用遺傳算法求解區(qū)間［0,31］上解:

(1)設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群S1:s1=01101,s2=11000s3=01000,s4=10011(2)定義適應(yīng)度函數(shù):f(x)=x2(3)計(jì)算各代種群中每個(gè)個(gè)體的適應(yīng)度值,并相應(yīng)對(duì)其染色體進(jìn)行遺傳操作。解:

首先計(jì)算種群S1中各個(gè)體的適應(yīng)度f(wàn)(si)。

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361首先計(jì)算種群S1中各個(gè)體的適應(yīng)度f(wàn)(si)再計(jì)算種群S1中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31再計(jì)算種群S1中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為由此

賭輪選擇示意s40.31s20.49s10.14s30.06

賭輪選擇法賭輪選擇示意s4s2s1s30.06賭輪選擇法

在算法中賭輪選擇法可用下面的子過(guò)程來(lái)模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③

若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其

中的qi稱(chēng)為染色體xi(i=1,2,…,n)的積累概

率,其計(jì)算公式為在算法中賭輪選擇法可用下面的子過(guò)程來(lái)模擬:①在［選擇-復(fù)制

設(shè)從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù)如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

選擇-復(fù)制設(shè)從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù)如交配(交叉)設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。設(shè)s1’與s2’配對(duì)，s3’與s4’配對(duì)。分別交換后兩位基因，得新染色體：

s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

于是，經(jīng)復(fù)制得新群體：

s1’=11000（24）,s2’=01101（13）

s3’=11000（24）,s4’=10011（19）交配(交叉)于是，經(jīng)復(fù)制得新群體：變異:變異率pm=0.001。這樣，群體S1中共有

5×4×0.001=0.02位基因可以變異。0.02位顯然不足1位，所以本輪遺傳操作不做變異。于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）變異:變異率pm=0.001。于是，得到第二代種群S2：

第二代種群S2中各染色體的情況第二代種群S2中各染色體的情況

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體：s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交配(交叉)運(yùn)算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

這一輪仍然不會(huì)發(fā)生變異。

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的s1’=11

第三代種群S3中各染色體的情況于是，得第三代種群S3：

s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第三代種群S3中各染色體的情況于是，得第三代種群S3

設(shè)這一輪的選擇-復(fù)制結(jié)果為：

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交配(交叉)運(yùn)算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

這一輪仍然不會(huì)發(fā)生變異。設(shè)這一輪的選擇-復(fù)制結(jié)果為：做交配(交叉顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問(wèn)題的解，即函數(shù)y=x2的最大值為961。

于是，得第四代種群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=YYy=x2

8131924

X第一代種群y=x2

12162527

XY第二代種群y=x2

9192428

XY第三代種群y=x2

16242831

X第四代種群YYy=x28131924例2:求下列函數(shù)的最大值。

maxf(x1,

x2)=100(x12-x22)2+(1-x1)2s.t.-2.048≤xi

≤2.048(i=1,2)該函數(shù)有兩個(gè)局部極大點(diǎn)，分別是:

f(2.048,-2.048)=3897.7342

和

f(-2.048,-2.048)=3905.9262其中后者為全局最大點(diǎn)。例2:求下列函數(shù)的最大值。該函數(shù)有兩個(gè)局部極大點(diǎn)，分別解：第一步：確定編碼方法。用長(zhǎng)度為l0位的二進(jìn)制(最大可表示1023)表示一個(gè)變量。從離散點(diǎn)-2.048到離散點(diǎn)2.048，依次讓它們分別對(duì)應(yīng)于從0000000000(0)到1111111111(1023)之間的二進(jìn)制編碼。再將分別表示x1和x2的二個(gè)10位長(zhǎng)的二進(jìn)制編碼串連接在一起，組成一個(gè)20位長(zhǎng)的二進(jìn)制編碼串，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問(wèn)題的染色體編碼方法。例如

X：00001

101111101110001就表示一個(gè)個(gè)體。解：第二步：確定解碼方法。

解碼時(shí)先將20位長(zhǎng)的二進(jìn)制編碼串切斷為二個(gè)10位長(zhǎng)的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2。依據(jù)前述個(gè)體編碼方法相對(duì)定義域的離散化方法可知，將代碼yi

轉(zhuǎn)換為變量xi的解碼公式為：例如，對(duì)前述個(gè)體

X：0000110111110111000