基于高斯采樣和隨機采樣聚類的差分演化算法

程　鋼， 劉　罡， 胡延忠

(湖北工業(yè)大學(xué)計算機學(xué)院， 湖北 武漢 430068)

基于高斯采樣和隨機采樣聚類的差分演化算法

程鋼， 劉罡， 胡延忠

(湖北工業(yè)大學(xué)計算機學(xué)院， 湖北 武漢 430068)

[摘要]基于中心采樣的概念，提出隨機采樣方法。研究差分演化算法，提出基于高斯采樣和隨機采樣的聚類差分演化算法。通過實驗，論證了高斯采樣和隨機采樣顯著的加快收斂速度、提升算法的求解能力，表明該算法對復(fù)雜的全局優(yōu)化問題有很好地求解能力，比經(jīng)典差分演化算法具有更好的求解性能。

[關(guān)鍵詞]差分演化算法； 全局優(yōu)化； 隨機采樣

針對全局優(yōu)化問題， R.storn和K.Price提出差分演化算法(Differential Evolution，DE)，算法采用實數(shù)編碼方式，其原理及演化流程與遺傳算法十分相似，如父代生成子代的操作均包括變異、交叉和選擇，且很好的解決了全局優(yōu)化問題[1-4]。

本文提出隨機采樣的方法。隨機采樣與中心采樣相比，前者因其隨機性，其搜索能力更靈活、更有效。由于差分演化算法擅長全局搜索整個解空間，解的局部區(qū)域開拓相對緩慢。為了改進(jìn)差分演化算法的求解性能，本文將隨機采樣、高斯采樣和一步K均值聚類方法結(jié)合到差分演化算法中，旨在提高差分演化算法對解得局部區(qū)域的開拓能力，提出了基于高斯采樣和隨機采樣的聚類差分演化算法(GRCDE)。

1差分演化算法

差分演化算法利用差分變異操作將種群中任意個體選取兩個差分向量加權(quán)；再根據(jù)一定規(guī)則加到新的個體上，隨后進(jìn)入交叉操作，通過交叉系數(shù)產(chǎn)生新個體，該變異方式有效利用種群分布特性，提高了全局搜索能力，避免了其它演化算法中存在的變異機制不足現(xiàn)象；算法在選擇操作上采取貪婪選擇操作，選擇適應(yīng)值大的個體保存到下一代。

差分演化算法的關(guān)鍵步驟：

1)變異操作

變異操作指算法將種群中任意個體選取兩個差分向量加權(quán)從上一代種群中生成新個體進(jìn)入下一代。變異機制實現(xiàn)了對搜索空間的搜索。

在差分演化算法中，很多變異操作機制在文獻(xiàn)[5]提出，現(xiàn)將一些比較知名的變異機制介紹如下：

隨機差分向量法

DE/rand/1 :Vi=Xr1+F(Xr2-Xr3)

(1)

最優(yōu)解加隨機向量差分法

DE/best/1:Vi=Xbest+F(Xr1-Xr2)

(2)

最優(yōu)解與隨機向量差分法

DE/rand-to-best/1:

Vi=Xi+λ(Xbest-Xi)+F(Xr1-Xr2)

(3)

其中，Vi是目標(biāo)向量，Xi是變異向量。r1，r2，r3∈{1，2,…,NP}是隨機選擇不同的整數(shù)且不同于運行指數(shù)i；Xbest代表目前這一代最好的個體；F(>0)變異因子；λ是增加的控制參數(shù)。

2)交叉操作

交叉操作的目的是對種群中前幾代所求得的解進(jìn)行重組。交叉操作對種群中的當(dāng)前向量和變異向量進(jìn)行重組，從而構(gòu)建了新的試驗向量；再經(jīng)過交叉操作，通過對上一代向量和新的試驗向量的適應(yīng)值進(jìn)行比較，兩者中適應(yīng)值高的進(jìn)入下一代。交叉操作如下：

其中uij是試驗向量。

3)選擇操作

選擇操作采用“貪婪”的搜索策略，經(jīng)過前面兩步操作后，生成的試驗向量個體ui,G與目標(biāo)向量個體Vi,G進(jìn)行競爭，對兩者中適應(yīng)值相比較，更優(yōu)的個體才被選中進(jìn)入下一代。選擇操作如

其中Xi,G+1是新的種群個體向量。

2改進(jìn)的差分演化算法

2.1隨機采樣

