一種基于加權(quán)海明距離的自適應(yīng)遺傳算法

徐承愛，林 偉 ，肖 紅

(廣東工業(yè)大學(xué)計算機(jī)學(xué)院，廣州510006)

遺傳算法(Genetic Algorithms，GA)是一種模仿自然界生物進(jìn)化機(jī)制的隨機(jī)全局搜索和優(yōu)化方法.它借鑒了達(dá)爾文的進(jìn)化論和孟德爾的遺傳學(xué)說，能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程以求得最優(yōu)解.廣泛應(yīng)用于組合優(yōu)化、模式識別、自動控制、圖像處理和人工生命等眾多領(lǐng)域［1］.

標(biāo)準(zhǔn)遺傳算法通過選擇、交叉和變異等3 種基本操作算子實現(xiàn)種群的進(jìn)化，搜索問題最優(yōu)解，但其存在著早熟收斂和搜索效率低等問題. Srinivas 和Patnaik［2］提出基于個體適應(yīng)度的遺傳算法，使得交叉率和變異率隨著種群的進(jìn)化而自適應(yīng)改變;任子武和傘冶［3］在Srinivas 的基礎(chǔ)上提出一種改進(jìn)的自適應(yīng)遺傳算法，該算法使群體中最大適應(yīng)度的個體交叉率和變異率不為零，有效跳出局部最優(yōu)解;王杰等［4］提出一種雙變異率的改進(jìn)遺傳算法，并使用海明距離控制交叉操作，提高了群體的多樣性;田豐等［5］提出一種基于個體相似度的雙種群遺傳算法，加入內(nèi)部競爭和種群交流策略，有效抑制早熟現(xiàn)象.研究發(fā)現(xiàn)，上述改進(jìn)算法的全局搜索能力和效率有了一定的提高，但早熟收斂和效率低等問題仍然嚴(yán)峻.針對該問題，本文從交叉率和變異率自適應(yīng)調(diào)整入手，提出一種基于加權(quán)海明距離的自適應(yīng)遺傳算法(HAGA)，運(yùn)用6個經(jīng)典測試函數(shù)對算法進(jìn)行了仿真實驗.結(jié)果表明，該算法可以顯著提高遺傳優(yōu)化的全局搜索能力，加快遺傳算法的收斂速度.

1 傳統(tǒng)自適應(yīng)遺傳算法

遺傳算法參數(shù)中交叉率Pc和變異率Pm的選擇是影響算法性能的關(guān)鍵.交叉率Pc越大，新個體產(chǎn)生的速度就越快，然而Pc過大時遺傳模式被破壞的可能性增加;Pc過小，使得搜索過程緩慢.對于變異概率Pm，Pm過小，不容易產(chǎn)生新的個體模式;Pm取值過大，GA 就變成了純粹的隨機(jī)搜索算法［1］.針對不同的優(yōu)化問題，需通過反復(fù)實驗來確定Pc和Pm，很難找到適應(yīng)于每個問題的最佳值. 自適應(yīng)遺傳算法(AGA)［2］中Pc和Pm能夠隨適應(yīng)度函數(shù)大小自適應(yīng)調(diào)整，在保持群體多樣性的同時保證遺傳算法的收斂性.該算法中Pc和Pm調(diào)整公式如下:

其中，fmax為群體中最大的適應(yīng)度值，favg為每代群體的平均適應(yīng)度值，f'為要交叉的2個個體中較大的適應(yīng)度值，f 為要變異個體的適應(yīng)度值. k1，k2，k3，k4為(0，1)區(qū)間常數(shù). 這種調(diào)整方法對于群體處于進(jìn)化后期比較合適，但對于進(jìn)化初期不利.由于在進(jìn)化初期，群體中的較優(yōu)個體幾乎處于一種不發(fā)生變化的狀態(tài)，而此時的優(yōu)良個體不一定是優(yōu)化的全局最優(yōu)解，容易使算法陷入早熟收斂.

2 基于加權(quán)海明距離的自適應(yīng)遺傳算法

2.1 加權(quán)海明距離

