數(shù)學(xué)建模遺傳算法與優(yōu)化問(wèn)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)十 遺傳算法與優(yōu)化問(wèn)題一、問(wèn)題背景與實(shí)驗(yàn)?zāi)康倪z傳算法（Genetic AlgorithmGA），是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型，它是由美國(guó)Michigan大學(xué)的J.Holland教授于1975年首先提出的遺傳算法作為一種新的全局優(yōu)化搜索算法，以其簡(jiǎn)單通用、魯棒性強(qiáng)、適于并行處理及應(yīng)用范圍廣等顯著特點(diǎn)，奠定了它作為21世紀(jì)關(guān)鍵智能計(jì)算之一的地位本實(shí)驗(yàn)將首先介紹一下遺傳算法的基本理論，然后用其解決幾個(gè)簡(jiǎn)單的函數(shù)最值問(wèn)題，使讀者能夠?qū)W會(huì)利用遺傳算法進(jìn)行初步的優(yōu)化計(jì)算1遺傳算法的基本原理遺傳算法的基本思想正是基于模仿生物界遺傳學(xué)的遺傳過(guò)程它把問(wèn)題

2、的參數(shù)用基因代表，把問(wèn)題的解用染色體代表（在計(jì)算機(jī)里用二進(jìn)制碼表示），從而得到一個(gè)由具有不同染色體的個(gè)體組成的群體這個(gè)群體在問(wèn)題特定的環(huán)境里生存競(jìng)爭(zhēng)，適者有最好的機(jī)會(huì)生存和產(chǎn)生后代后代隨機(jī)化地繼承了父代的最好特征，并也在生存環(huán)境的控制支配下繼續(xù)這一過(guò)程群體的染色體都將逐漸適應(yīng)環(huán)境，不斷進(jìn)化，最后收斂到一族最適應(yīng)環(huán)境的類似個(gè)體，即得到問(wèn)題最優(yōu)的解值得注意的一點(diǎn)是，現(xiàn)在的遺傳算法是受生物進(jìn)化論學(xué)說(shuō)的啟發(fā)提出的，這種學(xué)說(shuō)對(duì)我們用計(jì)算機(jī)解決復(fù)雜問(wèn)題很有用，而它本身是否完全正確并不重要（目前生物界對(duì)此學(xué)說(shuō)尚有爭(zhēng)議）（1）遺傳算法中的生物遺傳學(xué)概念由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法

3、；故而在這個(gè)算法中要用到各種進(jìn)化和遺傳學(xué)的概念首先給出遺傳學(xué)概念、遺傳算法概念和相應(yīng)的數(shù)學(xué)概念三者之間的對(duì)應(yīng)關(guān)系這些概念如下：序號(hào)遺傳學(xué)概念遺傳算法概念數(shù)學(xué)概念1個(gè)體要處理的基本對(duì)象、結(jié)構(gòu)也就是可行解2群體個(gè)體的集合被選定的一組可行解3染色體個(gè)體的表現(xiàn)形式可行解的編碼4基因染色體中的元素編碼中的元素5基因位某一基因在染色體中的位置元素在編碼中的位置6適應(yīng)值個(gè)體對(duì)于環(huán)境的適應(yīng)程度，或在環(huán)境壓力下的生存能力可行解所對(duì)應(yīng)的適應(yīng)函數(shù)值7種群被選定的一組染色體或個(gè)體根據(jù)入選概率定出的一組可行解8選擇從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作保留或復(fù)制適應(yīng)值大的可行解，去掉小的可行解9交叉一組染色體上對(duì)應(yīng)

4、基因段的交換根據(jù)交叉原則產(chǎn)生的一組新解10交叉概率染色體對(duì)應(yīng)基因段交換的概率（可能性大?。╅]區(qū)間0,1上的一個(gè)值，一般為0.650.9011變異染色體水平上基因變化編碼的某些元素被改變12變異概率染色體上基因變化的概率（可能性大?。╅_區(qū)間(0,1)內(nèi)的一個(gè)值, 一般為0.0010.0113進(jìn)化、適者生存?zhèn)€體進(jìn)行優(yōu)勝劣汰的進(jìn)化，一代又一代地優(yōu)化目標(biāo)函數(shù)取到最大值，最優(yōu)的可行解（2）遺傳算法的步驟遺傳算法計(jì)算優(yōu)化的操作過(guò)程就如同生物學(xué)上生物遺傳進(jìn)化的過(guò)程，主要有三個(gè)基本操作（或稱為算子）：選擇（Selection）、交叉（Crossover）、變異（Mutation）遺傳算法基本步驟主要是：先把問(wèn)

5、題的解表示成“染色體”，在算法中也就是以二進(jìn)制編碼的串，在執(zhí)行遺傳算法之前，給出一群“染色體”，也就是假設(shè)的可行解然后，把這些假設(shè)的可行解置于問(wèn)題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過(guò)交叉、變異過(guò)程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群經(jīng)過(guò)這樣的一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，它就是問(wèn)題的最優(yōu)解下面給出遺傳算法的具體步驟，流程圖參見(jiàn)圖1：第一步：選擇編碼策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換染色體結(jié)構(gòu)空間；第二步：定義適應(yīng)函數(shù)，便于計(jì)算適應(yīng)值；第三步：確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法以及確定交叉概率、變異概率等

