智能優(yōu)化方法及MATLAB-GA工具箱簡介

智能優(yōu)化方法及MATLABGA工具箱簡介2011.4自動化創(chuàng)新實(shí)踐課程專題講座陸寧云目錄1優(yōu)化問題2經(jīng)典優(yōu)化方法3現(xiàn)代優(yōu)化方法4遺傳算法5基于GA的優(yōu)化問題求解實(shí)例6Matlab的GA工具箱簡介優(yōu)化問題簡介生活中經(jīng)常遇到的求利潤最大、用料最省、效率最高等問題，都是優(yōu)化問題。所謂最優(yōu)化問題就是在滿足一定的約束條件下，尋找一組參數(shù)值，以使某些最優(yōu)性度量得到滿足，即使系統(tǒng)的某些性能指標(biāo)達(dá)到最大或最小。最優(yōu)化問題描述：其中

為目標(biāo)函數(shù)，

為約束函數(shù)，S為約束域。經(jīng)典優(yōu)化方法非線性規(guī)劃線性規(guī)劃動態(tài)規(guī)劃。。。整數(shù)規(guī)劃多目標(biāo)規(guī)劃1線性規(guī)劃研究線性約束條件下線性目標(biāo)函數(shù)的極值問題的數(shù)學(xué)理論和方法。2非線性規(guī)劃具有非線性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃。3動態(tài)規(guī)劃解決多階段決策過程最優(yōu)化問題的優(yōu)化方法。本質(zhì)上還是一種非線性規(guī)劃方法，核心是Bellman提出的最優(yōu)性原理。經(jīng)典優(yōu)化方法4多目標(biāo)規(guī)劃研究目標(biāo)函數(shù)多于一個時的最優(yōu)化問題。5整數(shù)規(guī)劃要求問題的最優(yōu)解中的全部或一部分變量為整數(shù)的數(shù)學(xué)規(guī)劃。從約束條件的構(gòu)成又可細(xì)分為線性，二次和非線性的整數(shù)規(guī)劃經(jīng)典優(yōu)化方法缺點(diǎn)：應(yīng)用對象受限，計(jì)算量大，收斂速度慢現(xiàn)代優(yōu)化算法又稱智能優(yōu)化算法或現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù),而不是單純憑借專家經(jīng)驗(yàn)，理論上可以在一定的時間內(nèi)找到最優(yōu)解或近似最優(yōu)解?，F(xiàn)代優(yōu)化方法模擬物理中固體退火原理（加溫，等溫，冷卻），從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解是一種全局性鄰域搜索算法，模擬人類具有記憶功能的尋優(yōu)特征。它通過局部鄰域搜索機(jī)制和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，并通過破禁水平來釋放一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索，以最終實(shí)現(xiàn)全局優(yōu)化。由大量處理單元互聯(lián)組成的非線性、自適應(yīng)信息處理系統(tǒng)。是由人工建立的以有向圖為拓?fù)浣Y(jié)構(gòu)的動態(tài)系統(tǒng)，它通過對連續(xù)或斷續(xù)的輸入作狀態(tài)響應(yīng)而進(jìn)行信息處理禁忌搜索算法模擬退火算法人工神經(jīng)網(wǎng)絡(luò)現(xiàn)代優(yōu)化方法是通過模擬。鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機(jī)搜索算法。系統(tǒng)初始化為一組隨機(jī)解，通過迭代搜尋最優(yōu)值。與GA類似。模擬螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法蟻群算法粒子群算法現(xiàn)代優(yōu)化方法遺傳算法(GeneticAlgorithm,GA)：

現(xiàn)代優(yōu)化方法GA遺傳算法是20世紀(jì)60年代由美國Michigan大學(xué)的J.H.Holland教授首先提出的，主要模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，把搜索空間映射為遺傳空間，把可能的解編碼成一個向量——染色體，向量的每個元素成為基因。通過不斷計(jì)算各染色體的適應(yīng)值，獲得最優(yōu)解。遺傳學(xué)中常用的詞匯：

