桑淵博，曾建潮，2

(1. 太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024;2.中北大學(xué)計(jì)算機(jī)與控制工程學(xué)院，太原 030051)

微粒群算法從1995年被提出后，因?yàn)樗暮芏鄡?yōu)越性在各個(gè)領(lǐng)域得到了廣泛的應(yīng)用，如函數(shù)的優(yōu)化、工程界的系統(tǒng)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、深度學(xué)習(xí)等。優(yōu)越性表現(xiàn)在算法結(jié)構(gòu)簡(jiǎn)單、所要考慮的參數(shù)少、搜索性能穩(wěn)定高效。對(duì)于求解問(wèn)題上，問(wèn)題的求解規(guī)模影響著微粒群算法的執(zhí)行效率，如求解問(wèn)題精度、時(shí)間消耗長(zhǎng)短、問(wèn)題的結(jié)果的收斂程度等方面體現(xiàn)出了些許不足。另外，在很多工程領(lǐng)域中常常會(huì)遇到局部最優(yōu)解的影響，使得問(wèn)題的求解達(dá)不到工程的要求。在此之前出現(xiàn)了針對(duì)微粒群算法上的諸多改進(jìn)，例如引入慣性權(quán)重的微粒群算法[1]、帶收縮因子的微粒群算法和基于島嶼模型的微粒群算法[2]等等。但這些改進(jìn)同樣都會(huì)遇到當(dāng)求解大規(guī)模問(wèn)題或大規(guī)模的問(wèn)題變量時(shí)計(jì)算耗時(shí)的問(wèn)題，所以算法的分布式計(jì)算[3]和并行計(jì)算[4]就會(huì)體現(xiàn)出諸多好處，不僅可以減少執(zhí)行時(shí)間而且還能增加種群的多樣性從而使得求得解更好。

分布式計(jì)算是利用集群計(jì)算對(duì)同一問(wèn)題或者不同問(wèn)題進(jìn)行求解，和使用單機(jī)計(jì)算形成對(duì)比，可以在一定程度上解決計(jì)算耗時(shí)的問(wèn)題。在分布式進(jìn)化計(jì)算方面[5]，主從式分布計(jì)算模型[6]、細(xì)粒度分布計(jì)算模型[7]、粗粒度分布計(jì)算模型[8]和混合分布計(jì)算模型等幾類(lèi)模型分別得到研究。研究是以這些模型為基礎(chǔ)，結(jié)合具體算法和分布式計(jì)算環(huán)境的特點(diǎn)，圍繞其實(shí)現(xiàn)方法和應(yīng)用問(wèn)題展開(kāi)的。在現(xiàn)在的大數(shù)據(jù)時(shí)代背景下，分布式并行處理框架廣泛應(yīng)用于各個(gè)領(lǐng)域基于分布式并行處理框架的開(kāi)源系統(tǒng)Hadoop、Spark應(yīng)運(yùn)而生，并在許多應(yīng)用領(lǐng)域取得了巨大的成功。所以也可將進(jìn)化智能算法和當(dāng)前的分布式并行處理框架相結(jié)合，由程磊生，吳志健等人將微粒群算法在Spark集群中完成分布式計(jì)算，通過(guò)11個(gè)測(cè)試函數(shù)測(cè)試多種改進(jìn)的PSO算法進(jìn)行仿真實(shí)驗(yàn)得到該算法求解精度變高且加速效果明顯。

1 微粒群優(yōu)化算法

微粒群優(yōu)化算法(Particle Swarm Optimization, PSO)，它是一個(gè)模擬鳥(niǎo)群覓食過(guò)程的智能優(yōu)化算法。PSO算法因?yàn)榫哂休^強(qiáng)的全局搜索及全局收斂能力并且易實(shí)現(xiàn)的特點(diǎn)，所以在很多領(lǐng)域得到了成功的應(yīng)用[9]。但是在做一些計(jì)算復(fù)雜性的優(yōu)化問(wèn)題時(shí)，會(huì)出現(xiàn)收斂速度較慢、計(jì)算時(shí)間長(zhǎng)、求解精度不高等問(wèn)題。算法描述如下：