中心采樣是由Rahnamayan[6]提出。在搜索空間中，搜索區(qū)間的中心有很大概率接近問題的解。隨機采樣基于中心采樣的概念，給定搜索區(qū)間[-(|a|+|b|),(|a|+|b|)],如圖1所示，該區(qū)間內(nèi)的隨機點按式(4)所示，對于n維情況，具體如

ri=(|ai|+|bi|) rand(-1,1)

(4)

由于最優(yōu)解的位置具有不確定性，為了增加包含最優(yōu)解的概率，需要對搜索區(qū)間進(jìn)行擴展。由于ri位于區(qū)間[-(|a|+|b|),(|a|+|b|)]內(nèi)的隨機性，使其在整個區(qū)間內(nèi)移動。在中心采樣中，ci是位于區(qū)間(ai，bi)的固定中心點。與中心采樣相比，隨機采樣的搜索區(qū)間更大。事實上，中心采樣可以被視為隨機采樣的子集。當(dāng)rand(-1, 1)為0.5時，隨機采樣退化為中心采樣。與中心采樣使用的固定值相比，隨機采樣使用的隨機數(shù)有更大的靈活性，使得候選解有更大的機會接近全局最優(yōu)解。直觀的解釋如圖1所示。

圖 1　隨機抽樣圖

圖中x是候選解，s是全局最優(yōu)解，r是搜索區(qū)間 [-(|a|+|b|),(|a|+|b|)]內(nèi)產(chǎn)生的隨機點，r=(|a|+|b|)rand(-1,1)(其中rand(-1,1)是均勻分布在(-1,1)的隨機數(shù))。

整個搜索區(qū)間[-(|a|+|b|),(|a|+|b|)]可以分為[-(|a|+|b|),r]和[r,(|a|+|b|)]兩個子區(qū)間。由此可見，x和s既可能在不同子區(qū)間，也可能在同一子區(qū)間。當(dāng)x和s在不同子區(qū)間時，r位于x和s之間。無論s在何位置，x和r分別到s的距離都滿足‖x-s‖≥‖r-s‖。當(dāng)x和s在相同的子區(qū)間時，則存在x和r一起競爭誰更接近s。由于s位置的不確定性，隨機點r可能比區(qū)間[-(|a|+|b|),(|a|+|b|)]的中心點更接近全局最優(yōu)解s。因此，隨機采樣具有更大靈活性，使得隨機點r有更高的概率接近全局最優(yōu)解s。

2.2隨機采樣的變異機制和高斯采樣的變異機制

在演化階段初期，由于種群具有較大的分布偏差，搜索過程主要集中于對整個空間的全局搜索；隨著運行代數(shù)增長，分布偏差逐漸變小，搜索過程就逐步轉(zhuǎn)為對局部區(qū)域的開拓。當(dāng)搜索過程處于局部開拓時，使用隨機采樣變異機制和高斯采樣變異機制對每個子種群進(jìn)行搜索。隨機采樣和高斯采樣都具備很好的局部開拓的性能。數(shù)學(xué)上表示為：

隨機變異機制

(5)

高斯變異機制

(6)

2.3基于高斯采樣和隨機采樣聚類的差分演化算法

差分演化算法擅長全局搜索整個解空間，然而差分演化算法對解的局部區(qū)域開拓相對緩慢。為此本文將隨機采樣、高斯采樣和一步K均值聚類方法結(jié)合到差分演化算法中，試圖提高差分演化算法對局部區(qū)域的開拓能力；提出了基于高斯采樣和隨機采樣的聚類差分演化算法(GRCDE)。在GRCDE中，使用目標(biāo)空間距離測度的一步K均值聚類算法用于劃分種群。利用高斯變異機制和隨機變異機制分別在每個子種群中搜索新的個體?；趦煞N不同原理的變異機制可以有效地對子空間進(jìn)行搜索，增強差分演化算法對局部區(qū)域的開拓能力。在GRCDE中，2種變異機制生成了兩個新的試驗向量，然后兩個試驗向量中最好的一個向量被用來替換子種群中的目標(biāo)向量。GRCDE使用的差分演化算法變異機制采用折衷選擇機制[5,7]。

具體情況如式(7)所示

Vi= Xr1+ F (Xr2- Xr3)

(7)

其中，Xr1的適應(yīng)值優(yōu)于Xi的適應(yīng)值，r1≠r2≠r3≠i。這種算法變異機制是從當(dāng)前種群中按如下要求隨機選擇一個個體，該個體的適應(yīng)值必須優(yōu)于作為變異對象的目標(biāo)個體適應(yīng)值。這種方法在保持收斂速率的同時，有助于維持種群的多樣性。

