基于均勻設計的并行變異遺傳算法*

龐 博

（赤峰工業職業技術學院 赤峰 024000）

1 引言

遺傳算法（Genetic Algorithm，GA）作為一種隨機仿生優化算法，自20世紀70年代由Holland教授提出以來，經過數十年的發展，在理論仿真與工程實際中均取得了良好表現［1］。遺傳算法通過對待優化問題編碼，隨機初始化群體，模仿自然界生物進化機制，按照“優勝劣汰”原則對群體進行選擇、交叉、變異操作，逐步得到問題最優解或次優解，從而解決用常規數學方法難以解決的問題。標準遺傳算法主要通過遺傳操作選擇與產生新個體進而實現進化，但各操作方式都存在隨機性大導致優化速度和優化精度較差的問題。為此，許多學者分別在編碼［2］、適應度函數［3］、初始群體［4～5］、選擇［6］、交叉［7～9］、變異［10～11］等方面進行改進；有學者將其它算法與遺傳算法相結合［12］，優勢互補，取得了良好效果。本文在分析了標準遺傳算法的不足及相關文獻之后，提出一種基于完全均勻設計的并行變異遺傳算法（Uniform Design-Parallel Mutation GA，UD-PMGA），力圖用相對簡單的思想實現遺傳算法的高效搜索，通過測試函數仿真與比較，驗證了算法的有效性。

2 初始化群體

初始群體的多樣性對算法的全局收斂及尋優速度都有重要影響，因此，產生均勻分布的初始群體成為眾多學者的研究內容。正交設計與均勻設計是初始群體均勻化的主流方法［4～5］。正交設計法由于試驗數等于水平數的平方，因此要保證較高的水平數以實現高精度的初始化，其群體規模必然呈平方倍增長，基于區域分解組合思想的方法也不能從本質上降低計算量，造成計算量難以承受；如果采用較低的水平數，則初始群體的均勻性無法保證。均勻設計的水平數等于試驗數，因此更適于遺傳算法的群體初始化。

文獻［13］以中心偏差作為目標函數，用改進的遺傳算法獲得均勻性良好的均勻設計表。但其計算量過大，且算法復雜難以實現普遍應用。文獻［14］為均勻設計表的設計提供了簡單實用的Matlab程序，只需要輸入水平數和因素數，就可得到相應的多個中心偏差很小的均勻矩陣。本文根據文獻［14］的方法生成均勻設計表UM，將基因的定義域均分為size（群體規模）個區間，取每個區間的中值作為水平值，群體規模等于水平數，即均勻矩陣的行數，問題的維數即基因的個數等于均勻矩陣的列數，進而生成均勻的初始群體。由于采用均勻設計初始化群體，同時對于連續變化的最值問題，實數編碼比二進制編碼方式效果更好［2］，因此本文選用實數編碼方式。根據均勻設計理論［15］，一般情況下，水平數與因素數的比值越大，產生的矩陣均勻性越好。因此，群體規模不應太小，否則初始群體的均勻性會大大下降，對于高維優化問題更是如此。

3 遺傳操作算子的改進

3.1 改進的錦標賽選擇機制

選擇算子模仿自然界中的“優勝劣汰”規律，按照一定的機制從父代群體中選擇適應度較好的部分個體，經過復制生成子代種群。選擇操作中比較常見的兩種方法是輪盤賭和錦標賽。文獻［6］的研究認為：錦標賽選擇方法在求解精度和求解速度上整體要優于輪盤賭選擇方法，競賽規模為種群規模的60%～80%優化效果較好。如取種群規模為10，競賽規模為60%，則選出的個體最多涵蓋適應度排名前5的5個個體，此5個（或小于5個）個體經過不同數量的復制構成下一代群體進行交叉及變異操作。若群體規模為100，則只能選出適應度排名前41位的個體，且適應度越高的個體被選擇的概率越大。經上述文獻方法選擇出的群體，具有一定的隨機性，其均勻性并不可靠。為此本文提出兩種改進的錦標賽選擇機制。一是簡單覆蓋法，取適應度較高的一半個體覆蓋整個群體。二是不同個體覆蓋法，選擇適應度排名靠前且各自不同的50%的個體覆蓋父代群體。對于標準遺傳算法的三個算子中，選擇操作系統消耗比重最大，主要緣于輪盤賭選擇或錦標賽選擇方法的適應度計算與比較［16］。改進方法用一次排序和復制完成選擇，在促進群體進化和保證群體多樣性的同時，降低了算法的復雜性與計算量。