度量個體相似度的傳統(tǒng)方法主要有海明距離和加權(quán)海明距離.海明距離指2 條染色體間相同基因座上不同基因的數(shù)量;而加權(quán)海明距離指按照基因座位置和作用不同在海明距離基礎(chǔ)上添加合適的權(quán)值，然后對不同基因的權(quán)值進(jìn)行求和計算［6］. 采用海明距離度量父個體的相似度［7－8］，雖然對群體的多樣性判斷有一定貢獻(xiàn)，但不能充分說明個體間的差異程度.在編碼中，基因座所在的地位和作用往往是不同的，即使個體間的海明距離相同，他們的親屬關(guān)系仍有差異.因而本文考慮到各染色體基因座重要性的不同，使用加權(quán)海明距離判別個體間的相似度.加權(quán)海明距離計算公式:

其中，Hij為個體i 與個體j 的加權(quán)海明距離，Havg每代種群中個體間的平均加權(quán)海明距離，aim與ajm為染色體上的基因，w(xm)為染色體各個基因座的加權(quán)值，本文使用指數(shù)函數(shù)計算其加權(quán)值.為了說明海明距離與加權(quán)海明距離的量度差異，舉一實例.如個體A:，個體B:和個體C:

同為30 位長度的二進(jìn)制基因串，個體A 與個體B、個體A 與個體C 間的海明距離均為3，加權(quán)海明距離HAB=24+217+228=2.69 ×108、HAC=24+217+224=1.69 ×107.通過演算可知，雖然個體間海明距離相同，但加權(quán)海明距離存在較大差異，即其表現(xiàn)型在實際地理位置上卻相距很遠(yuǎn). 因此相對于海明距離，加權(quán)海明距離可以較好地度量個體間的相似度.在進(jìn)行交叉率調(diào)整時，增大低相似度個體間的交叉率，減小高相似度個體間的交叉率，進(jìn)而提高種群的多樣性，避免局部收斂.

2.2 選擇算子

在遺傳算法中，傳統(tǒng)的選擇策略包括輪盤賭選擇策略和錦標(biāo)賽選擇策略. 輪盤賭選擇法模擬輪盤賭過程，維護(hù)適應(yīng)度較大者入選概率較高的原則;而錦標(biāo)賽選擇法學(xué)習(xí)錦標(biāo)賽競爭的方法，通過隨機(jī)選取候選者，并在候選者中擇優(yōu)錄取的方式實現(xiàn)選擇操作.張琛和詹志輝［9］對輪盤賭選擇策略和錦標(biāo)賽選擇策略進(jìn)行了深入的研究，發(fā)現(xiàn)錦標(biāo)賽選擇策略在求解精度和求解速度上要優(yōu)于輪盤賭選擇策略.本文算法使用錦標(biāo)賽選擇策略挑選優(yōu)秀個體.

具體操作步驟為:(1)設(shè)定每次選擇的個體數(shù)量N;(2)從種群中隨機(jī)選擇N個個體構(gòu)成一組;(3)根據(jù)每個個體的適應(yīng)度值，選擇其中適應(yīng)度值最好的個體進(jìn)入子代種群;(4)重復(fù)步驟(2)、(3)，直到新一代種群生成為止.

2.3 交叉算子和變異算子

經(jīng)研究發(fā)現(xiàn)，針對交叉率和變異率的自適應(yīng)調(diào)整，研究者主要集中在研究適應(yīng)度對其的影響［2－4，10－12］，缺乏考慮種群的多樣性. 本文在文獻(xiàn)［3］、文獻(xiàn)［13］的基礎(chǔ)上添加相似度判斷以及相似度調(diào)整因子，綜合考慮加權(quán)海明距離指標(biāo)和適應(yīng)度指標(biāo)，提出自適應(yīng)調(diào)整交叉率和變異率的計算公式:

其中，Hbest為要變異的個體與最優(yōu)個體間的加權(quán)海明距離，Pc1、Pc2分別是最大和最小交叉概率，Pm1、Pm2分別是最大和最小變異概率，α 為最大加權(quán)海明距離，K 為調(diào)節(jié)交叉率、變異率的權(quán)值.

