1、第1章最優化問題的基本概念1.1 最優化的概念最優化就是依據最優化原理和方法，在滿足相關要求的前提下，以盡可能高的效率求得工程問題最優解決方案的過程。1.2 最優化問題的數學模型1 .最優化問題的一般形式findX1,X2,Xnminf(x,X2,Xn)s.t.gu(X1,X2,Xn)0u1,2,phv(X1,X2,Xn)0v1,2,q2 .最優化問題的向量表達式findXminf(X)s.t.G(X)0H(X)0式中：XX1,X2,XnTG(X)gKX),g2(X),gp(X)TH(X)%(X),h2(X),hp(X)T3 .優化模型的三要素設計變量、約束條件、目標函數稱為優化設計的三要素！

2、設計空間：由設計變量所確定的空間。設計空間中的每一個點都代表一個設計方案1.3優化問題的分類按照優化模型中三要素的不同表現形式，優化問題有多種分類方法：1按照模型中是否存在約束條件，分為約束優化和無約束優化問題2按照目標函數和約束條件的性質分為線性優化和非線性優化問題3按照目標函數個數分為單目標優化和多目標優化問題4按照設計變量的性質不同分為連續變量優化和離散變量優化問題第2章最優化問題的數學基礎21n元函數的可微性與梯度、可微與梯度的定義1 .可微的定義設f(X)是定義在n維空間Rn的子集D上的n元實值函數，且X0D。若存在n維向量L,對于任意n維向量P,都有.f(X0P)f(X0)ltp.

3、lim0llP0p|則稱f(X)在X0處可微。2 .梯度設有函數F(X),XXi,X2,XnT,在其定義域連續可導。我們把F(X)在定義域某點X處的所有一階偏導數構成的列向量，定義為F(X)在點X處的梯度。記為:X1X2TFXn梯度有3個性質：函數在某點的梯度方向為函數過該點的等值線的法線方向;函數值沿梯度方向增加最快，沿負梯度方向下降最快；梯度描述的只是函數某點鄰域的局部信息。22極小點及其判別條件一、相關概念1.極小點與最優解設f(X)是定義在n維空間Rn的子集D上的n元實值函數，若存在X*D及實數0,使得XN(X,)D(XXWRtf(X)f(X),則稱X為f(X)的局部極小點；若則稱X若

4、f(X)f(X),則稱X為f(X)的嚴格局部極小點。XD,都有f(X)f(X),則稱X為f(X)的全局極小點，若f(X)f(X),為f(X)的全局嚴格極小點。findX對最優化問題(X)st.G(X)H(X)而百00滿足所有約束條件的向量XXi，X2，,XnT稱為上述最優化問題的一個可行解，全體可行解組成的集合稱為可行解集。在可行解集中，滿足:f(X)minf(X)的解稱為優化問題的取優解。2.凸集和凸函數凸集：設DRn,若對所有的X1、X2D,及0,1,都有X1(1)X2D,則稱D為凸集。凸函數：設f:DRnR1,D是凸集，如果對于所有的X1、X2D,及0,1,都有fX1(1)X2f(X1)

5、(1)f(X2),則稱f(X)為D上的凸函數。二、局部極小點的判別條件駐點：設f(X)是定義在n維空間Rn的子集D上的n元實值函數，X*是D的點，若f(X)0,則稱X為f(X)的駐點。局部極小點的判別：設f(X)是定義在n維空間Rn的子集D上的n元實值函數，具有連續的二階偏導數。若X*是f(X)的駐點，且2f(X*)是正定矩陣，則X*是f(X)的嚴格局部極小點。第3章無約束優化方法3.1 下降迭代算法及終止準則一、數值優化方法的基本思想基本思想就是在設計空間選定一個初始點Xk,從該點出發，按照某一方向Sk(該方向的確定原則是使函數值下降)前進一定的步長;得到一個使目標函數值有所下降的新設計點X

6、k1,然后以該點為新的初始點，重復上面過程，直至得到滿足精度要求的最優點X。該思想可用下式表示：Xk1XkkSk二、迭代計算的終止準則工程中常用的迭代終止準則有3種：點距準則相鄰兩次迭代點之間的距離充分小時，迭代終止。數學表達為：Xk1Xk函數下降量準則(值差準則)相鄰兩次迭代點的函數值之差充分小，迭代終止。數學表達為：|f(Xk1)f(Xk)|梯度準則目標函數在迭代點處的梯度模充分小時，迭代終止數學表達為：|f（Xk1）|、算法的收斂速度對于某一確定的下降算法，其優劣如何評價？人們通常采用收斂速度來評價。下面給出度量收斂速度的幾個概念。1 .P階收斂設序列Xk收斂于解X*,若存在常數P0及L

7、、ko,使當kko時下式:成立，則稱Xk為P階收斂。2 .線性收斂設序列Xk收斂于解X*,若存在常數ko、L及（0,1）,使當kko時下式：Xk1X*Lk成立，則稱Xk為線性收斂。3 .超線性收斂設序列Xk收斂于解X*,若任給0都存在ko0,使當kko時下式：Xk1X*XkX*成立，則稱Xk為超線性收斂。3.2 一維最優化方法一、確定初始區間的進退法任選一個初始點Xo和初始步長h,由此可確定兩點X1Xo和X2X1h,通過比較這兩點函數值f（X1）、f（X2）的大小，來決定第三點X3的位置。比較這三點函數值是否呈“高一一低一一高”排列特征，若是則找到了單峰區問，否則向前或后退繼續尋求下進退法依據

8、的基本公式:X2X3具體步驟為：任意選取初始點Xo和恰當的初始步長h；令X1Xo,取x2X1h,計算f（X1）、f（X2）;若f（X1）f（X2）,說明極小點在X2右側，應加大步長向前搜索。轉；若f（X1）f（X2）,說明極小點在X1左側，應以X1點為基準反向小步搜索。轉;大步向前搜索：令h2h,取X3x2h,計算fd);若f(X2)f(X3)，則f(X1)、f(X2)、f(X3)呈“高低高”排列，說明X1,X3即為所求的單峰區間；若f(X2)f(X3),說明極小點在X3右側，應加大步長向前搜索。此時要注意做變換：舍棄原X1點，以原X2點為新的X1點，原X3點為新的X2點。轉，直至出現“高一一

