張國強 彭曉明

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實驗分析

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

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

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

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

4 結(jié)語

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

[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)用與軟件實現(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)遺傳算法的改進及在系統(tǒng)辨識中應(yīng)用研究[J].系統(tǒng)仿真學(xué)報,2006,18(1):41～66

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