基于海明距離改進(jìn)的自適應(yīng)遺傳算法

鞏 固， 郝國(guó)生， 王文虎

(1.江蘇師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 徐州 221116; 2.江蘇師范大學(xué) 科文學(xué)院,江蘇 徐州 221116)

0 引言

遺傳算法(genetic algorithm,GA)是模擬生物進(jìn)化論的仿生算法,具有簡(jiǎn)單、通用、魯棒性強(qiáng)和適于并行分布處理的特點(diǎn)．自1975年Holland系統(tǒng)提出遺傳算法以來(lái),很多研究者一直致力于推動(dòng)遺傳算法的改進(jìn)和發(fā)展,在編碼方式、控制參數(shù)的確定、預(yù)防陷于局部最優(yōu)等方面進(jìn)行了深入的研究,提出了各種改進(jìn)的遺傳算法．Srinivas等[1]1994年提出了一種自適應(yīng)遺傳算法(adaptive general algorithm,AGA),實(shí)現(xiàn)交叉概率Pc和變異概率Pm隨群體的適應(yīng)度自動(dòng)改變[1-3]．算法運(yùn)行中,當(dāng)種群個(gè)體的適應(yīng)度趨于一致或者局部最優(yōu)時(shí),Pc和Pm增加,以跳出局部最優(yōu);當(dāng)群體個(gè)體適應(yīng)度比較分散時(shí),Pc和Pm減少,以利于優(yōu)良個(gè)體的生存[4-6]．

雖然遺傳算法得到了極大的發(fā)展和應(yīng)用,但仍存在著局部搜索能力不夠、欺騙問(wèn)題和“早熟”現(xiàn)象等[3-5]，影響了算法的全局收斂性和計(jì)算性能[2,6-7]．很多研究者針對(duì)“早熟”現(xiàn)象提出了不同解決方法,如分層遺傳算法、CHC算法、messy GA、基于小生境技術(shù)的遺傳算法、并行遺傳算法等,但是“早熟”現(xiàn)象仍然存在,在具體應(yīng)用中影響到結(jié)果的正確獲取[8-10]．針對(duì)AGA算法的不足,本文提出基因間距思想,利用Hamming距離控制種群的個(gè)體差異,將優(yōu)良基因很好地遺傳到下一代,使得染色體可以到達(dá)的范圍更大,從而產(chǎn)生最優(yōu)解的機(jī)會(huì)就變大．在這些工作的基礎(chǔ)上，給出了仿真實(shí)驗(yàn),結(jié)果驗(yàn)證了改進(jìn)的自適應(yīng)遺傳算法的有效性，且該算法增強(qiáng)了全局收斂性．

1 自適應(yīng)遺傳算法與改進(jìn)

1.1 自適應(yīng)遺傳算法

遺傳算法參數(shù)中的Pc和Pm對(duì)算法的性能起著非常重要的作用．若采用固定的Pc和Pm值難以適應(yīng)種群狀態(tài)的變化,有時(shí)候?qū)е逻M(jìn)化過(guò)程停滯不前．Srinvivas等提出一種自適應(yīng)遺傳算法,該算法中Pc和Pm能隨適應(yīng)值自動(dòng)改變[1]．同時(shí),適應(yīng)值高于群體平均適應(yīng)值的個(gè)體,對(duì)應(yīng)于較低的Pc和Pm,使得上代較優(yōu)解基因能進(jìn)入下一代;而低于平均適應(yīng)值的個(gè)體,對(duì)應(yīng)于較高的Pc和Pm,對(duì)應(yīng)解被淘汰掉.所以AGA的Pc和Pm能提供相對(duì)某個(gè)解的最佳Pc和Pm．AGA在保持群體多樣性的同時(shí),保證了遺傳算法的收斂性．Srinvivas等提出的自適應(yīng)算法中Pc和Pm公式[1-2,5]如下：

式中fmax為群體中最大的適應(yīng)度值,favg為每代群體的平均適應(yīng)度值,f′為要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值,f為要變異個(gè)體的適應(yīng)度值,k1,k2,k3和k4為(0,1)之間的值．

