基于概率的隨機(jī)搜索算法

基于概率的隨機(jī)搜索算法

遺傳算法（ga）是在生物界自然選擇和群體發(fā)展機(jī)制的基礎(chǔ)上形成的一種全局優(yōu)化算法。其本質(zhì)上是基于概率的隨機(jī)搜索算法。與其它的優(yōu)化算法相比較,遺傳算法具有以下優(yōu)點(diǎn):(1)通用性;(2)并行性;(3)簡(jiǎn)單性和可操作性;(4)穩(wěn)定性和全局性。1遺傳算法的基本程序?qū)崿F(xiàn)流程在遺傳算法中,首先將空間問(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數(shù)學(xué)函數(shù)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))./(2^bit_n—1),然后再隨機(jī)產(chǎn)生一個(gè)的初始種群(be_gen),其規(guī)模為popusize。下面用encoding函數(shù)來(lái)實(shí)現(xiàn)編碼和產(chǎn)生初始的種群:2.2適應(yīng)度值的計(jì)算決策變量經(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ò)程:2.3比例選擇法選擇就是利用碼后求得的各個(gè)個(gè)體的適應(yīng)度的大小,從中選出一些適應(yīng)度高的個(gè)體,并淘汰一些適應(yīng)度較小的個(gè)體以生成交配池的過(guò)程。然后再對(duì)優(yōu)良的個(gè)體進(jìn)行交叉和變異操作。在選擇算子中,先找出當(dāng)前群體中適應(yīng)度最高和最低的個(gè)體,將最佳個(gè)體bes_ind保留并替換最差個(gè)體,直接進(jìn)入下一代,將剩余個(gè)體evol_gen按適應(yīng)值比例選擇法進(jìn)行操作,即采用輪盤賭(roulettewheel)方式來(lái)實(shí)現(xiàn)。這種方式首先計(jì)算每個(gè)個(gè)體的適應(yīng)值,然后計(jì)算出該適應(yīng)值在群體適應(yīng)值總和中所占的比例,來(lái)表示該個(gè)體被選中的概率,這樣既能保證最佳個(gè)體的適應(yīng)度值不會(huì)減小,最佳個(gè)體不會(huì)被交叉變異操作所破壞,也能不斷提高該群體的平均適應(yīng)度值。比例選擇法體現(xiàn)了生物進(jìn)化過(guò)程中“優(yōu)勝劣汰,適者生存”的思想,并且保證將優(yōu)良的基因遺傳給下一代。我們可以用下面的函數(shù)來(lái)實(shí)現(xiàn)選擇算子:2.4交叉組合法:背景算子和交叉操作重組算子是產(chǎn)生新個(gè)體的主要方法,它決定了遺傳算法的全局搜索能力。重組操作的作用是將原有的優(yōu)良基因遺傳給下一代個(gè)體,并生成包含更優(yōu)良基因的新個(gè)體。通常使用的遺傳算子是一點(diǎn)交叉法,就是按交叉概率pc(0<pc1)實(shí)施交叉操作,兩個(gè)個(gè)體編碼串(string)在交叉位置處(crossp)相互交換各自的部分編碼,從而形成新的一對(duì)個(gè)體。程序如下:另外,一點(diǎn)交叉法操作的信息比較小,交叉點(diǎn)的位置的選擇可能會(huì)帶來(lái)較大的偏差,一點(diǎn)交叉算子不利于長(zhǎng)距離的保留和重組。2.5局部搜索能力變異算子是模擬自然界生物進(jìn)化的中染色體的基因突變現(xiàn)象,從而改變?nèi)旧w的結(jié)構(gòu)和物理性狀。變異算子是產(chǎn)生新個(gè)體的輔助方法,它決定了遺傳算法的局部搜索能力。變異操作通過(guò)按照變異概率(mp)隨機(jī)反轉(zhuǎn)某位等位基因的二進(jìn)制字符的值來(lái)實(shí)現(xiàn)。程序如下:當(dāng)重組操作發(fā)生早熟收斂時(shí),這時(shí)引入變異算子會(huì)有很好的效果。一方面,變異算子可以使群體進(jìn)化中丟失的等位基因信息得以恢復(fù),保持群體基因中的差異性,防止發(fā)生早熟收斂;另一方面,當(dāng)種群規(guī)模較大時(shí),在重組操作基礎(chǔ)上引入適度的變異,也能夠提高遺傳算法的局部搜索效率。3實(shí)際應(yīng)用的例子4遺傳generation公式用matlab語(yǔ)言編寫了遺傳算法程序,并通過(guò)了調(diào)試,用一個(gè)實(shí)際例子來(lái)對(duì)問(wèn)題進(jìn)行了驗(yàn)證,這對(duì)在matlab環(huán)境下用遺傳算法來(lái)解決優(yōu)化問(wèn)題有一定的意義。在這里我們以一個(gè)函數(shù)為例來(lái)驗(yàn)證遺傳算法程序的全局搜索能力,設(shè)函數(shù)為z=3*(1-x)^2*exp(-(x^2)-(y+1)^2)-10*(x/5-x^3-y^5)*exp(-x^2-y^2)-1/3*exp(-(x+1)^2-y^2),x∈[-3,3],y∈[-3,3]。如果取種群的規(guī)模popusize=20,搜索精度sca_var=0.000001,交叉率pc=0.98,變異概率mp=0.01。圖1是函數(shù)圖形示意圖,圖2中給出了遺傳generat