對于交叉率Pc，計算公式中引入相似度調(diào)節(jié)因子.綜合個體間的相似度以及適應(yīng)度值，自適應(yīng)調(diào)整Pc.調(diào)整過程為:(1)當(dāng)個體適應(yīng)度f'大于等于平均適應(yīng)度favg，并且加權(quán)海明距離Hij小于平均加權(quán)海明距離Havg時，表明配對個體性能好且相似度高，根據(jù)計算公式，給予配對個體較小的交叉率;(2)當(dāng)f'小于favg，并且Hij大于等于Havg時，表明配對個體性能差并且相似度低，根據(jù)計算公式，給予配對個體較大的交叉率;(3)當(dāng)Hij、f'處于其他范圍時，表明配對個體性能和相似度中等，根據(jù)計算公式，給予配對個體中等大小的交叉率. 對于變異率Pm，計算公式中引入相似度調(diào)節(jié)因子，綜合個體間的相似度以及適應(yīng)度值，自適應(yīng)調(diào)整Pm，其調(diào)整過程與交叉率Pc相似.通過上述調(diào)節(jié)公式，可以減少高相似度、高適應(yīng)度個體進(jìn)行交叉、變異的概率，增加低相似度、低適應(yīng)度個體交叉、變異的可能性，進(jìn)而提高算法的搜索性能.

2.4 精英保留策略

遺傳算法運(yùn)行過程中，雖然隨群體的進(jìn)化過程會產(chǎn)生越來越多的優(yōu)良個體，但由于交叉、變異等遺傳操作的隨機(jī)性，有可能破壞當(dāng)前群體中適應(yīng)度最好的個體，影響遺傳算法的運(yùn)行效率和收斂性. De Jong［14］首次提出一種精英保留策略. 該策略的實施可保證最優(yōu)個體不會被交叉、變異等遺傳運(yùn)算所破壞，提高遺傳算法的全局收斂性能.

精英保留策略的主要步驟是:(1)計算當(dāng)代群體中各個體的適應(yīng)值，找出適應(yīng)值最好的個體;(2)比較當(dāng)代最好個體與上一代最好個體(精英個體)的適應(yīng)值，較大者作為新的精英個體;(3)將上一步中的精英個體存放到子代群體結(jié)構(gòu)的第一位. 經(jīng)過上述操作，保護(hù)了最好的個體模式，使算法朝著最優(yōu)解的方向搜索.

2.5 雙重停機(jī)準(zhǔn)則

在設(shè)計遺傳算法的終止條件時，傳統(tǒng)的方法是采用總的進(jìn)化代數(shù)T 為終止依據(jù)，如果進(jìn)化代數(shù)達(dá)到T，則結(jié)束程序運(yùn)行［1］.但是，若初始群體以及參數(shù)選取非常理想，遺傳算法可以很快搜尋到最優(yōu)解.此時再采用該停機(jī)準(zhǔn)則，便會增加不必要的搜索時間.

因此，在算法執(zhí)行過程中，采用雙重停機(jī)判斷準(zhǔn)則:進(jìn)化代數(shù)達(dá)到總的進(jìn)化代數(shù)T;連續(xù)多次進(jìn)化的優(yōu)化結(jié)果不變，或優(yōu)化結(jié)果達(dá)到某一精度.在遺傳進(jìn)化過程中，滿足上述2個條件中的任何一個，都視為滿足終止條件.這種雙重停機(jī)準(zhǔn)則可以減少不必要的計算時間，提高收斂效率.該算法流程圖見圖1.

圖1 算法流程圖Figure 1 Flow chart of the algorithm

3 仿真測試

運(yùn)用6個經(jīng)典測試函數(shù)［1］在MATLAB 平臺上進(jìn)行仿真實驗，并與標(biāo)準(zhǔn)遺傳算法(GA)和傳統(tǒng)自適應(yīng)遺傳算法(AGA)進(jìn)行了對比測試.

3.1 測試用例

