最優(yōu)化問題和遺傳算法PPT課件

1、 MATLAB優(yōu)化工具箱（Optimization Toolbox）中包含有一系列優(yōu)化算法和模塊，可以用于求解線性規(guī)劃和二次規(guī)劃、函數(shù)的最大和最小值、非線性規(guī)劃、多目標(biāo)優(yōu)化、非線性最小二乘逼近和曲線擬合、非線性系統(tǒng)方程和復(fù)雜結(jié)構(gòu)的大規(guī)模優(yōu)化問題。 遺傳算法（Genetic Algorithm）是模擬生物自然進(jìn)化過程的進(jìn)化算法中一個(gè)重要的領(lǐng)域，它已經(jīng)被廣泛地應(yīng)用于自動(dòng)控制、機(jī)器學(xué)習(xí)、模式識(shí)別、圖形處理、人工神經(jīng)網(wǎng)絡(luò)、優(yōu)化調(diào)度、經(jīng)濟(jì)預(yù)測(cè)、通訊網(wǎng)絡(luò)和函數(shù)優(yōu)化等各個(gè)領(lǐng)域，它作為一種新的全局優(yōu)化搜索算法，在求解復(fù)雜的工程優(yōu)化問題中取得良好的效果。利用MATLAB系統(tǒng)中的遺傳算法工具箱（GA Toolbo

2、x）可以實(shí)現(xiàn)遺傳算法許多基本運(yùn)算。第1頁/共84頁9.1 MATLAB9.1 MATLAB優(yōu)化工具箱的應(yīng)用優(yōu)化工具箱的應(yīng)用 常用的優(yōu)化功能函數(shù)有 求解線性規(guī)劃問題的函數(shù)linprog 求解二次規(guī)劃問題的函數(shù)quadprog 求解無約束非線性規(guī)劃問題的函數(shù)fminbnd、fminunc和fminsearch 求解約束非線性規(guī)劃問題的函數(shù)fmincon 求解多目標(biāo)優(yōu)化問題的函數(shù)fgoalattain和fminimax 使用MATLAB優(yōu)化工具箱函數(shù)處理優(yōu)化設(shè)計(jì)問題的分析和計(jì)算的一般步驟是： 1、針對(duì)具體工程問題建立優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型（其中，不等式約束條件表示成的形式）；第2頁/共84頁 2、分析數(shù)

3、學(xué)模型中的目標(biāo)函數(shù)，并建立相應(yīng)的目標(biāo)函數(shù)文件（包括計(jì)算目標(biāo)函數(shù)必需的輸入?yún)?shù)，描述目標(biāo)函數(shù)表達(dá)式等內(nèi)容），以自定目標(biāo)函數(shù)文件名將它存儲(chǔ)在工作間MATLABWORK中； 3、分析數(shù)學(xué)模型中的非線性約束條件，并建立相應(yīng)的非線性約束函數(shù)文件（包括計(jì)算約束函數(shù)必需的輸入?yún)?shù)，描述約束函數(shù)表達(dá)式等內(nèi)容），以自定的約束函數(shù)文件名將它存儲(chǔ)在工作間MATLABWORK中； 4、分析優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型，選擇適用的優(yōu)化工具函數(shù)，并建立調(diào)用優(yōu)化工具函數(shù)的命令文件（內(nèi)容包括輸入初始點(diǎn)，建立設(shè)計(jì)變量的線性約束和邊界約束的矩陣和向量，使用優(yōu)化工具函數(shù)調(diào)用目標(biāo)函數(shù)文件和約束函數(shù)文件的語句，以及運(yùn)算結(jié)果輸出等內(nèi)容），將優(yōu)化工

4、具函數(shù)作為 “黑箱”調(diào)用，以自定的命令文件名將它存儲(chǔ)在工作間MATLABWORK中。第3頁/共84頁 將優(yōu)化設(shè)計(jì)的命令文件復(fù)制到MATLAB命令窗口的運(yùn)算提示符“”后面運(yùn)行。 如果編制的目標(biāo)函數(shù)文件、約束函數(shù)文件和命令文件存在錯(cuò)誤，MATLAB就會(huì)給出錯(cuò)誤的類型和在M文件中的位置，方便用戶對(duì)錯(cuò)誤進(jìn)行定位和檢查。 如果M文件沒有錯(cuò)誤（包括邏輯錯(cuò)誤和語法錯(cuò)誤），命令窗口就會(huì)顯示出運(yùn)算信息，獲得與所有條件都相容的優(yōu)化結(jié)果。第4頁/共84頁 9.1.1 9.1.1 線性規(guī)劃問題線性規(guī)劃問題 線性規(guī)劃（Linear Programming）是數(shù)學(xué)規(guī)劃中最簡(jiǎn)單和基本的問題，它主要用來解決在有限的資源條件下

