一種應(yīng)用動態(tài)區(qū)域劃分的多種群異構(gòu)進化算法*

沈丹萍

（蘇州信息職業(yè)技術(shù)學(xué)院計算機科學(xué)與技術(shù)系 蘇州 215200）

1 引言

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

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

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

2 應(yīng)用動態(tài)區(qū)域劃分的多種群異構(gòu)進化算法

運用差分進化算法（differential evolution algorithm，DE）和遺傳算法（genetic algorithm，GA）進行動態(tài)區(qū)域劃分搜索，多種群異構(gòu)策略見圖1。

圖1 多種群異構(gòu)策略

應(yīng)用動態(tài)區(qū)域劃分的多種群異構(gòu)進化算法見下式：

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

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

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

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

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

第5步：替換種群內(nèi)具有低適應(yīng)值的個體，得到｛b1，b2，…，bn｝。

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

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

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

搜索當(dāng)前最優(yōu)個體也采用同樣的方法。

3 實驗結(jié)果分析

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

表1 CEC2015函數(shù)庫

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

表2 CEC2015函數(shù)庫測試結(jié)果

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

根據(jù)上述結(jié)果可知，在所有維度下DD-MEA都具備更優(yōu)異的性能指標(biāo)，并且表現(xiàn)出更高的通用性以及穩(wěn)定性。

4 結(jié)語

1）構(gòu)建一種可以實現(xiàn)動態(tài)區(qū)域分類的多種群進化算法。從CEC2015函數(shù)庫內(nèi)選擇5個函數(shù)作為測試對象再對各算法進行了性能猜測試，以DD-MEA算法對算法各項性能指標(biāo)進行了測試。

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

3）F5函數(shù)表現(xiàn)出明顯的非對稱與旋轉(zhuǎn)特征，同時存在很多的局部最優(yōu)解，當(dāng)CA測試的維度不斷提高后，算法穩(wěn)定性也會不斷降低。在所有維度下DD-MEA都具備更優(yōu)異的性能指標(biāo)，并且表現(xiàn)出更高的通用性以及穩(wěn)定性。