自適應(yīng)遺傳算法的改進(jìn)與應(yīng)用*

張國(guó)強(qiáng) 彭曉明

(空軍雷達(dá)學(xué)院研究生管理大隊(duì)1) 武漢 430019)(空軍雷達(dá)學(xué)院預(yù)警監(jiān)視情報(bào)系2) 武漢 430019)

1 引言

自適應(yīng)遺傳算法是具有比例選擇,自適應(yīng)交叉和變異操作的遺傳算法的簡(jiǎn)稱。針對(duì)不同的優(yōu)化問(wèn)題,簡(jiǎn)單遺傳算法和一些改進(jìn)的遺傳算法的交叉概率和變異概率需要反復(fù)用實(shí)驗(yàn)來(lái)確定,而且不容易找到適用于所有問(wèn)題的最佳值。而自適應(yīng)遺傳算法的交叉概率和變異概率是隨適應(yīng)度自動(dòng)改變的,此方法能夠采用相對(duì)某個(gè)解的最佳交叉概率和變異概率。自適應(yīng)遺傳算法不但能維持種群的多樣性,而且還保證了遺傳算法的收斂性[1]。

自適應(yīng)遺傳算法的缺點(diǎn)[2]:自適應(yīng)遺傳算法比較適用于進(jìn)化的后期,對(duì)于進(jìn)化的初期很不利。因?yàn)樵谶M(jìn)化初期,一些適應(yīng)度較好的個(gè)體會(huì)處于一種幾乎不變化的狀態(tài),從而導(dǎo)致種群中的其它個(gè)體很快被淘汰,加快了種群的收斂速度,但種群卻很難收斂到全局最優(yōu)解,最終出現(xiàn)早熟收斂。

2 自適應(yīng)遺傳算法的改進(jìn)

1994年,Srinivas等人提出了一種根據(jù)適應(yīng)度動(dòng)態(tài)調(diào)整交叉概率Pc和變異概率Pm的自適應(yīng)遺傳算法(Adaptive Genetic Algorithm,AGA)[3]。在 AGA算法中,交叉概率和變異概率隨著個(gè)體的適應(yīng)度在種群平均適應(yīng)度和最大適應(yīng)度之間進(jìn)行線性調(diào)整。當(dāng)適應(yīng)度越接近最大適應(yīng)度時(shí),交叉概率和變異概率越小;當(dāng)適應(yīng)度值接近或等于最大適應(yīng)度值的個(gè)體時(shí),交叉概率和變異概率接近或等于零。

任子武等人在Srinivas等提出的自適應(yīng)遺傳算法的基礎(chǔ)上,提出一種改進(jìn)的自適應(yīng)遺傳算法(Improved Adaptive Genetic Algorithm,IA-GA)[4]。IAGA算法為了保證每一代的優(yōu)良個(gè)體不被破壞,采用了精英保留策略,即如果下一代種群的最優(yōu)個(gè)體適應(yīng)度值小于當(dāng)前種群最優(yōu)個(gè)體適應(yīng)度值,則將當(dāng)前種群最優(yōu)個(gè)體或者適應(yīng)度值大于下一代最優(yōu)個(gè)體適應(yīng)度值的多個(gè)個(gè)體直接復(fù)制到一代,隨機(jī)替代或替代最差的下一代種群中的相應(yīng)數(shù)量的個(gè)體。精英保留策略保證了當(dāng)前的最優(yōu)個(gè)體不會(huì)被交叉、變異等遺傳操作破壞。在IAGA算法中,交叉概率Pc和變異概率Pm按如下公式進(jìn)行自適應(yīng)調(diào)整。

在AGA算法中,當(dāng)適應(yīng)度值等于最大適應(yīng)度值的時(shí)候,交叉概率和變異概率的值為零,容易產(chǎn)生局部最優(yōu)解;在IAGA算法中,較差個(gè)體的變異能力較低,容易產(chǎn)生停滯現(xiàn)象。而精英保留策略雖然起到了保護(hù)和推廣優(yōu)秀個(gè)體的作用,但是其個(gè)體數(shù)目不宜過(guò)大,否則會(huì)使種群進(jìn)化陷入停滯不前,造成局部收斂[5]。

為了克服這兩種自適應(yīng)遺傳算法的不足之處,本文在Srinivas等人提出的AGA算法的基礎(chǔ)上,結(jié)合任子武等人提出的IAGA算法,對(duì)自適應(yīng)遺傳算法的交叉概率和變異概率進(jìn)行改進(jìn),提出了根據(jù)適應(yīng)度值來(lái)動(dòng)態(tài)調(diào)整交叉概率和變異概率的一種新的自適應(yīng)遺傳算法(New Adaptive Genetic Algorithm,NAGA)。交叉概率Pc和變異概率Pm按如下公式進(jìn)行自適應(yīng)調(diào)整。

因此,根據(jù)本文提出的新的自適應(yīng)遺傳算法的交叉概率和變異概率的公式,可以得出交叉概率Pc和變異概率Pm隨適應(yīng)度值的變化情況,如圖1所示。

圖1 NAGA算法自適應(yīng)交叉概率和變異概率

