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

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