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

桑淵博，曾建潮，2

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

微粒群算法從1995年被提出后，因為它的很多優越性在各個領域得到了廣泛的應用，如函數的優化、工程界的系統優化、神經網絡訓練、深度學習等。優越性表現在算法結構簡單、所要考慮的參數少、搜索性能穩定高效。對于求解問題上，問題的求解規模影響著微粒群算法的執行效率，如求解問題精度、時間消耗長短、問題的結果的收斂程度等方面體現出了些許不足。另外，在很多工程領域中常常會遇到局部最優解的影響，使得問題的求解達不到工程的要求。在此之前出現了針對微粒群算法上的諸多改進，例如引入慣性權重的微粒群算法[1]、帶收縮因子的微粒群算法和基于島嶼模型的微粒群算法[2]等等。但這些改進同樣都會遇到當求解大規模問題或大規模的問題變量時計算耗時的問題，所以算法的分布式計算[3]和并行計算[4]就會體現出諸多好處，不僅可以減少執行時間而且還能增加種群的多樣性從而使得求得解更好。

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

1 微粒群優化算法

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

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

算法流程：

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

2) 計算每個粒子目標函數適應值；

3) 將種群中的每個粒子的目標函數的適應值與該個體所經歷過的最好位置pg的目標函數適應值相比較，若好，則將當前位置作為當前個體的最好位置pg；

4) 然后再比較種群中的每個粒子的目標函數適應值與種群的全局最好位置pg相比較，若較好，則將其作為全局最優解pg；

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

6) 如果未達到終止條件則返回步驟2)，(終止條件一般是是否達到最大進化代數或者達到足夠好的目標函數適應值精度)；

2 與Spark結合的MDPSO算法

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

2.1 Spark分布式計算平臺

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

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

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

2.2 MDPSO算法

MDPSO(Mixed Dimension Particle Swarm Optimization)算法是能夠實現粗粒度下的并行算法[10]。采用多子種群的進化方式會將總的種群分割成n個子種群，在遷移周期內，每個子種群會在集群的各個節點上面進行獨立的進化計算，當進化次數達到遷移周期時將各個子種群中的全局最優解收集起來，然后對收集后的最優解進行混合(混合的方式是把各個子種群的全局最優解對應維度上的數據混合，形成了D(粒子維度)個數據集合)。然后再通過隨機發送的方式將各個維度上的數據隨機的發到各個子種群，子種群得到新的全局最優解后再進行進化計算。直到達到所設置的終止條件。

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

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

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

MDPSO算法可以并行執行的部分體現在以下幾個方面：

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

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

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

3) 每個粒子中的各個維度之間并行進化。

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算法說明：各個種群采用面向對象方式進行初始化，面向對象方式是將種群所有屬性整合到一起，對象中的屬性有粒子位置、粒子速度、當前個體粒子的最優位置、子種群中的全局最優位置、遷移周期等。

3 仿真實驗

3.1 實驗平臺

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

3.2 實驗設計方案

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

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

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

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

3.3 實驗結果及分析

對于方案1，分別用兩個算法對每個測試函數分別運行30次，記錄測試結果的最好值、最差值和平均值，實驗結果如表1所示。F8、F11函數分別在IPPSO算法和MDPSO算法迭代進化過程中的收斂圖如圖3、圖4所示。

表1 兩算法求解函數結果
Tab.1 The results of two algorithms solve functions

函數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函數收斂圖
Fig.3 F8 function convergence diagram

圖4 F11函數收斂圖
Fig.4 F11 function convergence diagram

圖3、圖4說明：設置每個子種群遷移周期是10代，對于F8函數的收斂情況途中只展示到了280*10次進化結果，F11函數的收斂情況展示了58*10代，因為后面的都收斂于這個結果。為了使圖像結果更清晰，所以就選擇了代表性的代數。

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

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

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

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

4 結 論

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