5、完成最多的任務(wù)，或是確定如何統(tǒng)籌任務(wù)完成以使用最少的資源。 線性規(guī)劃的數(shù)學(xué)模型包括決策變量X、約束條件和目標(biāo)函數(shù)三個(gè)要素，它的決策變量是非負(fù)的，而且約束函數(shù)和目標(biāo)函數(shù)都是線性函數(shù)。 線性規(guī)劃的數(shù)學(xué)模型表示為min. .Tf XstAXbAeqXbeqlbXub第5頁/共84頁 用于求解線性規(guī)劃的MATLAB函數(shù)是linprog，其調(diào)用格式為： xopt,fopt=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) 其中，輸入?yún)?shù)有： f是目標(biāo)函數(shù)各維變量的系數(shù)向量； A和b是不等式約束函數(shù)的系數(shù)矩陣和常數(shù)向量； Aeq和beq是等式約束函數(shù)系數(shù)矩陣和常數(shù)向量； lb

6、和ub分別是設(shè)計(jì)變量的下限和上限； x0是初始點(diǎn)； options是設(shè)置優(yōu)化選項(xiàng)參數(shù)（參考表9-1）。 輸出參數(shù)有： xopt和fopt是返回目標(biāo)函數(shù)最優(yōu)解及其函數(shù)值。第6頁/共84頁第7頁/共84頁第8頁/共84頁 例例9-1 9-1 求解線性規(guī)劃問題 編制求解線性規(guī)劃問題的M文件： % 求解線性規(guī)劃問題 f=-2,-1,3,-5; % 各維變量的系數(shù)向量 A=1,2,4,-1;2,3,-1,1;1,0,1,1; % 系數(shù)矩陣 b=6,12,4; % 不等式約束函數(shù)的常數(shù)向量 lb=0,0,0,0; % 設(shè)計(jì)變量的下限 xopt,fopt=linprog(f,A,b,lb) 12341234

7、12341341234min235. .24623124,0fXxxxxstxxxxxxxxxxxx xx x 第9頁/共84頁 由于線性規(guī)劃問題中沒有等式約束，所以相應(yīng)的系數(shù)矩陣Aeq和常數(shù)向量beq用空矩陣符號(hào)“”表示。程序運(yùn)行結(jié)果： Optimization terminated successfully. xopt = 0.0000 2.6667 0.0000 4.0000 fopt = -22.6667 可見，約束最優(yōu)解位于兩個(gè)邊界約束 和 的交集上。01x03x第10頁/共84頁 9.1.2 9.1.2 二次規(guī)劃問題二次規(guī)劃問題 二次規(guī)劃問題（Quadratic Programmi

8、ng）是最簡(jiǎn)單的非線性規(guī)劃問題，其目標(biāo)函數(shù)是二次函數(shù)，而約束函數(shù)是線性函數(shù)。由于二次規(guī)劃問題的求解比較成熟，有時(shí)可以將一些求解比較困難的一般非線性約束規(guī)劃問題轉(zhuǎn)化為較易處理的序列二次規(guī)劃子問題求解。 用于求解二次規(guī)劃問題的函數(shù)是 quadprog 二次規(guī)劃的 數(shù)學(xué)模型為 1min2. .TTfXX HXC XstAXbAeqXbeqlbXub第11頁/共84頁 使用格式為 xopt,fopt= quadprog (H,C,A,b,Aeq,beq,lb,ub,x0,options) 其中，輸入?yún)?shù)有： H是目標(biāo)函數(shù)的海色矩陣； C是目標(biāo)函數(shù)設(shè)計(jì)變量一次項(xiàng)的系數(shù)向量； A和b是不等式約束函數(shù)的系數(shù)

9、矩陣和常數(shù)向量； Aeq和beq是等式約束函數(shù)的系數(shù)矩陣和常數(shù)向量 lb和ub分別是設(shè)計(jì)變量的下限和上限； x0是初始點(diǎn)； options是設(shè)置優(yōu)化選項(xiàng)參數(shù)（參考表9-1）。 輸出參數(shù)有： xopt和fopt返回目標(biāo)函數(shù)的最優(yōu)解及其函數(shù)值。第12頁/共84頁 例例9-2 9-2 求解約束優(yōu)化問題 將目標(biāo)函數(shù)寫成二次函數(shù)的形式 其中：222123123123123123222. .32624,0fXxxxx xxstg Xxxxh Xxxxx x x12TTfXX HXC X123xXxx220240002H 001C 第13頁/共84頁 線性不等式約束函數(shù)的系數(shù)矩陣和常數(shù)向量為 線性等式約束函

