鞏 固， 郝國生， 王文虎

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

Hij≥0.33Nch,

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

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

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

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

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

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

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

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

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

%

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

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

<ε,

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

2 實驗結(jié)果與分析

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

-100≤x,y≤100;

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

-5.12≤x,y≤5.12.

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

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

由表1的實驗結(jié)果和圖1可以看出,與標(biāo)準(zhǔn)遺傳算法和自適應(yīng)遺傳算法相比,改進的自適應(yīng)遺傳算法所求得的函數(shù)平均值更接近于函數(shù)的最優(yōu)值,平均進化代數(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é)束語

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

參考文獻:

[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)用與軟件實現(xiàn)[M].西安:西安交通大學(xué)出版社,2003.

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

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

[5] 沈斌,周瑩君,王家海.基于自適應(yīng)遺傳算法的流水車間作業(yè)調(diào)度[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)工程理論與實踐,2005,25(11):92.

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