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

為目標函數，

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

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

細胞(Cell)：構成生物的基本的結構和單位。

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

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

復制(reproduction):細胞在分裂時，遺傳物質DNA通過復制而轉移到新產生的細胞中，并集成舊細胞的基因。現代優化方法遺傳算法

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

變異(Mutation)：在細胞復制時，可能產生復制差錯，從而使DNA發生變異，產生出新的染色體。

進化(Evolution):生物在其延續生存的過程中，逐漸適應于其生存環境，使得其品質不斷得到改良，這種生命現象稱之為進化

群體(Population):生物進化是以集團的形式進行的，這樣的集團稱為群體現代優化方法遺傳算法

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

通常：M=20~100現代優化方法遺傳算法的實現個體適應度評價

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

）。

對于求目標函數最大值的優化問題

對于求目標函數最大值的優化問題

現代優化方法遺傳算法的實現個體被選中的概率其中現代優化方法遺傳算法的實現顯然，個體適應度越高，被選中的概率越大遺傳算子：現代優化方法選擇交叉變異遺傳算法實現選擇(Selection)：

根據個體的相對適應度反復地從群體中選擇M個個體組成下一代群體。

選擇算法：輪盤賭選擇隨機遍歷抽樣現代優化方法遺傳算法的實現截斷選擇錦標賽選擇交叉(Crossover)

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

交叉原理：a）對群體中的個體進行兩兩配對，當群體總數為M，則共有M/2對相互配對的個體組現代優化方法遺傳算法的實現b)設置交叉點，隨機設置某一基因座后的位置為交叉點，若染色體長度為L，則共有L-1個可能的交叉點位置。C)設置交叉概率Pc。

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

以變異概率Pm改變染色體的某一個基因,當以二進制編碼時，變異的基因由0變成1，或者由1變成0。變異過程：

a）依據變異概率Pm指定變異點。b）對指定的變異點進行取反運算。現代優化方法遺傳算法的實現Pm=0.01~0.001變異示例11010100父代01010101子代變異基因變異基因現代優化方法遺傳算法的實現停止準則

a）種群中個體的最大適應值超過預設定值

b）種群中個體的平均適應值超過預設定值

c）種群中個體的進化代數超過預設定值現代優化方法遺傳算法的實現現代優化方法基于GA的優化問題求解實例計算由簡單的代數運算我們知道x=31。

采用GA：1）編碼：2）形成初始群體，計算適應度現代優化方法基于GA的優化問題求解實例個體編號初始群體適應度

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

設置變異點，將個體字符串某位符號進行逆變。5）終止

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

輸出函數：x-----最優解fval-----最優適應度輸入函數fitnessfun-----適應度函數nvars-----變量個數

現代優化方法Matlab的GA工具箱使用簡介輸入參數A,b----不等式約束Aeq,beq----等式約束Lb,ub----變量的上下限nonlcon----非線性函數約束options----傳遞給ga的參數，不寫matlab自動取默認值,參考gaoptimset現代優化方法Matlab的GA工具箱使用簡介

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

現代優化方法Matlab的GA工具箱使用簡介將非線性約束函數創建為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函數求解，對應的程序如下現代優化方法Matlab的GA工具箱使用簡介

ObjectiveFunction=@simple_objective;

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

ConstraintFunction=@simple_