帶密度加權(quán)的自適應(yīng)遺傳算法①

聶文亮,蔡 黎,邱 剛,李春莉

(重慶三峽學(xué)院 信號與信息處理重點實驗室,重慶 404000)

遺傳算法(Genetic Algorithm,GA)是由美國Michigan大學(xué)的Hoiiand教授于1975年首先提出,是一種借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法[1].由于遺傳算法通用性強,被廣泛應(yīng)用于非線性、多目標、多變量、復(fù)雜的自適應(yīng)系統(tǒng)中.

但是傳統(tǒng)的遺傳算法收斂速度慢、容易陷入局部最優(yōu),尤其在計算復(fù)雜問題時無法求出最優(yōu)解,所以國內(nèi)外學(xué)者對其進行了改進.目前,對遺傳算法的改進主要體現(xiàn)在三個方面:1)對遺傳算子進行動態(tài)調(diào)整,最早由Srinvas等人提出[2,3];2)對遺傳算法的個體進行優(yōu)化,比如在文獻[4]中提出個體可進化的適應(yīng)度函數(shù)評價機制;3)采用1)和2)結(jié)合的方法改進遺傳算法,比如文獻[5]提出的帶基因修復(fù)的自適應(yīng)遺傳算法.

雖然近年來有大量的改進遺傳算法被提出,但是課題組在研究遺傳算法時發(fā)現(xiàn),如果能夠根據(jù)種群個體的分布情況動態(tài)調(diào)整遺傳算子,可以增強種群個體的多樣性,同時有利于加快算法收斂.因此,本文提出了一種帶密度加權(quán)的自適應(yīng)遺傳算法—DWAGA(Adaptive Genetic Algorithm with Density Weighted),該算法可以根據(jù)種群分布情況動態(tài)調(diào)整交叉和變異概率,使得算法具有跳出局部極大值加快收斂速度的能力,同時本文還對該算法的改進過程、方法進行了詳細的分析,最后通過求解三個函數(shù)的最優(yōu)解驗證了算法的有效性.

1 問題提出

采用傳統(tǒng)自適應(yīng)遺傳算法對如公式(1)所示函數(shù)進行最優(yōu)求解,并對其個體分布情況進行分析.

從圖1可以看出,遺傳算法在第5代到第18代,以及第25代–第95代之間停留了較長的時間,雖然也進行交叉、變異等遺傳操作,但是由于種群過于集中于某一區(qū)域,導(dǎo)致個體已近似相當(dāng),即使進行了遺傳操作,但是變化不大.尤其在算法迭代后期,特別容易陷入局部最優(yōu)解.

因此,本文提出一種可以根據(jù)種群分布特點動態(tài)調(diào)整遺傳算子的自適應(yīng)遺傳算法,該算法旨在破壞種群的局部穩(wěn)定性,保持種群個體的多樣性,同時加快算法的收斂速度.

圖1 種群個體適應(yīng)度分布圖

2 改進的遺傳算法——DWAGA

2.1 確定種群密度

種群初始化后,對其個體按其適應(yīng)度值由小到大的順序進行排序,如圖2所示.

圖2 種群適應(yīng)度值分布圖

圖2中,M表示種群規(guī)模,fmax表示當(dāng)代種群中個體的最大適應(yīng)度值,fmin表示當(dāng)代種群中個體的最大適應(yīng)度值,favg表示當(dāng)代種群個體的平均適應(yīng)度值.為了便于進行下一步的描述,做如下定義.

群體范圍:

某個體到適應(yīng)度平均值處的距離(f表示要變異個體的適應(yīng)度值):

2.2 自適應(yīng)參數(shù)調(diào)整

從模式理論[1]可知,當(dāng)選擇策略確定后影響遺傳算法收斂性的主要因素是由遺傳算子來決定的.Srinvas首先提出了自適應(yīng)遺傳算法[2],其思想是當(dāng)種群個體適應(yīng)度值低于種群平均適應(yīng)度值時,說明個體性能較差,增大交叉概率Pc和變異概率Pm,使得該個體被破壞或者淘汰;相反,當(dāng)種群個體適應(yīng)度值高于種群平均適應(yīng)度值時,說明種群個體優(yōu)良,相應(yīng)地減小Pc和Pm,使該個體得以保存到下一代中.其中計算交叉概率和變異概率的公式如下:

