1、matlab 實用教程 實驗十 遺傳算法與優化問題matlab實用教程實驗十遺傳算法與優化問題一、問題背景與實驗目的二、相關函數 命令）及簡介三、實驗內容四、自己動手 一、問題背景與實驗目的遺傳算法 GeneticAlgorithm GA ），是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，它是由美國Michigan大學的J.Holland教授于1975年首先提出的.遺傳算法作為一種新的全局優化搜索算法 ，以其簡單通用、魯棒性強、適于并行處理及應用范圍廣等顯著特點，奠定了它作為21世紀關鍵智能計算之一的地位.本實驗將首先介紹一下遺傳算法的基本理論，然后用其解決幾個簡單的函數最值問題，

2、使 讀者能夠學會利用遺傳算法進行初步的優化計算.1 .遺傳算法的基本原理 遺傳算法的基本思想正是基于模仿生物界遺傳學的遺傳過程.它把問題的參數用基因代表 ，把問題的解用染色體代表在計算機里用二進制碼表示），從而得到一個由具有不同染色體的個體組成的群體.這個群體在問題特定的環境里生存競爭，適者有最好的機會生存 和產生后代.后代隨機化地繼承了父代的最好特征，并也在生存環境的控制支配下繼續這 一過程.群體的染色體都將逐漸適應環境，不斷進化，最后收斂到一族最適應環境的類似 個體，即得到問題最優的解.值得注意的一點是，現在的遺傳算法是受生物進化論學說的 啟發提出的，這種學說對我們用計算機解決復雜問題很有

3、用，而它本身是否完全正確并不 重要 目前生物界對此學說尚有爭議）.1）遺傳算法中的生物遺傳學概念 因為遺傳算法是由進化論和遺傳學機理而產生的直接搜索優化方法；故而在這個算法中要 用到各種進化和遺傳學的概念.首先給出遺傳學概念、遺傳算法概念和相應的數學概念三者之間的對應關系.這些概念如 下：序號遺傳學概念遺傳算法概念數學概念1 個體要處理的基本對象、結構也就是可行解 2群體個體的集合被選定的一組可行解 3染色體個體的表現形式可行解的編碼 4基因染色體中的元素編碼中的元素 5基因位某一基因在染色體中的位置元素在編碼中的位置 6適應值個體對于環境的適應程度，或在環境壓力下的生存能力可行解所對應的適應

4、函數值 7種群被選定的一組染色體或個體根據入選概率定出的一組可行解 8選擇從群體中選擇優勝的個體，淘汰劣質個體的操作保留或復制適應值大的可行解，去掉 小的可行解9交叉一組染色體上對應基因段的交換根據交叉原則產生的一組新解 10交叉概率染色體對應基因段交換的概率可能性大小）閉區間 0,1上的一個值，一般為 0.650.9011變異染色體水平上基因變化編碼的某些元素被改變 12變異概率染色體上基因變化的概率可能性大小）開區間 （0,1 內的一個值 , 一般為 0.0010.01 13進化、 適者生存個體進行優勝劣汰的進化，一代又一代地優化目標函數取到最大值，最優的可行 解<2）遺傳算法的步驟

5、 遺傳算法計算優化的操作過程就如同生物學上生物遺傳進化的過程，主要有三個基本操作<或稱為算子）：選擇（Selection）、交叉 <Crossover）、變異 <Mutation ）. 遺傳算法基本步驟主要是：先把問題的解表示成 “染色體 ”，在算法中也就是以二進制編碼 的串，在執行遺傳算法之前，給出一群 “染色體 ”，也就是假設的可行解.然后，把這些假 設的可行解置于問題的 “環境 ”中，并按適者生存的原則，從中選擇出較適應環境的 “染色體 ”進行復制，再通過交叉、變異過程產生更適應環境的新一代 “染色體 ”群.經過這樣的一代 一代地進化，最后就會收斂到最適應環境的一個 “