6、遺傳參數(shù)；第四步：隨機(jī)產(chǎn)生初始化群體；第五步：計(jì)算群體中的個(gè)體或染色體解碼后的適應(yīng)值；第六步：按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，形成下一代群體；第七步：判斷群體性能是否滿足某一指標(biāo)、或者是否已完成預(yù)定的迭代次數(shù)，不滿足則返回第五步、或者修改遺傳策略再返回第六步產(chǎn)生初始群體是否滿足終止條件得到結(jié)果結(jié)束程序是否計(jì)算每個(gè)個(gè)體的適應(yīng)值以概率選擇遺傳算子選擇一個(gè)個(gè)體復(fù)制到新群體選擇兩個(gè)個(gè)體進(jìn)行交叉插入到新群體選擇一個(gè)個(gè)體進(jìn)行變異插入到新群體得到新群體圖1 一個(gè)遺傳算法的具體步驟遺傳算法有很多種具體的不同實(shí)現(xiàn)過(guò)程，以上介紹的是標(biāo)準(zhǔn)遺傳算法的主要步驟，此算法會(huì)一直運(yùn)行直到找到滿足條件的最優(yōu)解

7、為止2遺傳算法的實(shí)際應(yīng)用例1：設(shè)，求 注：這是一個(gè)非常簡(jiǎn)單的二次函數(shù)求極值的問(wèn)題，相信大家都會(huì)做在此我們要研究的不是問(wèn)題本身，而是借此來(lái)說(shuō)明如何通過(guò)遺傳算法分析和解決問(wèn)題在此將細(xì)化地給出遺傳算法的整個(gè)過(guò)程（1）編碼和產(chǎn)生初始群體首先第一步要確定編碼的策略，也就是說(shuō)如何把到2這個(gè)區(qū)間內(nèi)的數(shù)用計(jì)算機(jī)語(yǔ)言表示出來(lái)編碼就是表現(xiàn)型到基因型的映射，編碼時(shí)要注意以下三個(gè)原則：完備性：?jiǎn)栴}空間中所有點(diǎn)（潛在解）都能成為GA編碼空間中的點(diǎn)（染色體位串）的表現(xiàn)型；健全性：GA編碼空間中的染色體位串必須對(duì)應(yīng)問(wèn)題空間中的某一潛在解；非冗余性：染色體和潛在解必須一一對(duì)應(yīng)這里我們通過(guò)采用二進(jìn)制的形式來(lái)解決編碼問(wèn)題，將某個(gè)

8、變量值代表的個(gè)體表示為一個(gè)0，1二進(jìn)制串當(dāng)然，串長(zhǎng)取決于求解的精度如果要設(shè)定求解精度到六位小數(shù)，由于區(qū)間長(zhǎng)度為，則必須將閉區(qū)間 分為等分因?yàn)?所以編碼的二進(jìn)制串至少需要22位將一個(gè)二進(jìn)制串（b21b20b19b1b0）轉(zhuǎn)化為區(qū)間內(nèi)對(duì)應(yīng)的實(shí)數(shù)值很簡(jiǎn)單，只需采取以下兩步（Matlab程序參見(jiàn)附錄4）：1）將一個(gè)二進(jìn)制串（b21b20b19b1b0）代表的二進(jìn)制數(shù)化為10進(jìn)制數(shù)：2） 對(duì)應(yīng)的區(qū)間內(nèi)的實(shí)數(shù)：例如，一個(gè)二進(jìn)制串a(chǎn)=表示實(shí)數(shù)0.=()2=二進(jìn)制串，則分別表示區(qū)間的兩個(gè)端點(diǎn)值-1和2利用這種方法我們就完成了遺傳算法的第一步編碼，這種二進(jìn)制編碼的方法完全符合上述的編碼的三個(gè)原則首先我們來(lái)隨機(jī)的

9、產(chǎn)生一個(gè)個(gè)體數(shù)為4個(gè)的初始群體如下：pop(1)=， % a1， % a2， % a3 % a4（Matlab程序參見(jiàn)附錄2）化成十進(jìn)制的數(shù)分別為：pop(1)= 1.，0. ，-0. ，0. 接下來(lái)我們就要解決每個(gè)染色體個(gè)體的適應(yīng)值問(wèn)題了（2）定義適應(yīng)函數(shù)和適應(yīng)值由于給定的目標(biāo)函數(shù)在內(nèi)的值有正有負(fù)，所以必須通過(guò)建立適應(yīng)函數(shù)與目標(biāo)函數(shù)的映射關(guān)系，保證映射后的適應(yīng)值非負(fù)，而且目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對(duì)應(yīng)于適應(yīng)值增大的方向，也為以后計(jì)算各個(gè)體的入選概率打下基礎(chǔ)對(duì)于本題中的最大化問(wèn)題，定義適應(yīng)函數(shù)，采用下述方法：式中既可以是特定的輸入值，也可以是當(dāng)前所有代或最近K代中的最小值，這里為了便于計(jì)算，將采用了