式中,fmax表示當(dāng)代種群中個體的最大適應(yīng)度值,fmin表示當(dāng)代種群中個體的最大適應(yīng)度值,favg表示當(dāng)代種群個體的平均適應(yīng)度值,f’表示要變異個體的適應(yīng)度值.

從公式(2)和公式(3)中看出,當(dāng)種群適應(yīng)度值等于最大適應(yīng)度值時,交叉概率和變異概率的值為零,這樣就過分地保留了種群在前期進化階段適應(yīng)度值最大的個體,使得種群進化過程緩慢,極易陷入局部最優(yōu)解.基于這個原因,段玉倩等人對上述自適應(yīng)遺傳算法進行了改進[3].

如圖3所示,在改進的自適應(yīng)遺傳算法中,設(shè)置種群交叉概率的最大值和最小值,且最小值不等于零.在種群個體為最大適應(yīng)度值時,仍可以以最小的交叉概率來進行操作,這樣就使得種群個體不會處于一種停滯不變的狀態(tài).計算交叉概率的公式如下式(4),變異概率計算公式類似,省略.

圖3 自適應(yīng)遺傳算法交叉概率取值圖

公式(3)雖然改善了公式(1)和(2)中存在的不足,但仍缺乏對種群整體分布的分析,尤其是若種群個體過分集中于某一區(qū)域,則容易陷入局部最優(yōu)解.因此,本文在上述自適應(yīng)遺傳算法的基礎(chǔ)上[3-5],提出帶密度加權(quán)的自適應(yīng)遺傳算法.依據(jù)種群中心區(qū)域密度ρ對Pc作出修正,如公式(5).

式(4)中A為常數(shù),其值大小反映了對種群中心區(qū)域密度的重視程度.α為極小的常數(shù),防止分母為零導(dǎo)致的錯誤,通常取值為極小的數(shù).0＜Pcmin＜Pcmax＜1,本文中Pcmax=0.9,Pcmin=0.4.ρ為種群中心區(qū)域密度.其他符號的意義同前不變.

當(dāng)h小于等于δ時,種群個體適應(yīng)度分布不均勻,在個體適應(yīng)度平均值處(中心區(qū)域)集中,容易陷入局部最優(yōu)解.因此,采用增大中心區(qū)域個體的交叉概率,破壞該區(qū)域個體的穩(wěn)定性,使得該個體被淘汰或者在交叉過程中產(chǎn)生新的個體,以此實現(xiàn)跳出局部極值的能力.

當(dāng)h大于δ時,種群個體適應(yīng)度分布均勻,對于適應(yīng)度低于平均適應(yīng)度的個體,取較高的Pc,使該個體被淘汰掉;而高于群體平均適應(yīng)度的個體,取較低的Pc使個體得以保護進入下一代.

同理可以得到自適應(yīng)遺傳算法變異概率的計算公式,如公式(6).

式中,0＜Pmmin＜Pmmax＜1,本文中Pmmax=0.1,Pmmin=0.01.其他符號的意義同前不變.

3 DWAGA算法性能分析

3.1 評估函數(shù)[6,7]

3.1.1 一元函數(shù)

函數(shù)表達式為:

該函數(shù)為一元多峰值函數(shù),其函數(shù)值隨自變量變化如圖4所示.在其定義域內(nèi)有全局最大值3.85,在整個定義域內(nèi),該函數(shù)還存在多個極大值,呈臺階式分布.該一元函數(shù)用來考查算法在存在多個極值時的搜尋能力.

圖4 一元函數(shù)圖像

3.1.2 Schaffer函數(shù)

該函數(shù)在其定義域內(nèi)有最大值F2(0,0)=1,但是在極大點附近有由全局次優(yōu)點F2(x1,x2)=0.99形成的圈脊,如果算法局部搜索能力較弱,則極易收斂于次優(yōu)點.其函數(shù)值隨自變量變化如圖5所示.此函數(shù)將用以考查算法在全局最優(yōu)點被局部最優(yōu)解包圍時從局部最優(yōu)跳離的能力.

圖5 Schaffer函數(shù)圖像

3.1.3 De Jone’s函數(shù)

函數(shù)表達式為:

圖6 De Jone’s函數(shù)圖像

