一種改進(jìn)的遺傳算法

杜玉平

(朔州師范高等專科學(xué)校 數(shù)學(xué)與計(jì)算機(jī)系，山西 朔州 036000)

自20世紀(jì)70年代受達(dá)爾文的進(jìn)化論的啟發(fā),借鑒生物進(jìn)化過程而得出了遺傳算法(Genetic Algorithm,GA)[1],這是一種啟發(fā)式搜索優(yōu)化算法。由于算法簡(jiǎn)單易操作,因此經(jīng)常用它去解決神經(jīng)網(wǎng)絡(luò)和函數(shù)優(yōu)化方面的問題.

GA算法也存在缺點(diǎn),如收斂慢,局部搜索性不強(qiáng)等問題，因此,文中提出一種基于黃金分割的改進(jìn)遺傳算法(IGA),IGA算法是先改進(jìn)了黃金分割搜索,再將其結(jié)合到遺傳算法中而得到的。IGA算法與標(biāo)準(zhǔn)GA算法相比具有很好的全局收斂性,能有效的抑制未成熟收斂。通過性能函數(shù)測(cè)試,新算法能有效進(jìn)行全局尋優(yōu),且提高收斂進(jìn)度和解的精確度,驗(yàn)證了本文算法改進(jìn)的有效性。

圖1 標(biāo)準(zhǔn)遺傳算法流程圖Fig.1 Standard Genetic Algorithm flow chart

1 標(biāo)準(zhǔn)遺傳算法概述

John Holland結(jié)合生物進(jìn)化機(jī)制總結(jié)出了遺傳算法(GA),GA算法是堅(jiān)持優(yōu)勝劣汰原則,在一代代進(jìn)化遺傳過程中,去掉適應(yīng)值低的,留下適應(yīng)值高的,進(jìn)而使種群慢慢趨于最優(yōu)。GA算法應(yīng)用于實(shí)際問題中,先結(jié)合問題找出適應(yīng)度函數(shù),然后建立一個(gè)初始群體,該群體是由多個(gè)解組成,每個(gè)解對(duì)應(yīng)一個(gè)染色體即一個(gè)編碼。接著結(jié)合適應(yīng)度值大小進(jìn)行群體的一系列遺傳運(yùn)算操作,衍生出下一代,經(jīng)過代代進(jìn)化獲得適應(yīng)度值最好的個(gè)體,它就是所求尋優(yōu)問題的結(jié)果即最優(yōu)解。標(biāo)準(zhǔn)遺傳算法(Standard Genetic Algorithm,SGA)[2]的基本流程圖如圖1所示。

一般編碼有二進(jìn)制編碼、實(shí)數(shù)編碼等,因?yàn)槎M(jìn)制編碼簡(jiǎn)單易實(shí)施,所以標(biāo)準(zhǔn)GA算法主要用二進(jìn)制對(duì)染色體進(jìn)行編碼,尋優(yōu)問題的一個(gè)解對(duì)應(yīng)一個(gè)染色體。初始群體一般是隨機(jī)給定的,其規(guī)模一般根據(jù)尋優(yōu)問題而定,常取20～200個(gè)。選擇個(gè)體交配時(shí)我們一般采取輪盤賭選擇,也可采取比例或精英選擇,可根據(jù)問題而定。遺傳運(yùn)算主要有兩種:交叉和變異,交叉一般采用算術(shù)交叉,變異算子一般采用高斯變異,高斯變異的變異概率為pm,它的取值一般在0.001～0.100,變異和交叉運(yùn)算可以預(yù)防早熟,提高全局尋優(yōu)能力。

2 改進(jìn)的遺傳算法(IGA)

2.1 黃金分割的搜索操作

黃金分割法是一種優(yōu)化方法,它是遵循保存好的,去掉壞的,等比收縮原則來逐漸縮小收縮區(qū)域,進(jìn)而找到最優(yōu)解。具體做法:在[a,b]中取值λ=a+0.382(b-a),μ=a+0.618(b-a),若f(λ)>f(μ),則令a=λ,重新開始。若f(λ)≤f(μ),則令b=μ,重新開始。這樣一次次重復(fù),每次將尋優(yōu)范圍縮小0.382倍或0.618倍,最后剩下一點(diǎn),這一點(diǎn)就是尋優(yōu)問題最優(yōu)解。

IGA算法是將黃金分割做一個(gè)改進(jìn)操作,然后將其結(jié)合到標(biāo)準(zhǔn)GA算法中。詳細(xì)做法如下:

設(shè)可行區(qū)域D為n維,D:{(x1,x2,…,xn)|a1≤x1≤b1,…,an≤xn≤bn},任取屬于D的一點(diǎn),把它作為初始最優(yōu)點(diǎn),計(jì)算該點(diǎn)函數(shù)值,把它作為最優(yōu)解。在縱橫兩個(gè)方向(即單數(shù)維和雙數(shù)維的方向)分別以0.382倍和0.618倍劃分D,把D劃分成3n個(gè)小的區(qū)域塊。計(jì)算每個(gè)區(qū)域塊的中心的函數(shù)值,然后和已知的最優(yōu)值比較,比如第i個(gè)小區(qū)域塊的中心函數(shù)值優(yōu)于已知的最優(yōu)值,則把該值作為新的最優(yōu)值和最優(yōu)點(diǎn);否則,我們估算一下該區(qū)域塊的最優(yōu)值,不優(yōu)于我們已有的最優(yōu)值,則把該區(qū)域塊去掉;否則,將其再繼續(xù)進(jìn)行如上的分割操作,直到分割的直徑達(dá)到我們所要求為止。最后留下來的那個(gè)點(diǎn)的函數(shù)值就是要求的最優(yōu)值。

