基于精英協(xié)同的多種群分布估計算法

周 丹 謝 敏 劉 方 韋 劍

(南京郵電大學通達學院計算機工程系 江蘇 揚州 225127)

基于精英協(xié)同的多種群分布估計算法

周 丹 謝 敏 劉 方 韋 劍

(南京郵電大學通達學院計算機工程系 江蘇 揚州 225127)

針對傳統(tǒng)分布估計算法局部搜索能力弱，易陷入早熟收斂的問題，在分布估計算法的基礎上引入精英策略并采用劃分子種群獨立進化的方式，提出一種基于精英協(xié)同的多種群分布估計算法。該算法混合了兩種后代產生的策略：一種是進化過程采用精英協(xié)同操作用于進行局部搜索并開辟出新的搜索空間，另一種是采用劃分子種群獨立進化方式保證種群間個體的多樣性?；鶞蕼y試函數實驗結果表明，該算法在收斂性和多樣性方面均表現(xiàn)出明顯優(yōu)勢。

分布估計算法 早熟收斂 精英協(xié)同 子種群

0 引 言

多目標優(yōu)化問題在工程實踐和科學研究中一直是非常重要的研究課題之一[1]，現(xiàn)實生活中的優(yōu)化問題往往受到多個相互沖突目標的影響，該類多目標優(yōu)化問題存在一個Pareto[2]最優(yōu)解。為了研究解決多目標優(yōu)化問題，國內外學者分別提出了不同的多目標進化算法，比如：NSGA-II[3]、MOPSO[4]、RM-MEDA[5]、NNIA[6]等。

分布估計算法EDA(Estimation of Distribution Algorithm)是一類新型的優(yōu)化算法。EDA首先采用統(tǒng)計分析的方法對較優(yōu)秀的個體進行統(tǒng)計分析，然后根據分析結果建立概率模型并通過采樣產生下一代解， 最后經過不斷的重復統(tǒng)計建模和采樣過程，得到問題的最優(yōu)解。分布估計算法與傳統(tǒng)進化算法不同：沒有類似遺傳算法中的交叉、變異操作，是基于對種群的進化趨勢進行統(tǒng)計，根據統(tǒng)計結果建立模型，利用進化思想對建立的模型進行進化。綜上，EDA算法是一種“宏觀”層面的進化，具有良好的全局搜索能力，但與此同時局部搜索能力不足。

分析EDA局部搜索能力差，易陷入早熟收斂的原因：(1) EDA沒有類似于交叉、變異等基于“微觀”層面上的進化操作或建模。(2) 在整個進化期間隨著進化代數的增加，種群間個體不斷接近，降低了種群的多樣性。為了解決以上不足，學者們提出了不同的改進方案：Zhang等學者針對多目標優(yōu)化問題提出了RM-MEDA[5]；程玉虎等在傳統(tǒng)EDA基礎上結合混沌變異操作提出了EDA-DP[7]；Madera等結合子種群劃分獨立進化提出了dEDA[8]。

在上述算法的基礎之上，提出一種基于精英協(xié)同的多種群分布估計算法。該算法將初始種群的非支配個體根據網格選擇，分為兩個不同級別的精英種群，兩個精英種群協(xié)同操作，促進精英個體的進化。將初始種群根據子種群劃分，劃分為若干個子種群，每一個子種群對應一個概率分布模型，結合子種群精英個體的濃度各自獨立的進化，以保證該算法不僅具有更好的全局收斂性，且能夠更好地保證種群的多樣性。

1 網格選擇

為進一步發(fā)揮精英個體的優(yōu)勢地位，為每一個非支配解確定級別。首先對種群中個體進行非支配排序，可得到非支配解集合Elite，采用網格選擇將非支配解集合Elite分為級別1的精英種群EH和級別2的精英種群EL。

