第9章 最優(yōu)化問(wèn)題和遺傳算法.ppt

1、第9章 最優(yōu)化問(wèn)題和遺傳算法,優(yōu)化設(shè)計(jì)問(wèn)題數(shù)學(xué)模型的一般形式是 優(yōu)化設(shè)計(jì)問(wèn)題數(shù)學(xué)模型包括維設(shè)計(jì)變量、約束條件（不等式約束條件和等式約束條件）和目標(biāo)函數(shù)三項(xiàng)要素。優(yōu)化問(wèn)題的數(shù)學(xué)模型是實(shí)際優(yōu)化問(wèn)題的數(shù)學(xué)抽象，在滿足所有的約束條件和情況下，求解維設(shè)計(jì)變量，使某項(xiàng)或多項(xiàng)設(shè)計(jì)目標(biāo)（技術(shù)經(jīng)濟(jì)指標(biāo)）達(dá)到最優(yōu)。,MATLAB優(yōu)化工具箱（Optimization Toolbox）中包含有一系列優(yōu)化算法和模塊，可以用于求解線性規(guī)劃和二次規(guī)劃、函數(shù)的最大和最小值、非線性規(guī)劃、多目標(biāo)優(yōu)化、非線性最小二乘逼近和曲線擬合、非線性系統(tǒng)方程和復(fù)雜結(jié)構(gòu)的大規(guī)模優(yōu)化問(wèn)題。 遺傳算法（Genetic Algorithm）是模擬生物

2、自然進(jìn)化過(guò)程的進(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)化問(wèn)題中取得良好的效果。利用MATLAB系統(tǒng)中的遺傳算法工具箱（GA Toolbox）可以實(shí)現(xiàn)遺傳算法許多基本運(yùn)算。,9.1 MATLAB優(yōu)化工具箱的應(yīng)用,常用的優(yōu)化功能函數(shù)有 求解線性規(guī)劃問(wèn)題的函數(shù)linprog 求解二次規(guī)劃問(wèn)題的函數(shù)quadprog 求解無(wú)約束非線性規(guī)劃問(wèn)題的函數(shù)fminbnd、fminunc和fminsearch 求解約束非線性規(guī)劃問(wèn)題的函數(shù)fmincon 求

3、解多目標(biāo)優(yōu)化問(wèn)題的函數(shù)fgoalattain和fminimax 使用MATLAB優(yōu)化工具箱函數(shù)處理優(yōu)化設(shè)計(jì)問(wèn)題的分析和計(jì)算的一般步驟是： 1、針對(duì)具體工程問(wèn)題建立優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型（其中，不等式約束條件表示成的形式）；,2、分析數(shù)學(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)

4、化設(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ǔ)句，以及運(yùn)算結(jié)果輸出等內(nèi)容），將優(yōu)化工具函數(shù)作為 “黑箱”調(diào)用，以自定的命令文件名將它存儲(chǔ)在工作間MATLABWORK中。,將優(yōu)化設(shè)計(jì)的命令文件復(fù)制到MATLAB命令窗口的運(yùn)算提示符“”后面運(yùn)行。 如果編制的目標(biāo)函數(shù)文件、約束函數(shù)文件和命令文件存在錯(cuò)誤，MATLAB就會(huì)給出錯(cuò)誤的類型和在M文件中的位置，方便用戶對(duì)錯(cuò)誤進(jìn)行定位和檢查。 如果M文件沒(méi)有錯(cuò)誤（包括邏輯錯(cuò)誤和語(yǔ)法錯(cuò)誤），命令窗口就會(huì)顯示出運(yùn)算信息

5、，獲得與所有條件都相容的優(yōu)化結(jié)果。,9.1.1 線性規(guī)劃問(wèn)題 線性規(guī)劃（Linear Programming）是數(shù)學(xué)規(guī)劃中最簡(jiǎn)單和基本的問(wèn)題，它主要用來(lái)解決在有限的資源條件下完成最多的任務(wù)，或是確定如何統(tǒng)籌任務(wù)完成以使用最少的資源。 線性規(guī)劃的數(shù)學(xué)模型包括決策變量X、約束條件和目標(biāo)函數(shù)三個(gè)要素，它的決策變量是非負(fù)的，而且約束函數(shù)和目標(biāo)函數(shù)都是線性函數(shù)。 線性規(guī)劃的數(shù)學(xué)模型表示為,用于求解線性規(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ù)向量

6、； A和b是不等式約束函數(shù)的系數(shù)矩陣和常數(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ù)值。,例9-1 求解 線性規(guī)劃問(wèn)題 編制求解線性規(guī)劃問(wèn)題的M文件： % 求解線性規(guī)劃問(wèn)題 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=li

