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

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

遺傳算法(Genetic Algorithm,GA)是由美國(guó)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í)無(wú)法求出最優(yōu)解,所以國(guó)內(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)遺傳算法.

雖然近年來(lái)有大量的改進(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)選擇策略確定后影響遺傳算法收斂性的主要因素是由遺傳算子來(lái)決定的.Srinvas首先提出了自適應(yīng)遺傳算法[2],其思想是當(dāng)種群個(gè)體適應(yīng)度值低于種群平均適應(yīng)度值時(shí),說(shuō)明個(gè)體性能較差,增大交叉概率Pc和變異概率Pm,使得該個(gè)體被破壞或者淘汰;相反,當(dāng)種群個(gè)體適應(yīng)度值高于種群平均適應(yīng)度值時(shí),說(shuō)明種群個(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í),仍可以以最小的交叉概率來(lái)進(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ù)用來(lái)考查算法在存在多個(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ù)用來(lái)考查算法在存在多個(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]