網格選擇基本思想如下：為解分配辨識向量的ε支配計算方法[13](ε是一個可以事先預設的參數)，在為每一個解分配一個辨識向量，即給該解分配了一個生存區(qū)域，劃分生存區(qū)域的機制可根據解本身的取值來自適應地分配。在進化初期，由于非支配個體較少，可適當將ε的值取大，后期隨著進化代數的增加，非支配個體較多，可適當降低ε的取值。

如圖1所示，對圖中非支配個體進行網格選擇，其中個體‘1’、‘2’和‘3’處于同一生存區(qū)域內，個體‘2’距它們共同的辨識向量‘A’較近，所以被保留，而‘3’和極端解‘1’由于距A較遠而被刪除。由于極端解對應某一目標函數的極值，對整個解集的分布和最終決策的選擇具有重要意義，所以極端解‘1’不應被刪除。最終該區(qū)域中‘1’、‘2’都會被保留。該生存區(qū)域網格選擇結果為：個體‘1’、‘2’定義為級別1種群EH中的精英個體，個體‘3’定義為級別2種群EL中的精英個體。

圖1 網格選擇示意圖

2 子種群劃分

傳統(tǒng)EDA隨著進化代數的增加，種群間個體逐步接近，種群多樣性差。為提高算法多樣性，將整個種群分成若干個子種群，每個子種群獨立的建模進化，設將目標函數空間劃分成S個子種群，具體劃分方式如下：(1) 種群中全部個體劃分到第一象限，為單位超球面選擇S個分布均勻的單位向量，S個子種群的中間向量為w1,w2,…,ws。(2) 所有個體結合目標方程計算個體與S個中間向量(w1,w2,…,ws)的夾角，夾角值為(v1,v2,…,vs)若vi(i=1,2,…,s)最小，則將該個體分配給i子種群。

如圖2所示二目標為例，將種群分成S(S=6)個子種群。w1,w2,…,w6為S個子種群的中間向量，計算個體A和B與S個中間向量的夾角并進行比較，通過比較將A分配給w5所在的子種群，將B分配給w6所在的子種群。

圖2 子種群劃分方法

3 精英分級協(xié)同進化

為了提高算法的收斂性，級別1精英種群EH和級別2精英種群EL采用協(xié)同進化策略[11]推動精英個體的進化。EH內個體采用長方體交叉算子CCOI算子相互協(xié)作，產生高質量解；EH對EL進行引導，引導操作時采用CCOI[15]算子，并根據個體之間的距離，離散交叉算子DCO[15]算子、翻轉交叉算子FCO[15]算子交互使用，推進相似個體的進化，避免進化陷入局部最優(yōu)。

3.1 精英協(xié)作

精英協(xié)作是指兩個EH中的個體合作進化，提高父代解質量。CCOI算子中的新個體由式(1)產生，其中λk=U(0,2)。用x和y表示來自EH的兩個父代個體，用zu和zv表示中間狀態(tài)，用u和v分別表示x和y在精英協(xié)作之后產生的個體。

(1)

用式(2)判斷新產生的個體是否超出解空間的約束范圍，未超出解空間的新個體若可支配其父代個體，則更新到子代中。

(2)

3.2 精英引導

精英引導是指一個EH個體對EL個體的引導，促進EL中個體向EH中個體靠近。用x和y表示來自EH和EL的兩個父代個體，用zu和zv表示中間狀態(tài)。用式(2)判斷新產生的個體是否超出解空間的約束范圍，未超出解空間的新個體若可支配其父代個體，則更新到子代中。

(3)

FCO算子中的新個體由式(4)產生，其中1

(4)

4 基于雙精英協(xié)同的多種群分布估計算法

為進一步提高傳統(tǒng)分布估計算法解決多目標優(yōu)化問題的性能，本文結合精英協(xié)同和多種群劃分獨立進化，提出一種基于雙精英協(xié)同的多種群分布估計算法。基本思想如下：一方面采用精英協(xié)同思想對種群進行“微觀”層面的進化，另一方面各個子種群結合該子種群中精英個體的濃度建模，確定進化的方向和規(guī)模，保證種群的多樣性。具體算法步驟如下所示：

