MATLAB實驗遺傳算法及優(yōu)化設(shè)計

1、實驗六遺傳算法與優(yōu)化設(shè)計、實驗?zāi)康?. 了解遺傳算法的基本原理和基本操作（選擇、交叉、變異）2.學(xué)習(xí)使用Matlab中的遺傳算法工具箱（gatool）來解決優(yōu)化設(shè)計問題;、實驗原理及遺傳算法工具箱介紹1. 一個優(yōu)化設(shè)計例子圖1所示是用于傳輸微波信號的微帶線 （電極）的橫截面結(jié)構(gòu)示意圖,上下兩根黑條分別代表上電極和下電極，一般下電極接地，上電極接輸入信號，電極之間是介質(zhì)（如空氣，陶瓷等）。微帶電極的結(jié)構(gòu)參數(shù)如圖所示，W、t分別是上電極的寬度和厚度,D是上下電極間距。當(dāng)微波信號在微帶線中傳輸時，由于趨膚效應(yīng)，微帶線中的電流集中在電極的表面，會產(chǎn)生較大的歐姆損耗。根據(jù)微帶傳輸線理論，高頻工作狀態(tài)下（

2、假定信號頻率1GHz），電極的歐姆損耗可以寫成（簡單起見，不考慮電極厚度造成電極寬度的增加）圖1微帶線橫截面結(jié)構(gòu)以及場分布示意圖Rs8.68a = + 50DjW 2( W TV D W ；+-ln fTie (云+0.94jy <"d+ 0.94丿L W兀wI tD丿(1)可見電極的結(jié)構(gòu)參數(shù)影響著電極損耗,其中Rs =臥為金屬的表面電阻率，F(xiàn)為電阻率。這就是所謂的最優(yōu)化問題或者稱為通過合理設(shè)計這些參數(shù)可以使電極的歐姆損耗做到最小，規(guī)劃設(shè)計問題。此處設(shè)計變量有 3個：W、D、t,它們組成 決策向量W, D ,t T，待優(yōu)化函數(shù)a（W,D,t）稱為目標(biāo)函數(shù)。上述優(yōu)化設(shè)計問題可以抽

3、象為數(shù)學(xué)描述:min f (X )* st.gj(x)蘭0,j =12.,P其中=（X1,X2,.,Xn T是決策向量,X1,，Xn為n個設(shè)計變量。這是一個單目標(biāo)的數(shù)學(xué)其中每一個Vi代表一個基因，染色體的長度m不一定等于設(shè)計變量的數(shù)目n,取決于染色規(guī)劃問題：在一組針對決策變量的約束條件gj（<0,j =1,.,p下，使目標(biāo)函數(shù)最小化（有時也可能是最大化，此時在目標(biāo)函數(shù)f（x ）前添個負(fù)號即可）。滿足約束條件的解 X稱為可行解，所有滿足條件的 X組成問題的可行解空間。2.遺傳算法基本原理和基本操作遺傳算法（Genetic Algorithm, GA）是一種非常實用、高效、魯棒性強(qiáng)的優(yōu)化技術(shù)

4、，廣泛應(yīng)用于工程技術(shù)的各個領(lǐng)域 （如函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、圖像處理、生產(chǎn)調(diào)度等）。遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化算法。按照達(dá)爾文的進(jìn)化論，生物在進(jìn)化過程中“物競天擇”，對自然環(huán)境適應(yīng)度高的物種被保留下來，適應(yīng)度差的物種而被淘汰。物種通過遺傳將這些好的性狀復(fù)制給下一代，同時也通過種間的交配（交叉）和變異不斷產(chǎn)生新的物種以適應(yīng)環(huán)境的變化。從總體水平上看，生物在進(jìn)化過程中子代總要比其父代優(yōu)良，因此生物的進(jìn)化過程其實就是一個不斷產(chǎn)生優(yōu)良物種的過程，這和優(yōu)化設(shè)計問題具有驚人的相似性，從而使得生物的遺傳和進(jìn)化能夠被用于實際的優(yōu)化設(shè)計問題。按照生物學(xué)知識，遺傳信息一基

5、因（Gene）的載體是染色體（Chromosome），染色體中一定數(shù)量的基因按照一定的規(guī)律排列（即編碼），遺傳基因在染色體中的排列位置稱為基因座（Locus），在同一個基因座上所有可能的基因就稱為等位基因（Allele），生物所持有的基因以及基因的構(gòu)成形式稱為生物的基因型（Genotype），而該生物在環(huán)境中所呈現(xiàn)的相應(yīng)性狀稱為該生物的 表現(xiàn)型（Phenotype）。在遺傳過程中，染色體上的基因能夠直接復(fù)制給子代從交叉（Crossover）而重組，即兩個染色體在某個相同的位置處被截斷，其前后兩串基因交叉組合而形成兩個新的染色體。在基而使得子代具有親代的特征，此外，兩條染色體之間也通過因復(fù)制時也

6、會產(chǎn)生微小的 變異（Mutation），從而也產(chǎn)生了新的染色體。因此交叉和變異是產(chǎn)生新物種的主要途徑。由于自然選擇，在子代群體新產(chǎn)生的物種（或染色體）當(dāng)中，只有那些對環(huán)境 適應(yīng)度高的才能生存下來，即適應(yīng)度越高的被選擇的概率也越大，然后又是通過遺傳和變異再自然選擇， 一代一代不斷進(jìn)化。因此生物遺傳和進(jìn)化的基本過程就是：選擇（即復(fù)制）、交叉和變異。遺傳算法就是通過模擬生物進(jìn)化的這幾個基本過程而實現(xiàn)的。編碼編碼是設(shè)計遺傳算法首要解決的問題。在生物進(jìn)化中，選擇、交叉、變異這些基本過程都是基于遺傳信息的編碼方式進(jìn)行的，即基于染色體的基因型而非表現(xiàn)型，因此要模擬生物進(jìn)化過程，遺傳算法必須首先對問題的可行解

7、X （決策向量）進(jìn)行某種編碼，以便借鑒生物學(xué)中染色體和基因等概念。在遺傳算法中，將每一個決策向量X用一個染色體 V來表示:X =(X1,.,Xn $ = V =V1,V2,.,Vm（表現(xiàn)型）（基因型）體上基因的編碼方式。一般有兩種編碼方式：二進(jìn)制編碼和浮點數(shù)編碼。如果是二進(jìn)制編碼，每一個設(shè)計變量 Xi的真實值用一串二進(jìn)制符號0和1按照一定的編碼規(guī)則來表示，每個二進(jìn)制符號就代表一個基因， 因此染色體長度要遠(yuǎn)大于設(shè)計變量的數(shù)目。這種由二進(jìn)制編碼構(gòu)Xi用其取值范圍成的排列形式 V就是染色體（也稱 個體）的基因型，而基因型經(jīng)過解碼后所對應(yīng)的決策向 量X （即可行解）就是個體的表現(xiàn)型。如果是浮點數(shù)編碼，

8、每個設(shè)計變量Vi,因此個體的編碼長度m也就Umin,U Lax 內(nèi)的一個浮點數(shù)表示，構(gòu)成染色體的一個基因等于決策變量的個數(shù) n由于這種編碼方式使用的是決策變量的真實值，所以也稱真值編碼方法。無論哪種編碼方式，所有可能的染色體（個體）V構(gòu)成問題的搜索空間（種群），遺（后面敘述適應(yīng)度的計傳算法對最優(yōu)解的搜索就是在搜索空間中搜索適應(yīng)度最高的染色體 算），因此通過編碼將一個問題的可行解從其解空間轉(zhuǎn)換到了遺傳算法能夠處理的搜索空間。經(jīng)過個體的編碼后，就可以進(jìn)行遺傳算法的基本操作：選擇、交叉和變異。 選擇（復(fù)制）操作生物的進(jìn)化是以選擇也就是復(fù)制，是在群體中選擇適應(yīng)度高的個體產(chǎn)生新群體的過程。集團(tuán)為主體的，

9、與此相應(yīng)，遺傳算法的運(yùn)算對象是有M個個體或染色體組成的集合，稱為種群，M也稱為種群規(guī)模。遺傳算法在模擬自然選擇時，以個體的適應(yīng)度（Fitness）高低為而適應(yīng)度低的個體遺傳到下選擇依據(jù)，即適應(yīng)度高的個體被遺傳到下一代種群的概率較高,代的概率則相對較低。個體適應(yīng)度由適應(yīng)度函數(shù)Fit（f（X ）計算，適應(yīng)度函數(shù)總是和個體一種最簡單表現(xiàn)型（i.e. X ）的目標(biāo)函數(shù)值f（X）關(guān)聯(lián)，一般是由目標(biāo)函數(shù)經(jīng)過一定的變換得到。的方法就是直接使用目標(biāo)函數(shù)f（X）作為適應(yīng)度函數(shù):'f （X ）目標(biāo)函數(shù)最小化問題Fit（f（X）眾l-f （ X ）目標(biāo)函數(shù)最大化問題選定了適應(yīng)度函數(shù)之后，個體適應(yīng)度也隨之確定

10、,則在選擇操作時，個體被選中的概率Pi = M三Fi(i =1,2,，M )其中Fi為個體的適應(yīng)度。這種選擇方式稱為比例選擇，也稱輪盤賭選擇。除此之外還有多種選擇方法，如隨機(jī)競爭選擇、均勻選擇、無回放隨機(jī)選擇等，不一一介紹。 交叉操作所謂交叉就是以一定的概率（交叉概率）從群體中選擇兩個個體（染色體）按照某種方式交 換其部分基因，從而形成兩個新的個體。 在遺傳算法中它是產(chǎn)生新個體同時也是獲得新的優(yōu)良個體的主要方法，它決定了遺傳算法的全局搜索能力。對于不同的編碼方式，交叉操作的具體方法也不相同，對于浮點數(shù)編碼，一般使用算術(shù)交叉； 對于二進(jìn)制編碼有單點交叉和多Pc,這個概率表明種群點交叉等方式。不論

11、何種方式，在交叉操作時首先應(yīng)定義交叉概率中參與交叉的個體數(shù)目的期望值是PC ”M，M是種群規(guī)模。通常交叉概率應(yīng)取較大的值,以便產(chǎn)生較多的新個體，增加全局搜索力度。但是Pc過大時優(yōu)良個體被破壞的可能性也越大，如果Pc太小則搜索進(jìn)程變慢，影響算法的運(yùn)行效率。一般建議的取值范圍是 0.4-0.99。 變異操作Pm用其遺傳算法中的變異操作就是將染色體上某些基因座上的基因以一定的變異概率 他的等位基因替代， 從而形成新的個體。 對于浮點數(shù)編碼，變異操作就是將變異點處的基因1”變用該基因取值范圍內(nèi)的一個隨機(jī)數(shù)替換。對于二進(jìn)制編碼則是將變異點處的基因由“ 成“ 0”，“0”變成“1”。變異操作也有多種方法，

12、如均勻變異、非均勻變異、高斯變異等。變異操作的概率Pm要比交叉操作的概率 Pc小得多，變異只是產(chǎn)生新個體的輔助手段。但它是遺傳算法必不可少的一個環(huán)節(jié)，因為變異操作決定了算法的局部搜索能力，它彌補(bǔ)了交叉操作無法對搜索空間的細(xì)節(jié)進(jìn)行局部搜索的不足,因此交叉和變異操作相互配合共同完成對搜索空間的全局和局部搜索。以上簡要介紹了遺傳算法的基本原理和操作，歸納起來，基本遺傳算法一般可以表示為一個8元組:SGA=（C,E,F0,M ,工甲,T）式中，C個體的編碼方法；E個體適應(yīng)度評價函數(shù)；P0初始種群；M種群規(guī)模；選擇 操作；r交叉操作；普變異操作；T是進(jìn)化終止代數(shù)（進(jìn)化終止條件）。其中有4個運(yùn)行參 數(shù)需要

13、預(yù)先設(shè)定：M, T, Pc，Pm種群規(guī)模 M 一般取為20100 ；終止代數(shù)T 一般取100500 ；交叉概率Pc一般取0.4-0.99;變異概率Pm一般取0.0001-0.1最后給出遺傳算法的基本步驟：選擇二進(jìn)制編碼或浮點數(shù)編碼把問題的解表示成（個體），也就是初始種群。計算每一個個體的適應(yīng)度值，按適者生存的原則，從中選擇出適應(yīng)度較大的 “染色體”進(jìn)行復(fù)制，再通過交叉、“染色體”。隨機(jī)產(chǎn)生一群“染色體”變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群，即子代。重復(fù)第3步。經(jīng)過這樣的一代一代地進(jìn)化，最后就會收斂到最適應(yīng)環(huán)境（適應(yīng)度最大）的一個“染色體”（即個體）上，它就是問題的最優(yōu)解。圖 2給出了基本

14、遺傳算法設(shè)計流程圖，其中t代表當(dāng)前代數(shù)，T是進(jìn)化終止代數(shù)。t=l,初始化種群個體適應(yīng)度計算進(jìn)化結(jié)束*圖2基本遺傳算法設(shè)計流程圖3. Matlab遺傳算法工具箱（gatool）Matlab的遺傳算法工具箱有一個精心設(shè)計的圖形用戶界面，可以幫助用戶直觀、方便、 快速地利用遺傳算法求解最優(yōu)化問題。在Matlab命令窗口輸入命令：gatool可以打開遺傳算法工具箱的圖形用戶界面，如圖3所示。GA工具箱的參數(shù)設(shè)置步驟如下:輸入適應(yīng)度函數(shù)輸入適應(yīng)度一 函數(shù)中的變量數(shù)目開始執(zhí)行遺f專算法結(jié)果彎態(tài)顯示圖3.遺傳算法工具示數(shù)述 顯參描（1）首先，使用遺傳算法工具箱必須輸入下列信息:Fitness functio

15、n（適應(yīng)度函數(shù)）這里指的是待優(yōu)化的函數(shù)，也即目標(biāo)函數(shù)。該工具箱總是試圖尋找目標(biāo)函數(shù)的最小值。輸入適應(yīng)度函數(shù)的格式為fitnessfun，其中符號 產(chǎn)生函數(shù)fitnessfun的句柄，fitnessfun代表用戶編寫的計算適應(yīng)度函數(shù) （目標(biāo)函數(shù)）的M文件名，該M文件的編寫方法如下:假定我們要計算Rastrigin函數(shù)的最小值2 2f (x1,x2)=20+x1 +X2 -10(cos2；ix1 +cos2；ix2)M函數(shù)文件確定這個函數(shù)必須接受一個長度為2的行向量X，也即決策向量，向量的長度等于變量數(shù)目，行向量X的每個元素分別和變量X1和X2對應(yīng)。另外 M文件要返回一個標(biāo)量乙其值等于該函數(shù)的值。

16、下面是計算Rastrigin函數(shù)的M文件代碼:function Z=Ras_fu n(X)Z=20+X(1)A2+X(2)A2-10*(cos(2* pi*X(1)+cos(2* pi*X(2);M文件編寫、保存后，再在 gatool工具箱界面Fitness function欄輸入 Ras_fun Number of variable（變量個數(shù)）2。目標(biāo)函數(shù)中的變量數(shù)目，也即適應(yīng)度函數(shù)輸入向量的長度。在上例中，它的值是（2）其次，設(shè)置遺傳算法參數(shù)，即Options設(shè)置。以下只介紹部分運(yùn)行參數(shù)的設(shè)置，其他未提及的參數(shù)采用默認(rèn)設(shè)置即可。種群參數(shù)（Population ）Population siz

17、e （種群規(guī)模）：每一代中的個體數(shù)目，一般是20-100之間。種群規(guī)模大,算法搜索更徹底，可以增加算法搜索全局最優(yōu)而非局部最優(yōu)的概率，但是耗時也更長。variable），第一行是每個變量的下限，第二行是每個變量的上限。如果只輸入2©的矩陣，則每個變量的初始搜索范圍都一樣。注意，初始范圍僅限定初始種群中個體Initial range （初始范圍）：其值是兩行的矩陣，代表初始種群中個體的搜索范圍，實際上 是決策向量X中每個變量Xi的初始搜索范圍。矩陣的列數(shù)等于變量個數(shù)（ Number of（或決 策向量）的范圍，后續(xù)各代中的個體可以不在初始范圍之內(nèi)。初始范圍不能設(shè)置太小， 否則造成個體之

18、間的差異過小，即種群的多樣性降低，不利于算法搜索到最優(yōu)解。復(fù)制參數(shù)(Reproduction )0.40.99，默認(rèn) 0.8。100500，默認(rèn)是 100。當(dāng)遺傳算法運(yùn)行到該參Crossover fraction （交叉概率）：一般取算法終止準(zhǔn)則（Stopping Criteria提供了 5種算法終止條件:Gen eratio ns：最大的進(jìn)化代數(shù)，一般取數(shù)指定的世代，計算終止。Inf （無窮大）。計算終止。缺省是-Inf。Time limit :指明算法終止執(zhí)行前的最大時間，單位是秒。缺省是Fitness limit（適應(yīng)度限）：當(dāng)最優(yōu)適應(yīng)度值小于或等于此參數(shù)值時,Stall gen era

19、tio n（停滯代數(shù)）：如果每一代的最佳適應(yīng)度值在該參數(shù)指定的代數(shù)沒有改善, 則終止計算。缺省是50代。Stall time（停滯時間）：如果每一代的最佳適應(yīng)度值在該參數(shù)指定的時間間隔內(nèi)沒有改 善，則終止計算。缺省是20秒。（3）設(shè)置繪圖參數(shù)，即 Plots設(shè)置。繪圖參數(shù)（Plots）工作時可以從遺傳算法得到圖形數(shù)據(jù)。當(dāng)選擇各種繪圖參數(shù)并執(zhí)行遺傳算法時，一個圖形窗口在分離軸上顯示這些圖形。下面介紹其中2個參數(shù)Best fitn ess：選擇該繪圖參數(shù)時，將繪制每一代的最佳適應(yīng)度值和進(jìn)化世代數(shù)之間的關(guān)系圖，如圖4的上圖所示。圖中藍(lán)色點代表每一代適應(yīng)度函數(shù)的平均值，黑色點代表每一代的最佳值。Dis

20、ta nee:選擇此參數(shù)時，繪制每一代中個體間的平均距離。它反映個體之間的差異程度，所以可用來衡量種群的多樣性。圖4的下圖顯示的即是每一代個體間的平均距離。20304D5060Generation708090100Best 0.00089516 Mean 0.0611227Average Distance Benween Individuals20SO4。5060Generation70SO90100(4)執(zhí)行算法：參數(shù)設(shè)置好了之后，點擊工具箱界面上的按鈕“Star”執(zhí)行求解器。在算法運(yùn)行的同時，“Curre nt gen eration (當(dāng)前代數(shù))”文本框中顯示當(dāng)前的進(jìn)化代數(shù)。通過單擊&q

21、uot;Pause”按鈕可以使計算暫停，之后再點擊“ Resume可以恢復(fù)計算。當(dāng)計算完成時，“Status and results”窗格中出現(xiàn)如圖 5所示的情形。Status and results:IGh ruMtinfi.GA ttrminated-Fitness function value_ 0. 003909079476933379Optinii lati on terminated： maciimum number o£ generati ons eKceeded.<|Final Point:1 2其中包含下列信息:算法終止時適應(yīng)度函數(shù)的最終值一即目標(biāo)函數(shù)的最優(yōu)值

22、Fit ness fun ctio n value: 0.003909079476983379算法終止原因Op timizati on term in ated: maximum nu mber of gen erati ons exceeded/ 超出最大進(jìn)化世代數(shù) ） 最終點一即目標(biāo)函數(shù)的最優(yōu)解X1 X2 = -0.004-0.00193（兩個變量的例子）三、實驗內(nèi)容1. Rastrigin函數(shù)的最小值問題函數(shù)表達(dá)式如 式，函數(shù)圖像如下圖6所示，它有多個局部極小值，但是只有一個全局最小值。Rastrigin函數(shù)的全局最小值的精確解是0,出現(xiàn)在X1 X2=0 0處。使用遺傳算法工具箱近似求解Rastrigin函數(shù)的最小值首先編寫計算適應(yīng)度函數(shù)的 M文件，然后設(shè)置運(yùn)行參數(shù)（繪圖參數(shù)Plots勾選Best fitness 和Distanee兩項，其它參數(shù)可以使用默認(rèn)值），執(zhí)行求解器（Run solver）計算Rastrigin函數(shù) 的最優(yōu)值。觀察種群多樣性對優(yōu)化結(jié)果的影響決定遺傳算法的一個重要性能是種群的多樣性。個體之間的距離越大，則多樣性越高；反之則多樣性越低。多樣性過高或過低遺傳算法都可能運(yùn)行不好。通過實驗調(diào)整Population（種群）的Initial range（初始范圍）參數(shù)可得到種群適當(dāng)?shù)亩鄻有?。取Initial range參數(shù)值1; 1.1觀察Rastr