細(xì)胞(Cell)：構(gòu)成生物的基本的結(jié)構(gòu)和單位。

染色體(Chromosome):細(xì)胞中含有的一種微小絲狀化合物。

基因(Gene):遺傳的基本單位。

復(fù)制(reproduction):細(xì)胞在分裂時，遺傳物質(zhì)DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，并集成舊細(xì)胞的基因?，F(xiàn)代優(yōu)化方法遺傳算法

交叉(Crossover):兩個同源染色體之間通過交叉而重組。

變異(Mutation)：在細(xì)胞復(fù)制時，可能產(chǎn)生復(fù)制差錯，從而使DNA發(fā)生變異，產(chǎn)生出新的染色體。

進(jìn)化(Evolution):生物在其延續(xù)生存的過程中，逐漸適應(yīng)于其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱之為進(jìn)化

群體(Population):生物進(jìn)化是以集團(tuán)的形式進(jìn)行的，這樣的集團(tuán)稱為群體現(xiàn)代優(yōu)化方法遺傳算法

適應(yīng)度(Fitness):每個個體對其生存環(huán)境都有不同的適應(yīng)能力，這種適應(yīng)能力稱為適應(yīng)度現(xiàn)代優(yōu)化方法遺傳算法現(xiàn)代優(yōu)化方法遺傳算法求解問題流程編碼，初始種群個體適應(yīng)度評價(jià)遺傳算子停止準(zhǔn)則編碼（解碼）：一般采用二進(jìn)制0/1字符編碼。x(十進(jìn)制數(shù))y(二進(jìn)制數(shù))現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)編碼解碼轉(zhuǎn)換精度：產(chǎn)生初始群體MM越大，搜索范圍越寬，但每代的遺傳操作時間越長；M越小，搜索范圍越小，但每代的遺傳操作時間越短。

通常：M=20~100現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)個體適應(yīng)度評價(jià)

在GA中，以個體適應(yīng)度的大小來確定該個體被遺傳到下一代的概率。個體適應(yīng)度越高，被選中的概率越大（要求個體適應(yīng)度

）。

對于求目標(biāo)函數(shù)最大值的優(yōu)化問題

對于求目標(biāo)函數(shù)最大值的優(yōu)化問題

現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)個體被選中的概率其中現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)顯然，個體適應(yīng)度越高，被選中的概率越大遺傳算子：現(xiàn)代優(yōu)化方法選擇交叉變異遺傳算法實(shí)現(xiàn)選擇(Selection)：

根據(jù)個體的相對適應(yīng)度反復(fù)地從群體中選擇M個個體組成下一代群體。

選擇算法：輪盤賭選擇隨機(jī)遍歷抽樣現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)截?cái)噙x擇錦標(biāo)賽選擇交叉(Crossover)

在GA中交叉是產(chǎn)生新個體的主要手段，類似于生物學(xué)的雜交，使不同個體的基因互相交換，從而產(chǎn)生新個體。

交叉原理：a）對群體中的個體進(jìn)行兩兩配對，當(dāng)群體總數(shù)為M，則共有M/2對相互配對的個體組現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)b)設(shè)置交叉點(diǎn)，隨機(jī)設(shè)置某一基因座后的位置為交叉點(diǎn)，若染色體長度為L，則共有L-1個可能的交叉點(diǎn)位置。C)設(shè)置交叉概率Pc。

被交叉的個體數(shù)目：Mc=Pc*M現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)交叉示例：11111111父代1111000000000000子代111100000000000011111111交叉點(diǎn)位置現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)交叉方法單點(diǎn)交叉多點(diǎn)交叉均勻交叉洗牌交叉現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)變異(Mutation)

以變異概率Pm改變?nèi)旧w的某一個基因,當(dāng)以二進(jìn)制編碼時，變異的基因由0變成1，或者由1變成0。變異過程：