9、低一一高”排列，則單峰區間可得；反向小步搜索(要注意做變換)：為了保證X3點計算公式的一致性，做變換：將1原X2點記為新X1點，原Xi點記為新X2點，令hh,取X3X2h,轉4例：用進退法確定函數f(x)X26x9的單峰區間a,b,設初始點x00,h1。解：Xo0h1x1xo0x2x1h1f(x1)9f(x2)4“xjf(X2)說明極小點在X2點右側，應加大步長向前搜索令h2h212,取x3x2h123則f(x3)0f(X2)f(X3)說明極小點在X3點右側，應加大步長向前搜索舍棄原X1o的點，令X11X23,則f(X1)4f(X2)o令h2h224,取X3X2h347則f(x3)16f(X2

10、)0f(x1)、f(X2)f%)呈“高低高”排列X1,X3為單峰區間,即區間1,7即為所求二、黃金分割法黃金分割法是基于區間消去思想的一維搜索方法，其搜索過程必須遵循以下的原則：對稱取點的原則：即所插入的兩點在區間位置對稱；插入點繼承的原則：即插入的兩點中有一個是上次縮減區間時的插入點；等比收縮的原則：即每一次區間消去后，單峰區間的收縮率保持不變。設初始區間為a,b,則插入點的計算公式為:xia0.382(ba)x2a0.618(ba)黃金分割法的計算步驟如下：給定初始區間a,b和收斂精度；給出中間插值點并計算其函數值：x1a0.382(ba)f(x1)x2a0.618(ba)f(x2).比較

