面向分布式計算的混合維度微粒群算法

桑淵博，曾建潮，2

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

微粒群算法從1995年被提出后，因為它的很多優(yōu)越性在各個領(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)簡單、所要考慮的參數(shù)少、搜索性能穩(wěn)定高效。對于求解問題上，問題的求解規(guī)模影響著微粒群算法的執(zhí)行效率，如求解問題精度、時間消耗長短、問題的結(jié)果的收斂程度等方面體現(xiàn)出了些許不足。另外，在很多工程領(lǐng)域中常常會遇到局部最優(yōu)解的影響，使得問題的求解達(dá)不到工程的要求。在此之前出現(xiàn)了針對微粒群算法上的諸多改進(jìn)，例如引入慣性權(quán)重的微粒群算法[1]、帶收縮因子的微粒群算法和基于島嶼模型的微粒群算法[2]等等。但這些改進(jìn)同樣都會遇到當(dāng)求解大規(guī)模問題或大規(guī)模的問題變量時計算耗時的問題，所以算法的分布式計算[3]和并行計算[4]就會體現(xiàn)出諸多好處，不僅可以減少執(zhí)行時間而且還能增加種群的多樣性從而使得求得解更好。

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

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

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

假設(shè)種群P={p1,p2,…,pn},即種群是由N個粒子組成，N稱為種群規(guī)模。粒子在d維空間的位置表示為xi={xi1,xi2,…,xid}，粒子速度表示為vi={vi1,vi2,…,vid}.在粒子速度、位置變化過程中，當(dāng)前個體粒子的最優(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是一個[0,1)的服從某種分布的隨機(jī)數(shù)常量，稱為慣性權(quán)重。慣性權(quán)重的大小代表了對當(dāng)前粒子速度繼承的多少，如果慣性權(quán)重大則能夠使粒子的速度較大，從而可以提高粒子的全局搜索能力。C1，C2是粒子學(xué)習(xí)因子，C1代表粒子自身的學(xué)習(xí)能力，控制下一次會朝著自己最好位置的軌跡進(jìn)化，C2則是控制著粒子向著全局最優(yōu)解的位置進(jìn)化。所以C1，C1的選取能夠直接的影響PSO算法的性能，合適的C1，C2可以加速問題結(jié)果的收斂而不易導(dǎo)致陷入局部最優(yōu)。r1，r1是兩個隨機(jī)數(shù)，在[0,1)且服從均勻分布。為了使粒子在進(jìn)化過程中防止粒子速度過大而超越搜索區(qū)域，可以將粒子的速度進(jìn)行限制，例如：可設(shè)置為在[-Vmax,Vmax]范圍，其中Vmax=γxmax，0.1≤γ≤1.0.

算法流程：

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

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

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

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

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

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

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

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

2.1 Spark分布式計算平臺

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

圖1 分布式計算框架
Fig.1 Framework of distributed computing

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

2.2 MDPSO算法

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

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

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

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

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

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

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

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

3) 每個粒子中的各個維度之間并行進(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算法說明：各個種群采用面向?qū)ο蠓绞竭M(jìn)行初始化，面向?qū)ο蠓绞绞菍⒎N群所有屬性整合到一起，對象中的屬性有粒子位置、粒子速度、當(dāng)前個體粒子的最優(yōu)位置、子種群中的全局最優(yōu)位置、遷移周期等。

3 仿真實驗

3.1 實驗平臺

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

3.2 實驗設(shè)計方案

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

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

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

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

3.3 實驗結(jié)果及分析

對于方案1，分別用兩個算法對每個測試函數(shù)分別運(yùn)行30次，記錄測試結(jié)果的最好值、最差值和平均值，實驗結(jié)果如表1所示。F8、F11函數(shù)分別在IPPSO算法和MDPSO算法迭代進(jìn)化過程中的收斂圖如圖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說明：設(shè)置每個子種群遷移周期是10代，對于F8函數(shù)的收斂情況途中只展示到了280*10次進(jìn)化結(jié)果，F(xiàn)11函數(shù)的收斂情況展示了58*10代，因為后面的都收斂于這個結(jié)果。為了使圖像結(jié)果更清晰，所以就選擇了代表性的代數(shù)。

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

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

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

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

4 結(jié) 論

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