10、一個(gè)特定的輸入值若取，則當(dāng)時(shí)適應(yīng)函數(shù)；當(dāng)時(shí)適應(yīng)函數(shù)由上述所隨機(jī)產(chǎn)生的初始群體，我們可以先計(jì)算出目標(biāo)函數(shù)值分別如下（Matlab程序參見(jiàn)附錄3）：f pop(1)= 1. , 1. , -1. , 0. 然后通過(guò)適應(yīng)函數(shù)計(jì)算出適應(yīng)值分別如下（Matlab程序參見(jiàn)附錄5、附錄6）：取，gpop(1)= 2. , 2. , 0 , 1. （3）確定選擇標(biāo)準(zhǔn)這里我們用到了適應(yīng)值的比例來(lái)作為選擇的標(biāo)準(zhǔn)，得到的每個(gè)個(gè)體的適應(yīng)值比例叫作入選概率其計(jì)算公式如下：對(duì)于給定的規(guī)模為n的群體pop=，個(gè)體的適應(yīng)值為，則其入選概率為由上述給出的群體，我們可以計(jì)算出各個(gè)個(gè)體的入選概率首先可得 ，然后分別用四個(gè)個(gè)體的適應(yīng)

11、值去除以，得：P(a1)=2. / 6. = 0. % a1P(a2)=2. / 6. = 0. % a2P(a3)= 0 / 6. = 0 % a3P(a4)=1. / 6. = 0. % a4（Matlab程序參見(jiàn)附錄7）（4）產(chǎn)生種群計(jì)算完了入選概率后，就將入選概率大的個(gè)體選入種群，淘汰概率小的個(gè)體，并用入選概率最大的個(gè)體補(bǔ)入種群，得到與原群體大小同樣的種群（Matlab程序參見(jiàn)附錄8、附錄11）要說(shuō)明的是：附錄11的算法與這里不完全相同為保證收斂性，附錄11的算法作了修正，采用了最佳個(gè)體保存方法（elitist model），具體內(nèi)容將在后面給出介紹由初始群體的入選概率我們淘汰掉a3，

12、再加入a2補(bǔ)足成與群體同樣大小的種群得到newpop(1)如下：newpop(1)=， % a1， % a2， % a2 % a4（5）交叉交叉也就是將一組染色體上對(duì)應(yīng)基因段的交換得到新的染色體，然后得到新的染色體組，組成新的群體（Matlab程序參見(jiàn)附錄9）我們把之前得到的newpop(1)的四個(gè)個(gè)體兩兩組成一對(duì)，重復(fù)的不配對(duì)，進(jìn)行交叉（可以在任一位進(jìn)行交叉）， 交叉得：， ， 交叉得：， 通過(guò)交叉得到了四個(gè)新個(gè)體，得到新的群體jchpop (1)如下：jchpop(1)=，這里采用的是單點(diǎn)交叉的方法，當(dāng)然還有多點(diǎn)交叉的方法，不過(guò)有些煩瑣，這里就不著重介紹了（6）變異變異也就是通過(guò)一個(gè)小概率

13、改變?nèi)旧w位串上的某個(gè)基因（Matlab程序參見(jiàn)附錄10）現(xiàn)把剛得到的jchpop(1)中第3個(gè)個(gè)體中的第9位改變，就產(chǎn)生了變異，得到了新的群體pop(2)如下：pop(2)= ， 然后重復(fù)上述的選擇、交叉、變異直到滿足終止條件為止（7）終止條件遺傳算法的終止條件有兩類常見(jiàn)條件：（1）采用設(shè)定最大（遺傳）代數(shù)的方法，一般可設(shè)定為50代，此時(shí)就可能得出最優(yōu)解此種方法簡(jiǎn)單易行，但可能不是很精確（Matlab程序參見(jiàn)附錄1）；（2）根據(jù)個(gè)體的差異來(lái)判斷，通過(guò)計(jì)算種群中基因多樣性測(cè)度，即所有基因位相似程度來(lái)進(jìn)行控制3遺傳算法的收斂性前面我們已經(jīng)就遺傳算法中的編碼、適應(yīng)度函數(shù)、選擇、交叉和變異等主要操作

14、的基本內(nèi)容及設(shè)計(jì)進(jìn)行了詳細(xì)的介紹作為一種搜索算法，遺傳算法通過(guò)對(duì)這些操作的適當(dāng)設(shè)計(jì)和運(yùn)行，可以實(shí)現(xiàn)兼顧全局搜索和局部搜索的所謂均衡搜索，具體實(shí)現(xiàn)見(jiàn)下圖2所示圖2 均衡搜索的具體實(shí)現(xiàn)圖示應(yīng)該指出的是，遺傳算法雖然可以實(shí)現(xiàn)均衡的搜索，并且在許多復(fù)雜問(wèn)題的求解中往往能得到滿意的結(jié)果，但是該算法的全局優(yōu)化收斂性的理論分析尚待解決目前普遍認(rèn)為，標(biāo)準(zhǔn)遺傳算法并不保證全局最優(yōu)收斂但是，在一定的約束條件下，遺傳算法可以實(shí)現(xiàn)這一點(diǎn)下面我們不加證明地羅列幾個(gè)定理或定義，供讀者參考（在這些定理的證明中，要用到許多概率論知識(shí)，特別是有關(guān)馬爾可夫鏈的理論，讀者可參閱有關(guān)文獻(xiàn)）定理1 如果變異概率為，交叉概率為，同時(shí)采用

