Matlab環(huán)境下的遺傳算法程序設(shè)計(jì)及優(yōu)化問(wèn)題求解.docx

Matlab環(huán)境下的遺傳算法程序設(shè)計(jì)及優(yōu)化問(wèn)題求解摘要:本文介紹了遺傳算法的流程及幾個(gè)算子，給出了在matlab 語(yǔ)言環(huán)境下實(shí)現(xiàn)編碼、譯碼、選擇、重組和變異各算子的編程方法，最后用一個(gè)實(shí)例來(lái)說(shuō)明遺傳算法在尋找全局最優(yōu)解中的應(yīng)用。 關(guān)鍵詞:遺傳算法 ;matlab ;程序設(shè)計(jì) 中圖分類號(hào):TP312文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2007)04-11049-03 遺傳算法(GA)是借鑒生物界自然選擇和群體進(jìn)化機(jī)制而形成的一種全局尋優(yōu)算法，其本質(zhì)上是一種基于概率的隨機(jī)搜索算法 。與其它的優(yōu)化算法相比較，遺傳算法具有以下優(yōu)點(diǎn):(1)通用性;(2)并行性;(3)簡(jiǎn)單性和可操作性;(4)穩(wěn)定性和全局性。 1 遺傳算法概述 在遺傳算法中，首先將空間問(wèn)題中的決策變量通過(guò)一定的編碼表示成遺傳空間的一個(gè)個(gè)體，它是一個(gè)基因型串結(jié)構(gòu)數(shù)據(jù);然后將目標(biāo)函數(shù)轉(zhuǎn)換成適應(yīng)度值，用來(lái)評(píng)價(jià)每個(gè)個(gè)體的優(yōu)劣，并將其作為遺傳操作的依據(jù)。遺傳操作包括三個(gè)算子:選擇、重組和變異 。選擇是從當(dāng)前群體中選擇適應(yīng)值高的個(gè)體以生成交配池的過(guò)程，交配池是當(dāng)前代與下一代之間的中間群體。選擇算子的作用是用來(lái)提高群體的平均適應(yīng)度值。重組算子的作用是將原有的優(yōu)良基因遺傳給下一代個(gè)體，并生成包含更復(fù)雜基因的新個(gè)體，它先從交配池中的個(gè)體隨機(jī)配對(duì)，然后將兩兩配對(duì)的個(gè)體按一定方式相互交換部分基因。變異算子是對(duì)個(gè)體的某一個(gè)或幾位按某一較小的概率進(jìn)行反轉(zhuǎn)其二進(jìn)制字符，模擬自然界的基因突變現(xiàn)象。 遺傳算法的基本程序?qū)崿F(xiàn)流程如下: (1)先確定待優(yōu)化的參數(shù)大致范圍，然后對(duì)搜索空間進(jìn)行編碼; (2)隨機(jī)產(chǎn)生包含各個(gè)個(gè)體的初始種群; (3)將種群中各個(gè)個(gè)體解碼成對(duì)應(yīng)的參數(shù)值，用解碼后的參數(shù)求代價(jià)函數(shù)和適應(yīng)度函數(shù)，運(yùn)用適應(yīng)度函數(shù)評(píng)估檢測(cè)各個(gè)個(gè)體適應(yīng)度; (4)對(duì)收斂條件進(jìn)行判斷，如果已經(jīng)找到最佳個(gè)體，則停止，否則繼續(xù)進(jìn)行遺傳操作; (5)進(jìn)行選擇操作，讓適應(yīng)度大的個(gè)體在種群中占有較大的比例，一些適應(yīng)度較小的個(gè)體將會(huì)被淘汰; (6)隨機(jī)交叉，兩個(gè)個(gè)體按一定的交叉概率進(jìn)行交叉操作，并產(chǎn)生兩個(gè)新的子個(gè)體; (7)按照一定的變異概率變異，使個(gè)體的某個(gè)或某些位的性質(zhì)發(fā)生改變; (8)重復(fù)步驟(3)至(7)，直至參數(shù)收斂達(dá)到預(yù)定的指標(biāo)。 使用遺傳算法需要確定的運(yùn)行參數(shù)有:編碼串長(zhǎng)度、交叉和變異概率、種群規(guī)模。編碼串長(zhǎng)度由問(wèn)題的所要求的精度來(lái)決定。交叉概率控制著交叉操作的頻率，交叉操作是遺傳算法中產(chǎn)生新個(gè)體的主要方法，所以交叉概率通常應(yīng)取較大值，但如果交叉概率太大的話又可能反過(guò)來(lái)會(huì)破壞群體的優(yōu)良模式，一般取0.4,0.99 。變異概率也是影響新個(gè)體產(chǎn)生的一個(gè)因素，如果變異概率太小，則產(chǎn)生新個(gè)體較少;如果變異概率太大，則又會(huì)使遺傳算法變成隨機(jī)搜索，為保證個(gè)體變異后與其父體不會(huì)產(chǎn)生太大的差異，通常取變異概率為0.0001,0.1以保證種群發(fā)展的穩(wěn)定性。種群規(guī)模太大時(shí)，計(jì)算量會(huì)很大，使遺傳算法的運(yùn)行效率降低，種群規(guī)模太小時(shí)，可以提高遺傳算法的運(yùn)行速度，但卻種群的多樣性卻降低了，有可能找不出最優(yōu)解，通常取種群數(shù)目20,100。從理論上講，不存在一組適用于所有問(wèn)題的最佳參數(shù)值，隨著問(wèn)題參數(shù)的變化，有效問(wèn)參數(shù)的差異往往是十分顯著的。 2 用Matlab 語(yǔ)言來(lái)實(shí)現(xiàn)遺傳算法 Matlab是一個(gè)高性能的計(jì)算軟件，配備有功能強(qiáng)大的數(shù)學(xué)函數(shù)支持庫(kù)，適用范圍大，編程效率高，語(yǔ)句簡(jiǎn)單，功能齊備，是世界上頂級(jí)的計(jì)算與仿真程序軟件 。利用Matlab來(lái)編寫遺傳算法程序簡(jiǎn)單而且易于操作。 2.1 編碼 編碼就是把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法能夠處理的搜索空間的轉(zhuǎn)化方法，編碼形式?jīng)Q定了重組算子的操作。遺傳算法是對(duì)編碼后的個(gè)體作選擇與交叉運(yùn)算，然后通過(guò)這些反復(fù)運(yùn)算達(dá)到優(yōu)化目標(biāo)。遺傳算法首要的問(wèn)題是通過(guò)編碼將決策變量表示成串結(jié)構(gòu)數(shù)據(jù)。我們常用的是二進(jìn)制編碼，即用二進(jìn)制數(shù)構(gòu)成的符號(hào)串來(lái)表示每個(gè)個(gè)體。通常根據(jù)搜索精度(sca_var)、決策變量上界(range(2) 的和下界(range(1)來(lái)確定各個(gè)二進(jìn)制字符串的長(zhǎng)度(bit_n)，搜索精度為sca_var=(range(2),range(1)./(2bit_n1),然后再隨機(jī)產(chǎn)生一個(gè)的初始種群(be_gen),其規(guī)模為popusize。下面用encoding 函數(shù)來(lái)實(shí)現(xiàn)編碼和產(chǎn)生初始的種群: function be_gen , bit_n=encoding(sca_var,range(1) , range(2), popusize) bit_n=ceil(log2 ( range(2),range(1)./sca_var); be_gen= randint( popusize, sum(bit_n); 2.2 譯碼 決策變量經(jīng)過(guò)編碼之后，各個(gè)個(gè)體構(gòu)成的種群be_gen要通過(guò)解碼才能轉(zhuǎn)換成原問(wèn)題空間的決策變量構(gòu)成的種群vgen，這樣才能計(jì)算其相應(yīng)的各個(gè)適應(yīng)度值。另外，譯碼首先要求出二進(jìn)制數(shù)對(duì)應(yīng)的十進(jìn)制數(shù)decimal,然后根據(jù)下面的公式求出實(shí)際決策變量X: X=range(1)+decimal*sca_dec .通?？梢杂胐ecoding函數(shù)來(lái)實(shí)現(xiàn)譯碼的過(guò)程: functionvgen,fitness=decoding(fcn , be_gen,bit_n,range(1),range(2) popusize=size(be_gen,1); n_var=length(bit_n); sca_dec=(range(2),range(1)./(2bit_n,1); bit_n=cumsun(bit_n); bit_n=0 bit_n; for i=1:n_var be_var(i)=be_gen(:,bits(i)+1:bit_n(i +1); var(i)= range( 1)( i )+sum(ones(popusize,1)*2.(