一種異型改進(jìn)的自適應(yīng)遺傳算法

馮九林，殷 鋒，黃光華

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

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

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

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

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

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

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

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

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

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

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

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

2.2 精英保留策略

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

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

3 仿真驗(yàn)證與性能分析

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

以該函數(shù)為目標(biāo)函數(shù)，選擇二進(jìn)制編碼[9]，采用常用的輪盤賭抽樣選擇方法.在HIAGA 中采用公式(5)、(6)進(jìn)行自適應(yīng)調(diào)整，公式中的參數(shù)Pc1 =0.8，Pc2 =0.6，Pm1 =0.04，Pm2 =0.006；在LAGA 中采用公式(1)、(2)進(jìn)行自適應(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

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

4 結(jié)語(yǔ)

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