7、nprog(f,A,b,lb),由于線性規(guī)劃問(wèn)題中沒(méi)有等式約束，所以相應(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 可見(jiàn)，約束最優(yōu)解位于兩個(gè)邊界約束 和 的交集上。,9.1.2 二次規(guī)劃問(wèn)題 二次規(guī)劃問(wèn)題（Quadratic Programming）是最簡(jiǎn)單的非線性規(guī)劃問(wèn)題，其目標(biāo)函數(shù)是二次函數(shù)，而約束函數(shù)是線性函數(shù)。由于二次規(guī)劃問(wèn)題的求解比較成熟，有時(shí)可以將一些求解比較困難的一般非線性約束規(guī)

8、劃問(wèn)題轉(zhuǎn)化為較易處理的序列二次規(guī)劃子問(wèn)題求解。 用于求解二次規(guī)劃問(wèn)題的函數(shù)是 quadprog 二次規(guī)劃的 數(shù)學(xué)模型為,使用格式為 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ù)矩陣和常數(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ù)值。,例

9、9-2 求解約束優(yōu)化問(wèn)題 將目標(biāo)函數(shù)寫成二次函數(shù)的形式 其中：,線性不等式約束函數(shù)的系數(shù)矩陣和常數(shù)向量為 線性等式約束函數(shù)的系數(shù)矩陣和常數(shù)向量為 編制求解二次規(guī)劃的M文件 % 求解二次規(guī)劃問(wèn)題 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ì)變量的下限,xopt,fopt=quadprog(H,C,A,b,Aeq,be

10、q,lb) % 調(diào)用線性規(guī)劃函數(shù) % 最優(yōu)點(diǎn)的約束函數(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 可見(jiàn)，二次規(guī)劃的約束最優(yōu)解位于不等式約束和等式約束的交集。,9.1.3 無(wú)約束非線性規(guī)劃問(wèn)題 1、函數(shù)fminbnd應(yīng)用 函數(shù)fminbnd只能求解單變量的無(wú)約束非線性規(guī)劃問(wèn)題，而且要求目標(biāo)函數(shù)為連續(xù)函數(shù)。調(diào)用格式

11、xopt,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ù)（見(jiàn)表9-1）。例如options(1)為負(fù)值時(shí)，則顯示中間過(guò)程，默認(rèn)值是options(1)=0；options(2)為最優(yōu)解xopt的誤差范圍，默認(rèn)值是1e-4；等等。,輸出參數(shù)有： Xopt為返回的滿足fun取得最小值的x的值； fopt為目標(biāo)函數(shù)最小值； exitflag表示退出條件：exitflag0表示計(jì)算收斂，exitflag=0表示超過(guò)了最大