3.2 交叉算子

交叉算子模仿自然界生物繁衍過程中的基因重組，通過不同方式的交叉操作產生新個體，以期獲得適應度更高的個體。文獻［7］提出選擇個體適應值最相近且空間距離最近的兩個個體進行交叉可以提高交叉操作的搜索效率。文獻［8］根據個體相似度對群體進行劃分，之后在子種群之間和種群之內同時進行交叉操作，并用貪婪算法選出較優個體。文獻［9］通過改進交叉算子，將子代個體落在兩個父代個體之間及其兩側，認為交叉后的子代將大概率地優于父代個體，但其并沒有全面分析適應度及空間距離對子代個體的影響。考慮一種極端情況，兩個父代個體適應度相等且分居極值兩側時，如圖1所示。

圖1 兩個交叉點在極值兩側且適應度相等示意圖

在此情況下，采用常規交叉操作能以概率1獲得優于兩個父代個體的子代個體。對于多峰函數，隨著進化的進行，多峰函數轉化為單峰特性或單調特性［9］。因此本文提出適應度最相近且空間距離最大的兩個個體作為父代個體進行交叉能夠以較高的概率搜索到適應度更高的子代個體。

交叉操作具體流程如下：

1）在每一代選擇操作之后，對群體適應度進行排序［X1，X2……Xn］。

2）判斷Xi+1（i=1，2……n-1）與待交叉個體Xi（i=1，2……n）適應度是否相同，若相同，轉入步驟2），若不同，取此個體放入配對池2，轉入步驟3）。

3）判斷Xi-1（i=2，3……n）與待交叉個體Xi適應度是否相同，若相同，轉入步驟3），若不同，取此個體放入配對池2，轉入步驟4）。

4）判斷配對池1和配對池2是否為空，如果其中一個為空，則取另一個作為交叉對象；若兩個都不為空，則分別計算兩個配對池中兩個個體與待交叉個體的歐式距離，取距離較大者作為交叉對象；若兩個配對池均為空，則直接將待交叉個體放入子代群體。

5）按式（1）進行交叉操作。

交叉完成后，用子代個體和父代個體中適應度較高的兩個個體替換原父代個體。需要注意的是，對于個體X（i）的最佳交叉對象是個體X（j），但個體X（j）的最佳交叉對象不一定是個體X（i），因此需要對每個個體尋找其最佳交叉對象。所有個體都完成上述操作后即完成此代交叉操作。

3.3 自適應并行變異

變異算子的思想來自生物的基因突變，標準變異算子對極少數個體進行變異操作，產生新個體以保持種群的多樣性，但較低的變異概率嚴重限制了變異操作的搜索效率。許多自適應變異方法盡管有一定改善，但搜索效率仍有提升空間。文獻［1］采用根據進化代數和基因定義域的自適應變異步長，變異操作公式較復雜，而且沒有考慮個體適應度對搜索效率的影響。文獻［10］提出標準變異操作和當前最優解變異操作并行的變異策略。若最優解變異得到一個更優解，則取更優解，否則取標準變異方法得到的隨機值。如果此次變異操作未搜索到優于當前最優解的“更優解”，可能會把適應度低于父代個體的新個體直接放入下一代群體中，而且對于高維優化問題意義不大。文獻［11］用當前最優解為變異操作指引方向，同時引入固定參數的按比例放縮變異，存在基因無法“過0”即正負數不能轉換的缺陷。

本文提出一種基于高斯函數的自適應變異比例和自適應變異步長并行的變異搜索策略。通過對高斯函數適當變形，以進化代數為自變量，以變異比例和變異步長參數為函數值，通過合理設置函數參數實現進化初期變異比例和變異步長快速減小，以加快算法收斂；進化后期變異比例和變異步長緩慢減小加強局部搜索。相關代碼如下：

miu=1；sigmaf=500；

n=exp（-（kg-miu）.^2/（2*sigmaf））*1.8+k；

%n為變異比例參數，kg為進化代數，k為調節參數。