由于Pc和Pm對(duì)遺傳算法的性能影響較大,故應(yīng)防止因Pc和Pm選擇不當(dāng)造成算法過(guò)早收斂或收斂速度慢的現(xiàn)象出現(xiàn)．但Pc和Pm的選取不能簡(jiǎn)單地隨適應(yīng)度線性變化．本文結(jié)合文獻(xiàn)[4-7]的思想,采用余弦形式改進(jìn)自適應(yīng)遺傳算法算子,構(gòu)造的自適應(yīng)遺傳算子為

1.2 自適應(yīng)遺傳算法的改進(jìn)

用Hamming距離控制初始種群的個(gè)體差異,以擴(kuò)大種群的多樣性,遏制超長(zhǎng)個(gè)體的快速繁殖．方法如下:在產(chǎn)生初始種群的過(guò)程中,每產(chǎn)生一個(gè)新個(gè)體都與前面的所有個(gè)體進(jìn)行比較,若新個(gè)體與前面某一個(gè)個(gè)體的Hamming距離小于某一設(shè)定值(一般為3到5,該數(shù)的設(shè)定與鏈碼長(zhǎng)度有關(guān)),則停止比較，跳出循環(huán),重新產(chǎn)生新個(gè)體,直到得到所有個(gè)體間均有一定差異的種群．由于種群中的個(gè)體解遍及整個(gè)解空間,因而能很好地反映搜索空間,從而擴(kuò)大種群的多樣性,遏制超長(zhǎng)個(gè)體的快速繁殖．依據(jù)Hamming距離Hij產(chǎn)生初始種群,使得初始種群的各個(gè)體之間保持一定的距離,各個(gè)體盡可能均勻地分布在整個(gè)解空間上．

兩個(gè)個(gè)體基因組字符串中字符不相同的數(shù)目為兩個(gè)基因組字符串的Hamming距離,距離越大,則兩個(gè)個(gè)體基因組字符串間所包含的不相同模式的數(shù)量就越多,種群中的模式也就越多,兩個(gè)個(gè)體所對(duì)應(yīng)的參數(shù)差別也越大．考慮到形成初始種群時(shí)的方便、快速以及盡可能均勻分布,初始種群的任何兩個(gè)個(gè)體之間要滿足如下條件:

在進(jìn)行選擇操作時(shí),采用競(jìng)爭(zhēng)選擇并采用最優(yōu)保留策略．由于兩個(gè)相近個(gè)體的雜交很難產(chǎn)生相對(duì)較好的個(gè)體,因此要對(duì)被選擇的兩個(gè)個(gè)體進(jìn)行海明距離判斷,以增加雜交后代的多樣性,產(chǎn)生更好的個(gè)體,促進(jìn)雜交后代的改良．被選擇的兩個(gè)個(gè)體的海明距離要滿足如下要求：

Hij≥0.33Nch,

式中Nch為基因組字符串的長(zhǎng)度．個(gè)體基因串滿足要求,則被選擇；否則重新進(jìn)行選擇.這樣就增加了兩個(gè)被選擇個(gè)體雜交后產(chǎn)生優(yōu)良后代的概率．

當(dāng)種群進(jìn)化到一定程度時(shí),個(gè)體之間的相似度隨進(jìn)化代數(shù)逐漸提高,如果僅用Hamming距離來(lái)判斷個(gè)體之間的相似性,則有可能碰到“海明懸崖”問(wèn)題,即Hamming距離較近的個(gè)體其歐式距離有可能比較遠(yuǎn),兩者的變化不一致．如A，B兩個(gè)個(gè)體基因如下：

同為30位長(zhǎng)度的二進(jìn)制基因串,個(gè)體基因串均采用一個(gè)20位長(zhǎng)二進(jìn)制基因串(個(gè)體基因組串左邊)和一個(gè)10位基因串(個(gè)體基因組串右邊)自變量構(gòu)成．兩個(gè)個(gè)體的模式看似存在很大的相似性,僅在第9位和第25位(由右邊計(jì)算位置,第一個(gè)為0)上存在差異,但其表現(xiàn)型在實(shí)際地理位置上卻相距很遠(yuǎn)．為了避開海明懸崖問(wèn)題,文中對(duì)于基因型個(gè)體之間的相似性問(wèn)題,引入基因座權(quán)重