12、的迭代次數(shù)，exitflag 0表示計(jì)算不收斂。 output表示輸出信息，它有3分量：iterations表示迭代次數(shù)，funcCount表示代入函數(shù)次數(shù)，algorithm表示選用的優(yōu)化算法。 例9-3 求解單變量的無(wú)約束非線性規(guī)劃問(wèn)題,% 單變量函數(shù)的無(wú)約束非線性優(yōu)化 fun=(x5+x3+x2-1)/(exp(x2)+sin(-x); % 定義一維目標(biāo)函數(shù) xopt,fopt,exitflag,output= fminbnd(fun,-2,2) ezplot(fun,-2,2); % 繪制符號(hào)函數(shù)圖形 grid on; xlabel(bf x);ylabel(bf y); title(

13、bf單變量函數(shù)的無(wú)約束非線性優(yōu)化) gtext(bf y=(x5+x3+x2-1)/(ex2 +sin(-x); gtext(bf x*);,M文件運(yùn)行結(jié)果： xopt = 0.2176 fopt = -1.1312 exitflag = 1 output = iterations: 12 % 迭代次數(shù) funcCount: 13 % 調(diào)用函數(shù)次數(shù) algorithm: golden section search, parabolic interpolation message: 1x112 char,2、函數(shù)fminsearch應(yīng)用 函數(shù)fminsearch可用于求解單變量或多變量的無(wú)約束非

14、線性規(guī)劃問(wèn)題，它的優(yōu)化算法比較簡(jiǎn)單，適合處理目標(biāo)函數(shù)階次低、間斷點(diǎn)多和比較簡(jiǎn)單的優(yōu)化問(wèn)題。它的使用格式為 xopt,fopt,exitflag,output= fminsearch (fun,x0,options) 其中，輸出參數(shù)有： xopt和fopt分別是返回目標(biāo)函數(shù)的最優(yōu)解及其函數(shù)值。 返回參數(shù)exitflag表示退出條件：exitflag0表示計(jì)算收斂，exitflag=0表示超過(guò)了最大的迭代次數(shù)，exitflag 0表示計(jì)算不收斂。 返回參數(shù)output表示輸出信息，它有3分量：iterations表示迭代次數(shù)，funcCount表示代入函數(shù)次數(shù)，algorithm表示選用的優(yōu)化算法

15、。,輸入?yún)?shù)有： fun是目標(biāo)函數(shù)； x0是初始點(diǎn)； options是設(shè)置優(yōu)化選項(xiàng)參數(shù)（見(jiàn)表9-1）。如， options(1)為負(fù)值時(shí)，則顯示中間過(guò)程，默認(rèn)值是options(1)=0； options(2)為最優(yōu)解xopt的誤差范圍，默認(rèn)值是1e-4； options(3)為最優(yōu)解fopt的誤差范圍，默認(rèn)值是1e-4； options(14)是為函數(shù)求值的最大次數(shù)，默認(rèn)值是options(14)=200；等等。,例10-4 求二維無(wú)約束非線性函數(shù)的最優(yōu)解： % 二維無(wú)約束非線性優(yōu)化 fun=(x(1)2-2*x(1)*exp(-x(1)2-x(1)*x(2)-x(2)2); xopt,fo

16、pt,exitflag,output=fminsearch(fun,1,1) f=(x2-2*x)*exp(-x2-x*y-y2);% 符號(hào)函數(shù) ezmeshc(f); % 繪制符號(hào)函數(shù)圖形（含等高線） xlabel(bf x);ylabel(bf y);zlabel(bf f(x,y);,M文件運(yùn)行結(jié)果： xopt = 0.6111 -0.3055 fopt = -0.6414 exitflag = 1 output = iterations: 36 funcCount: 70 algorithm: Nelder-Mead simplex direct search message: 1x1

17、96 char,3、函數(shù)fminunc應(yīng)用 函數(shù)fminunc的優(yōu)化算法比較復(fù)雜，而且可供選擇的幾種不同算法，適用于求解比較復(fù)雜的優(yōu)化問(wèn)題。它的調(diào)用格式是： x，fval，exitflag，output，grad，hessian= fminunc(fun，x0，options，P1，P2) 其中，輸出參數(shù)有： x是返回目標(biāo)函數(shù)的最優(yōu)解； fval是返回目標(biāo)函數(shù)在最優(yōu)解x點(diǎn)的函數(shù)值； exitflag是返回算法的終止標(biāo)志； output是返回優(yōu)化算法的信息的一個(gè)數(shù)據(jù)結(jié)構(gòu)；,grad是返回目標(biāo)函數(shù)在最優(yōu)解x點(diǎn)的梯度； hessian是返回目標(biāo)函數(shù)最優(yōu)解x點(diǎn)hessian矩陣值 輸入?yún)?shù)有： fun

18、是調(diào)用目標(biāo)函數(shù)的函數(shù)文件名； x0是初始點(diǎn)； options是設(shè)置優(yōu)化選項(xiàng)參數(shù)（參考表9-1），包括有18個(gè)元素，用以在計(jì)算時(shí)控制精度要求、輸出形式、算法選擇、迭代次數(shù)、梯度等重要問(wèn)題，可用空矩陣符號(hào)“ ”表示它的默認(rèn)值； P1、P2等是傳遞給fun的附加參數(shù)。 例9-5 求二維無(wú)約束非線性函數(shù)的最優(yōu)解,% 二維無(wú)約束非線性優(yōu)化 % 函數(shù)fminunc求解二維無(wú)約束非線性優(yōu)化問(wèn)題 fun=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1) x0=0,0; options=optimset(largescale,off,display,iter,tol

19、x,1e-8,tolfun,1e-8); x,fval,exitflag,output,grad,hessian=fminunc(fun,x0,options) f=exp(x)*(4*x2+2*y2+4*x*y+2*y+1); ezmesh(f); % 繪制符號(hào)函數(shù)圖形 xlabel(bf x);ylabel(bf y);zlabel(bf f(x,y);,說(shuō)明：在優(yōu)化函數(shù)fminunc的輸入?yún)?shù)options命令中各個(gè)選項(xiàng)的意義是 largescale,off表示關(guān)閉了大規(guī)模方式； display用來(lái)控制計(jì)算過(guò)程的顯示； iter表示顯示優(yōu)化過(guò)程的每次計(jì)算結(jié)果（off不顯示所有輸出，fin