本文提出的改進(jìn)的交叉概率和變異概率,是根據(jù)適應(yīng)度值的集中程度,以種群為單位,自適應(yīng)地變化整個(gè)種群的交叉概率Pc和變異概率Pm,采用種群的最大適應(yīng)度值 fmax,最小適應(yīng)度值 fmin和平均適應(yīng)度值 favg這三個(gè)變量來(lái)衡量種群適應(yīng)度值的集中程度。使交叉概率Pc和變異概率Pm隨著個(gè)體的適應(yīng)度值在種群的最小適應(yīng)度、平均適應(yīng)度和最大適應(yīng)度之間進(jìn)行調(diào)整。

由式(1)可知,當(dāng)要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值大于或等于平均適應(yīng)度值時(shí)的自適應(yīng)調(diào)整公式以及當(dāng)要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值小于平均適應(yīng)度值時(shí),則認(rèn)為交叉概率Pc等于指定值。而本文的改進(jìn)的交叉概率要隨著個(gè)體的適應(yīng)度值在種群的最小適應(yīng)度、平均適應(yīng)度和最大適應(yīng)度之間進(jìn)行調(diào)整。當(dāng)要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值小于平均適應(yīng)度值時(shí),要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值應(yīng)該在最小適應(yīng)度值和平均適應(yīng)度值之間調(diào)整。由此得到本文的交叉概率Pc式(3)。同理由式(2)得到變異概率Pm式(4)。

改進(jìn)后的交叉概率和變異概率不但能夠隨適應(yīng)度自動(dòng)改變,而且使種群中最大適應(yīng)度值的個(gè)體的交叉概率和變異概率不為零,這就相應(yīng)地提高了種群中表現(xiàn)優(yōu)良的個(gè)體的交叉概率和變異概率,使得它們不會(huì)處于一種近似停滯不前的狀態(tài),從而使算法跳出局部最優(yōu)解。將個(gè)體的適應(yīng)度與當(dāng)代種群的平均適應(yīng)度進(jìn)行比較,在種群演化中有效地保留了優(yōu)秀個(gè)體的模式,增強(qiáng)了較差個(gè)體的變異能力,使算法能跳出局部最優(yōu)解,克服早熟的缺點(diǎn)。

3 仿真實(shí)驗(yàn)分析

為了比較本文算法(NAGA算法)的收斂速度,選取一個(gè)簡(jiǎn)單的單峰值函數(shù)(DeJong球函數(shù))進(jìn)行實(shí)驗(yàn)。將NAGA算法與AGA算法以及IAGA算法的獨(dú)立實(shí)驗(yàn)結(jié)果進(jìn)行比較。待優(yōu)化的函數(shù)為:

其中,x∈[-5.12,+5.12],此問(wèn)題為極大值問(wèn)題,該函數(shù)的極大值在(0,0,0)處為100。將各算法分別獨(dú)立實(shí)驗(yàn)30次的結(jié)果平均值記錄于表中,則實(shí)驗(yàn)結(jié)果比較如表1所示。

表1 各種遺傳算法達(dá)到指定函數(shù)值的平均進(jìn)化代數(shù)比較表

由表1中的數(shù)據(jù)可以發(fā)現(xiàn),NAGA算法在收斂速度上有了明顯提高。AGA算產(chǎn)生了實(shí)驗(yàn)結(jié)果不收斂的現(xiàn)象;IAGA算法雖然沒(méi)有產(chǎn)生實(shí)驗(yàn)結(jié)果不收斂的現(xiàn)象,但是可以看出,當(dāng)優(yōu)化函數(shù)值接近最優(yōu)值100時(shí),NAGA算法在30次實(shí)驗(yàn)中的平均進(jìn)化代數(shù)為3.8,其實(shí)驗(yàn)結(jié)果明顯優(yōu)于其它兩種算法因此,從表1的實(shí)驗(yàn)結(jié)果比較可知,NAGA算法不僅具有較快的收斂速度,而且能得到更優(yōu)越的解,它的性能比簡(jiǎn)單遺傳算法和現(xiàn)有的一些自適應(yīng)遺傳算法均有一定改善。

4 結(jié)語(yǔ)

全局優(yōu)化和快速收斂本來(lái)就是相互矛盾的,一種較好的算法就要綜合考慮全局優(yōu)化和快速收斂,選擇一種實(shí)際效果較好的方法實(shí)驗(yàn)結(jié)果表明,本文提出的改進(jìn)的自適應(yīng)遺傳算法(NAGA算法)在提高收斂性能的同時(shí),基本保持了遺傳算法的運(yùn)算速度,在快速收斂和全局最優(yōu)之間獲得了較好的平衡,從而保證了種群能夠快速協(xié)調(diào)地進(jìn)化。

[1]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～861

[2]王小平,曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2002:9,14～15,25～28,68

[3]SRINIVAS M,PATNAILK L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE T ransaction on System,Man and Cybernetics,1994,24(4):656～667

[4]任子武,傘冶.自適應(yīng)遺傳算法的改進(jìn)及在系統(tǒng)辨識(shí)中應(yīng)用研究[J].系統(tǒng)仿真學(xué)報(bào),2006,18(1):41～66

[5]黃康,許志偉,董迎暉.改進(jìn)的遺傳算法及其在多目標(biāo)優(yōu)化設(shè)計(jì)中的應(yīng)用[J].機(jī)械設(shè)計(jì),2005,22(9):735～738