式中i表示第i位基因座.根據(jù)基因座權(quán)重的定義,個(gè)體如果在第i位基因值存在差異,且i越大,則個(gè)體表現(xiàn)型之間的距離越遠(yuǎn)．

在AGA中,因早期出現(xiàn)的優(yōu)良個(gè)體被過(guò)分保護(hù),使得算法將迅速向最優(yōu)解收斂,而在算法中后期,種群中的個(gè)體因過(guò)于集中又會(huì)使交叉操作喪失產(chǎn)生新模式的能力,同時(shí)因大部分個(gè)體適應(yīng)度都接近種群平均適應(yīng)度,變異概率較小又使得算法很快就收斂到局部最優(yōu)解．本文的算法中,以配對(duì)個(gè)體的差異度作為設(shè)置交叉概率的出發(fā)點(diǎn),差異度越大說(shuō)明它們通過(guò)交叉操作相互交換信息的價(jià)值也越大,而且以差異度來(lái)衡量交叉率也可以避免近親之間的交叉繁殖．以單點(diǎn)交叉操作為例,假設(shè)個(gè)體基因長(zhǎng)度是L,而配對(duì)的2個(gè)個(gè)體不同的基因位數(shù)是m位(即它們的海明距離是m)，則任選交叉點(diǎn)而將這m個(gè)基因分在交叉點(diǎn)同側(cè)的可能情形共有N種：

適應(yīng)度函數(shù)

θ=Jf(x)+Wif(x),

式中f(x)為目標(biāo)優(yōu)化函數(shù)，

在代數(shù)迭代過(guò)程中,為了很好地檢查局部個(gè)體基因串演變情況,每隔3代按

%

檢查運(yùn)算一次．當(dāng)所有種群的基因串與最優(yōu)個(gè)體的海明距離與個(gè)體基因串的比值小于5%時(shí),則進(jìn)行種群中的最優(yōu)個(gè)體保留策略,其他個(gè)體隨機(jī)產(chǎn)生.這樣可以避免在AGA運(yùn)行的中后期,因種群中的個(gè)體過(guò)于集中，使交叉操作喪失產(chǎn)生新模式的能力;同時(shí),因大部分個(gè)體適應(yīng)度都接近種群平均適應(yīng)度,變異概率較小又使得算法很快就收斂到局部最優(yōu)解問(wèn)題．

對(duì)于文中優(yōu)化的自適應(yīng)遺傳算法的終止條件,采用按兩代種群中最大適應(yīng)度的相對(duì)誤差來(lái)確定.算法終止評(píng)判標(biāo)準(zhǔn)為

<ε,

式中E(Gk+1,Gk)表示兩次迭代的誤差,maxGk+1和maxGk分別表示第k次和k+1次迭代時(shí)個(gè)體基因串的最大適應(yīng)度值的倒數(shù),ε為算法給定的評(píng)判標(biāo)準(zhǔn)．當(dāng)然，算法如果運(yùn)行500代以上也可終止,采用該終止條件主要是由于遺傳算法具有較大的隨機(jī)性．

2 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文提出算法的有效性,采用幾組多峰值函數(shù)獲取最優(yōu)解實(shí)例,利用Matlab 7.0編程和舍費(fèi)爾德(Sheffield)大學(xué)開發(fā)的遺傳算法工具箱[11],遺傳算法參考文獻(xiàn)[2-3]的附錄源程序,分別對(duì)標(biāo)準(zhǔn)遺傳算法(SGA)、未改進(jìn)的自適應(yīng)遺傳算法和改進(jìn)的自適應(yīng)遺傳算法(IAGA)最優(yōu)解尋找過(guò)程進(jìn)行比較．個(gè)體編碼采用二進(jìn)制編碼．3個(gè)函數(shù)如下：

-100≤x,y≤100;

maxf2=xsin(10πx)+2.0, -1≤x≤2;

-5.12≤x,y≤5.12.

實(shí)驗(yàn)對(duì)每個(gè)函數(shù)運(yùn)行最大次數(shù)為50次,種群采用最大100,編碼采用32位．實(shí)驗(yàn)對(duì)比結(jié)果見表1．

