閆曉梅，王麗芳，嚴莉娜

(太原科技大學(xué)電子信息工程學(xué)院，太原 030024)

分布估計算法源于遺傳算法，用估計算子和采樣算子代替了遺傳算法中的交叉算子和變異算子，避免了遺傳算法中存在的構(gòu)造塊被破壞的問題[1]。分布估計算法的概念是在1996年正式提出的[2]，但該算法最早的代表性研究成果是1994年提出的PBIL算法[3]。由于分布估計算法從宏觀上控制算法的進化方向，而且分布估計算法具有良好的理論基礎(chǔ)，因此引起了國內(nèi)外學(xué)者的廣泛關(guān)注，成為智能計算領(lǐng)域的研究熱點之一[4]。學(xué)者們針對分布估計算法提出了不同的改進策略[5]和具有不同估計采樣算子的算法[6]，并在諸多領(lǐng)域進行了應(yīng)用方面的研究[7-8]。

Copula分布估計算法是將Copula理論用于分布估計算法的估計和采樣之中，將多變量的聯(lián)合分布函數(shù)分解成一個Copula函數(shù)和多個單變量的分布函數(shù)，并由此構(gòu)造出不同的估計算子和采樣算子[9]。經(jīng)驗Copula分布估計算法是根據(jù)群體的分布情況構(gòu)造經(jīng)驗函數(shù)，建立了相應(yīng)的采樣算子。經(jīng)驗Copula分布估計算法是一種全局優(yōu)化算法，對于標準測試問題的優(yōu)化，它能夠很快搜索到全局最優(yōu)解的附近，但是后期的搜索就很慢。從文獻[10]的實驗結(jié)果中也可以很清楚地看到這一點。在算法搜索后期，雖然每代都有進化，但是進化的速度非常慢，每一代的改變也非常小。這些情況說明經(jīng)驗Copula分布估計算法的全局搜索能力強，而局部求精的能力弱。因此在經(jīng)驗Copula分布估計算法中可以引入局部求精能力強，收斂速度快的局部搜索算法。

1 經(jīng)驗Copula分布估計算法與爬山法的混合優(yōu)化算法

爬山法是一種局部搜索算法，如果從適當?shù)钠鹗嘉恢瞄_始，那么用爬山法可以很快搜索到局部的極值點。在經(jīng)驗Copula分布估計算法進化的過程中，可以加入局部搜索算法，以增強算法的局部求精能力。在經(jīng)驗Copula分布估計算法中，每個新個體的產(chǎn)生都是根據(jù)上一代優(yōu)勢群體的分布模型產(chǎn)生的，產(chǎn)生規(guī)則單一，致使新一代群體個性差異較小。增加群體中的個性差異，同時又不能過于背離群體的分布模型，是改進算法的一個思路。當經(jīng)驗Copula分布估計算法進化一代后，隨機選擇若干個體進行局部搜索，將搜索得到的新個體作為新一代群體中的一部分參與進化。這樣在算法中增加了個體的差異性，同時對群體的進化方向不會有很大的影響。

算法的具體步驟如下：

(1)初始化群體。在m維搜索空間中隨機產(chǎn)生N個個體，組成初始群體。確定選擇率s和變異率t.

(2)評價適應(yīng)值。根據(jù)相應(yīng)的評價標準對群體中的每個個體評價，得到每個個體的適應(yīng)值。

(3)如果達到算法終止條件，例如達到規(guī)定的進化代數(shù)或相鄰若干代群體的最優(yōu)適應(yīng)值沒有變化，則算法停止，群體中的最優(yōu)個體即為優(yōu)化的結(jié)果。否則執(zhí)行步驟(4).

(4)精英保留。以最小化問題為例，將群體中適應(yīng)值最小的個體保留至下一代。

(5)選擇優(yōu)勢群體。采用截斷選擇或比例選擇等選擇算子，從當前群體中選出s*N個適應(yīng)值較小的個體組成優(yōu)勢群體。

(6)爬山法搜索。從當前群體或優(yōu)勢群體中隨機選擇t*N個個體為起始點進行爬山法搜索，得到t*N個新個體，將這些新個體作為新一代群體中的一部分。

(7)估計概率模型。根據(jù)選擇出的優(yōu)勢群體，利用文獻[10]中的算法1構(gòu)造經(jīng)驗Copula函數(shù)，并估計各維的邊緣分布函數(shù)。

(8)采樣得到新個體。根據(jù)經(jīng)驗Copula函數(shù)采樣得到一組(0，1)區(qū)間內(nèi)的隨機數(shù)，然后根據(jù)邊緣分布函數(shù)采樣得到(1-t)N-1個新個體。

(9)由以上的N個個體組成新一代群體，繼續(xù)執(zhí)行步驟(2).