fisum=0；fisum=fisum+fi（i）；

%對當前群體適應度求和。

fiavg=fisum/size；

n1avg（i）=fiavg/（fi（i）+0.001）；

%加0.001是為防止發生除零現象。

n1（i）=n*n1avg（i）；

%n1（i）為考慮適應度加權后的變異比例參數。

tem（i，j）=qunti（i，j）*（（rand+0.5）*n1（i）+1-n1（i））；

%自適應變異比例。

km=kmu/（exp（-（kg-miu）.^2/（2*sigmaf））*1.8+k1）；

%變異步長參數，kmu=120，k1=0.01。

tem1（i，j）=qunti（i，j）+（rand*2-1）*（max-min）/km；

%自適應變異步長。

上述代碼中，關鍵參數為 sigmaf、k、kmu、k1。對于參數k，建議前1/3進化代數取0.1，中間1/3進化代數取0.01，后1/3進化代數取0.001。仿真過程中發現，上述四個參數在數量級范圍內變化不會對算法的優化結果造成明顯影響，說明算法對參數設置不敏感，這是任何優化算法期望出現的特點。自適應變異比例參數n1應限定在［0.005，1.9］區間內。如果變異操作后基因值超出定義域，則取當前值到相近定義域端點之間的隨機值。兩種操作同時進行，并與父代個體進行適應度比較，取適應度最高者進入下一代群體。

3.4 預選擇機制

預選擇機制屬于小生境遺傳算法的一種進化機制，由Cavichio在1970年提出，其基本思想是：當子代個體的適應度超過其父代個體的適應度時，所產生的子代個體才能替代其父代而遺傳到下一代群體中，否則父代個體仍保留在下一代群體中。由于子代個體與父代個體之間編碼結構的相似性，所以替換掉的只是一些編碼結構相似的個體，故能夠有效地維持群體的多樣性，并造就小生境的進化環境［17］。本文將預選擇思想應用在交叉與變異操作中，通過保留當前局部最優解，加快算法尋優速度的同時還可以保證算法的收斂性與有效性。

4 仿真測試與分析

4.1 測試函數

為了驗證本文算法的改進效果，通過15個常見的函數進行測試，函數表達式及定義域如表1所示。為避免算法對個別函數存在較好搜索效果的特殊性，選擇不同類型、不同特性的函數對UD-PMGA算法進行測試，并與相關文獻算法進行比較。測試函數 f5又叫Rosenbrock's Vally函數，最優解位于一個平坦且狹長的山谷谷底，一般算法很容易搜索到山谷底部，但由于山谷底部點的函數值變化很小，所以想要搜索到全局最優解很困難，因而經常被用來測試各種優化算法的搜索性能［18］。表1中函數f1、f2為1維函數，f3、f4、f5、f7為2維函數，f6為10維函數，其余函數為30維。函數f1、f2、f3求最大值，其余函數求最小值。仿真環境為Matlab，在Dell Inspiron 15 5000 Series筆記本電腦運行30次所得UD-PMGA算法優化結果。

表1 測試函數及相關要求

4.2 仿真結果

表2為UD-PMGA算法對函數f1～f6的優化結果及與文獻［18］IAGA算法和文獻［19］NCGA算法的比較。算法參數設置與對比文獻一致。函數f4、f5取群體規模分別為100和50做兩次試驗以方便與相關文獻進行比較，其余函數群體規模均為100。函數f5分別在群體規模為100、定義域為［-5，5］和群體規模為50、定義域為［-10，10］兩組參數下進行兩次試驗以方便與文獻［18］和文獻［19］進行比較。進化代數為1000。函數f2收斂精度要求1E-4，函數f6收斂精度要求1E-3，其它函數收斂精度要求均為1E-6。采用平均值、最優值、最差值和平均收斂代數作為算法評價標準。

通過優化結果比較發現，除函數f5以外，UD-PMGA算法對其它函數每次搜索到的最優解均相同，說明UD-PMGA算法有著非常強的穩定性。盡管UD-PMGA算法對表中個別函數收斂到指定精度的速度稍慢于IAGA、NCGA兩種算法，但其最終解的質量及算法的穩定性明顯優于兩種對比算法。本文在用UD-PMGA算法對函數f5進行仿真的過程中，首先采用前文2.1節中的第一種選擇方法進行選擇，但最終解的質量及算法穩定性并不理想，因此改用第二種選擇方法進行選擇操作。結果表明，采用第二種選擇方法可以獲得更優解及更高的穩定性，但算法的收斂速度明顯低于其它兩種算法。由此可以看出，第二種選擇方法是以收斂速度的下降為代價進而獲得更高質量的解及更高的算法穩定性。