6、染色體 ”上，它就是問題的最優解. 下面給出遺傳算法的具體步驟，流程圖參見圖 1：第一步：選擇編碼策略，把參數集合<可行解集合）轉換染色體結構空間；第二步：定義適應函數，便于計算適應值； 第三步：確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法以及確定交叉概率、 變異概率等遺傳參數；第四步：隨機產生初始化群體； 第五步：計算群體中的個體或染色體解碼后的適應值； 第六步：按照遺傳策略，運用選擇、交叉和變異算子作用于群體，形成下一代群體； 第七步：判斷群體性能是否滿足某一指標、或者是否已完成預定的迭代次數，不滿足則返 回第五步、或者修改遺傳策略再返回第六步.圖1 一個遺傳算法的具體步驟

7、遺傳算法有很多種具體的不同實現過程，以上介紹的是標準遺傳算法的主要步驟，此算法 會一直運行直到找到滿足條件的最優解為止.2.遺傳算法的實際應用 例1：設，求 注：這是一個非常簡單的二次函數求極值的問題，相信大家都會做.在此我們要研究的不 是問題本身，而是借此來說明如何通過遺傳算法分析和解決問題. 在此將細化地給出遺傳算法的整個過程.<1）編碼和產生初始群體 首先第一步要確定編碼的策略，也就是說如何把 到2這個區間內的數用計算機語言表示出來. 編碼就是表現型到基因型的映射，編碼時要注意以下三個原則： 完備性：問題空間中所有點 < 潛在解）都能成為GA編碼空間中的點 < 染色體位

8、串）的表現 型；健全性：GA編碼空間中的染色體位串必須對應問題空間中的某一潛在解； 非冗余性：染色體和潛在解必須一一對應. 這里我們通過采用二進制的形式來解決編碼問題，將某個變量值代表的個體表示為一個0，1 二進制串.當然，串長取決于求解的精度.如果要設定求解精度到六位小數，因為區 間長度為，則必須將閉區間分為等分因為所以編碼的二進制串至少需要22位將一個二進制串 <b21b20b19b1b0 ）轉化為區間內對應的實數值很簡單，只需采取以下兩步 <Matlab 程序參見附錄 4）：1） 將一個二進制串<b21b20b19b1b0代表的二進制數化為 10進制數：2）對應的區間內

9、的實數：例如，一個二進制串 表示實數0.637197.二進制串 <>， ，> 則分別表示區間的兩個端點值-1 和2.利用這種方法我們就完成了遺傳算法的第一步 編碼，這種二進制編碼的方法完全符合上述的編碼的三個原則. 首先我們來隨機的產生一個個體數為 4個的初始群體如下： pop（1>=， % a1， % a2， % a3<> % a4<Matlab 程序參見附錄 2）化成十進制的數分別為：pop（1>= 1.523032 ， 0.574022 ， -0.697235 ， 0.247238 接下來我們就要解決每個染色體個體的適應值問題了.<2

10、）定義適應函數和適應值 因為給定的目標函數 在內的值有正有負，所以必須通過建立適應函數與目標函數的映射關系，保證映射后的適應 值非負，而且目標函數的優化方向應對應于適應值增大的方向，也為以后計算各個體的入 選概率打下基礎.對于本題中的最大化問題，定義適應函數，采用下述方法：式中既可以是特定的輸入值，也可以是當前所有代或最近K代中的最小值，這里為了便于計算，將采用了一個特定的輸入值.若取，則當時適應函數；當時適應函數由上述所隨機產生的初始群體，我們可以先計算出目標函數值分別如下<Matlab 程序參見附錄 3 ）：f pop（1>= 1.226437 , 1.318543 , -1.

