馮九林，殷 鋒，黃光華

(西南民族大學(xué)計算機科學(xué)與技術(shù)學(xué)院，四川 成都 610041)

遺傳算法(Genetic Algorithm， 簡稱GA)[1-2]是一種經(jīng)典的全局優(yōu)化算法，其交叉概率和遺傳概率值的數(shù)據(jù)類型是一種靜態(tài)浮點型，一般采用窮舉法試探出一個能使搜索效果達到最好的定值，取一定值顯然對整個搜索過程是欠佳的.因此有了自適應(yīng)遺傳算法(Adaptive GA，簡稱AGA)[3-4]的誕生，AGA 采用線性數(shù)學(xué)公式來自適應(yīng)調(diào)整遺傳算子的交叉概率和變異概率值，自適應(yīng)調(diào)整改進后，GA 的收斂速度[5]雖有所提高，但是AGA 在演化過程中仍然存在明顯的早熟現(xiàn)象.

文章提出了的HIAGA，讓交叉算子中的交叉概率值和和變異算子中的變異概率值隨著文中提出的曲線變化而變化，通過對個體的適應(yīng)度、每次進化的種群的平均適應(yīng)度以及每次進化的種群中的最大適應(yīng)度的相機組合得到一個值，該值[9]常用以衡量個體適應(yīng)度變化，故文中稱該值為個體適應(yīng)度變化率，用符號?表示(如公式4 所示).種群中個體適應(yīng)度和?成正比例關(guān)系，而?的改變使交叉概率值和變異概率值呈曲線變化.不同適應(yīng)度的個體通過文章中所提出的曲線能自適應(yīng)分配到一個利于進化的概率值，從而使劣質(zhì)個體快速進化成優(yōu)質(zhì)個體，使優(yōu)質(zhì)個體和進化過程沒有停滯的機率.再結(jié)合精英保留策略思想，減小優(yōu)質(zhì)個體的破壞率，進一步提升收斂速度和精確度.

1 線性自適應(yīng)遺傳算法

在標(biāo)準(zhǔn)自適遺傳算法AGA 中，線性自適應(yīng)[6-8]調(diào)整遺傳算子的交叉率和變異率的公式可詳見文獻[7]，公式中會存在Pc 或Pm 為零時的狀況，而出現(xiàn)這種狀況時，整個進化過程幾乎只有選擇算子在作用，破壞了該算法進化理論的核心思想，若此時的優(yōu)良個體并不是全局最優(yōu)解，則得到的最終結(jié)果極可能會是局部極值[9-11]，從而失去了該算法建立的意義.因此文獻[9]在此基礎(chǔ)上提出了一種改進的線性AGA( LinearAdaptive GA，以下簡稱LAGA)[12-14]，使群體中最大適應(yīng)度的個體不會因為其交叉率和變異率為零而使進化過程停滯.其調(diào)整公式[15]如公式(1)及公式(2)所示，該調(diào)整公式的詳細(xì)信息及應(yīng)用見文獻[15].

在LAGA 中，雖然有效的彌補了AGA 中的不足，但卻忽視了改進后的不足之處.在上述公式中，當(dāng)種群中favg 趨近于fmax 時，公式中分母趨近于零，導(dǎo)致整個分式趨向于無窮小，使得Pc 和Pm 趨向于無窮小.從而也會有交叉算子和變異算子失效，僅選擇算子有效的現(xiàn)象發(fā)生.

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

2.1 交叉概率Pc 值和變異概率Pm 值的曲線調(diào)整

通過了解文獻[7]的曲線調(diào)整分析，本文在數(shù)學(xué)領(lǐng)域中得到一種曲線函數(shù)，由雙曲正弦和雙曲余弦這兩種基本雙曲函數(shù)推導(dǎo)而來的Tanh 函數(shù)，即雙曲正切函數(shù)，通過對雙曲正切函數(shù)求導(dǎo)得到其導(dǎo)數(shù)公式后得到公式(3)，當(dāng)x=0 時，f(x) = 1；通過計算得出，當(dāng)x ≥5.512 時，f(x) 無限趨近于零，且該函數(shù)在整個定義域中的值域?qū)儆?0 -1].