15、比例選擇法（按個(gè)體適應(yīng)度占群體適應(yīng)度的比例進(jìn)行復(fù)制），則標(biāo)準(zhǔn)遺傳算法的變換矩陣P是基本的定理2 標(biāo)準(zhǔn)遺傳算法（參數(shù)如定理1）不能收斂至全局最優(yōu)解由定理2可以知道，具有變異概率，交叉概率為以及按比例選擇的標(biāo)準(zhǔn)遺傳算法是不能收斂至全局最最優(yōu)解我們?cè)谇懊媲蠼饫?時(shí)所用的方法就是滿足定理1的條件的方法這無(wú)疑是一個(gè)令人沮喪的結(jié)論然而，慶幸的是，只要對(duì)標(biāo)準(zhǔn)遺傳算法作一些改進(jìn)，就能夠保證其收斂性具體如下：我們對(duì)標(biāo)準(zhǔn)遺傳算法作一定改進(jìn)，即不按比例進(jìn)行選擇，而是保留當(dāng)前所得的最優(yōu)解（稱作超個(gè)體）該超個(gè)體不參與遺傳最佳個(gè)體保存方法（elitist model）的思想是把群體中適應(yīng)度最高的個(gè)體不進(jìn)行配對(duì)交叉而直接復(fù)

16、制到下一代中此種選擇操作又稱復(fù)制（copy）De Jong對(duì)此方法作了如下定義：定義 設(shè)到時(shí)刻t（第t代）時(shí)，群體中a*（t）為最佳個(gè)體又設(shè)A（t1）為新一代群體，若A（t1）中不存在a*（t），則把a(bǔ)*(t)作為A（t1）中的第n+1個(gè)個(gè)體（其中，n為群體大?。∕atlab程序參見(jiàn)附錄11）采用此選擇方法的優(yōu)點(diǎn)是，進(jìn)化過(guò)程中某一代的最優(yōu)解可不被交叉和變異操作所破壞但是，這也隱含了一種危機(jī)，即局部最優(yōu)個(gè)體的遺傳基因會(huì)急速增加而使進(jìn)化有可能限于局部解也就是說(shuō)，該方法的全局搜索能力差，它更適合單峰性質(zhì)的搜索空間搜索，而不是多峰性質(zhì)的空間搜索所以此方法一般都與其他選擇方法結(jié)合使用定理3 具有定理1

17、所示參數(shù)，且在選擇后保留當(dāng)前最優(yōu)值的遺傳算法最終能收斂到全局最優(yōu)解當(dāng)然，在選擇算子作用后保留當(dāng)前最優(yōu)解是一項(xiàng)比較復(fù)雜的工作，因?yàn)樵摻庠谶x擇算子作用后可能丟失但是定理3至少表明了這種改進(jìn)的遺傳算法能夠收斂至全局最優(yōu)解有意思的是，實(shí)際上只要在選擇前保留當(dāng)前最優(yōu)解，就可以保證收斂，定理4描述了這種情況定理4 具有定理1參數(shù)的，且在選擇前保留當(dāng)前最優(yōu)解的遺傳算法可收斂于全局最優(yōu)解例2：設(shè)，求 ，編碼長(zhǎng)度為5，采用上述定理4所述的“在選擇前保留當(dāng)前最優(yōu)解的遺傳算法”進(jìn)行此略，留作練習(xí)二、相關(guān)函數(shù)（命令）及簡(jiǎn)介本實(shí)驗(yàn)的程序中用到如下一些基本的Matlab函數(shù)：ones, zeros, sum, size,

18、 length, subs, double 等，以及 for, while 等基本程序結(jié)構(gòu)語(yǔ)句，讀者可參考前面專門關(guān)于Matlab的介紹，也可參考其他數(shù)學(xué)實(shí)驗(yàn)章節(jié)中的“相關(guān)函數(shù)（命令）及簡(jiǎn)介”內(nèi)容，此略三、實(shí)驗(yàn)內(nèi)容上述例1的求解過(guò)程為：群體中包含六個(gè)染色體，每個(gè)染色體用22位01碼，變異概率為0.01，變量區(qū)間為 ，取Fmin=，遺傳代數(shù)為50代，則運(yùn)用第一種終止條件（指定遺傳代數(shù)）的Matlab程序?yàn)椋篊ount,Result,BestMember=Genetic1(22,6,-x*x+2*x+0.5,-1,2,-2,0.01,50)執(zhí)行結(jié)果為：Count = 50Result = 1.03

