最優(yōu)化模型與算法

1、最優(yōu)化模型與算法最優(yōu)化模型與算法2內(nèi)容概要n優(yōu)化模型簡介n優(yōu)化模型分類n優(yōu)化算法及其分類 nMatlab優(yōu)化工具箱n現(xiàn)代智能優(yōu)化算法3優(yōu)化模型簡介概念、基本形式概念、基本形式n什么是優(yōu)化？就是從各種方案中選取一個最好的。從數(shù)學(xué)角度看，優(yōu)化理論就是研究如何在狀態(tài)空間中尋找到全局最優(yōu)點(diǎn)。n一般的優(yōu)化具有下面形式：min f (x1, x2, , xn)s.t. g(x) 0，xD其中x1, x2, , xn（即問題的可行域，代表問題參數(shù)的選擇范圍），即minf (X)，其中X（矢量形式）。f(x)是決策問題的數(shù)學(xué)模型，也是決策問題的目標(biāo)函數(shù)目標(biāo)函數(shù)，g(x) 0是決策問題的約束條件約束條件， X是

2、決策問題的決策變量決策變量，D是決策問題的定義域（可行域可行域）。問題歸結(jié)為求極值。極值點(diǎn)非常多，需要找到全局最小點(diǎn)。注：求問題的最大和最小是同一個問題，算法完全一樣。n分布模型的參數(shù)估計(jì)問題是典型的優(yōu)化問題，最大似然估計(jì)模型是典型的優(yōu)化模型。4優(yōu)化模型分類n1.根據(jù)是否存在約束條件 有約束模型，無約束模型 注：有約束問題通常采用轉(zhuǎn)換方法將有約束模型轉(zhuǎn)換為無約束模型再求解。n2.根據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式的性質(zhì) 線性規(guī)劃，非線性規(guī)劃，二次規(guī)劃，多目標(biāo)規(guī)劃等 注：最常見的優(yōu)化模型為非線性規(guī)劃模型。n3.根據(jù)決策變量的連續(xù)性 連續(xù)性優(yōu)化模型，離散性優(yōu)化模型（典型的組合優(yōu)化問題，最短路） 注：兩類

3、模型在求解方法上有較大不同，本次講解針對前一種。5優(yōu)化算法及其分類n什么是優(yōu)化算法？ 專門用于求解優(yōu)化模型的方法叫做優(yōu)化算法，優(yōu)化算法與優(yōu)化模型有本質(zhì)區(qū)別。n優(yōu)化算法可分為兩大類 1 梯度類算法 牛頓法、二分法、共軛梯度法、梯度下降法、單純形法等，該類算法也稱為局部優(yōu)化算法，明顯缺陷是局部優(yōu)化。Matlab優(yōu)化工具箱多用該類算法。 2 非梯度類算法 （1）遍歷搜索法，在組合優(yōu)化中稱為窮舉法，計(jì)算量大，適用于小規(guī)模計(jì)算求解。 （2）隨機(jī)搜索法，包括遺傳算法、模擬退火算法、群類算法、禁忌搜索法等，又稱為現(xiàn)代優(yōu)化算法，是一類全局最優(yōu)算法，求解的準(zhǔn)確性與時間長度、迭代次數(shù)直接相關(guān)。常用的優(yōu)化功能函數(shù)常

4、用的優(yōu)化功能函數(shù)l求解求解線性規(guī)劃線性規(guī)劃問題的主要函數(shù)是問題的主要函數(shù)是linprog。l求解求解二次規(guī)劃二次規(guī)劃問題的主要函數(shù)是問題的主要函數(shù)是quadprog。l求解求解無約束非線性規(guī)劃無約束非線性規(guī)劃問題的主要函數(shù)是問題的主要函數(shù)是fminbnd、fminunc和和fminsearch。l求解求解約束非線性規(guī)劃約束非線性規(guī)劃問題的函數(shù)是問題的函數(shù)是 fmincon 。l多目標(biāo)優(yōu)化問題的MATLAB函數(shù)有fgoalattain和和fminimax。MATLAB優(yōu)化工具箱優(yōu)化求解一般步驟優(yōu)化求解一般步驟 建立目標(biāo)函數(shù)文件建立目標(biāo)函數(shù)文件 針對具體工程問題建立針對具體工程問題建立優(yōu)化設(shè)計(jì)的數(shù)