假設(shè)種群P={p1,p2,…,pn},即種群是由N個(gè)粒子組成，N稱(chēng)為種群規(guī)模。粒子在d維空間的位置表示為xi={xi1,xi2,…,xid}，粒子速度表示為vi={vi1,vi2,…,vid}.在粒子速度、位置變化過(guò)程中，當(dāng)前個(gè)體粒子的最優(yōu)解記為和 全局最優(yōu)解記為Pg={pg1,pg2,…,pgd}，其進(jìn)化公式為(1)、(2).

Vid(t+1)=w*Vid(t)+C1r1(Pid(t)-Xid(t))+C2r2(Pgd(t)-Xid(t))

(1)

Xid(t+1)=Xid(t)+Vid(t)

(2)

其中，t表示代數(shù)，w是一個(gè)[0,1)的服從某種分布的隨機(jī)數(shù)常量，稱(chēng)為慣性權(quán)重。慣性權(quán)重的大小代表了對(duì)當(dāng)前粒子速度繼承的多少，如果慣性權(quán)重大則能夠使粒子的速度較大，從而可以提高粒子的全局搜索能力。C1，C2是粒子學(xué)習(xí)因子，C1代表粒子自身的學(xué)習(xí)能力，控制下一次會(huì)朝著自己最好位置的軌跡進(jìn)化，C2則是控制著粒子向著全局最優(yōu)解的位置進(jìn)化。所以C1，C1的選取能夠直接的影響PSO算法的性能，合適的C1，C2可以加速問(wèn)題結(jié)果的收斂而不易導(dǎo)致陷入局部最優(yōu)。r1，r1是兩個(gè)隨機(jī)數(shù)，在[0,1)且服從均勻分布。為了使粒子在進(jìn)化過(guò)程中防止粒子速度過(guò)大而超越搜索區(qū)域，可以將粒子的速度進(jìn)行限制，例如：可設(shè)置為在[-Vmax,Vmax]范圍，其中Vmax=γxmax，0.1≤γ≤1.0.

算法流程：

1) 首先初始化一個(gè)粒子數(shù)為N的 種群，包括粒子位置、速度、個(gè)體最優(yōu)解位置、全局最優(yōu)解位置等；

2) 計(jì)算每個(gè)粒子目標(biāo)函數(shù)適應(yīng)值；

3) 將種群中的每個(gè)粒子的目標(biāo)函數(shù)的適應(yīng)值與該個(gè)體所經(jīng)歷過(guò)的最好位置pg的目標(biāo)函數(shù)適應(yīng)值相比較，若好，則將當(dāng)前位置作為當(dāng)前個(gè)體的最好位置pg；

4) 然后再比較種群中的每個(gè)粒子的目標(biāo)函數(shù)適應(yīng)值與種群的全局最好位置pg相比較，若較好，則將其作為全局最優(yōu)解pg；

5) 根據(jù)進(jìn)化公式(1)，(2)對(duì)種群粒子的速度和位置進(jìn)行進(jìn)化更新；

6) 如果未達(dá)到終止條件則返回步驟2)，(終止條件一般是是否達(dá)到最大進(jìn)化代數(shù)或者達(dá)到足夠好的目標(biāo)函數(shù)適應(yīng)值精度)；

2 與Spark結(jié)合的MDPSO算法

分布式計(jì)算技術(shù)是研究如何將一個(gè)大的問(wèn)題分解成多個(gè)小的任務(wù)，再將這些被分解的小的任務(wù)分配給多個(gè)計(jì)算機(jī)節(jié)點(diǎn)進(jìn)行并行處理，然后將每個(gè)小人物計(jì)算的中間結(jié)果匯總在一起，如此反復(fù)，直到整個(gè)問(wèn)題的解決，以此來(lái)達(dá)到成倍的縮減時(shí)間的消耗同時(shí)且不影響最終的結(jié)果的效果。