該函數(shù)為二維區(qū)域的多峰值函數(shù),在其定義域內(nèi)共有25個局部極大值,呈跳躍狀分布在獨立的區(qū)域內(nèi),極大值點自變量之間變化幅值大,極易使算法陷入局部最大值點而停止進化,其函數(shù)值隨自變量變化如下圖6所示.其中,該函數(shù)的全局最大值點為F3(–32,–32)=1.該函數(shù)用來考查算法在存在多個極值的二維函數(shù)中的尋優(yōu)能力.

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

為了驗證算法的有效性,文中采用表1中的測試條件,對上述3個函數(shù)進行500次尋優(yōu)計算,在收斂次數(shù)、平均收斂代數(shù)、以及最佳適應(yīng)度值三方面對自適應(yīng)遺傳算法(Adaptive Genetic Algorithm,AGA)、改進的自適應(yīng)遺傳算法(Improve Adaptive Genetic Algorithm,IAGA),以及本文提出的帶密度加權(quán)的自適應(yīng)遺傳算法(Adaptive Genetic Algorithm with Density Weighted,DWAGA)進行了統(tǒng)計和比較,詳見表2,表3,表4.

表1 測試條件

表2 F1收斂性能

表3 F2收斂性能

表4 F3收斂性能

從表2、表3、表4的實驗結(jié)果可以看出,在3個測試函數(shù)下,文中提出的DWAGA算法收斂總次數(shù)最多.同時,改進的自適應(yīng)遺傳算法收斂代數(shù)明顯快于標準的自適應(yīng)遺傳算法,其中本文提出的DWAGA收斂速度最快.

同時,為了分析AGA、IAGA、DWAGA這3種算法在整個迭代周期上的性能,文中分別列出了在不同測試函數(shù)下3種算法的適應(yīng)度平均值分布圖,如圖7所示.

圖7 AGA、IAGA、DWAGA算法在三種測試函數(shù)下每代適應(yīng)度平均值曲線圖

從圖7中可以看出,AGA算法在迭代中期長期保持不變,IAGA和DWAGA算法都得到了改善,其中DWAGA算法改善最為明顯,收斂速度最快.同時,文中三個測試函數(shù)的適應(yīng)度函數(shù)就是函數(shù)的表達式,因此都是求解相應(yīng)函數(shù)的全局最大值點,通過圖7的比較,AGA和IAGA算法都多次停留在局部極值處,但是本文提出的DWAGA算法能夠快速跳出局部極值,向最大值點處收斂,有效地提高了算法的收斂速度.

4 結(jié)論

通過對傳統(tǒng)的自適應(yīng)遺傳算法進行了深入研究,針對其收斂速度慢、難以跳出局部極大值的情況,本文提出DWAGA算法進行改善,通過對三個函數(shù)求解最優(yōu)解的實驗,表明該算法在收斂速度、平均收斂次數(shù),以及全局最大值的搜尋能力上都明顯優(yōu)于傳統(tǒng)自適應(yīng)遺傳算法,從而驗證該算法的有效性和魯棒性.

1 Holland JH.Adaptation in natural and artificial system:An introductory analysis with applications to biology,control and artificial intelligence.Cambridge,MA:MIT Press,1992.

2 Srinivas M,Patnaik LM.Adaptive probabilities of crossover and mutation in genetic algorithms.IEEE Transactions on Systems,Man,and Cybernetics,1994,24(4):656–667.[doi:10.1109/21.286385]

3 段玉倩,賀家李.遺傳算法及其改進.電力系統(tǒng)及其自動化學(xué)報,1998,10(1):39–52.

4 林明玉,黎明,周琳霞.基于可進化性的自適應(yīng)遺傳算法.計算機工程,2010,36(20):173–175.[doi:10.3969/j.issn.1000-3428.2010.20.061]

5 劉冀成,胡雅毅.帶基因修復(fù)策略的自適應(yīng)遺傳算法.計算機應(yīng)用,2006,26(6):1401–1402,1405.

6 Wang SH,Lu ZY,Wei L,et al.Fitness-scaling adaptive genetic algorithm with local search for solving the multiple depot vehicle routing problem.Simulation,2016,92(7):601–616.[doi:10.1177/0037549715603481]

7 Deng Y,Liu Y,Zhou DY.An improved genetic algorithm with initial population strategy for symmetric TSP.Mathematical Problems in Engineering,2015,2015:212749.

8 曲志堅,張先偉,曹雁鋒,等.基于自適應(yīng)機制的遺傳算法研究.計算機應(yīng)用研究,2015,32(11):3222–3225,3229.[doi:10.3969/j.issn.1001-3695.2015.11.004]