5、學(xué)模型優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型不等式約束條件表不等式約束條件表示成示成g(X) 0的形的形式式 建立調(diào)用優(yōu)化工具函數(shù)建立調(diào)用優(yōu)化工具函數(shù)的的M文件或命令文件文件或命令文件建立約束函數(shù)文件建立約束函數(shù)文件運(yùn)行優(yōu)化工具函數(shù)的運(yùn)行優(yōu)化工具函數(shù)的M文文件或命令文件求解件或命令文件求解min f (x1, x2, , xn)s.t. g(x) 0無約束非線性規(guī)劃問題的MATLAB函數(shù)fminbnd要求目標(biāo)函數(shù)為連續(xù)函數(shù)要求目標(biāo)函數(shù)為連續(xù)函數(shù)只求解單變量問題只求解單變量問題fminunc可求解單變量和多變量問題可求解單變量和多變量問題適用于簡單優(yōu)化問題適用于簡單優(yōu)化問題可求解復(fù)雜優(yōu)化問題可求解復(fù)雜優(yōu)化問題fmi

6、nsearchxopt,fopt,exitflag=fminsearch(fun,x0,options)無約束多元函數(shù)最小值無約束多元函數(shù)最小值函數(shù)函數(shù)fminsearch調(diào)用格式調(diào)用格式設(shè)置優(yōu)化選項(xiàng)參數(shù)設(shè)置優(yōu)化選項(xiàng)參數(shù)初始點(diǎn)初始點(diǎn)目標(biāo)函數(shù)目標(biāo)函數(shù)返回最優(yōu)設(shè)計(jì)變量返回最優(yōu)設(shè)計(jì)變量返回目標(biāo)函數(shù)值返回目標(biāo)函數(shù)值返回算法的終止返回算法的終止指示變量值指示變量值例 求y=2x13 +4x1x23-10 x1x2+x22 的最小值點(diǎn).解：X=fminsearch(2*x(1)3+4*x(1)*x(2)3-10*x(1)*x(2)+x(2)2, 0,0)結(jié)果為: X = 1.0016 0.8335或在MA

7、TLAB編輯器中建立函數(shù)文件.function f=myfun(x)f=2*x(1)3+4*x(1)*x(2)3-10*x(1)*x(2)+x(2)2;保存為myfun.m，在命令窗口鍵入 X=fminsearch (myfun, 0,0) 或 X=fminsearch(myfun, 0,0)結(jié)果為： X = 1.0016 0.8335有約束的多元函數(shù)最小值有約束的多元函數(shù)最小值數(shù)學(xué)模型形式：數(shù)學(xué)模型形式： min f （X） s.t. AXb （線性線性不等式約束）不等式約束） AeqX=beq （線性線性等式約束）等式約束） C(X)0 （非線性非線性不等式約束條件）不等式約束條件） Ce

8、q(X)=0（非線性非線性等式約束）等式約束） Lb X Ub （邊界約束條件）（邊界約束條件）其中：x、b、beq、lb、ub是向量，A、Aeq為矩陣，C(x)、Ceq(x)是返回向量的函數(shù)，f(x)為目標(biāo)函數(shù)，f(x)、C(x)、Ceq(x)可以是非線性函數(shù).函數(shù) fmincon格式格式 x = fmincon(fun,x0,A,b)x = fmincon(fun,x0,A,b,Aeq,beq)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x = fmincon(fun,x

9、0,A,b,Aeq,beq,lb,ub,nonlcon,options)x,fval = fmincon()x,fval,exitflag = fmincon()x,fval,exitflag,output = fmincon()x,fval,exitflag,output,lambda = fmincon()x,fval,exitflag,output,lambda,grad = fmincon()x,fval,exitflag,output,lambda,grad,hessian = fmincon()參數(shù)說明：參數(shù)說明：fun為目標(biāo)函數(shù)，它可用前面的方法定義；nonlcon的作用是通過接

10、受的向量x來計(jì)算非線性非線性不等約束和非線性非線性等式約束分別在x處的估計(jì)C和Ceq，通過指定函數(shù)名函數(shù)名或函數(shù)名句柄函數(shù)名句柄來使用，如：x = fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,mycon)，先建立非線性約束函數(shù)，并保存為mycon.m：function C,Ceq = mycon(x)C = % 計(jì)算x處的非線性不等約束的函數(shù)值.Ceq = % 計(jì)算x處的非線性等式約束的函數(shù)值.lambda是Lagrange乘子，它體現(xiàn)哪一個約束有效.output輸出優(yōu)化信息；grad表示目標(biāo)函數(shù)在x處的梯度；hessian表示目標(biāo)函數(shù)在x處的Hessian值.控制參