算法1：GRCDE算法

Step1：隨機生成初始種群P，在種群P中對每一個個體的適應(yīng)值進(jìn)行評估，設(shè)置迭代計數(shù)器t=1；

Step2：當(dāng)終止標(biāo)準(zhǔn)不滿足繼續(xù)執(zhí)行；

Step3：根據(jù)Vi= Xr1+ F (Xr2- Xr3) 生成新的試驗向量V={vi,1;vi,2,…,vi,D}；

Step4：依據(jù)t%m=0判斷多少代進(jìn)行一次聚類；

Step 6：(隨機變異機制和高斯變異機制)對于第i個子種群，使用隨機變異機制生成的新的個體A，同時也使用高斯變異機制生成新的個體B。在A和B通過競爭后，選取優(yōu)勝者去取代第i個子種群中相應(yīng)的個體。

Step 7：判斷是否達(dá)到終止輸出條件，滿足輸出結(jié)果，否則繼續(xù)Step2。

在GRCDE中，種群被分成K個子種群，并且利用兩種不同的變異操作機制對子種群進(jìn)行開拓。多個不同的變異機制與單個的變異機制相比，可以同時搜索更多的個體。通過多個父體交叉后產(chǎn)生的新個體之間進(jìn)行競爭比較，優(yōu)勝者將被選出并進(jìn)入下一代種群。這種方法提高了搜索效率并且增加了搜索到最優(yōu)解的機會。

3GRCDE性能分析

3.1實驗設(shè)置

針對GRCDE的性能，選取了3個演化學(xué)界常用基礎(chǔ)函數(shù)進(jìn)行測試。3個函數(shù)都是高維函數(shù)，f1是單峰函數(shù)，f2是有噪聲的四次函數(shù)，f3是有很多局部最小值的多峰函數(shù)。

實驗設(shè)置如下：維度D=30；種群規(guī)模NP=100；變異因子F=0.5；交叉概率因子CR=0.9；聚類周期m=MAX_NFEs(最大個體評估次數(shù))=5000；運行次數(shù)：各種算法將每個函數(shù)運行50次。“Mean”表示在50次運行內(nèi)發(fā)現(xiàn)了最好的適應(yīng)值?！癝R”表示成功運行的次數(shù)?！癗FEs”是評估適應(yīng)值的數(shù)量。 “MeanNFEs”表示算法的函數(shù)評估數(shù)量的平均數(shù)量成功。“Stddev”表示函數(shù)標(biāo)準(zhǔn)偏差值和最大評估適應(yīng)性數(shù)量平均值。如果算法在運行50次沒有1次成功，表示算法對該問題不適用，并用“N/A”表示。

(xi-1)2), -30≤xi≤30

(8)

-1.28≤xi≤1.28

(9)

-5≤xi≤10

(10)

3.2對GRCDE和DE的比較

1)比較解的精度

對于DE/rand/1,DE/best/1/和GRCDE的基礎(chǔ)測試函數(shù)，最大評估次數(shù)MAX_NFEs=2.00E+05，并在表1中進(jìn)行了總結(jié)。在圖2中DE/rand/1，DE/best/1，GRCDE分別運行函數(shù)f1,f2,f3的演化過程，關(guān)于DE/rand/1,DE/best/1和GRCDE性能如圖2所示。通過分析表1和圖2的結(jié)果可知，在上述實驗中GRCDE求解性能比DE優(yōu)越。

(a)函數(shù)f1

(b)函數(shù)f2

(c)函數(shù)f3圖 2　算法運行幾種測試函數(shù)的過程

2)比較收斂速度和成功運行的次數(shù)

由于收斂速度是算法性能一項重要指標(biāo)，現(xiàn)比較了不同算法的收斂速度。需要對目標(biāo)函數(shù)的閾值進(jìn)行選擇和比較，對于所有函數(shù)不同的閾值具有不同功能，表2中Threshold表示目標(biāo)函數(shù)的閾值，其中f1、f3閾值設(shè)為1.00×10-10,f2閾值設(shè)為5.00×10-3。在到達(dá)終止標(biāo)準(zhǔn)時算法終止，在本節(jié)中，當(dāng)最好的適應(yīng)值低于預(yù)定義的閾值，或者個體評估次數(shù)的數(shù)量(NFEs)達(dá)到最大評估次數(shù) (MAX_NFEs= 5.00×105)時，算法終止運算。