2.1 Spark分布式計(jì)算平臺(tái)

分布式進(jìn)化計(jì)算框架可以由進(jìn)化算法、分布式模型、集群環(huán)境、物理平臺(tái)4個(gè)基本條件組成，如圖1所示。近幾年在集群計(jì)算平臺(tái)發(fā)展上，尤為突出的有Hadoop和SparK.而Spark是建立在抽象的RDD (Resilient Distributed Datasets)之上，RDD模型中的迭代計(jì)算是基于內(nèi)存處理的模型，使得Spark在進(jìn)行算法迭代運(yùn)算時(shí)在計(jì)算速度上會(huì)快很多。

圖1 分布式計(jì)算框架
Fig.1 Framework of distributed computing

綜合以上描述，可以將微粒種群分割化，分割成多個(gè)子種群來(lái)進(jìn)行獨(dú)立的進(jìn)化。一方面滿(mǎn)足微粒群算法并行的思想，另一方面更符合Spark集群計(jì)算的模式?？梢詫⒆臃N群的粒子信息通過(guò)Spark的RDD化分發(fā)到各個(gè)計(jì)算節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)可以獨(dú)立的計(jì)算一個(gè)或多個(gè)子種群且各個(gè)子種群間的影響很小。

2.2 MDPSO算法

MDPSO(Mixed Dimension Particle Swarm Optimization)算法是能夠?qū)崿F(xiàn)粗粒度下的并行算法[10]。采用多子種群的進(jìn)化方式會(huì)將總的種群分割成n個(gè)子種群，在遷移周期內(nèi)，每個(gè)子種群會(huì)在集群的各個(gè)節(jié)點(diǎn)上面進(jìn)行獨(dú)立的進(jìn)化計(jì)算，當(dāng)進(jìn)化次數(shù)達(dá)到遷移周期時(shí)將各個(gè)子種群中的全局最優(yōu)解收集起來(lái)，然后對(duì)收集后的最優(yōu)解進(jìn)行混合(混合的方式是把各個(gè)子種群的全局最優(yōu)解對(duì)應(yīng)維度上的數(shù)據(jù)混合，形成了D(粒子維度)個(gè)數(shù)據(jù)集合)。然后再通過(guò)隨機(jī)發(fā)送的方式將各個(gè)維度上的數(shù)據(jù)隨機(jī)的發(fā)到各個(gè)子種群，子種群得到新的全局最優(yōu)解后再進(jìn)行進(jìn)化計(jì)算。直到達(dá)到所設(shè)置的終止條件。

對(duì)于分布式迭代算法來(lái)說(shuō)，Spark的RDD并行計(jì)算模型具有高效的容錯(cuò)機(jī)制、基于內(nèi)存計(jì)算、中間結(jié)果不需要寫(xiě)入磁盤(pán)等的優(yōu)點(diǎn)。尤其是它的基于內(nèi)存計(jì)算特別適合做一些算法的迭代計(jì)算，在集群環(huán)境下大大節(jié)省了很多的數(shù)據(jù)訪問(wèn)時(shí)間。為適應(yīng)當(dāng)前大數(shù)據(jù)計(jì)算、云計(jì)算的環(huán)境，本文提出了基于Spark的混合維度微粒群(MDPSO)算法。MDPSO算法流程圖如圖2所示。

算法的具體思路如下：先初始化N個(gè)子種群，每個(gè)子種群含有相同粒子數(shù)，然后通過(guò)Spark的輸入算子makeRDD或者parallelize函數(shù)將N個(gè)子種群并行到集群中去。然后各個(gè)種群開(kāi)始自己的獨(dú)立采用微粒群算法的方式進(jìn)行進(jìn)化計(jì)算，當(dāng)達(dá)到設(shè)置的遷移周期時(shí)通過(guò)collection算子進(jìn)行收集各個(gè)節(jié)點(diǎn)上的全局最優(yōu)解，其次采用混合維度的方法將數(shù)據(jù)拆分整合，最后再隨機(jī)的發(fā)到各個(gè)子種群中的對(duì)應(yīng)維度中去。各個(gè)種群信息交流完畢后再通過(guò)makeRDD或者parallelize算子使并行化，以此方式循環(huán)，直到達(dá)到終止條件，最后輸出結(jié)果。

