改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法

陳 琳，王子微，莫玉良，潘海鴻

(廣西大學(xué)機械工程學(xué)院，廣西 南寧 530004)

1 引言

在工程實踐中，函數(shù)優(yōu)化及組合優(yōu)化等問題需要在復(fù)雜的搜索空間中尋找最優(yōu)解，但隨著問題規(guī)模的擴(kuò)大以及約束條件的增多，常引發(fā)組合爆炸。多種優(yōu)化算法種遺傳算法在實際大規(guī)模系統(tǒng)應(yīng)用中具有強穩(wěn)健性，對函數(shù)依賴程度低等優(yōu)點[1-3]。它是一種利用自然選擇和生物進(jìn)化思想在搜索空間中搜索最優(yōu)解的隨機搜索算法。然而在傳統(tǒng)遺傳算法中，遺傳算子通常人為預(yù)先設(shè)置。且在解決復(fù)雜的多極值函數(shù)問題上需要數(shù)千次的遺傳迭代才可尋得最優(yōu)解，故很多學(xué)者致力于改善進(jìn)化過程，提出自適應(yīng)遺傳算法以提升算法效率[4-5]。

自適應(yīng)遺傳算法在收斂速度加快的同時卻引發(fā)早熟現(xiàn)象。為此，王悅等[6]提出使用實數(shù)編碼、線性排序的適應(yīng)度分配方法、實值變異和基于適應(yīng)度的線性筆記的改進(jìn)交叉策略，通過實驗驗證了該算法收斂最為平穩(wěn)。Tarek等[7]提出將局部搜索引入到遺傳算法中來創(chuàng)建混合算法，通過實驗驗證該算法可以自適應(yīng)學(xué)習(xí)并提高搜索全局最優(yōu)解的能力。楊從銳等[8]提出交叉突變調(diào)整新標(biāo)準(zhǔn)，將平均適應(yīng)度和最優(yōu)適應(yīng)度比值的反正弦作為參考因素，將π/6作為參考閾值，通過判斷新增參考因素與閾值的大小關(guān)系并以此對交叉率及突變率進(jìn)行調(diào)整。Wang等[9]提出一種改進(jìn)的NSGA2算法用于解決多目標(biāo)問題。NSGA2算法每次迭代計算后，在Pareto最優(yōu)集上執(zhí)行一種局部搜索策略以搜索更好的解，從而使NSGA2算法獲得更好的局部搜索能力。這些學(xué)者主要是在進(jìn)化過程中根據(jù)進(jìn)化的不同階段改進(jìn)建立相應(yīng)的交叉概率及變異概率。這在一定程度上能夠改善算法的搜索能力，但因引入諸多人為經(jīng)驗參數(shù)，導(dǎo)致測試結(jié)果不穩(wěn)定。

針對該問題，提出一種改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法。該自適應(yīng)遺傳算法中的復(fù)制率、交叉率和突變率可根據(jù)種群規(guī)模、種群中個體的分布情況和遺傳迭代不同階段進(jìn)行自適應(yīng)變化，進(jìn)而克服過早收斂陷入局部最優(yōu)解，并提高搜索精度。

2 自適應(yīng)遺傳算法遺傳算子設(shè)計

自適應(yīng)遺傳算法的交叉率和突變率改進(jìn)：

1)交叉率的改進(jìn)：如交叉兩個體中的較大適應(yīng)度與種群最大適應(yīng)度之差較大時，視為該交叉?zhèn)€體為非優(yōu)質(zhì)個體，需適當(dāng)增加其交叉率，使其交叉獲得優(yōu)質(zhì)樣本的概率提升；如種群最佳適應(yīng)度與平均適應(yīng)度之差較大時，視為樣本較為分散(意味著適應(yīng)度函數(shù)尚未進(jìn)入極值)，需適當(dāng)下降其交叉率使分散的種群盡快迭代；在交叉?zhèn)€體間的較優(yōu)適應(yīng)度值小于種群平均適應(yīng)度時，樣本視為較劣樣本，為減少計算量，較劣樣本的交叉率將不再依據(jù)種群分布加以考慮并設(shè)置為恒定值。故將交叉率改進(jìn)為