11、380607 , 0.933350 然后通過適應函數計算出適應值分別如下 <Matlab 程序參見附錄 5、附錄 6）： gpop(1>= 2.226437 , 2.318543 , 0 , 1.933350 <3)確定選擇標準 這里我們用到了適應值的比例來作為選擇的標準，得到的每個個體的適應值比例叫作入選 概率其計算公式如下：對于給定的規模為n的群體pop= ，個體 的適應值為，則其入選概率為 由上述給出的群體，我們可以計算出各個個體的入選概率首先可得然后分別用四個個體的適應值去除以，得：P(a1>=2.226437 / 6.478330 = 0.343675 % a

12、1P(a2>=2.318543 / 6.478330 = 0.357892 % a2P(a3>= 0 / 6.478330 = 0 % a3P(a4>=1.933350 / 6.478330 = 0.298433 % a4<Matlab 程序參見附錄 7) <4)產生種群 計算完了入選概率后，就將入選概率大的個體選入種群，淘汰概率小的個體，并用入選概率最大的個體補入種群，得到與原群體大小同樣的種群<Matlab程序參見附錄8、附錄11)要說明的是：附錄 11的算法與這里不完全相同為保證收斂性，附錄11的算法作了修正，采用了最佳個體保存方法 <eliti

13、st model )，具體內容將在后面給出介紹由初始群體的入選概率我們淘汰掉a3，再加入a2補足成與群體同樣大小的種群得到newpop(1> 如下：newpop(1>=， % a1， % a2， % a2 <> % a4<5)交叉 交叉也就是將一組染色體上對應基因段的交換得到新的染色體，然后得到新的染色體組， 組成新的群體 <Matlab 程序參見附錄 9)我們把之前得到的newpop(1>的四個個體兩兩組成一對，重復的不配對，進行交叉.<可以在任一位進行交叉)<110101110 10>， 交叉得：<100001100 10&