算法中的混合維度方法是：在各個(gè)子種群達(dá)到遷移周期時(shí)將各個(gè)子種群中的全局最優(yōu)解通過(guò)Spark的collect函數(shù)收集起來(lái)，然后將全局最優(yōu)解中各個(gè)維度上的粒子數(shù)據(jù)集合起來(lái)形成D(D為粒子維度數(shù))個(gè)集合，然后通過(guò)隨機(jī)發(fā)送的方式將數(shù)據(jù)集合中的數(shù)據(jù)不重疊的發(fā)送到各個(gè)子種群。例如：各個(gè)子種群的第1維數(shù)據(jù)組成一個(gè)集合，然后將這個(gè)集合中的數(shù)據(jù)再隨機(jī)的發(fā)送到各個(gè)子種群中的第1維。

MDPSO算法可以并行執(zhí)行的部分體現(xiàn)在以下幾個(gè)方面：

1) 每個(gè)子種群可以獨(dú)立進(jìn)化計(jì)算。

2) 在子種群內(nèi)部，粒子與粒子之間可以相互的獨(dú)立進(jìn)化計(jì)算。

圖2 MDPSO流程示意圖
Fig.2 MDPSO schematic diagram

3) 每個(gè)粒子中的各個(gè)維度之間并行進(jìn)化。

MDPSO算法偽代碼如下：

1:Initialize N population: objectPartical

2:generationNum = 0

3:While(generationNum< maxNum)

4:Parallel Population: objectParticalRDD

5:objectParticalRDD.map(elem =>

6:k = 0

7:while(k < migration cycle )

8:evolutionary computation the objectPartical

9:end while

10:)

11:collection the objectParticalRDD

12: mixed dimensions and send out randomly

13: end while

MDPSO算法說(shuō)明：各個(gè)種群采用面向?qū)ο蠓绞竭M(jìn)行初始化，面向?qū)ο蠓绞绞菍⒎N群所有屬性整合到一起，對(duì)象中的屬性有粒子位置、粒子速度、當(dāng)前個(gè)體粒子的最優(yōu)位置、子種群中的全局最優(yōu)位置、遷移周期等。

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

3.1 實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)采用3臺(tái)相同配置的服務(wù)器組成Spark集群計(jì)算平臺(tái)。每臺(tái)機(jī)器配置如下：操作系統(tǒng)為Centos6.8，Intel(R) Xeon(R) CPU，主頻1.80GHz，Hadoop和Spark對(duì)應(yīng)版本分別為Hadoop2.6.5和Spark1.6.1.

3.2 實(shí)驗(yàn)設(shè)計(jì)方案

為了驗(yàn)證MDPSO算法的性能，選取了6個(gè)無(wú)約束優(yōu)化的測(cè)試函數(shù)，其中F1、F2函數(shù)是單峰函數(shù)，F(xiàn)8-F11是多峰函數(shù)。具體函數(shù)定義參照文獻(xiàn)[11]。實(shí)驗(yàn)測(cè)試的算法包括MDPSO和IPPSO[2]算法。為了驗(yàn)證MDPSO算法的性能，設(shè)計(jì)了兩個(gè)實(shí)驗(yàn)方案：

實(shí)驗(yàn)方案1 比較上述兩種算法在粒子維度D=30的情況下求解上面的6個(gè)測(cè)試函數(shù)的效果，另外選取F8、F11函數(shù)記錄中間結(jié)果，通過(guò)分析中間結(jié)果集來(lái)查看函數(shù)的收斂情況。由于MDPSO算法求解過(guò)程中全局最優(yōu)解是波動(dòng)的，所以對(duì)求得的中間結(jié)果用擬合的方式畫(huà)出算法收斂圖。