20、al僅輸出最后結(jié)果）； tolx,1e-8是控制輸入變量x的允許誤差精度； tolfun,1e-8是控制目標(biāo)函數(shù)的允許誤差精度（缺省值是1e-4）。 M文件運(yùn)算結(jié)果： fun = exp(x(1)*(4*x(1)2+2*x(2)2 +4*x(1)*x(2)+2*x(2)+1),x = 0.5000 -1.0000 % 極小點(diǎn) fval = 1.8304e-015 % 目標(biāo)和數(shù)值 exitflag = 1 output = iterations: 7 funcCount: 33 stepsize: 1 firstorderopt: 2.4568e-008 algorithm: medium-sc

21、ale: Quasi-Newton line search % 擬牛頓線搜索算法 message: 1x85 char grad = 1.0e-007 * % 極小點(diǎn)的梯度 0.2457 0 hessian = 13.1946 6.5953 % 海色矩陣 6.5953 6.5949,9.1.4 約束非線性規(guī)劃問(wèn)題 約束非線性規(guī)劃問(wèn)題 的數(shù)學(xué)模型表示為 函數(shù)fmincon的調(diào)用格式是： xopt，fopt，exitflag，output，hession= fmincon(fun，x0，A，b，Aeq，beq，Lb，Ub，Nlc，options，P1，P2，),其中，輸出參數(shù)有： xopt是返回目

22、標(biāo)函數(shù)的最優(yōu)解； fopt是返回目標(biāo)函數(shù)在最優(yōu)解x點(diǎn)的函數(shù)值； exitflag是返回算法的終止標(biāo)志； output是返回優(yōu)化算法的信息的一個(gè)數(shù)據(jù)結(jié)構(gòu)； grad是返回目標(biāo)函數(shù)在最優(yōu)解x點(diǎn)的梯度； hessian是是返回目標(biāo)函數(shù)在最優(yōu)解x點(diǎn)的hessian矩陣值。 輸入?yún)?shù)有： fun是調(diào)用目標(biāo)函數(shù)的函數(shù)文件名； x0是初始點(diǎn)；,線性不等式約束條件的系數(shù)矩陣A和常數(shù)向量b； 線性等式約束條件的系數(shù)矩陣Aeq和常數(shù)向量beq； 設(shè)計(jì)變量的下界向量Lb和上界向量Ub； Nlc是定義非線性約束條件的函數(shù)名； options是設(shè)置優(yōu)化選項(xiàng)參數(shù)，參考表9-1； P1、P2等是傳遞給fun的附加參數(shù)。 參

23、數(shù)A，b，Aeq，beq，Lb，Ub，options如果沒(méi)有定義，可用空矩陣符號(hào)“ ”代替。,例9-6 求解約束非線性規(guī)劃問(wèn)題,% 約束非線性優(yōu)化問(wèn)題 % 1-目標(biāo)函數(shù)文件objfun.m function f=objfun(x) f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1); % 2-非線性約束函數(shù)文件confun.m function c,ceq=confun(x) % 非線性不等式約束 c(1)=1.5+x(1)*x(2)-x(1)-x(2); c(2)=-x(1)*x(2)-10; % 非線性等式約束 ceq=;,% 3-優(yōu)化函數(shù)應(yīng)

24、用 x0=-1 1; % 設(shè)計(jì)變量初值 A=1,1;b=0; % 描述線性不等式約束g3（X） Aeq=;beq=; % 沒(méi)有線性等式約束 lb=-10,-10; % 設(shè)計(jì)變量下限 ub=10,10; % 設(shè)計(jì)變量上限 options=optimset(largescale,off,display,iter); xopt,fval,exitflag,output=fmincon(objfun,x0,A,b,Aeq,beq,lb,ub,confun,options) c=confun(xopt) % 最優(yōu)點(diǎn)的非線性約束函數(shù)值,M文件運(yùn)行結(jié)果： xopt = -9.5474 1.0474 fval

25、 = 0.0236 exitflag = 1 output = iterations: 8 funcCount: 28 stepsize: 1 algorithm: medium-scale: SQP, Quasi-Newton, line-search firstorderopt: 8.5131e-007 cgiterations: message: 1x144 char c = 1.0e-007 * -0.9031 0.9031,9.1.5 多目標(biāo)規(guī)劃問(wèn)題 在規(guī)劃問(wèn)題中，目標(biāo)函數(shù)根據(jù)工程優(yōu)化設(shè)計(jì)問(wèn)題的主要準(zhǔn)則 或幾個(gè)設(shè)計(jì)準(zhǔn)則 來(lái)建立的。如果某項(xiàng)設(shè)計(jì)要求同時(shí)兼顧若干項(xiàng)設(shè)計(jì)目標(biāo)達(dá)到最優(yōu)，則屬于

26、多目標(biāo)優(yōu)化設(shè)計(jì)問(wèn)題。其中，由各項(xiàng)設(shè)計(jì)準(zhǔn)則 建立的目標(biāo)函數(shù)，稱為分目標(biāo)函數(shù)。多目標(biāo)優(yōu)化問(wèn)題要比單目標(biāo)優(yōu)化問(wèn)題復(fù)雜得多。 將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，使多目標(biāo)優(yōu)化問(wèn)題解的半有序性轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題解的完全有序性。這種轉(zhuǎn)化后問(wèn)題的解往往是原多目標(biāo)優(yōu)化問(wèn)題的一個(gè)或部分非劣解，不是全部的非劣解。如何得到一個(gè)能夠接受的最好非劣解，關(guān)鍵在于選擇某種形式的折中。,MATLAB優(yōu)化工具箱函數(shù)fgoalattain用于求解的多目標(biāo)優(yōu)化問(wèn)題，也稱為目標(biāo)達(dá)到問(wèn)題。其形式： 其中， 是各個(gè)分目標(biāo)函數(shù)， 和 是各個(gè)分目標(biāo)及其權(quán)重向量。,函數(shù)fgoalattain的使用格式為： xopt，fopt，exitfl