11、f(xj、f(xz),確定保留區間得到新的單峰區間a,b;收斂性判別：計算區間a,b長度并與比較，若*1，、x(ab)2否則轉;在保留區間繼承一點、插入一點，轉例：使用黃金分割法求解優化問題：minf(x)2x2x,0.2。解：x1a0.382(ba)30.382(53)0.056f(xi)0.1152)x2a0.618(ba)30.618(53)1.944f(x2)7.667f(x2)f(x1)舍棄(1.944,5,保留-31.9441.944繼承原木點，即x20.056f(x2)0.115插入xa0.382(ba)30.382(1.9443)1.111f(x1)0.987vf(x2)f(x

12、1).舍棄(0.056,1.944,保留-3,0.0560.056(3)繼承原木點，即x21.111f(x2)0.987插入x1a0.382(ba)30.382(0.0563)1.832f(x1)0.306:f(x2)f(x1).保留-1.832,0.0560.056(1.832);繼承原x2點，即x11.111f(x1)0.987f(x2)0.888插入x21.8320.618(0.0561.832)0.665f(X2)f(Xi).保留-1.832,-0.665如此迭代，到第8次,保留區為-1.111,-0.9400.940(1.111)0.171d.x1(1.1110.940)1.0255

13、f(x)0.99923.3 梯度法一、基本思想對于迭代式Xk1xkkSk,當取搜索方向Skf(Xk)時構成的尋優算法，稱為求解無約束優化問題的梯度法。二、迭代步驟給定出發點xk和收斂精度；計算xk點的梯度F(Xk),并構造搜索方向SkF(Xk);令Xk1Xkksk,通過一維搜索確定步長k，即：minF(XkkSk)求得新點Xk1收斂判斷：若JF(Xk1)|成立，輸出X*Xk1、F(X*)F(Xk1),尋優結束；否則令kk1轉繼續迭代，直到滿足收斂精度要求。三、梯度法的特點梯度法尋優效率受目標函數性態影響較大。若目標函數等值線為圓，則一輪搜索就可找到極致點；若當目標函數等值線為扁橢圓時，收斂速度

14、則顯著下降。梯度法中相鄰兩輪搜索方向相互垂直。3.4 牛頓法牛頓法分為基本牛頓法和阻尼牛頓法兩種。對于迭代式Xk1XkkSk，當取k1且搜索方向Sk2f(Xk)1f(Xk)時構成的尋優算法，稱為求解無約束優化問題的基本牛頓法；對于迭代式Xk1XkkSk，取搜索方向Sk2f(Xk)1f(Xk),k為從Xk出發、沿牛頓方向做一維搜索獲得的最優步長，所構成的尋優算法，稱為求解無約束優化問題的阻尼牛頓法。搜索方向Sk2f(Xk)1f(Xk)稱為牛頓方向。這里需要注意的是會求海塞陣的逆矩陣3.5 變尺度法我們把具有Xk1XkkAkf(Xk)迭代模式的尋優算法稱為變尺度法。其搜索方向表達式為：SkAkf(

15、Xk),稱為擬牛頓方向，其中Ak稱為變尺度矩庫。在迭代開始的時候，A0I；隨著迭代過程的繼續，Ak2f(Xk)1f(Xk),因此，變尺度法從梯度法出發，隨著迭代過程的繼續最終趨向于牛頓法。3.6 共腕梯度法一、共腕方向的概念設H為對稱正定矩陣，若有兩個n維向量Si和S2,滿足S1THS20,則稱向量Si與&關于矩陣H共腕，共腕向量的方向稱為共腕方向。若有一組非零向量S,S2,Sn滿足STHSj0(ij),則稱這組向量關于矩陣H共腕。對于n元正定二次函數，依次沿著一組共腕方向進行一維搜索，最多n次即可得到極值點。二、共腕方向的形成1對于函數f(X)f(X1,X2,Xn)-XtHXBtXC2沿任意

16、方向S0在設計空間上任意做兩條平行線，分別與目標函數等值線切于點X1、X2,令S1X2X1,則S0、S1關于矩陣H共腕。三、共腕梯度法對于迭代式Xk1XkkSk，取搜索方向Sk1f(Xk1)kSk其中：S0f(X),kf(Xk1)f(Xk)|2共腕梯度法相鄰兩輪搜索方向是一對共腕方向。3.7鮑威爾法基本迭代公式仍舊是：Xk1XkkSk基本鮑威爾法每輪搜索分為兩步：一環的搜索+在該環搜索完畢后生成的新方向上的一維搜索。對于基本鮑威爾法，相鄰兩輪搜索生成的搜索方向是共腕的。修正鮑威爾法與基本鮑威爾法類似，所不同的是每環搜索后生成的新方向要利用鮑威爾條件判別其可用性。注意掌握鮑威爾條件的表達式和應用

17、!每環搜索方向組的生成：1 .第一環的搜索方向組就是各坐標軸方向2 .下一環的搜索方向組由本環搜索方向組和本環生成的新方向共同確定，方法是：若本環的搜索結果滿足鮑威爾條件，則將本環搜索方向組中使目標函數下降量最大的方向去掉，并將本環生成的新方向遞補進去，就形成下一環的搜索方向組；若本環的搜索結果不滿足鮑威爾條件，則下一環的搜索方向組仍舊沿用本環搜索方向組不變。下一環搜索起點的確定：下一環搜索起點由本環搜索結果確定，方法是：若本環的搜索結果滿足鮑威爾條件,則以本環搜索終點為起點，沿新生成的方向作一維搜索，得到的新點作為本輪的搜索終點，也是下一輪的搜索起點；若本環的搜索結果不滿足鮑威爾條件，則取本

18、環搜索終點和反射點中目標函數值小的點作為本輪的搜索終點，也是下一輪的搜索起點。這里需要注意的是反射點的計算：x，2x；x0k式中：xk2是本環起點x0k相對于本環終點xk沿新生成方向的反射點。例:對于無約束目標函數minf(X)X122x24x12x1x2,利用修正Powell法從x01 ，出發求最優解解:令x0x0P1P0(72)x；x0(x；)自：則：x1x2X11令f（x2）行：0.5則：x231.5該環生成的新搜索方向為：s1x2x01.50.51對S1進行有效性判別:反射點x42X2X0321.5f1f(X0)f2_1f(X2)7.5f3f(X4)71f(X0)f(X；)3(7)4,

19、2f(X11)f(X2)7(7.5)0.5故最大下降量m故：f3%和(f12f2f3)(f1f2m(f1f3)2均成立方向S1可用以x2為起點，沿s1方向作一維搜索:x3x2s131.520.531.520.5由minf(X3)f(x2S1)得2/50.4故，本輪尋優的終點為:X113.8x31.7做收斂性判別:IV2.820.72,應繼續搜索下一輪尋優過程的起點為：x213.8x31.7下一輪尋優過程的搜索方向組為:(e2，S1)約束優化方法約束優化方法要求大家重點掌握懲罰函數法，包括點法、外點法、混合法。、外點法構造懲罰函數：pqk_k2k2min(X,r)f(X)rma)(gu(X),0

20、rhv(X)u1v1外點法既可以處理不等式約束優化問題，又可以處理等式約束優化問題。需要注意的是:懲罰因子隨迭代次數的增加是遞增的，當時得到的解就是原問題的最優解。例:用外點法求解minf(X)x；s.t.3x20x22xi解:構造懲罰函數(X,rk)2x12x2行：(X,rk)2x1x1x1x11、點法2x2x2一12x12x122222x12x12rk(x23)03rkkr*x1構造懲罰函數:(X,rk)f(X)11gu(X)2x1rk(3x2)22max3x2,0X2又2*乂2limx2k或：（X點法只能處理不等式約束優化問題,需要注意的是：懲罰因子是原問題的最優解。例：用點法求解約束優

21、化問題minf(X)x1X2_*3f(x)prk)f(X)rklnu1不能處理等式約束優化問題。隨迭代次數的增加是遞減的，當rkgu(X)0時得到的解就2s.t.x1x2x10解：構造懲罰函數(X,rk)x1x2k._2_k.rlnx2x1rlnx1一1x12x12x2x1一1x212x2x14日彳可x1,18rk14X2(18rk1)2rk16當rk0時，得_*f(x)0三、混合法構造懲罰函數:(X,rk)f(X)krik或：(X,r)f(X)1gu(X)pk._rlnu1q2hv(X)21qk2gu(X)r2hv(X)v1混合法的特點是：對于不等式約束按照點法構造懲罰項，對于等式約束按照外

22、點法構造懲罰項。混合法既可以處理不等式約束優化問題，也可以處理等式約束優化問題。例：用混合懲罰函數法求解約束優化問題-2minf(X)x123x2x2s.t.1x10x20解：構造懲罰函數(X,rk)x123x22X2k12rln1xjx2r2x1令(X,rk)2x2X2x2r得：x1k2rX2312(1)r_*f(x)10時，得x第5章遺傳算法本章要求重點掌握遺傳算法的5個要素、遺傳算法的尋優機制、遺傳算法的5個要素1.編碼將優化問題的解編碼，用以模擬生物個體的基因組成；2 .初始種群生成將優化問題多個隨機可行解匯成集合，用以模擬進化的生物種群；3 .個體適應度評估將優化問題目標函數加以變換，生成適應度函數來評價種群個體的適應度，用以模擬生物個體對環境的適應能力；4 .遺傳操作包含選擇、交叉、變異選擇：一種使適應度函數值大的個體有更大的存活