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

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

6.3復(fù)合形方法

6.4可行方向法

6.5懲罰函數(shù)法

6.6增廣乘子法

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

6.9二次規(guī)劃法

6.8廣義簡約梯度法

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

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

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

概述

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

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

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

xk+1=xk+αkdkdk::

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

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

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

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

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

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

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

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

隨機方向法的初始點x0必須是一個可行點，既滿足全部

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

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

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

函數(shù)最小的點xL

。4)比較xL

和x0兩點的目標函數(shù)值:①若f(xL)<f(x0)，則取xL

和x0連線方向為可行搜索方向；

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

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

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

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

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

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

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

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

x(1)為最壞點，稱為x(H)，通過映射得到新點x(R)，x(R)＝x(S)＋a(x(S)-x(H))以x(R)來代替x(H)，組成新的單純形x(R)x(2)x(3)。其中f(x(R))<f(x(H));

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

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

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

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

——擴張：若f(x(R))<f(x(L))，則可沿此方向擴張取若f(x(E))<f(x(L))，則擴張成功，以x(E)代替x(H)組成新復(fù)合形若f(x(E))>f(x(L))，則擴張失敗，以x(R)代替x(H)組成新復(fù)合形●X(S)X(R)X(H)X(E)變形法一——擴張：●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.變形法三

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

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

取

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

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

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

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

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

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

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

3.計算除最壞點外，其余頂點的形心:

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

4.則可行域為非凸集，取ai＝min[ai

(L),

ai(S)],

bi＝max[ai

(L),

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

5.計算映射點：

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,重新計算反射點步驟：是，a=1.3,轉(zhuǎn)步驟5是，轉(zhuǎn)步驟66.計算f(x(R))，若

7.若a>

:

檢查終止準則

若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)六.方法評價：

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

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

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

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

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

步長從一個邊界反彈到另一個邊界，直至滿足收斂

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

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

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

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

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

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

若約束面是非線性時，從x(k)點沿切線（面）方向d(k)

搜索，會進入非可行域。容差帶δ：

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

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

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

：

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

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

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

①可行條件:

[▽gj(xk)]T

dk≤0

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

②目標函數(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

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

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

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

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

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

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

x(k+1)=x(k)+a＊d§第四節(jié)可行方向法②取最大步長aM五.步長的確定a＊daMdx(k+收斂條件2）設(shè)計點xk滿足庫恩-塔克條件1）設(shè)計點xk及約束允差滿足收斂條件2）設(shè)計點xk滿足庫恩-塔克條件1）設(shè)計點x例用可行方向法求約束優(yōu)化問題的約束最優(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解：取初始點x0=[01]T，為約束邊界g1(x)=0上的一點。第一次迭代用優(yōu)選方向法確定可行方向。首先計算x0點的目標函數(shù)f(x0)和約束函數(shù)g1(x0)的梯度例用可行方向法求約束優(yōu)化問題的約束最優(yōu)解。為在可行下降扇形區(qū)內(nèi)尋找最優(yōu)方向，需求解一個以可行方向d=[d1d2]T為設(shè)計變量的線性規(guī)劃問題，其數(shù)學(xué)模型為：為在可行下降扇形區(qū)內(nèi)尋找最優(yōu)方向，需求解一個以可行方向d=[最優(yōu)方向是d*=[0.9840.179]T，它是目標函數(shù)等值線（直線束）和約束函數(shù)d12+d22=1（半徑為1的圓）的切點。第一次迭代的可行方向為d0=d*。最優(yōu)方向是d*=[0.9840.179]T，它是目標函第一次迭代的可行方向為d0=d*。若步長取0=6.098，則

可見第一次迭代點x1

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

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

計算投影算子P本次迭代的可行方向為第二次迭代用梯度投影法來確定可行方向。迭代點x1的目標函數(shù)負顯然，d1為沿約束邊界g3(x)=0的方向。若取1=2.909，則本次迭代點即為該問題的約束最優(yōu)點x*則得約束最優(yōu)解

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

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

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

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

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

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

①

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

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

的選擇：

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

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

③搜索方法：

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

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

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

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

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

，令k=0；

②

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

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

min.f(X)=x

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

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

的選擇:r(0)

過大，會使懲罰函數(shù)的等值線變形或偏心，求極

值困難。r(0)

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

＝1或者②x(0)

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

（1）初始點必須為嚴格的可行點

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

（3）迭代過程中各個點均為可行設(shè)計方案

（4）一般收斂較慢

（5）初始懲罰因子要選擇得當

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

外點法特點：

（1）初始點可以任選

（2）對等式約束和不等式約束均可適用

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

（4）一般收斂較快

（5）初始罰因子要選擇得當

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

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

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

(k)

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

r(k)

趨于無窮（外點法）時，算法才收斂，因此序

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

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

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

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

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

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

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

min

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

C＝2,

λ0=0,

r0=0.1，例:用拉格朗日乘子法求下列問題的最優(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)化問題。引入松弛變量Z＝[z1,

z2

,

…,

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

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

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

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

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

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

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

遺傳算法在求解優(yōu)化問題時首先對求解空間的各個解進行編碼。在尋優(yōu)過程中，通過對染色體

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

遺傳算法簡述二.基本思想：遺傳算法在求解優(yōu)化問題時首先對

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

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

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

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

(k)中的元素）

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

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

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

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

§第十一節(jié)

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

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

對于求極小化的目標函數(shù)（min

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

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

交配概率pc

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

——加大種群多樣性的重要因素，通常取0.001~0.1之間。概率太大，則使遺傳算法退化成隨機搜索算法；概率太小，產(chǎn)生新個體的機會太小。§第十一節(jié)

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

復(fù)制(選擇)

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

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

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

一點交配（二進制）：多點交配（二進制）：§第十一節(jié)

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

變異

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

遺傳算法簡述四.算法實現(xiàn)的幾個技術(shù)問題——遺傳算子四.算法實現(xiàn)的幾個技術(shù)問題——算法終止準則

事先規(guī)定出一個最大的進化步數(shù)，到達此步數(shù)時終止(一般取100-500代)。判斷當前最好的解已連續(xù)若干步?jīng)]有變化。算法已找到了一個可接受的最好解。§第十一節(jié)

遺傳算法簡述四.算法實現(xiàn)的幾個技術(shù)問題——算法終止準則

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

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

31

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

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

首先計算種群S1中各個體的適應(yīng)度f(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首先計算種群S1中各個體的適應(yīng)度f(si)再計算種群S1中各個體的選擇概率。選擇概率的計算公式為

由此可求得

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

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

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

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

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

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

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

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

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

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個染色體都被選中，則得到群體：s1’=11001（25）,s2’=01100（12）

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

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

分別交換后三位基因，得

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

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

這一輪仍然不會發(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）

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

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

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

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

f(2.048,-2.048)=3897.7342

和

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

X：00001

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

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

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

X：0000110111110111000