11、數(shù)控制參數(shù)options序號功能默認(rèn)值及其含義說明1輸出形式0，無中間結(jié)果輸出Options(1)=1,按照表格輸出結(jié)果Options(1)=-1,隱藏警告信息2解x的精度1e-4Options(2)設(shè)置x解的終止條件3函數(shù)f的精度1e-4Options(3)設(shè)置函數(shù)f的終止條件4約束g的精度1e-6Options(4)設(shè)置約束g的終止條件5選擇主要算法0Options(5)選擇主要優(yōu)化算法6搜索方向算法0fmin()函數(shù)為無約束優(yōu)化搜索方向提供3種算法：Options(6)=0,擬牛頓法BFGS公式Options(6)=1,擬牛頓法DFP公式Options(6)=2,梯度法7步長一維搜索0f

12、min()函數(shù)為無約束優(yōu)化的步長一維搜索提供2種算法：Options(7)=0,二次和三次混合插值法Options(7)=1,三次多項(xiàng)式插值法控制參數(shù)控制參數(shù)options序號功能默認(rèn)值及其含義說明8函數(shù)值輸出Options(8)輸出最終迭代函數(shù)值9梯度檢驗(yàn)0，不檢驗(yàn)Options(9)比較梯度10函數(shù)計(jì)算次數(shù)Options(10)輸出函數(shù)計(jì)算次數(shù)11梯度計(jì)算次數(shù)Options(11)輸出函數(shù)梯度計(jì)算次數(shù)12約束計(jì)算次數(shù)Options(12)輸出約束計(jì)算次數(shù)13等式約束個數(shù)0，等式約束為0 Options(13)輸入等式約束個數(shù)14最大迭代次數(shù)100n（n為變量維數(shù)）Options(14)輸入