實(shí)驗(yàn)方案2 針對(duì)MDPSO算法設(shè)置不同的遷移周期來(lái)查看對(duì)F9、F10函數(shù)結(jié)果的影響情況。方法：分別計(jì)算不同遷移周期30次，算出各自的平均值來(lái)查看結(jié)果。

在實(shí)現(xiàn)方案中的參數(shù)選擇上采用相同的原則，目的是保證實(shí)驗(yàn)結(jié)果對(duì)比的有效性，另外算法中的參數(shù)設(shè)置參考了文獻(xiàn)[12]中的設(shè)置。種群個(gè)數(shù)等于集群中的計(jì)算節(jié)點(diǎn)的CPU總核數(shù)，以實(shí)現(xiàn)真正的并行計(jì)算，所以?xún)蓚€(gè)算法的具體參數(shù)設(shè)置如下：將種群分為8個(gè)子種群，每個(gè)子種群中的粒子數(shù)設(shè)置為15個(gè)，粒子維度D=30，權(quán)重因子w是[0,1)的隨機(jī)數(shù)，學(xué)習(xí)因子C1=C1=1.4962，Vmax在每一維度的值設(shè)置為對(duì)應(yīng)維度變化范圍的0.15倍，進(jìn)化總代數(shù)設(shè)置5 000為代，所以總的評(píng)價(jià)次數(shù)FEs = 120＊5 000 = 600 000次，種群間的信息交流采用混合對(duì)應(yīng)維度信息的方式進(jìn)行。

3.3 實(shí)驗(yàn)結(jié)果及分析

對(duì)于方案1，分別用兩個(gè)算法對(duì)每個(gè)測(cè)試函數(shù)分別運(yùn)行30次，記錄測(cè)試結(jié)果的最好值、最差值和平均值，實(shí)驗(yàn)結(jié)果如表1所示。F8、F11函數(shù)分別在IPPSO算法和MDPSO算法迭代進(jìn)化過(guò)程中的收斂圖如圖3、圖4所示。

表1 兩算法求解函數(shù)結(jié)果
Tab.1 The results of two algorithms solve functions

函數(shù)Functions算法Algorithm最好值Best value最差值Worst value平均值Mean valueF2IPPSOMDPSO9.9E-2314.23E-1981.11E-2272.48E-1968.46E-2297.91E-197F8IPPSOMDPSO1.04E+041.23E+048.40E+038.49E+03-9.35E+03-1.15E+04F9IPPSOMDPSO31.8381.989 9114.42958.984 362.68232.305F10IPPSOMDPSO7.55E-153.99E-151.46E-143.99E-158.49E-153.99E-15F11IPPSOMDPSO0.00E+000.00E+000.0294980.00E+000.0077150.00E+00

圖3 F8函數(shù)收斂圖
Fig.3 F8 function convergence diagram

圖4 F11函數(shù)收斂圖
Fig.4 F11 function convergence diagram

圖3、圖4說(shuō)明：設(shè)置每個(gè)子種群遷移周期是10代，對(duì)于F8函數(shù)的收斂情況途中只展示到了280*10次進(jìn)化結(jié)果，F(xiàn)11函數(shù)的收斂情況展示了58*10代，因?yàn)楹竺娴亩际諗坑谶@個(gè)結(jié)果。為了使圖像結(jié)果更清晰，所以就選擇了代表性的代數(shù)。