14、gt;， <100 01000010>， 交叉得：<>， <> 通過交叉得到了四個新個體，得到新的群體 jchpop (1> 如下：jchpop（1>= ， ， ， <> 這里采用的是單點交叉的方法，當然還有多點交叉的方法，不過有些煩瑣，這里就不著重 介紹了<6）變異 變異也就是通過一個小概率改變染色體位串上的某個基因 <Matlab 程序參見附錄 10） 現把剛得到的 jchpop（1> 中第 3個個體中的第 9位改變，就產生了變異，得到了新的群體 pop（2 >如下：pop（2>= ， ， ， <

15、;> 然后重復上述的選擇、交叉、變異直到滿足終止條件為止<7）終止條件 遺傳算法的終止條件有兩類常見條件： <1）采用設定最大 <遺傳）代數的方法，一般可設 定為50代，此時就可能得出最優解此種方法簡單易行，但可能不是很精確<Matlab程序參見附錄 1）； <2）根據個體的差異來判斷，通過計算種群中基因多樣性測度，即所有基因 位相似程度來進行控制.3 遺傳算法的收斂性 前面我們已經就遺傳算法中的編碼、適應度函數、選擇、交叉和變異等主要操作的基本內 容及設計進行了詳細的介紹作為一種搜索算法，遺傳算法通過對這些操作的適當設計和 運行，可以實現兼顧全局搜索和局部

16、搜索的所謂均衡搜索，具體實現見下圖2所示.圖2 均衡搜索的具體實現圖示 應該指出的是，遺傳算法雖然可以實現均衡的搜索，并且在許多復雜問題的求解中往往能 得到滿意的結果，但是該算法的全局優化收斂性的理論分析尚待解決目前普遍認為，標 準遺傳算法并不保證全局最優收斂但是，在一定的約束條件下，遺傳算法可以實現這一 占八、下面我們不加證明地羅列幾個定理或定義，供讀者參考<在這些定理的證明中，要用到許多概率論知識，特別是有關馬爾可夫鏈的理論，讀者可參閱有關文獻）定理 1 如果變異概率為 ，交叉概率為，同時采用比例選擇法 <按個體適應度占群體適應度的比例進行復制），則標準遺傳算法 的變換矩陣P是

17、基本的.定理 2 標準遺傳算法 <參數如定理 1）不能收斂至全局最優解 由定理 2可以知道，具有變異概率，交叉概率為 以及按比例選擇的標準遺傳算法是不能收斂至全局最最優解我們在前面求解例1時所用的<稱作方法就是滿足定理 1的條件的方法這無疑是一個令人沮喪的結論 然而，慶幸的是，只要對標準遺傳算法作一些改進，就能夠保證其收斂性具體如下：我 們對標準遺傳算法作一定改進，即不按比例進行選擇，而是保留當前所得的最優解超個體）該超個體不參與遺傳 最佳個體保存方法 elitistmodel）的思想是把群體中適應度最高的個體不進行配對交叉而直接復制到下一代中.此種 選擇操作又稱復制copy）.

18、De Jong對此方法作了如下定義： 定義設到時刻t第t代）時，群體中a*t）為最佳個體又設 At + 1）為新一代群體，若 At + 1 ）中不存在a*t），則把a*（t作為At + 1）中的第n+1個個體 其中，n為群體大小）Matla b程序參見附錄11）.采用此選擇方法的優點是，進化過程中某一代的最優解可不被交叉和變異操作所破壞.但 是，這也隱含了一種危機，即局部最優個體的遺傳基因會急速增加而使進化有可能限于局 部解.也就是說，該方法的全局搜索能力差，它更適合單峰性質的搜索空間搜索，而不是 多峰性質的空間搜索.所以此方法一般都與其他選擇方法結合使用.定理3具有定理 1所示參數，且在選擇

19、后保留當前最優值的遺傳算法最終能收斂到全局最優解. 當然，在選擇算子作用后保留當前最優解是一項比較復雜的工作，因為該解在選擇算子作 用后可能丟失.但是定理 3至少表明了這種改進的遺傳算法能夠收斂至全局最優解.有意思 的是，實際上只要在選擇前保留當前最優解，就可以保證收斂，定理4描述了這種情況.定理4 具有定理 1參數的，且在選擇前保留當前最優解的遺傳算法可收斂于全局最優解. 例2：設，求，編碼長度為 5，采用上述定理 4所述的 “在選擇前保留當前最優解的遺傳算法 ”進行二、相關函數 命令）及簡介本實驗的程序中用到如下一些基本的Matlab函數：on es, zeros, sum, size,

20、le ngth, subs, double等，以及for,while等基本程序結構語句，讀者可參考前面專門關于Matlab的介紹，也可參考其他數學實驗章節中的 “相關函數 命令）及簡介 ”內容，此略.三、實驗內容上述例 1 的求解過程為： 群體中包含六個染色體，每個染色體用22位01碼，變異概率為 0.01 ，變量區間為，取 Fmin=，遺傳代數為50代，則運用第一種終止條件指定遺傳代數）的Matlab程序為：Count,Result,BestMember=Genetic1（22,6,'-x*x+2*x+0.5',-1,2,-2,0.01,50執行結果為：Count =50Re

21、sult =1.0316 1.0316 1.0316 1.0316 1.0316 1.03161.4990 1.4990 1.4990 1.4990 1.4990 1.4990BestMember =1.03161.4990圖2 例1的計算結果 注：上圖為遺傳進化過程中每一代的個體最大適應度； 而下圖為目前為止的個體最大適應度 單調遞增）我們通過 Matlab 軟件實現了遺傳算法，得到了這題在第一種終止條件下的最優解：當 取1.0316時，當然這個解和實際情況還有一點出入 <應該是取1時， ），但對于一個計算機算法來說已經很不錯了我們也可以編制 Matlab 程序求在第二種終止條件下的最優解此略，留作練習實踐表明 ，此時的遺傳算法只要經過 10代左右就可完成收斂，得到另一個“最優解 ”，與前面的最優解相差無幾四、自己動