19、16 1.0316 1.0316 1.0316 1.0316 1.0316 1.4990 1.4990 1.4990 1.4990 1.4990 1.4990BestMember = 1.0316 1.4990圖2 例1的計(jì)算結(jié)果（注：上圖為遺傳進(jìn)化過(guò)程中每一代的個(gè)體最大適應(yīng)度；而下圖為目前為止的個(gè)體最大適應(yīng)度單調(diào)遞增）我們通過(guò)Matlab軟件實(shí)現(xiàn)了遺傳算法，得到了這題在第一種終止條件下的最優(yōu)解：當(dāng)取1.0316時(shí)，當(dāng)然這個(gè)解和實(shí)際情況還有一點(diǎn)出入（應(yīng)該是取1時(shí)，），但對(duì)于一個(gè)計(jì)算機(jī)算法來(lái)說(shuō)已經(jīng)很不錯(cuò)了我們也可以編制Matlab程序求在第二種終止條件下的最優(yōu)解此略，留作練習(xí)實(shí)踐表明，此時(shí)的遺傳

20、算法只要經(jīng)過(guò)10代左右就可完成收斂，得到另一個(gè)“最優(yōu)解”，與前面的最優(yōu)解相差無(wú)幾四、自己動(dòng)手1 用Matlab編制另一個(gè)主程序Genetic2.m，求例1的在第二種終止條件下的最優(yōu)解提示：一個(gè)可能的函數(shù)調(diào)用形式以及相應(yīng)的結(jié)果為：Count,Result,BestMember=Genetic2(22,6,-x*x+2*x+0.5,-1,2,-2,0.01,0.00001)Count = 13Result = 1.0392 1.0392 1.0392 1.0392 1.0392 1.0392 1.4985 1.4985 1.4985 1.4985 1.4985 1.4985BestMember =

21、 1.0392 1.4985可以看到：兩組解都已經(jīng)很接近實(shí)際結(jié)果，對(duì)于兩種方法所產(chǎn)生的最優(yōu)解差異很小可見(jiàn)這兩種終止算法都是可行的，而且可以知道對(duì)于例1的問(wèn)題，遺傳算法只要經(jīng)過(guò)10代左右就可以完成收斂，達(dá)到一個(gè)最優(yōu)解2 按照例2的具體要求，用遺傳算法求上述例2的最優(yōu)解3 附錄9子程序 Crossing.m中的第3行到第7行為注解語(yǔ)句若去掉前面的%號(hào)，則程序的算法思想有什么變化？4 附錄9子程序 Crossing.m中的第8行至第13行的程序表明，當(dāng)Dim(1)=3時(shí)，將交換數(shù)組Population的最后兩行，即交換最后面的兩個(gè)個(gè)體其目的是什么？5 仿照附錄10子程序Mutation.m，修改附錄

22、9子程序 Crossing.m，使得交叉過(guò)程也有一個(gè)概率值（一般取0.650.90）；同時(shí)適當(dāng)修改主程序Genetic1.m或主程序Genetic2.m，以便代入交叉概率6 設(shè)，求 ，要設(shè)定求解精度到15位小數(shù)五、附錄附錄1：主程序Genetic1.mfunction Count,Result,BestMember=Genetic1(MumberLength,MemberNumber,FunctionFitness,MinX,MaxX,Fmin,MutationProbability,Gen)Population=PopulationInitialize(MumberLength,Member

23、Number);global Count;global CurrentBest;Count=1;PopulationCode=Population;PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength);PopulationFitnessF=FitnessF(PopulationFitness,Fmin);PopulationProbability=Probability(PopulationFitnessF);Population,CurrentBest,EachGenMaxFitnes

24、s=Elitist(PopulationCode,PopulationFitness,MumberLength);EachMaxFitness(Count)=EachGenMaxFitness;MaxFitness(Count)=CurrentBest(length(CurrentBest);while Count=0.5*ones(size(Temporary);【程序說(shuō)明】子程序 PopulationInitialize.m用于產(chǎn)生一個(gè)初始群體這個(gè)初始群體含有MemberNumber個(gè)染色體，每個(gè)染色體有MumberLength個(gè)基因（二進(jìn)制碼）附錄3：子程序Fitness.mfuncti

25、on PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)Dim=size(PopulationCode);PopulationFitness=zeros(1,Dim(1);for i=1:Dim(1)PopulationFitness(i)=Transfer(PopulationCode(i,:),FunctionFitness,MinX,MaxX,MumberLength);end【程序說(shuō)明】子程序Fitness.m用于計(jì)算群體中每一個(gè)染色體的目標(biāo)函數(shù)值子程序中含有5個(gè)輸入?yún)?shù)：Po

26、pulationCode表示用01代碼表示的群體，F(xiàn)unctionFitness 表示目標(biāo)函數(shù)，它是一個(gè)字符串，因此寫入調(diào)用程序時(shí)，應(yīng)該用單引號(hào)括出，MumberLength表示染色體位串的二進(jìn)制長(zhǎng)度MinX和MaxX 分別指變量區(qū)間的上下限附錄4：子程序 Translate.mfunction PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength)PopulationData=0;Dim=size(PopulationCode);for i=1:Dim(2) PopulationData=PopulationData+P