從公式(4)可以看出，當(dāng)f ≥favg 時，個體適應(yīng)率?與個體適應(yīng)度f 成正比.當(dāng)個體適應(yīng)度f =fmax 時，?=1.在求解最大優(yōu)化問題時，可利用公式(5)調(diào)整算法中的交叉概率值，而公式(6)則可用以調(diào)整算法進化過程中的變異概率.此式中，β =5.512，Pcmax 和Pcmin 分別為交叉率的上界和下界；Pmmax 和Pmmin 分別為變異率的上界和下界.

公式(5)的幾何圖形如圖1 中(a)所示，其形如高斯分布曲線，Pcmax 和Pcmin 分別代表最大交叉概率和最小交叉概率，Pc 和?分別為交叉概率和個體適應(yīng)度變化率；?min 和?max 分別為求函數(shù)最大值時的最小個體適應(yīng)率和最大個體適應(yīng)率；而?'min、?'及?'max 分別是求函數(shù)最小值時的最小個體適應(yīng)率、個體適應(yīng)度變化率和最大個體適應(yīng)率.結(jié)合公式(5)從圖1 中(a)可以分析出，隨著個體適應(yīng)度增大到與種群中最大個體適應(yīng)度接近或者相等時，則?無限接近乃至等于?max，此時對應(yīng)的則是最小交叉概率Pcmin；當(dāng)種群中個體適應(yīng)度很小時，則?接近甚至相等?min，此時對應(yīng)的則是最大交叉概率Pcmax.同理，在求函數(shù)最小值問題的時候?qū)?yīng)坐標(biāo)軸負(fù)半軸的部分，?avg 表示種群中個體適應(yīng)度達到平均適應(yīng)度時，種群中個體的個體適應(yīng)率的值.公式(6)的幾何圖形如圖1 中(b)所示，Pmmax 和Pmmin 分別表示最大變異概率和最小變異概率，Pm 和?c 則分別代表變異概率和個體適應(yīng)度變化率；?cmin、和?cmax 分別為求函數(shù)最大值時的最小個體適應(yīng)率以及最大個體適應(yīng)率；而?'cmin、?'及?'cmax 分別是求函數(shù)最小值時的最小個體適應(yīng)率、個體適應(yīng)率和最大個體適應(yīng)率.