實驗1:函數(shù)f1(圖2A)的理論最大值比3.85略大，收斂值為3.850.

實驗2:函數(shù)f2(圖2B)的理論最小值為－1.031 628，收斂值為－1.031 60.

實驗3:函數(shù)f3(圖2C)的理論最小值為－186.730 9，收斂值為－186.730.

實驗4:函數(shù)f4(圖2D)的全局極小值f(0，0)=0，收斂值為0.007.

實驗5:函數(shù)f5(圖2E)的最大值為3 600，收斂值為3 600.00.

實驗6:函數(shù)f6(圖2F)具有一個全局極小值，收斂值為0.001.

3.2 參數(shù)設(shè)置

算法均采用二進(jìn)制編碼，單點交叉，求解精度δ=1e－6，收斂準(zhǔn)則設(shè)為種群適應(yīng)度與全局最大適應(yīng)度的差，其絕對值小于等于0.001.根據(jù)函數(shù)的復(fù)雜程度設(shè)定最大進(jìn)化代數(shù)f1為100 代，f2、f6為300代，f3、f4、f5為500 代，3 種算法針對6個函數(shù)各自運(yùn)行100 次.記錄收斂次數(shù)、平均收斂代數(shù)、平均收斂值等指標(biāo).精度δ 計算公式為:

圖2 測試函數(shù)Figure 2 Test functions

其中，δ 為編碼精度，L 為編碼長度，xmax、xmin分別為變量最大及最小取值.根據(jù)公式及精度要求計算f1、f2、f3、f4、f5、f6的編碼長度，其值分別為22、28、25、28、24、22.

(1)標(biāo)準(zhǔn)遺傳算法(GA). 采用輪盤賭選擇策略，交叉概率Pc=0.85，變異概率Pm=0.05.

(2)傳統(tǒng)自適應(yīng)遺傳算法(AGA). 采用輪盤賭選擇策略，自適應(yīng)的交叉概率k1=0.65、k2=0.9，自適應(yīng)的變異概率k3=0.01、k4=0.1.

(3)基于加權(quán)海明距離的自適應(yīng)遺傳算法(HAGA).采用錦標(biāo)賽選擇策略，每次選擇的個體數(shù)量N=10. 最大和最小交叉率分別為Pc1=0.9、Pc2=0.4，最大和最小變異率分別為Pm1= 0.2、Pm2=0.001，參數(shù)K=2，權(quán)值ω=(20，21，…，2L－1).

3.3 結(jié)果與分析

系統(tǒng)環(huán)境為:(1)處理器:Intel(R)Core(TM)i5－3210M CPU;(2)操作系統(tǒng):Windows 7 Ultimate，32－bit;(3)仿真平臺:Matlab，R2012a(7.14.0.739)，32－bit.

性能指標(biāo)為:(1)種群規(guī)模:種群中個體的數(shù)量;(2)收斂次數(shù):運(yùn)行100 次算法，全局收斂的次數(shù);(3)平均收斂代數(shù):運(yùn)行100 次算法，種群收斂代數(shù)的算術(shù)平均值;(4)平均收斂值:運(yùn)行100 次算法，收斂結(jié)果的算術(shù)平均值.其中，收斂次數(shù)、平均收斂值指標(biāo)用于評價算法的全局搜索性能，平均收斂代數(shù)用于評價算法的搜索效率.

仿真測試見表1 ～表3，比較其中實驗數(shù)據(jù)，針對各項指標(biāo)，得出以下結(jié)論:

(1)收斂次數(shù):針對簡單的測試函數(shù)f1、f2、f6，3種算法收斂次數(shù)均較多，全局收斂性能較好，本文提出的HAGA 算法收斂次數(shù)多于GA 和AGA，說明HAGA 的全局收斂性能要好于GA 和AGA;針對較復(fù)雜的測試函數(shù)f3、f5，HAGA 具有明顯的優(yōu)勢，收斂次數(shù)均在85 次以上，AGA 分別為82 次、62 次，GA 分別為71 次、58 次;針對函數(shù)f4，HAGA 的收斂次數(shù)不夠理想，僅為74 次，但仍然高于AGA 的66次和GA 的60 次.