(1)

式中fmax為種群中個體最大適應(yīng)度值，f′為兩個要交叉?zhèn)€體中適應(yīng)度值較大個體的適應(yīng)度值，favg為種群中所有個體的平均適應(yīng)度值，k1，k2為0到1之間的數(shù)，通常人為設(shè)置。

2)突變率的改進(jìn)：與交叉率類似，需考慮調(diào)整要突變個體與平均適應(yīng)度差值，故將突變率改進(jìn)為

(2)

式中f為要突變個體的適應(yīng)度值，k3，k4為0到1之間的數(shù)，通常人為設(shè)置。

遺傳算法收斂性的測試用F7函數(shù)

f(x，y)=(x2+y2)0.25[sin2(50(x2+y2)0.1)+1.0]

(3)

該函數(shù)有無數(shù)個局部極值點，其中只有(0，0)為全局最小值點，最小值為0。適應(yīng)度收斂值誤差小于0.1即視為收斂至全局最優(yōu)解。

收斂性的仿真測試參數(shù)設(shè)置：k1=0.25，k2=0.25，k3=0.35，k4=0.35，x取值范圍為(-6，6)，y取值范圍為(-6，6)，復(fù)制率為dup=0.2，樣本數(shù)N為500，遺傳迭代代數(shù)為100。

F7函數(shù)適應(yīng)度遺傳迭代結(jié)果圖1中發(fā)現(xiàn)，其在迭代收斂速度上有較大的提升，但隨著收斂速度的提升出現(xiàn)早熟現(xiàn)象。為避免實驗結(jié)果的偶然性，對樣本進(jìn)行20次重復(fù)測試迭代，仿真結(jié)果有15次函數(shù)陷入局部最優(yōu)解，其適應(yīng)度收斂值在0.5-1.5間波動，并且無法跳出獲得最優(yōu)解。

圖1 F7函數(shù)適應(yīng)度遺傳迭代圖

表明自適應(yīng)遺傳算法中對于交叉率和突變率的改進(jìn)在解決復(fù)雜多極值問題上仍存在易陷入局部最優(yōu)解的問題。

3 改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法

產(chǎn)生上述問題的可能原因分析：

1)交叉率和突變率算子的設(shè)計未考慮樣本總數(shù)N。樣本量越大意味著樣本內(nèi)容越豐富，適應(yīng)度值覆蓋域越廣。而對于越豐富的樣本，一個較大的交叉和突變率意味著其造成的波動越大，使種群收斂減緩。

2)遺傳算子設(shè)計未考慮種群中個體的分布情況。圖2中d為中間區(qū)域樣本數(shù)量M與樣本總數(shù)N之比，當(dāng)d數(shù)值較小時，則樣本中間區(qū)域中個體分布較少，說明它們不是一個穩(wěn)定集中的群體，所以交叉和突變的概率需要減小。

圖2 種群中個體分布情況圖

3)迭代中復(fù)制率是定值。遺傳迭代中樣本分布范圍越大，即意味著樣本優(yōu)劣并存，此時需一個較大復(fù)制率以淘汰種群中的劣質(zhì)樣本；而隨著迭代進(jìn)行，樣本高度集中時，為避免陷入局部最優(yōu)，需保留部分分散的樣本為樣本交叉提供引入優(yōu)質(zhì)解的機會。

4)人為經(jīng)驗對交叉率和突變率算子中k1、k2、k3、k4取值，這需大量重復(fù)實驗測試才能得出最合適值，導(dǎo)致計算量大。

為此，提出一種改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法：

1)復(fù)制率的調(diào)整：自適應(yīng)遺傳算法中將復(fù)制率設(shè)置為定值，在樣本數(shù)較少時其影響不大，而在大樣本及多維空間迭代時，對于樣本總體而言，當(dāng)樣本適應(yīng)度分散時，較劣適應(yīng)度突出明顯，需快速去除樣本中較劣樣本；當(dāng)適應(yīng)度集中時，平均適應(yīng)度向最佳適應(yīng)度靠攏，復(fù)制率應(yīng)隨之下降。