27、opulationCode(i)*(2(MumberLength-i);endPopulationData=MinX+PopulationData*(MaxX-MinX)/(2Dim(2)-1);【程序說(shuō)明】子程序 Translate.m把編成碼的群體翻譯成變量的數(shù)值含有4個(gè)輸入?yún)?shù)，PopulationCode, MinX, MaxX, MumberLength附錄5：子程序Transfer.mfunction PopulationFitness=Transfer(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)Population

28、Fitness=0;PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength);PopulationFitness=double(subs(FunctionFitness,x,sym(PopulationData); 【程序說(shuō)明】子程序 Transfer 把群體中的染色體的目標(biāo)函數(shù)值用數(shù)值表示出來(lái)，它是Fitness的重要子程序其有5個(gè)輸入?yún)?shù)分別為PopulationCode, FunctionFitness, MinX, MaxX，MumberLength附錄6：子程序FitnessF.mfunction Populati

29、onFitnessF=FitnessF(PopulationFitness,Fmin)Dim=size(PopulationFitness);PopulationFitnessF=zeros(1,Dim(2);for i=1:Dim(2)if PopulationFitness(i)Fmin PopulationFitnessF(i)=PopulationFitness(i)-Fmin;endif PopulationFitness(i)CProbability(Index) Index=Index+1; end NewPopulation(i,:)=Population(Index,:);e

30、nd【程序說(shuō)明】子程序 Select.m 根據(jù)入選概率（計(jì)算累計(jì)概率）在群體中按比例選擇部分染色體組成種群，該子程序的3個(gè)輸入?yún)?shù)分別為：群體Population，入選概率PopulationProbability，群體中染色體的個(gè)數(shù)MemberNumber附錄9：子程序 Crossing.mfunction NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength)%PopulationFitness=% Fitness(Population,FunctionFitness,MinX,MaxX,Mumbe

31、rLength);%PopulationProbability=Probability(PopulationFitness);%SortResult,SortSite=sort(PopulationProbability);%Population=Population(SortSite,:);Dim=size(Population);if Dim(1)=3 Temp=Population(Dim(1),:); Population(Dim(1),:)=Population(Dim(1)-1,:); Population(Dim(1)-1,:)=Temp;endfor i=1:2:Dim(1)-

32、1 SiteArray=randperm(Dim(2); Site=SiteArray(1); Temp=Population(i,1:Site); Population(i,1:Site)=Population(i+1,1:Site); Population(i+1,1:Site)=Temp;endNewPopulation=Population;【程序說(shuō)明】子程序 Crossing.m 用于群體中的交叉并產(chǎn)生新群體其輸入?yún)?shù)為：Population, FunctionFitness，MinX，MaxX，MumberLength附錄10：子程序Mutation.mfunction NewPo