Step1 設置算法中的參數，種群規(guī)模為N，設置評價次數Max_e(參考文獻[18]中實驗設計，Max_e設置為90 000次)，當前評價次數Current_e=0(每次使用評價函數后Current_e=Current_e+1，Current_e=Max_e算法結束)，交叉概率Pcu=0.4，當前代數t=0，隨機產生初始種群Pop(t)。

Step2 通過對種群中個體非支配排序得到精英種群Elite，采用網格選擇為精英個體分級為：級別1的精英種群EH，級別2的精英種群EL。

Step3 根據子種群劃分得到S=6個子種群，確立各種群中的所有個體。

Step5 通過統(tǒng)計子種群中精英個體濃度確定分布估計算法方向與規(guī)模：根據精英個體在各個子種群中分布的濃度確定高斯分布的方向和規(guī)模，新生成的種群與父代種群合并個體濃度選取N個個體組成下一代種群Pop(t+1)。算法步驟如下：

(1) 子種群進化方向確定：經精英協(xié)同操作之后，種群EH和種群EL合并得精英種群ET，采用輪盤賭策略，根據ET種群中個體在各個子種群中分布的濃度比例確定各個子種群被選中建立概率模型的機率。具體如下：設種群數為S，種群ET在各個子種群的總濃度為eTotal=e1+e2+…+es=1，根據ei(i=1,2,…,s)的高低采用輪盤賭策略選擇一個子種群建立概率模型，輪盤賭策略原則為：精英個體濃度高的子種群被選中的概率低，精英個體濃度低的子種群被選中的概率高。

(2) 子種群進化規(guī)模確定：按建立的概率模型為選定的子種群產生N/ei(i=1,2,…,s)個新的個體。

(3) 后代種群選擇：新生成的個體與父代種群根據采用NSGA-II中擁擠距離比較算子[3]，選取規(guī)模為N的下一代種群Pop(t+1)。

Step6 判斷當前評價次數Current_e是否等于Max_e，如果相等算法結束輸出種群Pop，否則轉入Step2。

5 仿真實驗

5.1 實驗設計

何澤說，代價真的不小，給老百姓付成本去了五萬，工錢四萬，運輸和路上的繳費花了近兩萬，打點關系一萬，我這棵樹的本錢就花了十四五萬。何澤說的數字，完全是自由發(fā)揮，讓一點都不懂數字和經濟的我都有點好笑。其實他們盤弄我的總價，最多兩萬塊錢。

為檢驗本文算法的性能，在同一臺計算機的MatlabR2010b環(huán)境中，采用如表1中設置的實驗參數，結合著名的ZDT1、ZDT2、ZDT3、ZDT4、ZDT6[17]這5個測試函數對本文算法獨立運行30次進行測試，ZDT問題于2000年由Zitzler，Deb以及Thiele提出，其中ZDT1、ZDT2、ZDT3比較簡單。ZDT4與ZDT6的求解難度大，因為在ZDT4的搜索空間中，一共有219個不同的局部最優(yōu)前沿；ZDT6問題的Pareto前沿上的最優(yōu)解分布不均勻，且越接近Pareto前沿其解分布越不均勻。對ZDT1、ZDT2、ZDT3、ZDT4、ZDT6函數的求解，能有效檢驗算法的性能。將實驗結果與NSGA-II算法[3]、DEPEA算法[16]進行對比并根據實驗結果分析算法性能。NSGA-II算法采用基于種群個體分級快速非支配排序方法和擁擠距離比較算子提高算法進化性能；DEPEA算法采用基于子種群分級的方式結合多種算子推動算法進化。

表1 實驗參數設置

5.2 評價指標

采用以下指標[3]來評價算法的優(yōu)劣：(1)時間測度T(相同評價次數下算法所用的時間)；(2)收性測度M1；(3)分布性測度SD；(4)覆蓋指標C，并畫出Pareto前沿的圖形進行比較。

5.3 實驗結果與分析

