程　鋼， 劉　罡， 胡延忠

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

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

程鋼， 劉罡， 胡延忠

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

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

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

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

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

1差分演化算法

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

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

1)變異操作

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

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

隨機(jī)差分向量法

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

(1)

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

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

(2)

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

DE/rand-to-best/1:

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

(3)

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

2)交叉操作

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

其中uij是試驗(yàn)向量。

3)選擇操作

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

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

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

2.1隨機(jī)采樣

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

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

(4)

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

圖 1　隨機(jī)抽樣圖

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

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

2.2隨機(jī)采樣的變異機(jī)制和高斯采樣的變異機(jī)制

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

隨機(jī)變異機(jī)制

(5)

高斯變異機(jī)制

(6)

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

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

具體情況如式(7)所示

Vi= Xr1+ F (Xr2- Xr3)

(7)

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

算法1：GRCDE算法

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

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

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

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

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

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

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

3GRCDE性能分析

3.1實(shí)驗(yàn)設(shè)置

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

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

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

(8)

-1.28≤xi≤1.28

(9)

-5≤xi≤10

(10)

3.2對(duì)GRCDE和DE的比較

1)比較解的精度

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

(a)函數(shù)f1

(b)函數(shù)f2

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

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

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

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

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

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

4結(jié)束語

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

實(shí)驗(yàn)結(jié)果表明，高斯采樣和隨機(jī)采樣會(huì)顯著加快收斂速度，提升差分演化算法的求解能力。本文提出GRCDE在對(duì)復(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

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

[作者簡介]程鋼(1983-)， 男， 湖北洪湖人，湖北工業(yè)大學(xué)碩士研究生，研究方向?yàn)椴罘盅莼惴?，圖論

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

[中圖分類號(hào)]TP301.6

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