2 初始種群均勻化策略

在群體智能優(yōu)化算法中，初始種群要盡可能均勻地且互不相關(guān)地分散在搜索空間中。在以往實驗時往往直接利用隨機函數(shù)產(chǎn)生初始種群。圖1顯示了在二維搜索空間中隨機產(chǎn)生的群體，從中可見許多相鄰的網(wǎng)格中都沒有個體存在。這樣對算法的優(yōu)化結(jié)果會有一定的影響。因此需要設(shè)計一種均勻初始種群的產(chǎn)生策略。

該策略的基本思想就是將搜索空間中的每一維平均分成若干長度相等的區(qū)間，這樣整個搜索空間就分成了若干小區(qū)域。例如圖2中的二維搜索空間，用虛線將搜索空間分成了10×10的小區(qū)域，然后在每個小區(qū)域中隨機產(chǎn)生一個個體，從而組成在搜索空間中均勻分布的且互不相關(guān)的群體。如果按維數(shù)在每個小區(qū)域中依次產(chǎn)生個體，那么算法嵌套的層數(shù)會很深。因此需設(shè)計一種易行的產(chǎn)生策略。

圖1 隨機初始化種群Fig.1 The randomized population

圖2 均勻初始化種群Fig.2 The evenly-randomized population

為敘述方便，設(shè)搜索空間中每維的長度相等。以二維搜索空間為例，對二維搜索空間的每一維二等分，則將其劃分成了四個子空間，設(shè)每個子空間的邊長為h.如圖3所示，對每個子空間編號，分別是00，01，10，11，這四個編號恰好是兩位的二進制編碼，其產(chǎn)生方法可以采用基二算法或反射Gray碼算法即可獲得[11]。這樣在編號為00的子空間中隨機產(chǎn)生一個點(p，q)，那么(p，q)+(0，1)h就得到了01子空間中的一個點。其余子空間也相同。也就是說，在編號為00的子空間中隨機產(chǎn)生四個點，分別加上(0，0)，(0，h)，(h，0)和(h，h)就得到了上面論述中需要的四個隨機點，它們均勻地且互不相關(guān)地分散在搜索空間中。

對于M維搜索空間，若每一維二等分，則將其劃分成2M個子空間，對這些子空間編號，則形成M位二進制編碼。如三維搜索空間的每維二等分子空間編號為000，001，010，011，100，101，110，111.同樣，在編號為(00…0)的子空間中隨機產(chǎn)生2M個M維數(shù)，分別加上子空間編號(k1，k2，…，kM)h(其中，ki=0或1，2，…，M)就得到了相應(yīng)子空間中的隨機點。

上述方法只是將每維空間二等分。若要將每維空間四等分，則可使用兩層嵌套。不妨記每個子空間的邊長仍為h.例如先產(chǎn)生編號為00空間的一個隨機點(p，q)，那么(p，q)+(0，1)h+(1，1)2h就是編號為23的子空間中的點，如圖4所示。即編號為00空間的一個隨機點，先加上(0，0)h，(0，1)h，(1，0)h，或(1，1)h，再加上(0，0)2h，(0，1)2h，(1，0)2h，或(1，1)2h便可得任一子空間中的點。

圖3 二等分圖

圖4 四等分圖

對于M維搜索空間，若每一維四等分，則將其劃分成4M個子空間，不妨將每個子空間的邊長仍記為h.在編號為(00…0)的子空間中隨機產(chǎn)生4M個M維數(shù)，分別加上子空間編號(k1，k2，…，kM)h+(l1，l2，…，lM)2h(其中，ki=0或1，li=0或1，i=1，2，…，M)就得到了相應(yīng)子空間中的隨機點。

推而廣之，對于M維搜索空間，若每一維2n等分，則將其劃分成(2n)M個子空間，不妨將每個子空間的邊長仍記為h.則要在每個子空間中產(chǎn)生一個點需要s層嵌套。在編號為(00…0)的子空間中隨機產(chǎn)生(2n)M個M維數(shù)，分別加上 (k11，k12，…，k1M)h+(k21，k22，…，k2M)2h+…+(kn1，kn2，…，knM)(2n)h(其中，kij=0或1，i=1，2，…n，j=1，2，…，M)就得到了每個子空間中的隨機點。

以M維搜索空間，每一維四等分為例，該均勻初始化策略的算法步驟如下：

(1)按文獻[11]中的基二算法或反射Gray碼生成算法，產(chǎn)生2M個M位二進制編碼，保存在M×2M的二維數(shù)組A中，則每一列為一個二進制編碼。

(2)k=1；

for(i=1…2M)

for(j=1…2M)

pop(k)=A(i)h+A(j)2h+rand()

