周 丹 謝 敏 劉 方 韋 劍

(南京郵電大學(xué)通達(dá)學(xué)院計(jì)算機(jī)工程系 江蘇 揚(yáng)州 225127)

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

周 丹 謝 敏 劉 方 韋 劍

(南京郵電大學(xué)通達(dá)學(xué)院計(jì)算機(jī)工程系 江蘇 揚(yáng)州 225127)

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

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

0 引 言

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

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

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

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

1 網(wǎng)格選擇

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

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

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

圖1 網(wǎng)格選擇示意圖

2 子種群劃分

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

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

圖2 子種群劃分方法

3 精英分級(jí)協(xié)同進(jìn)化

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

3.1 精英協(xié)作

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

(1)

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

(2)

3.2 精英引導(dǎo)

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

(3)

FCO算子中的新個(gè)體由式(4)產(chǎn)生，其中1

(4)

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

為進(jìn)一步提高傳統(tǒng)分布估計(jì)算法解決多目標(biāo)優(yōu)化問(wèn)題的性能，本文結(jié)合精英協(xié)同和多種群劃分獨(dú)立進(jìn)化，提出一種基于雙精英協(xié)同的多種群分布估計(jì)算法?；舅枷肴缦拢阂环矫娌捎镁f(xié)同思想對(duì)種群進(jìn)行“微觀”層面的進(jìn)化，另一方面各個(gè)子種群結(jié)合該子種群中精英個(gè)體的濃度建模，確定進(jìn)化的方向和規(guī)模，保證種群的多樣性。具體算法步驟如下所示：

Step1 設(shè)置算法中的參數(shù)，種群規(guī)模為N，設(shè)置評(píng)價(jià)次數(shù)Max_e(參考文獻(xiàn)[18]中實(shí)驗(yàn)設(shè)計(jì)，Max_e設(shè)置為90 000次)，當(dāng)前評(píng)價(jià)次數(shù)Current_e=0(每次使用評(píng)價(jià)函數(shù)后Current_e=Current_e+1，Current_e=Max_e算法結(jié)束)，交叉概率Pcu=0.4，當(dāng)前代數(shù)t=0，隨機(jī)產(chǎn)生初始種群Pop(t)。

Step2 通過(guò)對(duì)種群中個(gè)體非支配排序得到精英種群Elite，采用網(wǎng)格選擇為精英個(gè)體分級(jí)為：級(jí)別1的精英種群EH，級(jí)別2的精英種群EL。

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

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

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

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

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

Step6 判斷當(dāng)前評(píng)價(jià)次數(shù)Current_e是否等于Max_e，如果相等算法結(jié)束輸出種群Pop，否則轉(zhuǎn)入Step2。

5 仿真實(shí)驗(yàn)

5.1 實(shí)驗(yàn)設(shè)計(jì)

何澤說(shuō)，代價(jià)真的不小，給老百姓付成本去了五萬(wàn)，工錢(qián)四萬(wàn)，運(yùn)輸和路上的繳費(fèi)花了近兩萬(wàn)，打點(diǎn)關(guān)系一萬(wàn)，我這棵樹(shù)的本錢(qián)就花了十四五萬(wàn)。何澤說(shuō)的數(shù)字，完全是自由發(fā)揮，讓一點(diǎn)都不懂?dāng)?shù)字和經(jīng)濟(jì)的我都有點(diǎn)好笑。其實(shí)他們盤(pán)弄我的總價(jià)，最多兩萬(wàn)塊錢(qián)。

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

表1 實(shí)驗(yàn)參數(shù)設(shè)置

5.2 評(píng)價(jià)指標(biāo)

采用以下指標(biāo)[3]來(lái)評(píng)價(jià)算法的優(yōu)劣：(1)時(shí)間測(cè)度T(相同評(píng)價(jià)次數(shù)下算法所用的時(shí)間)；(2)收性測(cè)度M1；(3)分布性測(cè)度SD；(4)覆蓋指標(biāo)C，并畫(huà)出Pareto前沿的圖形進(jìn)行比較。

5.3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

圖3 五種測(cè)試函數(shù)的優(yōu)化結(jié)果

6 結(jié) 語(yǔ)

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

[1] 公茂果,焦李成,楊咚咚,等.進(jìn)化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報(bào),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ì)算法[J].電子學(xué)報(bào),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ìn)化遺傳算法[J].軟件學(xué)報(bào),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é)同進(jìn)化數(shù)值優(yōu)化算法[J].軟件學(xué)報(bào),2009,20(11):2925-2938.

[16] 周丹,耿煥同,賈婷婷,等.一種基于雙精英種群的協(xié)同進(jìn)化算法研究[J].計(jì)算機(jī)應(yīng)用與軟件,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é)同進(jìn)化多目標(biāo)優(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。周丹，助教，主研領(lǐng)域：智能計(jì)算。謝敏，助教。劉方，助教。韋劍，助教。

TP183

A

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