表2和表3給出了5個標準測試函數獨立運行30次以下本文算法和NSGA-II算法(1)T、(2)M1、(3)SD、(4)C指標的平均值。表4給出了5個標準測試函數獨立運行30次以下本文算法和DEPEA(1)M1(2)SD指標的平均值。圖3(a)、(b)、(c)、(d)及(e)給出本文算法算法對5個標準測試函數的優(yōu)化結果與它們的真實Pareto前沿。

如表2和表3所示，本文算法在測試函數ZDT1、ZDT2、ZDT3、ZDT4及ZDT6上的測試結果T、M1、SD和C指標的平均值都明顯優(yōu)于NSGA-II。由于本文算法對精英種群的劃分是根據非支配解結合網格選擇得到兩個不同級別的精英種群，不同于NSGA-II基于種群個體分級快速非支配排序確定多個級別的種群的方式，因而本文算法的時間消耗(T)要明顯低于NSGA-II。NSGA-II只有單一的模擬二進制交叉算子[3]，而本文算法采用了多種算子配合推進算法進化，尤其當個體較為接近時，配合使用翻轉交叉算子FCO，能夠將某些維上好的結果迅速地傳到其他維上，因而算法不易陷入局部最優(yōu)，收斂性較好(M1)。為保證種群多樣性，本文算法劃分多個子種群，每個子種群建立概率模型并根據精英個體的濃度獨立的進化，保證種群多樣性，因而算法有較好的分布性(SD)。

表2 本文算法在T、M1、SD和C測度上的比較

表3 NSGA-II在T、M1、SD和C測度上的比較

如表4所示，本文算法在測試函數ZDT4、ZDT6這2個標準測試函數上面實驗結果明顯都優(yōu)于DEPEA算法。ZDT4、ZDT6問題求解的難度較大，本文算法能夠搜索出ZDT4函數219個其中的唯一的全局的Pareto最優(yōu)前沿，說明該算法有較好的全局搜索能力，與DEPEA算法相比，由于采用了基于子種群進化的方式，在進化的同時有考慮精英個體的濃度，因而有效的保證種群的多樣性，避免陷入局部最優(yōu)，所以保證了收斂性(M1)和分布性(SD)。本文算法求解ZDT6問題時最終得到的解都是收斂的，未出現(xiàn)不收斂的解，由于在劃分兩個精英種群時采用了網格選擇，可以更好地選擇出高級別的精英個體。結合三種交叉算子能夠更好地對不同級別的精英個體進行進化操作，推進算法持續(xù)進化，避免陷入局部最優(yōu)，保證算法的勘探和探索能力。

表4 本文算法、DEPEA在CM、SD測度上的比較

圖3 五種測試函數的優(yōu)化結果

6 結 語

本文在分布估計算法的基礎上引入精英協(xié)同進化和多種群獨立進化思想，提出了一種基于精英協(xié)同的多種群分布估計算法本文算法。該算法采用精英協(xié)同策略將精英個體分成不同級別的種群，對不同級別的精英個體采用不同的進化操作，可避免算法陷入局部最優(yōu)。它的多種群獨立進化方式能將整個種群分成若干個子種群，各個子種群獨立進化，解決傳統(tǒng)EDA個體隨進化代數增加逐步接近，種群多樣性差的問題，避免陷入早熟收斂。通過以上策略保證算法的探查和探究能力，結合實驗結果分析可見：該算法與NSGA-II算法、DEPEA算法相比，Pareto最優(yōu)解收斂更快，分布更加均勻。

[1] 公茂果,焦李成,楊咚咚,等.進化多目標優(yōu)化算法研究[J].軟件學報,2009,20(2):271-289.

[2] Horn J,Nafpliotis N,Goldberg D E.A Niched Pareto Genetic Algorithm for Multi-objective Optimization[C]//Proceedings of the lst IEEE Conference on Evolutionary Computation.Piscataway:IEEE Press,1994:82-87.