33、pulation=Mutation(Population,MutationProbability)Dim=size(Population);for i=1:Dim(1) Probability=rand(1); Site=randperm(Dim(2); if ProbabilityMutationProbability if Population(i,Site(1)=1 Population(i,Site(1)=0; end if Population(i,Site(1)=0 Population(i,Site(1)=1; end endendNewPopulation=Population

34、;【程序說(shuō)明】子程序Mutation.m用于群體中少量個(gè)體變量并產(chǎn)生新的群體輸入?yún)?shù)為：群體Population和變異概率MutationProbability附錄11：子程序Elitist.mfunction NewPopulationIncludeMax,CurrentBest,EachGenMaxFitness=Elitist(Population,PopulationFitness,MumberLength)global Count CurrentBest;MinFitness,MinSite=min(PopulationFitness);MaxFitness,MaxSite=max(

35、PopulationFitness);EachGenMaxFitness=MaxFitness;if Count=1 CurrentBest(1:MumberLength)=Population(MaxSite,:); CurrentBest(MumberLength+1)=PopulationFitness(MaxSite);else if CurrentBest(MumberLength+1)PopulationFitness(MaxSite); CurrentBest(1:MumberLength)=Population(MaxSite,:); CurrentBest(MumberLen

36、gth+1)=PopulationFitness(MaxSite); endPopulation(MinSite,:)=CurrentBest(1:MumberLength);endNewPopulationIncludeMax=Population;【程序說(shuō)明】子程序Elitist.m用到最佳個(gè)體保存方法（“優(yōu)勝劣汰”思想）輸入?yún)?shù)為：群體Population, 目標(biāo)函數(shù)值PopulationFitness和染色體個(gè)數(shù)MumberLength“遺傳算法”專題一、遺傳算法的主要特征：我們的目的是獲得“最好解”，可以把這種任務(wù)看成是一個(gè)優(yōu)化過(guò)程。對(duì)于小空間，經(jīng)典的窮舉法就足夠了；而對(duì)大空間，則需

37、要使用特殊的人工智能技術(shù)。遺傳算法(Genetic Algorithm)是這些技術(shù)中的一種，它是一類模擬生物進(jìn)化過(guò)程而產(chǎn)生的由選擇算子、雜交算子和變異算子三個(gè)基本算子組成的全局尋優(yōu)算法。它從一個(gè)初始族出發(fā)，由選擇算子選出性狀好的父本，由雜交算子進(jìn)行雜交運(yùn)算，變異算子進(jìn)行少許變異，在一定概率規(guī)則控制下隨機(jī)搜索模型空間。一代代進(jìn)化，直到最終解族對(duì)應(yīng)的誤差泛函值達(dá)到設(shè)定的要求。遺傳算法的結(jié)構(gòu)：Procedure Genetic Algorithmbegin initialize evaluate while (not termination-condition) do beginselect fro

38、m alter evaluate end end 圖1. 遺傳算法的結(jié)構(gòu)在第次迭代，遺傳算法維持一個(gè)潛在解的群體。每個(gè)解用其“適應(yīng)值”評(píng)價(jià)。然后通過(guò)選擇更合適個(gè)體（次迭代）形成一個(gè)新的群體。新的群體的成員通過(guò)雜交和變異進(jìn)行變換，形成新的解。雜交組合了兩個(gè)親體染色體（即待求參數(shù)的二進(jìn)制編碼串）的特征，通過(guò)交換父代相應(yīng)的片斷形成了兩個(gè)相似的后代。例如父代染色體為和，在第二個(gè)基因后雜交，產(chǎn)生的后代為和。雜交算子的目的是在不同潛在解之間進(jìn)行信息交換。變異是通過(guò)用一個(gè)等于變異率的概率隨機(jī)地改變被選擇染色體上的一個(gè)或多個(gè)基因（染色體中的一個(gè)二進(jìn)制位）。變異算子的意圖是向群體引入一些額外的變化性。遺傳算法的

39、特點(diǎn)：(1). 它不是直接作用于參變量集上，而是作用于參變量的某種編碼形成的數(shù)字串上。(2). 它不是從單個(gè)點(diǎn)，而是從一個(gè)解族開始搜索解空間，與傳統(tǒng)的“點(diǎn)對(duì)點(diǎn)”式的搜索方法不同。(3). 它僅僅利用適應(yīng)值信息評(píng)估個(gè)體的優(yōu)劣，無(wú)須求導(dǎo)數(shù)或其它輔助信息。(4). 它利用概率轉(zhuǎn)移規(guī)則，而非確定性規(guī)則。優(yōu)勢(shì)：(1). 不容易陷入局部極值，能以很大的概率找到全局最優(yōu)解。(2). 由于其固有的并行性，適合于大規(guī)模并行計(jì)算。二、遺傳算法的運(yùn)行步驟：1. 一般性描述：不失一般性，考慮求最大值的問(wèn)題。問(wèn)題：求一個(gè)有個(gè)變量的函數(shù)的的最大值。假設(shè)每個(gè)變量為域內(nèi)的一個(gè)值，且對(duì)所有的，。假定以某個(gè)要求的精度優(yōu)化函數(shù)：這

40、里取自變量小數(shù)點(diǎn)后第6位。1） 編碼和解碼：要達(dá)到要求的精度，每個(gè)域應(yīng)該被分割為個(gè)等尺寸的區(qū)間。用表示使成立的最小整數(shù)。這樣，對(duì)每個(gè)變量，由串長(zhǎng)為的二進(jìn)制編碼表達(dá)可以滿足精度要求。以下的公式對(duì)應(yīng)于每個(gè)串的自變量的值：其中表示二進(jìn)制串的十進(jìn)制值。代表一個(gè)潛在解的染色體被長(zhǎng)度為的二進(jìn)制串表達(dá)；前位對(duì)應(yīng)區(qū)間里的一個(gè)值，隨后的位對(duì)應(yīng)區(qū)間里的一個(gè)值，等等；最后的位對(duì)應(yīng)區(qū)間里的一個(gè)值。2） 產(chǎn)生潛在解初始群體：簡(jiǎn)單地以位的方式隨機(jī)地設(shè)定個(gè)染色體。如果確實(shí)有一些關(guān)于最優(yōu)分布的知識(shí)，可以使用這些信息來(lái)設(shè)定初始潛在解的集合。3） 根據(jù)適應(yīng)值評(píng)價(jià)解的適應(yīng)程度并據(jù)此生成新群體：通常使用一個(gè)根據(jù)適應(yīng)值調(diào)節(jié)刻度寬度的輪

41、盤。按照如下方法構(gòu)造輪盤（假設(shè)這里的適應(yīng)值時(shí)正值，否則可以使用一些比例機(jī)制調(diào)整）： 計(jì)算每個(gè)染色體的適應(yīng)值； 計(jì)算群體的總適應(yīng)值： 計(jì)算每個(gè)染色體的選擇概率： 計(jì)算每個(gè)染色體的累計(jì)概率： 對(duì)輪盤轉(zhuǎn)動(dòng)次，每次按照下面的方法為新群體選擇一個(gè)單個(gè)的染色體： 產(chǎn)生一個(gè)在區(qū)間0，1里的隨機(jī)數(shù)； 如果，則選擇第一個(gè)染色體；否則選擇使成立的第個(gè)染色體()。這樣做的效果是：好的染色體得到多個(gè)拷貝，中等染色體保持平穩(wěn)，最差染色體死亡。4） 雜交(crossover)和變異(mutation)決定新群體的性狀：設(shè)雜交概率為，此概率給出預(yù)計(jì)要進(jìn)行雜交的染色體個(gè)數(shù)。對(duì)于新群體中的每個(gè)染色體： 產(chǎn)生一個(gè)在區(qū)間0，1里的

42、隨機(jī)數(shù)； 如果，則選擇給定的染色體進(jìn)行雜交。隨機(jī)地對(duì)被選擇的染色體配對(duì)：對(duì)染色體中的每一個(gè)，產(chǎn)生一個(gè)在區(qū)間1, （為總長(zhǎng)，即染色體位數(shù)）里的隨機(jī)整數(shù)。表示雜交點(diǎn)的位置。兩個(gè)染色體 和 被他們的子代 和 所替代。 下一步的變異，是在一位一位(bit-by-bit)的基礎(chǔ)上進(jìn)行的。另一個(gè)遺傳系統(tǒng)參數(shù)，變異率，給出了我們預(yù)計(jì)的變異位數(shù)：。整個(gè)群體中所有染色體的每一位都有均等的機(jī)會(huì)經(jīng)歷變異，即從0到1或者相反： 產(chǎn)生一個(gè)在區(qū)間0，1里的隨機(jī)數(shù)； 如果，變異此位。隨著選擇、雜交和變異的進(jìn)行，新群體就為下一次的評(píng)價(jià)做好了準(zhǔn)備。該評(píng)價(jià)是用來(lái)為下一次選擇過(guò)程建立概率分布的，即建立一個(gè)根據(jù)當(dāng)前適應(yīng)值構(gòu)造寬距的輪

43、盤。其它的部分只是上述步驟的循環(huán)重復(fù)，見(jiàn)圖1。2. 例子：?jiǎn)栴}：求下列函數(shù)的極大值：，其中及。假定對(duì)每個(gè)變量要求的精度是小數(shù)點(diǎn)后第4位。圖2. 函數(shù)的圖按上面介紹的步驟求解此問(wèn)題：1） 解碼和解碼：變量的定義域長(zhǎng)度為15.1，所要求的精度意味著區(qū)間-3.0, 12.1至少要被分為15.110000個(gè)等距區(qū)間。由于，因此染色體的第一部分需要18位。變量的定義域長(zhǎng)度為1.7，所要求的精度意味著區(qū)間4.1, 5.8至少要被分為1.710000個(gè)等距區(qū)間。由于，因此染色體的第一部分需要15位。因此染色體的總長(zhǎng)度為位，前18位為，后15位為。例如，染色體 ()的前18位表示；后15位0010表示 ；所以