27、ag，output，hession= fgoalattain (fun，x0，goal，w，A，b，Aeq，beq，Lb，Ub，Nlc，options，P1，P2，) 其中，輸出參數(shù)有： xopt是返回目標(biāo)函數(shù)的最優(yōu)解； fopt是返回目標(biāo)函數(shù)在最優(yōu)解x點(diǎn)的函數(shù)值； exitflag是返回算法的終止標(biāo)志； output是返回優(yōu)化算法的信息的一個(gè)數(shù)據(jù)結(jié)構(gòu)； grad是返回目標(biāo)函數(shù)在最優(yōu)解x點(diǎn)的梯度； hessian是是返回目標(biāo)函數(shù)在最優(yōu)解x點(diǎn)的Hessian矩陣值。,輸入?yún)?shù)有： fun是調(diào)用目標(biāo)函數(shù)的函數(shù)文件名； x0是初始點(diǎn)； goal各個(gè)分目標(biāo)； w是各個(gè)分目標(biāo)的權(quán)重； 線性不等式約束條件

28、的系數(shù)矩陣A和常數(shù)向量b； 線性等式約束的系數(shù)矩陣Aeq和常數(shù)向量beq； 設(shè)計(jì)變量的下界向量Lb和上界向量Ub； Nlc是定義非線性約束條件的函數(shù)名； options是設(shè)置優(yōu)化選項(xiàng)參數(shù)，參考表9-1； P1、P2等是傳遞給fun的附加參數(shù)。,例9-7 求解多目標(biāo)線性規(guī)劃問(wèn)題： 已知設(shè)計(jì)變量初值x0=20,10,30,0，分目標(biāo)的初值f0=10000,40，分目標(biāo)的權(quán)重w=1,2e-4。,編制目標(biāo)函數(shù)文件： % 目標(biāo)函數(shù)fun_opt.m function f= fun_opt(x) f(1)= -(100*x(1)+90*x(2)+80*x(3)+70*x(4); f(2)=3*x(2)+2

29、*x(4); 編制多目標(biāo)優(yōu)化函數(shù)調(diào)用文件： % 多目標(biāo)規(guī)劃函數(shù)應(yīng)用 % 線性不等式約束條件的系數(shù)矩陣和常數(shù)向量 A= -1 -1 0 0; 0 0 -1 -1; 3 0 2 0; 0 3 0 2; b=-30 -30 120 48;,% 線性等式約束條件的系數(shù)矩陣和常數(shù)向量 Aeq=;beq=; % 設(shè)計(jì)變量的邊界條件 lb=zeros(1,4);ub=; % 設(shè)計(jì)變量和分目標(biāo)的初值 x0=20,10,30,0; f0=10000,40; % 分目標(biāo)的權(quán)重 w=1 2e-4; % 使用函數(shù)fgoalattain.m xopt,fopt=fgoalattain(fun_opt,x0,f0,w,A

30、,b,Aeq,beq,lb,ub),計(jì)算結(jié)果： Optimization terminated: Search direction less than 2*options.TolX and maximum constraint violation is less than options.TolCon. Active inequalities (to within options.TolCon = 1e-006): lower upper ineqlin ineqnonlin 4 1 1 3 2 xopt = 17.7035 12.2965 33.4447 -0.0000 fopt = 1.0

31、e+003 * -5.5526 0.0369,9.2 遺傳算法,遺傳算法從一個(gè)代表優(yōu)化問(wèn)題解的一組初值進(jìn)行搜索，這組解稱為一個(gè)種群（population），它們由一定數(shù)量的通過(guò)基因編碼的個(gè)體組成。種群中的每個(gè)個(gè)體稱為染色體（chromosome），它用一串代碼來(lái)標(biāo)識(shí)。不同的個(gè)體通過(guò)染色體的復(fù)制（copy）、交叉（crossover）或變異（mutation）生成新的后代（offspring）。后代也在一代一代地進(jìn)化，在每一代中使用“適應(yīng)度”（fitness）評(píng)估來(lái)檢驗(yàn)染色體的優(yōu)劣，根據(jù)適應(yīng)度的大小選擇淘汰部分劣質(zhì)后代，選擇部分優(yōu)良品質(zhì)（特征）后代得以保留和組合，使整個(gè)種群向優(yōu)化方向發(fā)展，經(jīng)過(guò)若

32、干代進(jìn)化后最終得出條件最優(yōu)個(gè)體作為算法的收斂條件。,1、編碼：先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，它們的不同組合就構(gòu)成了不同的點(diǎn)。 2、生成初始種群：采用隨機(jī)方法產(chǎn)生若干個(gè)初始串結(jié)構(gòu)數(shù)據(jù)，每個(gè)串結(jié)構(gòu)數(shù)據(jù)代表一個(gè)個(gè)體，全體初始串結(jié)構(gòu)數(shù)據(jù)構(gòu)成了初始種群。初始種群的大小一般是20-100，這樣既可以提高遺傳算法的穩(wěn)定性，又能夠保證種群的多樣性，容易獲得全局最優(yōu)解。 3、適應(yīng)度評(píng)估：對(duì)于不同的優(yōu)化問(wèn)題，采用不同的適應(yīng)度函數(shù)來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣性。 4、選擇：按照適者生存的目的，從當(dāng)前的種群中選擇出適應(yīng)度強(qiáng)的優(yōu)良個(gè)體，使它們有機(jī)會(huì)作為父代繁殖下一代，為下一代貢獻(xiàn)一個(gè)或多個(gè)后代的概率大。,5、

33、交叉：交叉算子根據(jù)交叉率將種群中兩個(gè)個(gè)體隨機(jī)地交換某些基因，從而產(chǎn)生新一代個(gè)體。新個(gè)體組合了父輩個(gè)體的特性，交叉體現(xiàn)了信息交換的思想。交叉率的選擇是根據(jù)具體問(wèn)題確定，一般取0.250.75，這樣既可以得到高適應(yīng)度的結(jié)構(gòu)，又可以保證搜索效率。 6、變異：變異算子根據(jù)變異率隨機(jī)地在當(dāng)前種群中選擇一個(gè)個(gè)體，對(duì)其以一定的概率隨機(jī)地改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)串的數(shù)值，從而產(chǎn)生新一代個(gè)體。由于生物界產(chǎn)生變異的概率很低，因此變異率一般取0.010.20。 交叉和變異是遺傳運(yùn)算的重要內(nèi)容。交叉是最主要的遺傳運(yùn)算，它在很大程度上決定了遺傳算法的性能。變異是基本的遺傳運(yùn)算，它在染色體上自發(fā)地產(chǎn)生隨機(jī)變化。,9.2.1

