一種應用動態區域劃分的多種群異構進化算法*

沈丹萍

（蘇州信息職業技術學院計算機科學與技術系 蘇州 215200）

1 引言

當前，進化算法被大量應用在對各類復雜問題的優化分析，同時還可以使用多種群策略方法來實現子種群對解空間各區域實現進化的過程，也可以利用遷移等方式為不同子種群間構建信息傳輸通道，通常將這種算法稱作多種群進化算法［1～7］。隨著研究的不斷深入，一些學者利用個體相似性、分布特征來完成進化，并選擇聚類方法對種群與搜索空間實施分類。有學者在文獻［8］中利用聚類算法對搜索區域實施分類獲得不同等級，同時重點搜索高等級區域以實現縮小搜索空間的目的，由此顯著提升收斂速率以及減小復雜度。還有學者［9］創建了一種高效的多種群遺傳算法，通過新的相似性函數來判斷二個點是否在相同集群內，由此實現把種群分成N個小集群的目標。文獻［10］構建得到一種可以對多個子種群進行參數自適應差分處理的進化算法，并使子種群完成信息的循環共享，利用上級子種群最優個體為本種群進化提供引導作用。

文獻［11］針對不同差分進化模型的具體特征來為子種群構建動態分配方法，由此實現不同策略的相互協同過程，之后對算法進行了測試發現利用該算法能夠實現性能的明顯優化。文獻［12］通過以并行差分的進化策略對種群聚類進行優化，使子種群獲得更強的通信遷移性能。文獻［13］主要研究了不同策略在協同進化過程中存在的貢獻度差異性，引入多種群協同的方式降低算法搜索范圍，從而更快速計算出全局最優解。

通過分析以上研究結果可知，引入多種群策略可以使進化算法獲得更高效的求解性能，這為利用進化算法來求解各類復雜優化問題創建了新思路［14～15］。但是，現階段利用多種群策略來實現的進化算法還存在如下不足之處：首先，通過拓撲結構來進行區間分類時無法判斷各區間重要性，也不能獲得子種群差異性；其次，通過異構方法來劃分區域時只能完成特定空間的處理；第三，關于如何對種群進行分類未建立統一標準，同時缺乏可靠的理論基礎，無法確保劃分得到的區域可以獲得比原先區域存在更大概率的最優解［16～17］。根據以上分析，本文構建了一種可以實現區域動態分類的高效率多種群進化算法，可以實現在原問題中融入云模型的分析方法再對原問題進行重新估計，再劃分經過估計處理得到的新問題對應的解空間，通過這種方式建立得到一套劃分子種群的參考體系，并使種群搜索范圍獲得有效縮小，實現問題求解難度的明顯減小。

2 應用動態區域劃分的多種群異構進化算法

運用差分進化算法（differential evolution algorithm，DE）和遺傳算法（genetic algorithm，GA）進行動態區域劃分搜索，多種群異構策略見圖1。

圖1 多種群異構策略

應用動態區域劃分的多種群異構進化算法見下式：

在分析實際優化問題時，需先構建合適的云模型再重新實施估計，按照估計得到的新問題來分類解空間，分別包括期望區域和違背區域共兩類，再對劃分形成的子區域運用特定搜索方法來降低搜索區域范圍，減小問題的求解難度，由此實現簡化問題求解過程的目標。針對以上分析結果，本文構建得到一種通過動態區域劃分來實現的多種群進化算法（DD-MEA），可將其分為如下幾個步驟：

第1步：對種群實施初始化，以t表示進化代數，Pt表示初始化種群。

第2步：通過問題適應值曲面對算子評估后建立云模型Ct=［Ex（t），En（t），He（t）］。

第3步：利用區域劃分算子把解空間分成期望區域EAt以及違背區域BAt，由此獲得代表個體｛b1，b2，…，bn｝。

第4步：統計適應值。計算y1=fg（Pt），y2=fc（Pt），通過評價算子來估計適應值，將其表示為fitness（Pt）=max（y1，y2）。

