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

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

(重慶三峽學(xué)院 信號(hào)與信息處理重點(diǎn)實(shí)驗(yàn)室,重慶 404000)

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

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

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

1 問題提出

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

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

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

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

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

2.1 確定種群密度

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

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

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

群體范圍:

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

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

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

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

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

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

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

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

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

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

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

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

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

3 DWAGA算法性能分析

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

3.1.1 一元函數(shù)

函數(shù)表達(dá)式為:

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

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

3.1.2 Schaffer函數(shù)

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

圖5 Schaffer函數(shù)圖像

3.1.3 De Jone’s函數(shù)

函數(shù)表達(dá)式為:

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

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

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

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

表1 測(cè)試條件

表2 F1收斂性能

表3 F2收斂性能

表4 F3收斂性能

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

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

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

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

4 結(jié)論

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

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 段玉倩,賀家李.遺傳算法及其改進(jìn).電力系統(tǒng)及其自動(dòng)化學(xué)報(bào),1998,10(1):39–52.

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

5 劉冀成,胡雅毅.帶基因修復(fù)策略的自適應(yīng)遺傳算法.計(jì)算機(jī)應(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 曲志堅(jiān),張先偉,曹雁鋒,等.基于自適應(yīng)機(jī)制的遺傳算法研究.計(jì)算機(jī)應(yīng)用研究,2015,32(11):3222–3225,3229.[doi:10.3969/j.issn.1001-3695.2015.11.004]