表1　所有函數(shù)最好適應(yīng)值的平均值和協(xié)方差的結(jié)果

表2　在預(yù)設(shè)精度下評估次數(shù)的平均值和成功運行次數(shù)

表2中所有函數(shù)都進(jìn)行50次獨立的運算，然后記錄收斂到閾值需要的平均個體評估次數(shù)的值和SR，其中SR是成功運行的次數(shù)。3種算法的NFEs平均值、標(biāo)準(zhǔn)偏差和成功運行次數(shù)SR，如表2所示。在表2中，所有算法的最大評估次數(shù)(MAX_NFEs)均為500,000，“N/A”代表到最大評估次數(shù) (MAX_NFEs) 時精度水平?jīng)]有達(dá)到要求。由此可見，GRCDE在3個函數(shù)中的收斂速度要比DE/best/1和DE/rand/1快，同時與差分演化算法相比，在GRCDE中NFEs的數(shù)量明顯減少。

4結(jié)束語

在GRCDE中，利用高斯采樣和隨機采樣設(shè)計兩種不同的變異機制。不同的變異機制充分利用不同的搜索技術(shù)以不同的搜索方式對解空間進(jìn)行搜索，這樣就提高了全局搜索的效率和局部開拓的能力。值得注意的是，如果種群的規(guī)模太小，變異機制的作用會受到限制。在GRCDE中，當(dāng)子種群的規(guī)模大于5時，變異機制才被用來搜索這個子種群。

實驗結(jié)果表明，高斯采樣和隨機采樣會顯著加快收斂速度，提升差分演化算法的求解能力。本文提出GRCDE在對復(fù)雜的全局優(yōu)化中具備很好地求解能力，這種改進(jìn)的差分演化算法具有良好求解性能。

[參考文獻(xiàn)]

[1]ReddyAS,VaisakhK.Shuffleddifferentialevolutionforlargescaleeconomicdispatch[J].ElectricPowerSystemsResearch, 2013, 96: 237-245.

[2]ZhongY,ZhangL.Remotesensingimagesubpixelmappingbasedonadaptivedifferentialevolution[J].Systems,Man,andCybernetics,PartB:Cybernetics,IEEETransactionson, 2012, 42(5): 1306-1329.

[3]ChakrabortyUK,AbbottTE,DasSK.PEMfuelcellmodelingusingdifferentialevolution[J].Energy, 2012, 40(1): 387-399.

[4]KhushabaRN,Al-AniA,Al-JumailyA.Featuresubsetselectionusingdifferentialevolutionandastatisticalrepairmechanism[J].ExpertSystemswithApplications, 2011, 38(9): 11 515-11 526.

[5]PriceKV.Differentialevolutionvs.thefunctionsofthe2ndICEO[C]//EvolutionaryComputation, 1997.IEEEInternationalConferenceon.IEEE, 1997: 153-157.

[6]RahnamayanS,WangGG.Center-basedsamplingforpopulation-basedalgorithms[C]//EvolutionaryComputation, 2009.CEC’09.IEEECongresson.IEEE, 2009: 933-938.

[7]PriceK,StornR,LampinenJ.differentialevolution-apracticalapproachtoglobaloptimization[M].BerlinGermany：Springer, 2005.

[責(zé)任編校： 張巖芳]

A Clustering Differential Evolution Algorithm Based on Random Sampling and Gaussian Sampling

CHENG Gang， LIU Gang， HU Yanzhong

(SchoolofComputerScience,HubeiUniv.ofTech. ,Wuhan430068,China)

Abstract：Based on the concept of center-based sampling, the paper proposed a method of random sampling. It studied the Differential Evolution, proposing the clustering differential evolution algorithm based on random sampling and Gaussian sampling (GRCDE). Experiment results indicate the Gaussian sampling and the random sampling remarkably accelerate the convergence rate and improves exploitation ability of DE. It shows that GRCDE has a better solving ability and our proposed GRCDE performs better than some DE variants.

Keywords：Differential Evolution, global optimization, random sampling

[收稿日期]2015-05-18

[基金項目]國家自然科學(xué)基金項目(61300127)

[作者簡介]程鋼(1983-)， 男， 湖北洪湖人，湖北工業(yè)大學(xué)碩士研究生，研究方向為差分演化算法，圖論

[文章編號]1003-4684(2016)02-0045-03

[中圖分類號]TP301.6

[文獻(xiàn)標(biāo)識碼]：A