3個(gè)函數(shù)有多個(gè)局部極值點(diǎn),SGA很容易陷入早熟,停滯在局部極值點(diǎn)．f1函數(shù)只有一個(gè)(0,0)為全局最大點(diǎn),最大值周圍有一個(gè)圈脊,取值均為0.990 283,函數(shù)采用SGA很容易陷入此局部極值點(diǎn)而出現(xiàn)早熟現(xiàn)象．函數(shù)f2有多個(gè)極值點(diǎn),SGA也容易出現(xiàn)早熟現(xiàn)象．函數(shù)f3是大海撈針類求解最優(yōu)化,是一個(gè)典型的遺傳算法欺騙問(wèn)題,當(dāng)x=0,y=0時(shí)，函數(shù)有最大值3 600．函數(shù)有4個(gè)局部極值點(diǎn),分別為(-5.12,5.12),(-5.12,-5.12),(5.12,5.12)和(5.12,-5.12),函數(shù)均值為2 748.78．

由表1的實(shí)驗(yàn)結(jié)果和圖1可以看出,與標(biāo)準(zhǔn)遺傳算法和自適應(yīng)遺傳算法相比,改進(jìn)的自適應(yīng)遺傳算法所求得的函數(shù)平均值更接近于函數(shù)的最優(yōu)值,平均進(jìn)化代數(shù)也明顯較少且搜索成功率較高．因此,提出的自適應(yīng)遺傳算法不僅能得到更優(yōu)的函數(shù)最優(yōu)解,而且收斂速度和搜索成功率也得到提高．

表1 函數(shù)優(yōu)化研究結(jié)果

圖1 函數(shù)f1(a),f2(b),f3(c)最優(yōu)解的變化

3 結(jié)束語(yǔ)

為了解決遺傳算法種群出現(xiàn)早熟和容易陷入局部最優(yōu)的問(wèn)題,本文在AGA和基因海明距離計(jì)算的基礎(chǔ)上，提出了對(duì)自適應(yīng)遺傳算法的改進(jìn)策略,并用實(shí)例驗(yàn)證了本文提出的算法在一些性能上要優(yōu)于GA和AGA,較好地避免了GA的早熟出現(xiàn)，也提高了AGA的效率.仿真實(shí)驗(yàn)結(jié)果顯示，改進(jìn)的遺傳算法能較好維持種群的多樣性,并能有效地提高全局搜索能力和局部快速搜索能力．

參考文獻(xiàn):

[1] Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithm[J].IEEE Trans on Systems,Man & Cybernetics,1994,24(2):656.

[2] 王小平,曹立明.遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2003.

[3] 韓瑞鋒.遺傳算法原理與應(yīng)用實(shí)例[M].北京:兵器工業(yè)出版社,2009.

[4] 林明玉,黎明,周琳霞.基于可進(jìn)化性的自適應(yīng)遺傳算法[J].計(jì)算機(jī)工程,2010,36(20):1735.

[5] 沈斌,周瑩君,王家海.基于自適應(yīng)遺傳算法的流水車間作業(yè)調(diào)度[J].計(jì)算機(jī)工程,2010,36(14):201.

[6] Hwang S F,He R S.Improving real-parameter genetic algorithm with simulated annealing for engineering problem[J].Advances Engineering Software,2006,37(6):406.

[7] Zhang J,Chung H S H,Lo W L.Clustering—based adaptive crossover and mutation probabilities for genetic algorithms[J].IEEE Transactions on Evolutionary Computation,2006,11(1):326.

[8] Dilettoso E,Salerno N.A self-adaptive nicking genetic algorithm for multimodal optimization of electromagnetic devices[J].IEEE Transactions on Magnetics,2006,42(2):1203.

[9] Wang Hongjian,Zhao Jie,Bian Xinqian,et al.An improved path planner based on adaptive genetic algorithm for autonomous underwater vehicle[C]//Proceedings of the IEEE International Conference on Mechatronics and Automation,2005，2:857.

[10] 黃永清,梁昌勇,張祥德,等.一種小種群自適應(yīng)遺傳算法[J].系統(tǒng)工程理論與實(shí)踐,2005,25(11):92.

[11] 雷英杰,張善文.MATLAB遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2005.