34、遺傳優(yōu)化算法函數(shù) 1、搜索函數(shù) 遺傳優(yōu)化算法工具箱中搜索函數(shù)ga的調(diào)用格式是 xf,endPop,bPop,trace= ga(bounds,evalFN,evalOps,startPop, opts, termFN,termOps,selectFN,selectOps,xOverFNs, xOverops,mutFNs,mutOps) 其中，輸出參數(shù)： xf是優(yōu)化解； endPop是最終種群； bPop是最終種群的一個(gè)軌跡； trace是每一代種群中的最好個(gè)體和平均結(jié)果矩陣。,輸入?yún)?shù)： bounds是變量上下限矩陣； evalFN是適應(yīng)度函數(shù)； evalOps是適應(yīng)度函數(shù)的輸入選項(xiàng)，缺省為

35、； startPop是初始種群； opts是向量epsilon prob_ops display，其中epsilon表示兩代之間的差距，prob_ops取0時(shí)為二進(jìn)制編碼，取1時(shí)為浮點(diǎn)編碼（計(jì)算精度較高），display表示運(yùn)行時(shí)是否顯示當(dāng)前個(gè)體和最好結(jié)果。默認(rèn)值1e-6 1 0； termFN是終止函數(shù)，默認(rèn)值maxGenterm； termOps是向終止函數(shù)輸入的參數(shù)，默認(rèn)100；,selectFN是選擇函數(shù)； selectOps是選擇參數(shù)； xOverFNs是一個(gè)包含空格字符串xOver.m文件； xOverops是xOver.m文件的輸入?yún)?shù)矩陣； mutFNs是一個(gè)包含空格字符串mu

36、tation.m文件； mutOps是mutation.m文件的輸入?yún)?shù)矩陣。 應(yīng)當(dāng)指出，遺傳算法搜索函數(shù)ga求的是函數(shù)的極大值，因此在求函數(shù)的極小值問(wèn)題時(shí)需要將極大值問(wèn)題轉(zhuǎn)換為極小值問(wèn)題。 2、編碼和種群生成函數(shù) 遺傳優(yōu)化算法工具箱中編碼和種群生成函數(shù)initializega的調(diào)用格式是,Function Pop= initializega(num,bounds, eevalFN,eevalOps,options) 其中，輸出參數(shù)： Pop是生成的初始種群； 輸入?yún)?shù)： num是種群中的個(gè)體數(shù)目； bounds是變量上下限矩陣； eevalFN是適應(yīng)度函數(shù)； eevalOps是傳遞給適應(yīng)度函