[3] Deb K,Pratap A,Agaiwal S,et al.A Fast and Elitist Multi-objective Genetic Algorithm:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[4] Coello C A C,Lechuga M S.MOPSO:A proposal for multiple objective particle swarm optimization[C]//Proceedings of the 2002 Congress on Evolutionary Computation.IEEE,2002,2:1051-1056.

[5] Zhang Q,Zhou A,Jin Y.RM-MEDA:A regularity model-based multiobjective estimation of distribution algorithm[J].IEEE Transactions on Evolutionary Computation,2008,12(1):41-63.

[6] Gong M,Jiao L,Du H,et al.Multiobjective immune algorithm with nondominated neighbor-based selection[J].Evolutionary Computation,2008,16(2):225-255.

[7] 程玉虎,王雪松,郝名林.一種多樣性保持的分布估計算法[J].電子學報,2010,38(3):591-597.

[8] Madera J,Alba E,Ochoa A.A parallel island model for estimation of distribution algorithms[M].Towards a New Evolutionary Computation.Springer,2006:159-186.

[9] Hastie T,Stuetzle W.Principal curves[J].Journal of the American Statistical Association,1989,84(406):502-516.

[10] Liu H,Li X.The multiobjective evolutionary algorithm based on determined weight and sub-regional search[C]//IEEE Congress on Evolutionary Computation.IEEE,2009:1928-1934.

[11] 劉全,王曉燕,傅啟明,等.雙精英協(xié)同進化遺傳算法[J].軟件學報,2012,23(4):765-775.

[12] Zhou S,Sun Z.A survey on estimation of distribution algorithms[J].Acta Automatica Sinica,2007,33(2):113-124.

[13] Deb K,Mohan M,Mishra S.Towards a quick computation of well-spread pareto-optimal solutions[C]//Proceedings of the 2nd International Conference on Evolutionary Multi-criterion Optimization.Springer,2003:222-236.

[14] Potter M A,Jong K A D.A cooperative coevolutionary approach to function optimization[C]//The Third Conference on Parallel Problem Solving from Nature (PPSN III).London:Springer,1994:249-257.

[15] 慕彩紅,焦李成,劉逸.M-精英協(xié)同進化數值優(yōu)化算法[J].軟件學報,2009,20(11):2925-2938.

[16] 周丹,耿煥同,賈婷婷,等.一種基于雙精英種群的協(xié)同進化算法研究[J].計算機應用與軟件,2015,32(2):244-248,271.

[17] Zitzler E,Deb K,Thiele L.Comparison of multiobjective evolutionary algorithms: Empirical results[J].Evolutionary Computation,2000,8(2):173-195.

[18] 耿煥同,朱海峰,張茜,等.均衡分布性與收斂性的協(xié)同進化多目標優(yōu)化算法[J].控制與決策,2013,28(1):55-60.

MULTI-POPULATION ESTIMATION OF DISTRIBUTION ALGORITHM BASED ON ELITE COOPERATION

Zhou Dan Xie Min Liu Fang Wei Jian

(DepartmentofComputerEngineering,TongdaCollege,NanjingUniversityofPostsandTelecommunications,Yangzhou225127,Jiangsu,China)

Aiming at the problem of weak ability of local search and falling into premature convergence easily which exist in the traditional estimation of distribution algorithm(EDA), a new algorithm based on the distributed estimation algorithm is proposed to solve the problems. In this algorithm,the elite strategy is introduced and the method of dividing the sub populations is adopted. The algorithm combines two types of reproducing strategies,one is using the elite cooperative operation for local search the evolution process and developing new searching areas, the other is dividing population into sub ones to ensure the diversity by independent evolution. Experimental results of benchmark test functions show that the algorithm has obvious advantages in both convergence and diversity.

Estimation of distribution algorithm Premature convergence Elite cooperation Sub population

2015-11-26。周丹，助教，主研領域：智能計算。謝敏，助教。劉方，助教。韋劍，助教。

TP183

A

10.3969/j.issn.1000-386x.2017.01.051