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

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

1 引言

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

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

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

2 自適應遺傳算法遺傳算子設計

自適應遺傳算法的交叉率和突變率改進：

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

(1)

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

2)突變率的改進：與交叉率類似，需考慮調整要突變個體與平均適應度差值，故將突變率改進為

(2)

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

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

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

(3)

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

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

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

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

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

3 改進的自適應復制、交叉和突變遺傳算法

產生上述問題的可能原因分析：

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

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

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

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

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

為此，提出一種改進的自適應復制、交叉和突變遺傳算法：

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

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

(4)

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

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

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

(5)

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

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

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

(6)

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

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

(7)

(8)

(9)

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

圖3 改進的自適應復制、交叉和突變遺傳算法流程圖

4 仿真分析

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

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

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

圖5 自適應遺傳算法適應度搜索結果

圖6 改進的自適應復制、交叉和突變遺傳算法適應度搜索結果

為避免保證實驗結果偶然性，分別用自適應遺傳算法和改進的自適應復制、交叉和突變遺傳算法進行50次重復實驗，結果見表1。

表1 2種遺傳算法搜索值

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

5 結論

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