37、數(shù)參數(shù)，默認(rèn) ； options是選擇編碼形式的參數(shù)：浮點(diǎn)編碼（默認(rèn)值 ）或是二進(jìn)制編碼。,9.2.2 無(wú)約束優(yōu)化的遺傳算法 1、一維無(wú)約束優(yōu)化的遺傳算法 例9-8 采用遺傳算法求解一維函數(shù) 在 范圍內(nèi)，函數(shù)取最大值時(shí)自變量值 1、使用優(yōu)化工具箱中優(yōu)化函數(shù)fmincon進(jìn)行計(jì)算 % 定義函數(shù)和變量 f=inline(15*sin(x/3)-20*cos(x/4)+50,x);,% 使用優(yōu)化函數(shù)fmincon計(jì)算 for x0=0:2:80,0:4:80 % 任意選擇初值 x=fmincon(f,x0,0,80); xf=;x0,x,f(x); end M文件運(yùn)行結(jié)果： Optimization

38、 terminated: magnitude of directional derivative in search direction less than 2*options.TolFun and maximum constraint violation is less than options.TolCon. No active inequalities. 可見(jiàn)，在求解區(qū)間內(nèi)任意選擇初值，并不能得到滿意的結(jié)果。,繪制該一維非線性函數(shù)的圖形，它是一條振蕩曲線，在解的區(qū)間0,80內(nèi)有多個(gè)極值點(diǎn)。,3、采用遺傳優(yōu)化算法求解 定義適應(yīng)度 % 定義適應(yīng)度函數(shù)文件 function sol,y=max

39、f_1(sol,options) x=sol(1); y=15*sin(x/3)-20*cos(x/4)+50; 生成初始種群，個(gè)體數(shù)目取15 % 生成初始種群，個(gè)體數(shù)目取15 startPop=initializega(15,0,80,maxf_1) % 在圖中以綠色“o”號(hào)標(biāo)示初始種群 plot(startPop(:,1),startPop(:,2),go); title(bf 一維非線性函數(shù)線圖和初始種群及遺傳優(yōu)化),調(diào)用遺傳優(yōu)化算法函數(shù)，取進(jìn)化繁殖100代，變異概率為0.08，浮點(diǎn)編碼 % 遺傳優(yōu)化算法搜索 xf,endPop,bPop,trace=ga(0,80,maxf_1,sta

40、rtPop,1e-6 1 1, maxGenterm, 100,normGeomSelect,0.08,arithXover,2,nonUnifMutation,2 100 3); xf % 在圖中以紅色“*”號(hào)標(biāo)示最優(yōu)種群 plot(endPop(:,1),endPop(:,2),r*); legend(圓圈：初始種群,星號(hào)：最優(yōu)種群) M文件運(yùn)行后，最優(yōu)種群的星號(hào)標(biāo)記在圖9-4中，計(jì)算結(jié)果是：,表9-2 遺傳算法搜索的中間結(jié)果,從表9-2可見(jiàn)，從第52代開(kāi)始，就可以得到較精確的結(jié)果。經(jīng)過(guò)100代搜索，獲得最優(yōu)種群及函數(shù)值 xf = 61.9343 84.1225 描述遺傳算法搜索過(guò)程 fi

41、gure(2); plot(trace(:,1),trace(:,2),b:);hold on; plot(trace(:,1),trace(:,3),r);grid; xlabel(bf Generation);ylabel(bf Fitness); title(bf 一維非線性遺傳算法的各代最好解與平均值); legend(虛線：各代種群平均值,實(shí)線：各代最優(yōu)解),2、多維無(wú)約束優(yōu)化的遺傳算法 例9-9 采用遺傳算法求解二維非線性優(yōu)化問(wèn)題 1、繪制二維非線性函數(shù)圖形 x=linspace(-3,12,35);y=linspace(4,6,15); x1,x2=meshgrid(x,y);