k=k+1；

end

end

在該算法中同樣設(shè)每維搜索范圍為[a，b]，則h=(b-a)/4，算法中rand()表示一個由a～a+h之間隨機數(shù)組成的M維列向量，pop中保存的就是均勻初始化得到的2M×2M=4M個個體。

3 仿真實驗

為測試算法性能，并與基本的經(jīng)驗Copula分布估計算法進行比較，對下面三個最小化標準測試函數(shù)進行測試。

與文獻[10]相同，問題維數(shù)D=10，三個問題的群體規(guī)模分別是2000、2000和750.算法最大的適應(yīng)值評價次數(shù)是300 000次，并使用截斷選擇算子進行優(yōu)勢群體的選擇。算法選擇率為0.5，變異率為0.05.采樣時使用的方差有下面三種策略。

A.方差為固定值。

實驗結(jié)果如表1-表3所示。其中文獻[10]中的算法用cEDAPG表示，隨機產(chǎn)生初始種群的經(jīng)驗Copula分布估計算法與爬山法的混合優(yōu)化算法用cEDA-Hill表示，采用初始種群均勻化策略的經(jīng)驗Copula分布估計算法與爬山法的混合優(yōu)化算法用cEDA-Hill2表示。

表1 三種算法優(yōu)化f1的結(jié)果比較Tab.1 The comparison of three algorithms on optimizing f1

表2 三種算法優(yōu)化f2的結(jié)果比較Tab.2 The comparison of three algorithms on optimizing f2

從實驗結(jié)果可以看出，爬山法和均勻初始化策略在算法中都起到了一定的作用。特別是對于測試函數(shù)f1，當選擇率為0.2，方差更新策略為C時，cEDA-Hill和cEDA-Hill2比cEDAPG在優(yōu)化結(jié)果上有明顯的改進。仿真結(jié)果表明經(jīng)驗Copula分布估計算法與爬山法的混合優(yōu)化算法以及均勻初始化策略都有一定的有效性。

4 結(jié)論

Copula分布估計算法是將Copula理論與分布估計算法相結(jié)合得到的一類新型優(yōu)化算法。經(jīng)驗Copula分布估計算法和爬山法的混合優(yōu)化算法利用了經(jīng)驗Copula分布估計算法對群體搜索方向的宏觀控制能力和爬山法在搜索空間中的局部搜索能力，使得算法在解決優(yōu)化問題時有了一定的改進。均勻初始化策略使得初始種群能夠均勻且互不相關(guān)地分散在搜索空間中，能夠更全面真實地反映優(yōu)化問題的特點，從而為算法進化提供良好的開端。但本文中提出的均勻初始化策略只限于對搜索空間中的每維進行多次二等份分割，即分成2n等份。一般的任意等份的且簡單易行的均勻初始化策略還有待進一步的研究。

表3 三種算法優(yōu)化f3的結(jié)果比較Tab.3 The comparison of three algorithms on optimizing f3

參考文獻：

[1] LARRANAGA J L P.Estimation of distribution algorithms，a new tool for evolutionary computation[M].Kluwer Academic Publishers，2002.

[2] MUHLENBEIN H，PAASS G.From recombination of genes to the estimation of distributions I.Binary Parameters[C]∥Proc.PPSN IV，Berlin，1996：178-187.

[3] BALUJA S.Population-based incremental learning：a method for integrating genetic search based function optimization and competitive learning[R].Technical Rep.CMU-CS-94-163，Pittsburgh，PA：Carnegie Mellon University，1994.

[4] 王圣堯，王凌，方晨，等.分布估計算法研究進展[J].控制與決策，2012，27(7)：961-966.

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

[6] 張放，魯華翔.利用條件概率和Gibbs抽樣技術(shù)為分布估計算法構(gòu)造通用概率模型[J].控制理論與應(yīng)用，2013，28(3)：307-315.

[7] 劉潔，王麗芳.copula EDA-BP混合優(yōu)化算法預(yù)測股票價格[J].太原科技大學(xué)學(xué)報，2014，35(3)：194-197.

[8] ABDOLLAHZADEH A，REYNOLDS A，CHRISTIE M.CORNE D.Estimation of distribution algorithms applied to history matching[J].SPE Journal，2013，18(3)：508-517.

[9] 王麗芳.Copula分布估計算法[M].北京：機械工業(yè)出版社，2012.

[10] 王麗芳，曾建潮，洪毅.利用Copula函數(shù)估計概率模型并采樣的分布估計算法[J].控制與決策：2011，26(9)：1333-1337，1342.

[11] RICHARD A BRUALDI.組合數(shù)學(xué)[M].馮舜璽，等，譯.北京：機械工業(yè)出版社，2001.