(2)平均收斂代數(shù):對于測試函數(shù)f2，由于函數(shù)表達(dá)式極其復(fù)雜并且變量范圍較大，導(dǎo)致收斂代數(shù)較多，HAGA、AGA 和GA 算法平均收斂代數(shù)分別為97、119 和136.對于其他測試函數(shù)，3 種算法在平均收斂代數(shù)上比較接近，但HAGA 算法平均收斂代數(shù)仍然要少于AGA 和GA，說明HAGA 在使用改進(jìn)的交叉算子、變異算子、精英保留策略和雙重停機(jī)準(zhǔn)則后，在搜索效率上有一定提升.

(3)平均收斂值:3 種算法的平均收斂值均與測試函數(shù)理論收斂值接近，進(jìn)一步說明本文提出的HAGA 算法的全局搜索性能和穩(wěn)定性能較好.

表1 標(biāo)準(zhǔn)遺傳算法收斂性能Table 1 The convergence performance of standard genetic algorithm

表2 傳統(tǒng)自適應(yīng)遺傳算法收斂性能Table 2 The convergence performance of traditional adaptive genetic algorithm

表3 基于加權(quán)海明距離的自適應(yīng)遺傳算法收斂性能Table 3 The convergence performance of adaptive genetic algorithm based on weighted hamming distance

6 種測試函數(shù)在GA、AGA、HAGA 等3 種算法下進(jìn)行搜索尋優(yōu)性能比較(圖3)，發(fā)現(xiàn):(1)對于函數(shù)f1、f3，HAGA 表現(xiàn)出了良好的搜索性能，在全局搜索能力和搜索效率上均要優(yōu)于GA 和AGA;(2)對于函數(shù)f5和f6，在進(jìn)化初期，GA 和AGA 在適應(yīng)值的變化率上優(yōu)于HAGA，但是隨著進(jìn)化代數(shù)的增長，種群相似度降低，GA 與AGA個體的質(zhì)量改善非常緩慢. 而HAGA 使用適應(yīng)度和相似度雙重調(diào)節(jié)機(jī)制，自適應(yīng)調(diào)整交叉率、變異率，可迅速改善個體適應(yīng)度值;(3)對于函數(shù)f2和f4，在進(jìn)化初期，HAGA與AGA 進(jìn)化速率相似，均要快于GA. 在進(jìn)化后期，AGA 與GA 陷入局部收斂，經(jīng)過多次進(jìn)化才跳出局部值，而HAGA 以較快的速率收斂到最優(yōu)值.

圖3 函數(shù)最大適應(yīng)值隨進(jìn)化代數(shù)的變化曲線Figure 3 The curves of the largest fitness value change during the evolution

4 結(jié)論

本文提出的基于加權(quán)海明距離的自適應(yīng)遺傳算法(HAGA)，綜合考慮個體間加權(quán)海明距離和適應(yīng)度值，自適應(yīng)調(diào)整交叉率和變異率;采用精英保留法，保證最優(yōu)個體不被破壞;使用雙重停機(jī)準(zhǔn)則，提高遺傳搜索效率.仿真測試表明，HAGA 算法在全局搜索能力和搜索效率上，明顯優(yōu)于GA 和AGA 算法.但是，針對某些特別復(fù)雜的函數(shù)，HAGA 仍然存在著早熟收斂的挑戰(zhàn). 下一步將嘗試引入具有較強(qiáng)局部搜索能力的位爬山算法，改善HAGA 進(jìn)化后期的搜索效率，并嘗試運(yùn)用HAGA 算法解決多目標(biāo)優(yōu)化問題.

［1］王小平，曹立明. 遺傳算法－理論、應(yīng)用與軟件實現(xiàn)［M］. 西安:西安交通大學(xué)出版社，2002.

［2］Srinivas M，Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms［J］.IEEE Transactions on Systems，Man and Cybernetics，1994，24(4):656－667.