圖1 HIAGA 交叉概率(a）和變異概率(b）自適應(yīng)調(diào)整曲線Fig.1 Crossover probability(a） and mutation probability(b） for adaptive adjustment curve of HIAGA

結(jié)合公式(6)從圖1 中的(b)可以分析出，隨著個體適應(yīng)度增大到與種群中最大個體適應(yīng)度無限接近或者相等時，則?無限接近或等于?max，此時變異概率Pm 對應(yīng)的則是最小變異概率Pmmin；當(dāng)種群中個體適應(yīng)度很小時，則?無限接近甚至等于?min，此時pm 對應(yīng)的則是最大變異概率Pmmax.

遺傳算法線性自適應(yīng)調(diào)整的不足之一就是自適應(yīng)調(diào)整的變化率太大，不能很好的把握算法初期和后期自適應(yīng)調(diào)整的‘度’，則導(dǎo)致了算法在函數(shù)全局尋優(yōu)的過程中陷入局部最優(yōu)解.而在HIAGA 中，進化過程的初期和后期正好彌補了AGA 和LAGA 算法的不足，在初期和后期，利用該函數(shù)曲線的特性，小量的調(diào)整交叉率和變化率，使自適應(yīng)更加合理.且利用該函數(shù)的對稱性，在求函數(shù)最小值時，該曲線自適應(yīng)調(diào)整公式不用有太大的改動，只需將fmax 改為fmin.當(dāng)求解函數(shù)最小值時，適應(yīng)度是負(fù)值，此時β = -5.512，且對應(yīng)的函數(shù)圖像是圖1中函數(shù)圖像負(fù)半軸部分.

2.2 精英保留策略

精英保留策略的方法是在種群進行遺傳操作之前將種群中適應(yīng)度最大的個體挑選出來，以防止種群中最優(yōu)的個體在交叉算子和變異算子操作中丟失.在本文改進的算法中，借鑒了精英保留策略的思想，通過上文中個體適應(yīng)率?來判斷該個體是否是適應(yīng)度最大的個體，當(dāng)?=1 時，該個體是適應(yīng)度最大的個體，則復(fù)制該個體后再進行變異算子操作，再將操作后的子代插入到新種群中.本文算法中的精英保留策略加入變異算子是因為當(dāng)個體適應(yīng)度很大時，變異算子的變異率值隨非線性調(diào)整曲線緩慢變化，優(yōu)質(zhì)個體被破壞的幾率很小，且讓個體適應(yīng)度大的而非全局最優(yōu)解的個體快速進化到全局最優(yōu)解. 本文改進的算法的執(zhí)行流程如圖2 所示，其中g(shù)en 是整型變量，?是上文所提及的個體適應(yīng)率.

圖2 改進的算法的執(zhí)行流程Fig.2 Execution flow of improved algorithm

3 仿真驗證與性能分析

為了驗證該改進算法的性能及有效性，選擇一個具有代表性且相當(dāng)復(fù)雜的函數(shù)(7)進行尋優(yōu)測試.分別對普通的遺傳算法(GA)，線性自適應(yīng)遺傳算法(LAGA)和文章提出的曲線自適應(yīng)遺傳算法(HIAGA)的全局最優(yōu)解的尋找過程進行比較.

以該函數(shù)為目標(biāo)函數(shù)，選擇二進制編碼[9]，采用常用的輪盤賭抽樣選擇方法.在HIAGA 中采用公式(5)、(6)進行自適應(yīng)調(diào)整，公式中的參數(shù)Pc1 =0.8，Pc2 =0.6，Pm1 =0.04，Pm2 =0.006；在LAGA 中采用公式(1)、(2)進行自適應(yīng)調(diào)整，初始化公式中的參數(shù)Pc1 =0.9，Pc2 =0.6， Pm1 =0.1，Pm2 =0.01；GA 調(diào)整公式參數(shù)為Pc =0.9，Pm=0.05，仿真結(jié)果如圖3 -5 所示.

圖3 30 次迭代最優(yōu)解的變化Fig.3 The change of the optimal solution of 30 iterations

圖4 70 次迭代最優(yōu)解的變化Fig.4 The change of the optimal solution of 70 iterations

圖5 150 次迭代最優(yōu)解的變化Fig.5 The change of the optimal solution of 150 iterations

上述圖中，帶“?”的實線均代表HIAGA，實線表示GA 和LAGA.圖3 是算法經(jīng)過30 次遺傳迭代后，得到的比較結(jié)果，圖3 中的(a)和(b)均是運行10 次后得到的結(jié)果，可以看出GA 和LAGA 偶爾有出現(xiàn)早熟現(xiàn)象而收斂到了局部最優(yōu)解，而HIAGA 收斂速度較快且未出現(xiàn)早熟現(xiàn)象；圖4 是算法經(jīng)過70 次遺傳迭代后，得到的比較結(jié)果，圖4中的(a)和(b)中均運行10 次后可以看出GA 和LAGA 仍然偶爾有出現(xiàn)早熟現(xiàn)象，而HIAGA 收斂速度較快且未出現(xiàn)早熟現(xiàn)象；圖5 是算法經(jīng)過150 次遺傳迭代后得到的比較結(jié)果，圖5 中的(a)和(b)中亦均運行10 次，HIAGA 的收斂速度比GA 和LAGA 的收斂速度都較快且曲線呈現(xiàn)較好的階梯狀，具有優(yōu)良的自適應(yīng)能力.

4 結(jié)語

相比與其它智能算法，遺傳算法的發(fā)展歷史較為悠久，但是就該算法的收斂速度和早熟現(xiàn)象仍然是研究人員不斷探索和改進的領(lǐng)域.而針對這兩個方面的問題，文章根據(jù)GA 和AGA 的相關(guān)理論和知識，對AGA 做出了相關(guān)改進.由MATLAB 軟件實驗仿真，得到的結(jié)果可知：文章中的HIAGA 對交叉算子中的交叉概率和變異算子的變異概率進行了自適應(yīng)生成策略方面的改進，對算法收斂速度和避免算法早熟等問題上都能取得較好的效果.