13、最大迭代次數(shù)15目標(biāo)個數(shù)0Options(15)輸入目標(biāo)個數(shù)16差分步長最小值1e-8Options(16)步長的下限或變量的最小梯度值17差分步長最大值0.1Options(17)步長的上限或變量的最大梯度值18步長Options(18)步長參數(shù)，第1次迭代時置1【例】求解約束非線性規(guī)劃：求解約束非線性規(guī)劃： 解解: :首先建立一個首先建立一個m文件文件mymyfun.mfunction y=myfun(x)y=-exp(x(1)*x(2)2*(3-exp(x(1)-x(2)2); 存儲為存儲為mymyfun.m首先將問題轉(zhuǎn)化為首先將問題轉(zhuǎn)化為matlab要求的格式要求的格式;即求出即求出f

14、un,A,b,Aeq,Beq,X0,Lb,Ub然后建立一個然后建立一個 m文件文件 confun.mfunction c,cep=confun(x)c=; % c為非線性不等式為非線性不等式cep=exp(x(1)+x(2)2-3; % cep為非線性等式為非線性等式然后存儲為然后存儲為conconfun.m最后在命令窗口中輸入：最后在命令窗口中輸入：A=;b=;Aeq=;beq=;Lb=;Ub=;x,f=fmincon(myfun,1;1, confun) 題目中有非線性約束條件，所以建立非線性約束題目中有非線性約束條件，所以建立非線性約束m-文件。文件。x = 0.8852 0.7592f

15、 = 6.2043e-016優(yōu)化過程演示n為了進(jìn)一步了解優(yōu)化模型的求解算法，給出具體實(shí)例的優(yōu)化過程演示。n例：以共軛梯度優(yōu)化算法優(yōu)化某函數(shù)進(jìn)行演示,并說明計(jì)算時間復(fù)雜度。18現(xiàn)代優(yōu)化算法 遺傳算法 模擬退火算法 禁忌搜索算法 蟻群算法 粒子群算法 差分進(jìn)化算法 特點(diǎn)： 基于客觀世界中的一些自然現(xiàn)象； 建立在計(jì)算機(jī)迭代計(jì)算的基礎(chǔ)上； 都屬于隨機(jī)搜索算法，具有全局優(yōu)化能力； 具有普適性，可解決實(shí)際應(yīng)用問題。注：群類算法還有魚群算法、蜂群算法、鳥群算法等?，F(xiàn)代優(yōu)化算法20現(xiàn)代優(yōu)化算法全局性優(yōu)化理論的一般性描述全局性優(yōu)化理論的一般性描述n兩種搜索方式：單點(diǎn)法和多點(diǎn)法。單點(diǎn)法是一種串行方式，即從一個初始

16、狀態(tài)（單個個體）出發(fā)，按照某種方式轉(zhuǎn)移狀態(tài)進(jìn)行全局優(yōu)化，這種方式通常要消耗較多機(jī)時；多點(diǎn)法是一種并行方式，即從可行域的多個初始狀態(tài)（多個個體）同時進(jìn)行搜索尋找全局最優(yōu)解，但是空間開銷大。根據(jù)各態(tài)歷經(jīng)假設(shè)，理論上二者可以具有相同的搜索效果。事實(shí)上，單CPU情況下的單點(diǎn)法和多點(diǎn)法并沒有本質(zhì)性的區(qū)別。 算法的提出 模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的 解決NP復(fù)雜性問題； 克服優(yōu)化過程陷入局部極??； 克服初值依賴性。什么是退火： 退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最

17、后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。 Metropolis準(zhǔn)則以概率接受新狀態(tài) 固體在恒定溫度下達(dá)到熱平衡的過程可以用Monte Carlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。若在溫度T，當(dāng)前狀態(tài)i 新狀態(tài)j若EjEi，則接受 j 為當(dāng)前狀態(tài)；否則，以概率 p=exp-(Ej-Ei)/kBT 接受j 為當(dāng)前狀態(tài)。即：p大于0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài) j 為當(dāng)前狀態(tài)；否則保留狀態(tài) i 為當(dāng)前狀態(tài)。 Metropolis準(zhǔn)則以概率接受新狀態(tài) p=exp-(Ej-Ei)/kBT 在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新

18、狀態(tài)。 在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；組合優(yōu)化與物理退火的相似性組合優(yōu)化與物理退火的相似性相似性比較 優(yōu)化問題優(yōu)化問題金屬物體金屬物體解解粒子狀態(tài)粒子狀態(tài)最優(yōu)解最優(yōu)解能量最低的狀態(tài)能量最低的狀態(tài)設(shè)定初溫設(shè)定初溫熔解過程熔解過程Metropolis抽樣過程抽樣過程等溫過程等溫過程控制參數(shù)的下降控制參數(shù)的下降冷卻冷卻目標(biāo)函數(shù)目標(biāo)函數(shù)能量能量SA算法描述27遺傳算法nDarwin 的物種進(jìn)化的主要思想是自然選擇(Natural selection)。生物通過競爭來進(jìn)化，以適應(yīng)環(huán)境。生物通過遺傳(Heredity)、變異(Mutation)等過程實(shí)現(xiàn)進(jìn)化。遺傳和變異的物質(zhì)基礎(chǔ)是染色體(

19、Chromosome)。染色體又是由DNA 和蛋白質(zhì)組成的?；蛑斜Ａ糁z傳物質(zhì)。通過基因的復(fù)制(production)、交叉(crossover)和變異(mutation)實(shí)現(xiàn)生物的性狀的變異和遺傳。n標(biāo)準(zhǔn)遺傳算法的基本框架是由Holland于20世紀(jì)60年代提出的，它使用二進(jìn)制編碼，采用賭輪選擇和隨機(jī)配對，關(guān)鍵是編碼編碼。這是一類模擬生物進(jìn)化過程的全局性優(yōu)化算法，其搜索效率取決于搜索策略或狀態(tài)轉(zhuǎn)移策略、編碼策略、運(yùn)行參數(shù)的合理配置等方面。對于具有下面數(shù)學(xué)結(jié)構(gòu)的研究對象min（或max）f (x)，s.t. g(x) 0，xD 遺傳算法可以具有較好的搜索效果。28遺傳算法n基本思路基本思路：

20、第一步：建立研究對象的數(shù)學(xué)結(jié)構(gòu)模型，確定目標(biāo)函數(shù)類型（即求目標(biāo)函數(shù)的最大值還是最小值?）。 第二步：確定表示可行解的染色體編碼方法，即確定個體基因型X及遺傳算法的搜索空間。 第三步：確定解碼方法，即確定由個體基因型X到相應(yīng)表現(xiàn)型的對應(yīng)關(guān)系或轉(zhuǎn)換關(guān)系。29遺傳算法n基本思路基本思路：第四步：設(shè)計(jì)遺傳算子，包括選擇算子、交叉算子、變異算子等的具體操作方法。第五步：確定個體適應(yīng)度的量化評價(jià)方法，即制定由目標(biāo)函數(shù) f(x) 到個體適應(yīng)度的轉(zhuǎn)換規(guī)則。第六步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)。包括編碼串長度l（對于二進(jìn)制編碼）、交叉概率Pc、變異概率Pm、種群規(guī)模M、終止代數(shù)T等運(yùn)行參數(shù)的設(shè)置。第七步：設(shè)計(jì)遺傳算法程序，其中使用了最優(yōu)保留策略。30遺傳算法n為了提高其搜索效率，可以在三個方面提出改進(jìn)措施：1) 采用更好的搜索策略。采用更好的搜索策略。主要包括：精英策略（elitist strategy）；構(gòu)造與