10、數(shù)的系數(shù)矩陣和常數(shù)向量為 編制求解二次規(guī)劃的M文件 % 求解二次規(guī)劃問題 H=2,-2,0;-2,3,0;0,0,2; % 函數(shù)的海色矩陣 C=0,0,1; % 各維變量的系數(shù)向量 A=1,3,2; % 不等式約束函數(shù)的系數(shù)矩陣 b=6; % 不等式約束函數(shù)的常數(shù)向量 Aeq=2,-1,1; % 等式約束函數(shù)的系數(shù)矩陣 beq=4; % 等式約束函數(shù)的常數(shù)向量 lb=zeros(3,1); % 設(shè)計(jì)變量的下限1,3,2A 6b 2, 1,1Aeq 4beq 第14頁/共84頁 xopt,fopt=quadprog(H,C,A,b,Aeq,beq,lb) % 調(diào)用線性規(guī)劃函數(shù) % 最優(yōu)點(diǎn)的約束函

11、數(shù)值 g=A*xopt-b % 不等式約束 h=Aeq*xopt-beq % 等式約束 M文件運(yùn)行結(jié)果： Optimization terminated successfully. xopt = 2.4783 1.0870 0.1304 fopt = 2.6739 g = 8.8818e-016 h = -4.4409e-016 可見，二次規(guī)劃的約束最優(yōu)解位于不等式約束和等式約束的交集。第15頁/共84頁 9.1.3 9.1.3 無約束非線性規(guī)劃問題無約束非線性規(guī)劃問題 1、函數(shù)fminbnd應(yīng)用 函數(shù)fminbnd只能求解單變量的無約束非線性規(guī)劃問題，而且要求目標(biāo)函數(shù)為連續(xù)函數(shù)。調(diào)用格式 x

12、opt,fopt,exitflag,output= fminbnd(fun,x1,x2,options) 其中，輸入?yún)?shù)有： fun是目標(biāo)函數(shù)； x1,x2是迭代搜索區(qū)間，即變量的邊界約束，即x1xx2； options是設(shè)置優(yōu)化選項(xiàng)參數(shù)（見表9-1）。例如options(1)為負(fù)值時(shí)，則顯示中間過程，默認(rèn)值是options(1)=0；options(2)為最優(yōu)解xopt的誤差范圍，默認(rèn)值是1e-4；等等。第16頁/共84頁 輸出參數(shù)有： Xopt為返回的滿足fun取得最小值的x的值； fopt為目標(biāo)函數(shù)最小值； exitflag表示退出條件：exitflag0表示計(jì)算收斂，exitflag=

13、0表示超過了最大的迭代次數(shù)，exitflag 0表示計(jì)算收斂，exitflag=0表示超過了最大的迭代次數(shù)，exitflag 9 | y2-4 | x(3)=0) & (g2=0) y=-f; % 滿足約束條件時(shí) else y=-(f+p); % 不滿足約束條件時(shí) end第79頁/共84頁 2、調(diào)用遺傳優(yōu)化算法函數(shù)，初始種群個(gè)體數(shù)目取20，其他默認(rèn)缺省參數(shù)（進(jìn)化繁殖100代） % 生成初始種群，個(gè)體數(shù)目取20 bounds=ones(2,1)*-1 3; % 變量上下限 startPop=initializega(20,bounds,minf_4,); % 遺傳優(yōu)化算法搜索 xf,en

14、dPop,beestSols,trace=ga(bounds,minf_4); beestSols xf M文件運(yùn)行結(jié)果: beestSols = % 略去輸出數(shù)據(jù)第80頁/共84頁 xf = 2.0310 0.8229 -0.0323 運(yùn)算結(jié)果表明，繁殖到第62代時(shí)獲得最優(yōu)解： 將最優(yōu)解代入兩個(gè)約束條件中進(jìn)行檢驗(yàn)： % 計(jì)算最優(yōu)點(diǎn)不等式約束函數(shù)值 g1y=xf(1)-2*xf(2)+1 g2y=0.25*xf(1)2-3*xf(2)2+1 M文件運(yùn)行結(jié)果： g1y = 1.3859 g2y = 4.2997e-007第81頁/共84頁 3、描述遺傳算法搜索過程 % 繪制遺傳優(yōu)化算法過程圖形 plot(trace(:,1),trace(:,2),b:);