44、該染色體對(duì)應(yīng)于，該染色體的適應(yīng)值為。2） 產(chǎn)生潛在解初始群體：設(shè)，隨機(jī)產(chǎn)生一個(gè)初始化的20個(gè)染色體組成的群體，并計(jì)算相應(yīng)的適應(yīng)函數(shù)值： 很明顯，染色體是最好的，是最差的。3） 根據(jù)適應(yīng)值評(píng)價(jià)解的適應(yīng)程度并據(jù)此生成新群體：現(xiàn)在系統(tǒng)為選擇過(guò)程建立一個(gè)輪盤。群體的總適應(yīng)值為對(duì)每個(gè)染色體，選擇概率為：每個(gè)染色體的累計(jì)概率為： 現(xiàn)在，準(zhǔn)備轉(zhuǎn)動(dòng)輪盤20次，每次為新群體選擇一個(gè)單個(gè)的染色體。假定在區(qū)間0, 1里的20個(gè)數(shù)的一個(gè)隨機(jī)序列是： 0. 0. 0. 0. 0.0. 0. 0. 0. 0.0. 0. 0. 0. 0.0. 0. 0. 0. 0.第一個(gè)數(shù)大于而小于，意味著染色體被選擇；第二個(gè)數(shù)大于而小于，意味著染色體被選擇，等等。最后，新群體由以下染色體組成：4） 雜交(crossover)和變異(mutation)決定新群體的性狀：設(shè)雜交概率，所以預(yù)計(jì)染色體中平均有25%（即20個(gè)中的5個(gè)）將經(jīng)歷雜交。雜交按照下面的方法進(jìn)行：對(duì)新群體中的每個(gè)染色體，產(chǎn)生一個(gè)在區(qū)間0, 1里的隨機(jī)數(shù)，如果，則選擇一個(gè)給定的染色體進(jìn)行雜交。假定隨機(jī)序列為：這說(shuō)明染色體、和被選擇雜交。這里很幸運(yùn)，給選擇的染色體數(shù)是偶數(shù)，可以很容易地配對(duì)；如果選擇的染色體數(shù)為奇數(shù)，可以加入一額外的染色體或者移走一被選擇染色