復(fù)制率算子設(shè)計中首先需考慮樣本最優(yōu)適應(yīng)度與平均適應(yīng)度的差值。當(dāng)樣本最優(yōu)適應(yīng)度與平均適應(yīng)度越大時，則樣本分布所跨區(qū)域越大，復(fù)制率應(yīng)增大以淘汰較劣樣本；當(dāng)中間區(qū)域的樣本分布越少(即d越小)，則樣本越分散，復(fù)制率也應(yīng)增大。復(fù)制率設(shè)計為

(4)

式中，fmax表示種群中個體適應(yīng)度的最大值，越高的最大適應(yīng)度值意味著種群樣本中所保存的樣本最優(yōu)性好，復(fù)制率會隨之降低；d表示樣本集中程度，越集中的樣本意味種群適應(yīng)度收斂程度越高，復(fù)制率亦會隨之上升，加快整個種群收斂速度。(fmax-favg)表示種群中個體最大適應(yīng)度值和種群中所有個體的平均適應(yīng)度值之差，該項表示整個種群適應(yīng)度的離散程度，兩者之差越大即表示種群分布越離散，故復(fù)制率也隨之增大。

2)交叉率的調(diào)整：在多極值問題上，需使用較多的樣本數(shù)，通常種群適應(yīng)度豐富度與樣本數(shù)成正相關(guān)，愈多的樣本意味著更高的樣本豐富度。對于越豐富的種群樣本，其擁有優(yōu)質(zhì)樣本的概率則越高，較大的交叉率會導(dǎo)致種群內(nèi)樣本交叉產(chǎn)生劣質(zhì)樣本的概率將大于產(chǎn)生優(yōu)質(zhì)樣本的概率。故初始交叉率應(yīng)適當(dāng)下降，以避免不必要的較劣樣本引入和波動。

在遺傳迭代中，隨著遺傳迭代次數(shù)t的增加，遺傳可分為前期和后期。遺傳前期樣本混雜，需盡快找出較優(yōu)解；而遺傳后期樣本平均適應(yīng)度已高度靠近最佳適應(yīng)度，較大的交叉率反而會帶來不必要的波動。當(dāng)個體適應(yīng)度較為集中或較為分散時，視為樣本進(jìn)入高度集中或高度分散兩種極端情況，此時應(yīng)需適當(dāng)調(diào)整交叉率。為此，將交叉率改進(jìn)為

(5)

式中，t為迭代次數(shù)，隨著迭代進(jìn)行種群已逐漸向種群中最優(yōu)適應(yīng)度靠攏，交叉率將隨迭代而逐漸減小。分子(fmax-f′)表示種群中個體最大適應(yīng)度值和兩個要交叉?zhèn)€體中適應(yīng)度值較大個體的適應(yīng)度值之差，該項表示交叉?zhèn)€體在種群中的離散程度，兩者之差越大即表示要交叉的兩個體的適應(yīng)度值越低，交叉率需隨之增大，增加引入優(yōu)質(zhì)樣本的概率；(fmax-favg)表示種群中個體最大適應(yīng)度值和種群中所有個體的平均適應(yīng)度值之差，其與(fmax-f′)的比值表示交叉兩個體適應(yīng)度與種群平均適應(yīng)度的差距，差值越大時意味著該兩個體越接近邊界位置，為增加引入優(yōu)質(zhì)樣本的概率，故交叉率隨之增大；越大的種群個數(shù)N意味著越豐富的種群適應(yīng)度，即有越大的可能含有優(yōu)質(zhì)解，故交叉率會隨之種群數(shù)N增大而減?。粯颖炯谐潭萪變大意味種群適應(yīng)度收斂程度變高，交叉率會隨之上升增加引入優(yōu)質(zhì)解的概率。

