自適應遺傳算法的改進與應用*

張國強 彭曉明

(空軍雷達學院研究生管理大隊1) 武漢 430019)(空軍雷達學院預警監視情報系2) 武漢 430019)

1 引言

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

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

2 自適應遺傳算法的改進

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

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

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

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

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

圖1 NAGA算法自適應交叉概率和變異概率

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

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

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

3 仿真實驗分析

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

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

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

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

4 結語

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

[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]王小平,曹立明.遺傳算法—理論、應用與軟件實現[M].西安:西安交通大學出版社,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]任子武,傘冶.自適應遺傳算法的改進及在系統辨識中應用研究[J].系統仿真學報,2006,18(1):41～66

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