第5步：替換種群內具有低適應值的個體，得到｛b1，b2，…，bn｝。

第6步：完成各項遺傳操作之后對種群實施更新。

第7步：對算子進行評價并更新評價集。

第8步：條件判斷結束。如果t>tmax，整個算法完成并將結果輸出，反之跳至第2步。

搜索當前最優個體也采用同樣的方法。

3 實驗結果分析

本文從CEC2015函數庫內選擇5個函數作為測試對象再對各算法進行了性能測試，對應的種群規模是200。采用上述測試函數對各算法分別以不同維度單獨運行30次，同時將進化代數設定在500。綜合分析了本文算法和其它算法的尋優性能，新增了5個測試函數，最后以DD-MEA算法對算法各項性能指標進行了測試。

表1 CEC2015函數庫

從表2中可以看到函數測試所得的結果，f代表算法平均尋優結果，是對30次尋優處理得到的目標值進行取平均計算所得的結果；s表示平均收斂代數，是算法收斂獲得全局最優解的進化代數平均值；t代表平均收斂時間，是在符合收斂條件的情況下需要達到的平均時間，其單位是s；“+”代表相同條件下采用本文算法計算得到的結果，跟其它算法存在明顯區別，同時對結果進行T檢驗，設定顯著性水平等于0.05。結果顯示，本文算法達到了最優的性能指標。

表2 CEC2015函數庫測試結果

通過分析表2結果可知，采用二維F1與F5函數進行優化處理后發現上述各算法都可以獲得最優解。在同樣的種群規模下時，DD-MEA可以獲得最小的平均收斂代數并顯著降低收斂時間，由此可以推斷DD-MEA的尋優速率明顯優于其它算法。F2函數是一種單峰的不可分離函數，隨著F2函數到達30維數時，CA與DE基本不能獲得全局最優解；CGA可以獲得接近最優解的結果，并且需要花費很長的進化時間；DD-MEA除了可以求解出全局最優解之外，還可以實現比CGA更小的進化代數并降低尋優時間，總體性能比其余各算法更優異。F3函數是一種多模態函數，并存在一個窄峽谷，F4函數是一種包含多峰結構的非均勻函數，導致算法函數值更易產生局部最優解。運用F3與F4函數時，CA、DE以及DD-MEA處于低維條件下可以求得最優解，不過性能指標和其它各算法相比具有較大差異，當維數超過5之后，CA、DE與CGA無法計算出最優解，得到的結果已經發生了大幅波動，DD-MEA計算結果出現于最優解附近，可以計算出跟最優解相近的結果。F5函數表現出明顯的非對稱與旋轉特征，同時存在很多的局部最優解，當CA測試的維度不斷提高后，算法穩定性也會不斷降低；處于低緯度條件下，DE可以獲得最優解；對于DD-MEA來說，除了可以在低維條件下獲得最優解以外，還可以有效縮短處理時間，并在高維求解過程中得到跟全局最優解相近的結果。F5是一個可分離與不對稱的函數，處于低維數狀態下時，上述各算法都可以計算出最優解。如果按照時間進行評價，CGA與DD-MEA具備CA與DE更優的性能且存在顯著差異性。

根據上述結果可知，在所有維度下DD-MEA都具備更優異的性能指標，并且表現出更高的通用性以及穩定性。

4 結語

1）構建一種可以實現動態區域分類的多種群進化算法。從CEC2015函數庫內選擇5個函數作為測試對象再對各算法進行了性能猜測試，以DD-MEA算法對算法各項性能指標進行了測試。

2）采用二維F1與F5函數進行優化處理后發現上述各算法都可以獲得最優解。在同樣的種群規模下時，DD-MEA可以獲得最小的平均收斂代數并顯著降低收斂時間，由此可以推斷DD-MEA的尋優速率明顯優于其它算法。

3）F5函數表現出明顯的非對稱與旋轉特征，同時存在很多的局部最優解，當CA測試的維度不斷提高后，算法穩定性也會不斷降低。在所有維度下DD-MEA都具備更優異的性能指標，并且表現出更高的通用性以及穩定性。