3)突變率的調(diào)整：自適應(yīng)遺傳算法突變率設(shè)置初始值較大且下降幅度較小，對于多極值函數(shù)而言，其樣本豐富度與其樣本數(shù)量成正比，故突變率取值應(yīng)與樣本總數(shù)N相關(guān)，對于越大的樣本總數(shù)意味著樣本中含有越詳細(xì)的總體特征。較大的突變率會導(dǎo)致樣本中波動增加，故突變率應(yīng)與樣本總數(shù)成負(fù)相關(guān)，以避免過高的突變率導(dǎo)致的適應(yīng)度函數(shù)不必要波動。

隨著遺傳迭代次數(shù)t的增加，較大的突變率所引入的新的樣本的波動會影響遺傳算法的收斂性，故突變率應(yīng)隨迭代次數(shù)增加應(yīng)適當(dāng)改變。當(dāng)個體適應(yīng)度較為集中時，往往意味著平均適應(yīng)度函數(shù)逼近一個極值，但無法確定其是否為最優(yōu)解，需對突變率進(jìn)行適當(dāng)調(diào)整，使其不易陷入局部最優(yōu)解。因此，將突變率改進(jìn)為

(6)

與交叉率算子設(shè)計相類似，綜合考慮種群個數(shù)、樣本集中程度和迭代次數(shù)變化的影響，突變率隨著N的增大而減小，隨著d的增加而增加，隨著迭代次數(shù)t的增加而逐漸減小。

遺傳算子驗證：在遺傳算法中，由于個體每次交叉突變均只和當(dāng)前狀態(tài)相關(guān)，與前期狀態(tài)無關(guān)，故采用馬爾科夫鏈序列來構(gòu)造種群的適應(yīng)度變化。根據(jù)馬爾科夫鏈序列的收斂條件對改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法中的遺傳算子進(jìn)行驗證

(7)

(8)

(9)

改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法中遺傳算子滿足使算法收斂的條件，使得該算法在理論上可收斂，求出全局最優(yōu)解(圖3)。

圖3 改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法流程圖

4 仿真分析

圖4 F7函數(shù)適應(yīng)度遺傳迭代圖

圖4為F7函數(shù)適應(yīng)度遺傳迭代圖，圖4中平均適應(yīng)度變化可看出，迭代50次后平均適應(yīng)度收斂已經(jīng)到達(dá)全局最優(yōu)解，其值為0.03074；迭代95次后，最佳適應(yīng)度值保持不變。

圖5和圖6分別為自適應(yīng)遺傳算法和改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法適應(yīng)度全局搜索結(jié)果。圖5中可知，自適應(yīng)遺傳算法搜索出的適應(yīng)度為0.6053，陷入局部最優(yōu)且距最小值相差較大。圖6中，改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法搜索的適應(yīng)度值為0.03074，小于設(shè)定的閾值0.1。顯然改進(jìn)后的算法全局搜索能力更強，結(jié)果更精確。

圖5 自適應(yīng)遺傳算法適應(yīng)度搜索結(jié)果

圖6 改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法適應(yīng)度搜索結(jié)果

為避免保證實驗結(jié)果偶然性，分別用自適應(yīng)遺傳算法和改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法進(jìn)行50次重復(fù)實驗，結(jié)果見表1。

表1 2種遺傳算法搜索值

由表1可知，改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法相比于自適應(yīng)遺傳算法在適應(yīng)度的搜索精度上提升了15.4225倍，并且陷入局部最優(yōu)的次數(shù)下降了13.5倍。

5 結(jié)論

為解決自適應(yīng)遺傳算法中常出現(xiàn)易陷入局部最優(yōu)解的問題，同時針對更加復(fù)雜且極值更多的適應(yīng)度函數(shù)，提出遺傳因子改進(jìn)方案，并理論證明其收斂性。通過F7函數(shù)對改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法進(jìn)行收斂性驗證。實驗結(jié)果表明該算法收斂速度快且精度高，同時不易陷入局部最優(yōu)解也證明改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法在解決早熟問題上的可行性。