［3］任子武，傘冶. 自適應(yīng)遺傳算法的改進(jìn)及在系統(tǒng)辨識中應(yīng)用研究［J］. 系統(tǒng)仿真學(xué)報，2006，18(1):41－43.Ren Z W，San Y. Improved adaptive genetic algorithm and its application research in parameter identification［J］.Journal of System Simulation，2006，18(1):41－43.

［4］王杰，馬雁，王非. 一種雙變異率的改進(jìn)遺傳算法及其仿真研究［J］. 計算機(jī)工程與應(yīng)用，2008，44(3):57－59.Wang J，Ma Y，Wang F. Study of improved genetic algorithm based on dual mutation and its simulation［J］.Computer Engineering and Applications，2008，44(3):57－59.

［5］田豐，姚愛民，孫小平，等. 基于個體相似度的雙種群遺傳算法［J］. 計算機(jī)工程與應(yīng)用，2011，32(5):1789－1791.Tian F，Yao A M，Sun X P，et al. Dual population genetic algorithm based onindividual similarity［J］. Computer Engineering and Applications，2011，32(5):1789－1791.

［6］李軍華，黎明，袁麗華. 基于個體相似度交叉率自適應(yīng)的遺傳算法［J］. 系統(tǒng)工程，2006，24(9):108－111.Li J H，Li M，Yuan L H. The genetic algorithms with adaptive crossover rate based on individuals'similarity［J］.Systems Engineering，2006，24(9):108－111.

［7］田小梅，鄭金華，李合軍. 基于父個體相似度的自適應(yīng)遺傳算法［J］. 計算機(jī)工程與應(yīng)用，2005(18):61－63.Tian X M，Zheng J H，Li H J.Adaptive genetic algorithm based on parents' similarity［J］. Computer Engineering and Applications，2005(18):61－63.

［8］鞏固，郝國生，王文虎. 基于海明距離改進(jìn)的自適應(yīng)遺傳算法［J］. 江蘇師范大學(xué)學(xué)報:自然科學(xué)版，2014，32(4):51－54.Gong G，Hao G S，Wang W H. Improved adaptive genetic algorithm based on Hamming distance［J］. Journal of Jiangsu Normal University:Natural Science Edition，2014，32(4):51－54.

［9］張琛，詹志輝. 遺傳算法選擇策略比較［J］. 計算機(jī)工程與設(shè)計，2009，30(23):5471－5474.Zhang C，Zhan Z H. Comparisons of selection strategy in genetic algorithm［J］.Computer Engineering and Design，2009，30(23):5471－5474.

［10］金晶，蘇勇. 一種改進(jìn)的自適應(yīng)遺傳算法［J］. 計算機(jī)工程與應(yīng)用，2005，41(18):64－69.Jin J，Su Y. An improved adaptive genetic algorithm［J］.Computer Engineering and Applications，2005，41(18):64－69.

［11］梁興建，詹志輝，譚偉，等. 基于最優(yōu)保留策略的改進(jìn)遺傳算法［J］. 計算機(jī)工程與設(shè)計，2014，35(11):3985－3990.Liang X J，Zhan Z H，Tan W，et al.Improved genetic algorithm based on elitist reserved strategy［J］. Computer Engineering and Design，2014，35(11):3985－3990.

［12］李紹新，張延嬌. 改進(jìn)的遺傳算法在蛋白質(zhì)結(jié)構(gòu)預(yù)測中的應(yīng)用［J］. 華南師范大學(xué)學(xué)報:自然科學(xué)版，2009，25(1):56－60.Li S X，Zhang Y J. The application of improved genetic algorithms for predicting protein structures［J］. Journal of South China Normal University:Natural Science Edition，2009，25(1):56－60.

［13］Ho S L，Xu G Z，F(xiàn)u W N.Optimization of array magnetic coil design for functional magneticstimulation based on improved genetic algorithm［J］. IEEE Transactions on Magnetics，2009，45(10):4849－4852

［14］De Jong K A. An analysis of the behavior of a class of generic adaptive systems［D］. Michigan:University of Michigan，1975.