實(shí)驗(yàn)方案1的結(jié)果表明，在進(jìn)化代數(shù)相同的情況下，MDPSO算法在求解多峰函數(shù)時(shí)，求解的結(jié)果比IPPSO算法求解的結(jié)果更接近于理論最優(yōu)解。但對(duì)于單峰函數(shù)在相同的進(jìn)化代數(shù)下MDPSO算法求得的解要弱于IPPSO算法求得的解。從F8、F11函數(shù)的收斂效果圖來(lái)看，MDPSO算法和IPPSO算法相比，MDPSO算法雖然收斂的速度要比IPPSO算法要慢，但它能跳出局部最優(yōu)而能找到更接近于理論最好值的全局最優(yōu)解的能力要強(qiáng)很多。因?yàn)楫?dāng)其中一個(gè)子種群中如果陷入了局部最優(yōu)，那另外若干子種群未陷入局部最優(yōu)，那這些子種群的全局最優(yōu)解通過(guò)信息交流就會(huì)幫助陷入局部最優(yōu)的子種群跳出而繼續(xù)尋找全局最優(yōu)解。

對(duì)于實(shí)驗(yàn)方案2，對(duì)MDPSO算法設(shè)置不同的遷移周期觀察對(duì)F9、F10函數(shù)進(jìn)化結(jié)果的影響如圖5、圖6.從圖5可以看出遷移周期由1增大到10時(shí)，求解的結(jié)果越來(lái)越好，之后隨著遷移周期的增長(zhǎng)求解的結(jié)果則越來(lái)越差，到了60代時(shí)求解結(jié)果最差。再隨著遷移周期的增長(zhǎng)，求解的結(jié)果雖然變得好了但變化不大。圖6顯示對(duì)于F10函數(shù)遷移周期由1到5時(shí)，求解效果越來(lái)越好，之后一直到遷移周期為150時(shí)求解效果變化不大，再之后求解效果則越來(lái)越差。出現(xiàn)上述結(jié)果原因是當(dāng)遷移周期由1變到10時(shí)各子種群之間的相互影響越來(lái)越小，增加了種群的多樣性，從而能夠找到更優(yōu)的解。但隨著遷移周期的繼續(xù)增加，子種群間的相互影響雖然越來(lái)越小但信息交流卻被弱化，使得其中一個(gè)子種群尋找到更好的解時(shí)無(wú)法及時(shí)通知其他子種群。那就等價(jià)于自己獨(dú)立進(jìn)化計(jì)算，使得整體的種群多樣性減小，那最終的尋優(yōu)效果就會(huì)變差，所以找到合適的遷移周期是關(guān)鍵。所以合適的遷移周期能夠使MDPSO算法對(duì)于復(fù)雜問(wèn)題的求解會(huì)有著很好的效果。

圖5 不同遷移周期對(duì)函數(shù)F9結(jié)果影響
Fig.5 The effect of different migration cycle on function F9

圖6 不同遷移周期對(duì)F10結(jié)果影響
Fig.6 The effect of different migration cycle on function F10

4 結(jié) 論

微粒群算法本身具有并行性，本文劃分了若干個(gè)子種群并以集群計(jì)算的形式 進(jìn)行了實(shí)現(xiàn)，增加了種群的多樣性有利于問(wèn)題的求解，在子種群信息交流時(shí)采用了對(duì)所有維度進(jìn)行隨機(jī)選取的方式，進(jìn)一步增加了種群的多樣性。通過(guò)不同的測(cè)試函數(shù)模擬求解問(wèn)題來(lái)驗(yàn)證MDPSO算法的可行性。由于算法提高了種群的多樣性使得求解問(wèn)題時(shí)更容易跳出局部最優(yōu)解而更容易找到全局最優(yōu)解。當(dāng)遇到計(jì)算量大的問(wèn)題時(shí)，即使采用了粗粒度的分布式計(jì)算技術(shù)，對(duì)于單機(jī)計(jì)算也是很費(fèi)時(shí)，所以將來(lái)可以采用GPU細(xì)粒度計(jì)算模式來(lái)減少單機(jī)計(jì)算時(shí)間，從而進(jìn)一步減少整個(gè)集群計(jì)算時(shí)間，以達(dá)到更好的效果。