表3所示為UD-PMGA對函數f7～f15的優化結果及與文獻［11］DMMGA算法、文獻［8］GACM算法的比較。算法參數設置與對比文獻一致。群體規模為100。f7進化100代，其他函數進化1000代。對函數f11、f14、f15，采用第二種選擇方法進行選擇操作，其他函數均采用第一種選擇方法。采用平均值和標準差兩個指標對算法進行評價。

從表3仿真結果看出，UD-PMGA對函數f7優化解的質量及算法穩定性明顯優于GACM算法，對函數f14的優化結果優于GACM算法幾個數量級，雖然不及DMMGA算法，但相差不大。對于其它所有函數，UD-PMGA算法所得優化結果相比兩種對比算法，解的平均值及標準差均有一個或幾個數量級的提高。總體來說，UD-PMGA算法在解的質量與算法穩定性方面要優于DMMGA和GACM兩種算法。為了與文獻［19］的算法進行全面比較，對UD-PMGA算法在參數設置為群體規模50、進化1000代、定義域為［-10，10］的情況下對函數f7進行仿真測試，所得最優解平均值為-1.03162845，標準差為0，仍然優于文獻所得結果-1.03162813。總體來說，UD-PMGA算法的搜索性能要優于NCGA算法。

表2 UD-PMGA與IAGA、NCGA算法的比較

表3 UD-PMGA與DMMGA、GACM算法的比較

圖2所示為函數f6用UD-PMGA算法和SGA算法優化的仿真結果。從仿真結果可以看出，UD-PMGA算法在收斂速度及收斂精度兩個方面的表現均優于SGA。在其它測試函數的仿真過程中發現，SGA對于部分單峰函數或低維函數的優化效果與UD-PMGA算法的優化效果相差并不太大，但對于多峰函數和高維函數，UD-PMGA算法的優越性變得非常明顯，這也說明了UD-PMGA算法對于標準遺傳算法的易陷入局部最優和局部搜索能力差的缺陷有了較大改善，驗證了本文算法的有效性。

通過對15個測試函數的仿真結果全面比較，相比其它文獻所提出的算法，對于低維函數，UD-PMGA算法能以非常高的穩定性收斂到全局最優解附近，所得最優解均優于其他對比算法，體現出UD-PMGA算法具有較高的搜索效率。這一方面得益于遺傳操作算子的改進對算法性能的提升，同時也說明基于全面均勻設計的初始群體能夠更加均勻地覆蓋解空間，提高了初始群體的多樣性，從而提高算法的搜索效率。相比于低維函數，UD-PMGA算法優化高維函數的穩定性遜色一些，這是因為高維函數的解空間非常大，初始群體對解空間的覆蓋率相對較低，均勻設計方法對算法效率的提升會有折扣，因此標準差并不為0，但由于采用改進的遺傳操作算子，UD-PMGA算法仍能到達函數最優解附近。

圖2 函數 f6用SGA和UD-PMGA算法優化對比

5 結語

本文針對標準遺傳算法收斂速度慢和局部搜索能力不足的缺點，提出UD-PMGA算法。算法采用完全均勻設計方法初始化種群，提出兩種改進的錦標賽機制進行選擇操作，降低算法的計算成本，同時增加種群的多樣性；提出如何選擇每個個體的最佳交叉對象，并用基于進化代數、個體適應度以及定義域自適應變化的變異比例和變異步長進行并行變異操作以提高算法的收斂速度和尋優精度。通過多個測試函數的仿真，與相關文獻算法進行比較，表明UD-PMGA算法具有較好的全局搜索能力和較高的局部搜索能力。但交叉對象的確定和并行變異操作增加了計算成本，使得UD-PMGA算法的運行時間較長，不利于算法的實際應用，因此如何以更低的計算成本獲得良好的搜索性能有待進一步研究，這也是遺傳算法及其它優化算法的改進與發展方向。