2.2 改進(jìn)的遺傳算法步驟

算法中,M表示群體的規(guī)模,{x1,x2，…,xM}表示群體中的個(gè)體,G(k)表示第k代群體,G表示群體的最大進(jìn)化代數(shù)。

Step 1:隨機(jī)給出初始化群體,設(shè)初始參數(shù)α,c∈(0,1)。

Step 2:將染色體的二進(jìn)制編碼轉(zhuǎn)化成十進(jìn)制,求出群體中每一個(gè)個(gè)體的適應(yīng)度值fitness=f(x),然后進(jìn)行群體個(gè)體適應(yīng)度值的排序,把最好的那個(gè)個(gè)體記為fmax并保存下來,選6個(gè)最好的個(gè)體組成優(yōu)秀者集合Y(k),也把他們保存下來,把群體適應(yīng)度值記為favg并計(jì)算該值。

Step 3:求ps=fit/sumfit,然后對(duì)群體以概率ps實(shí)施輪盤賭選擇。

Step 4:算術(shù)交叉,交叉概率為pc,將由選擇算子挑出的pc×m對(duì)雙親作一個(gè)算術(shù)交叉操作,設(shè)A=d1d2…dm和B=e1e2…em表示一對(duì)雙親的染色體,則C=c1c2…cm就是二者產(chǎn)生的新個(gè)體(ci=ridi+(1-ri)ei,ri是[0,1]間隨機(jī)數(shù)),更新群體個(gè)體,生成新群體。

Step 5: 高斯變異,取pm=0.1,Mr是隨機(jī)生成的且符合正態(tài)分布的,若pm

Step 8:判斷是否達(dá)到算法所規(guī)定的結(jié)束條件,若達(dá)到算法停止,并輸出結(jié)果,該結(jié)果就是所求問題最優(yōu)解,否則返回Step 3。

3 實(shí)例仿真

文中采用如下三個(gè)函數(shù)對(duì)IGA算法的收斂性進(jìn)行檢驗(yàn),算法中pc=0. 7,pm=0. 1,L=12,其中L為編碼長(zhǎng)度,并將本文算法(IGA)、標(biāo)準(zhǔn)遺傳算法和爬山法遺傳算法[3]進(jìn)行比較,驗(yàn)證了IGA算法的有效性。

例3f(xi,x2)=21.5+x1sin(4πx1)+x2sin(20πx2)，其中x1∈[-3.0,12.1],x2∈[4.1,5.8]

Rastrigin函數(shù)與Sphere函數(shù)二者最小值都為0, 例3函數(shù)實(shí)際最大值為38.8230。表1、表2給出了三種算法的數(shù)值結(jié)果比較和三種算法的收斂性的比較,圖2、圖3、圖4給出三種算法對(duì)于三個(gè)函數(shù)最優(yōu)值的進(jìn)化曲線圖。

從表1、表2以及圖2、圖3、圖4可以得出,本文算法(IGA)求出解的精度更高,全局收斂性能好。IGA算法優(yōu)于標(biāo)準(zhǔn)GA算法和爬山法混合遺傳算法,文中將黃金分割與遺傳算法相結(jié)合的改進(jìn)策略是有效的,尋優(yōu)成功率高。

表1 三種算法的數(shù)值結(jié)果比較Table 1 Comparison of numerical results of three algorithms

表2 三種算法的收斂性比較Table 2 Comparison of convergence of three algorithms

圖2 例1函數(shù)種群最優(yōu)值進(jìn)化曲線圖Fig.2 Example 1 evolution curve of optimal value of function population

圖3 例2函數(shù)種群最優(yōu)值進(jìn)化曲線圖Fig.3 Example 2 evolution curve of optimal value of function population

圖4 例3函數(shù)種群最優(yōu)值進(jìn)化曲線圖Fig.4 Example 3 evolution curve of optimal value of function population

4 結(jié)論

GA算法是一種應(yīng)用廣便于實(shí)施的的優(yōu)化方法,標(biāo)準(zhǔn)的GA算法有受局部最優(yōu)的影響而無法進(jìn)行全局尋優(yōu)的缺點(diǎn)。為了克服該缺點(diǎn)文中提出了一種改進(jìn)的遺傳算法(IGA),即將黃金分割進(jìn)行改進(jìn)操作,然后將其再與遺傳算法結(jié)合而得到。測(cè)驗(yàn)函數(shù)得出了很好的數(shù)值效果,進(jìn)而說明IGA算法的優(yōu)越性,IGA算法能很好地抑制未成熟收斂現(xiàn)象,進(jìn)而擺脫局部最優(yōu),很好地實(shí)施全局尋優(yōu),在全局收斂效果方面得到提高。