42、f=x1.*sin(4*pi*x1)+x2.*sin(20*pi.*x2)+21.5; surf(x1,x2,f);xlabel(bf x_1); ylabel(bf x_2);zlabel(bf f(x_1,x_2),title(bf f(x_1,x_2)=x_1sin(4pix_1) +x_2sin(20pix_2)+21.5),2、定義適應(yīng)度函數(shù) % 定義適應(yīng)度函數(shù)文件 function sol,y=minf_2(sol,options) x(1)=sol(1);x(2)=sol(2); y=x(1).*sin(4*pi.*x(1)+x(2).*sin(20*pi.*x(2)+21.5;

43、 3、生成初始種群 % 生成初始種群，個(gè)體數(shù)目取10 bounds=-3 12;4 6; % 變量上下限 initPop=initializega(10,bounds,minf_2);,4、采用遺傳優(yōu)化算法求解，進(jìn)化繁殖200代，其他默認(rèn)缺省參數(shù) % 遺傳優(yōu)化算法搜索 xf,endPop,beestSols,trace=ga(bounds,minf_2,maxGenTerm,200); beestSols xf M文件運(yùn)行結(jié)果是： xf = 11.6255 5.9250 39.0503 運(yùn)算結(jié)果表明，繁殖到第67代時(shí)獲得最優(yōu)解,5、描述遺傳算法搜索過(guò)程 plot(trace(:,1),trac

44、e(:,2),b:); hold on; plot(trace(:,1),trace(:,3),r); grid; xlabel(bf Generation);ylabel(bf Fitness); title(bf 二維非線性遺傳算法的各代最好解與平均值); legend(虛線：各代種群平均值,實(shí)線：各代最優(yōu)解) M文件運(yùn)行結(jié)果如圖9-7所示，圖中實(shí)線表示各代最優(yōu)解，虛線表示各代種群平均值。,9.2.3 約束優(yōu)化的遺傳算法 對(duì)于實(shí)際工程優(yōu)化問(wèn)題大都是約束優(yōu)化問(wèn)題，不能直接用經(jīng)典的遺傳算法求解。將約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，再用無(wú)約束優(yōu)化方法來(lái)求解。 對(duì)于約束優(yōu)化問(wèn)題，如果存在不等式約束

45、，可以利用懲罰函數(shù)方法將不等式約束函數(shù)構(gòu)造為目標(biāo)函數(shù)中懲罰項(xiàng)的方法，將約束優(yōu)化問(wèn)題轉(zhuǎn)換為無(wú)約束優(yōu)化問(wèn)題的泛函形式；如果存在等式約束，可以通過(guò)將等式約束求解的方法將其中的若干自變量表示成其他自變量的形式。也可以將不滿足等式約束時(shí)的目標(biāo)函數(shù)人為地設(shè)置為負(fù)數(shù)，迫使遺傳算法搜索脫離這樣的值。,1、懲罰函數(shù)法基本原理 懲罰函數(shù)法是一種求解約束優(yōu)化問(wèn)題的間接解法，它將約束優(yōu)化問(wèn)題轉(zhuǎn)化為一系列無(wú)約束優(yōu)化問(wèn)題來(lái)求解。根據(jù)懲罰項(xiàng)的函數(shù)形式不同，懲罰函數(shù)法又分為外點(diǎn)懲罰函數(shù)法和內(nèi)點(diǎn)懲罰函數(shù)法和混合懲罰函數(shù)法三種。 常用的外點(diǎn)懲罰函數(shù)法的基本原理是將約束優(yōu)化問(wèn)題,構(gòu)造為等價(jià)的參數(shù)型目標(biāo)函數(shù)，即懲罰函數(shù) 式中，泛函

46、定義全域： 如果迭代點(diǎn)在可行域內(nèi)，因?yàn)橛?，故 ，懲罰函數(shù)不受懲罰； 如果迭代點(diǎn)在可行域外，因?yàn)橛?，故 ，懲罰函數(shù)受到懲罰 外點(diǎn)懲罰函數(shù)法是將懲罰函數(shù)定義在可行域外部，在求解序列無(wú)約束優(yōu)化問(wèn)題的過(guò)程中，從可行域外部逐漸逼近原約束優(yōu)化問(wèn)題的最優(yōu)解。,2、多維約束線性優(yōu)化的遺傳算法 例9-10 采用遺傳算法 求解3維約束 線性優(yōu)化問(wèn)題 1、編制目標(biāo)函數(shù)文件 根據(jù)等式約束條件 ，得 原3維線性規(guī)劃問(wèn)題就轉(zhuǎn)化為2維線性規(guī)劃問(wèn)題。 對(duì)于不滿足不等式約束條件時(shí)，人為地將目標(biāo)函數(shù)設(shè)置為-100，有意排除這種種群。,% 定義適應(yīng)度函數(shù)文件 function sol,y=minf_3(sol,options) x=sol(1:2);x=x(:);x(3)=(6+4*x(1)-2*x(2)/3; y1=-2 1 1*x; % 線性不等式約束函數(shù)1 y2=-1 1 0*x; % 線性不等式約束函數(shù)2 % 將不等式約束設(shè)置為適應(yīng)度函數(shù)的條件 if (y19 | y2-4 | x(3)0) y=-100; % 不滿足約束條件時(shí)，目標(biāo)函數(shù)值為負(fù) else y=-1 2 3*x; % 滿足約束條件時(shí)，目標(biāo)函數(shù)表達(dá)式 end,2、調(diào)用遺傳優(yōu)化算法函數(shù)，進(jìn)化繁殖999代，其他默認(rèn)缺省參數(shù) % 生成初始種群，個(gè)體數(shù)目取10 boun