a）依據(jù)變異概率Pm指定變異點(diǎn)。b）對指定的變異點(diǎn)進(jìn)行取反運(yùn)算?，F(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)Pm=0.01~0.001變異示例11010100父代01010101子代變異基因變異基因現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)停止準(zhǔn)則

a）種群中個體的最大適應(yīng)值超過預(yù)設(shè)定值

b）種群中個體的平均適應(yīng)值超過預(yù)設(shè)定值

c）種群中個體的進(jìn)化代數(shù)超過預(yù)設(shè)定值現(xiàn)代優(yōu)化方法遺傳算法的實(shí)現(xiàn)現(xiàn)代優(yōu)化方法基于GA的優(yōu)化問題求解實(shí)例計(jì)算由簡單的代數(shù)運(yùn)算我們知道x=31。

采用GA：1）編碼：2）形成初始群體，計(jì)算適應(yīng)度現(xiàn)代優(yōu)化方法基于GA的優(yōu)化問題求解實(shí)例個體編號初始群體適應(yīng)度

101101131690.14211000245760.493010008640.06410011193610.31復(fù)制淘汰選擇后的新一代群體：01101，11000,11000,10011現(xiàn)代優(yōu)化方法基于GA的優(yōu)化問題求解實(shí)例個體編號復(fù)制初始群體復(fù)制后交換對象交換位置交換后群體交換后1011011316922011001442110002457612110016253110002447643110117294100111936133100002563）復(fù)制與交叉4）變異

設(shè)置變異點(diǎn)，將個體字符串某位符號進(jìn)行逆變。5）終止

反復(fù)執(zhí)行直到得到滿意的結(jié)果現(xiàn)代優(yōu)化方法基于GA的優(yōu)化問題求解實(shí)例現(xiàn)代優(yōu)化方法Matlab的GA工具箱使用簡介利用遺傳算法函數(shù)ga求解兩種方案利用遺傳算法工具箱gatool求解遺傳算法函數(shù)：[x,fval]=ga(fitnessfun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)

輸出函數(shù)：x-----最優(yōu)解fval-----最優(yōu)適應(yīng)度輸入函數(shù)fitnessfun-----適應(yīng)度函數(shù)nvars-----變量個數(shù)

現(xiàn)代優(yōu)化方法Matlab的GA工具箱使用簡介輸入?yún)?shù)A,b----不等式約束Aeq,beq----等式約束Lb,ub----變量的上下限nonlcon----非線性函數(shù)約束options----傳遞給ga的參數(shù)，不寫matlab自動取默認(rèn)值,參考gaoptimset現(xiàn)代優(yōu)化方法Matlab的GA工具箱使用簡介

遺傳算法工具箱gatool在matlab控制窗口輸入>>gatool打開ga工具箱，控制界面如下圖現(xiàn)代優(yōu)化方法Matlab的GA工具箱使用簡介現(xiàn)代優(yōu)化方法Matlab的GA工具箱使用簡介實(shí)例講解：將目標(biāo)函數(shù)創(chuàng)建為Simple_objective的m文件：functiony=simple_objective(x)y=100*(x(1)^2-x(2))^2+(1-x(1))^2;

現(xiàn)代優(yōu)化方法Matlab的GA工具箱使用簡介將非線性約束函數(shù)創(chuàng)建為simple_constraint的m文件：

function[c,ceq]=simple_constraint(x)c=[1.5+x(1)*x(2)+x(1)-x(2);-x(1)*x(2)+10];ceq=[];

用ga函數(shù)求解，對應(yīng)的程序如下現(xiàn)代優(yōu)化方法Matlab的GA工具箱使用簡介

ObjectiveFunction=@simple_objective;

nvars=2;%NumberofvariablesLB=[00];%LowerboundUB=[113];%Upperbound

ConstraintFunction=@simple_