翟光明，李國和,，吳衛(wèi)江,，洪云峰，周曉明，汪 靜

(1.中國石油大學(xué)(北京) 地球物理與信息工程學(xué)院，北京 102249； 2.中國石油大學(xué)(北京) 油氣數(shù)據(jù)挖掘北京市重點實驗室，北京 102249；3.石大兆信數(shù)字身份管理與物聯(lián)網(wǎng)技術(shù)研究院，北京 100029) (*通信作者電子郵箱guangminz@163.com)

基于Spark的人工蜂群改進(jìn)算法

翟光明1,2*，李國和1,2,3，吳衛(wèi)江1,2,3，洪云峰3，周曉明3，汪 靜1,2

(1.中國石油大學(xué)(北京) 地球物理與信息工程學(xué)院，北京 102249； 2.中國石油大學(xué)(北京) 油氣數(shù)據(jù)挖掘北京市重點實驗室，北京 102249；3.石大兆信數(shù)字身份管理與物聯(lián)網(wǎng)技術(shù)研究院，北京 100029) (*通信作者電子郵箱guangminz@163.com)

針對人工蜂群(ABC)算法求解組合優(yōu)化問題時效率低的問題，提出了基于Spark云計算框架的并行ABC改進(jìn)算法。首先，將蜂群劃分為子蜂群并將蜂群構(gòu)造為彈性分布式數(shù)據(jù)集，子蜂群使用廣播機制交換優(yōu)秀個體；然后，采用一系列轉(zhuǎn)換算子，實現(xiàn)蜜蜂尋找解過程的并行化；最后，用萬有引力質(zhì)量計算代替輪盤賭概率計算，減少計算量。通過旅行商問題(TSP)求解說明了算法的可行性。實驗結(jié)果表明：對比標(biāo)準(zhǔn)ABC算法，所提算法加速比最大達(dá)到3.24；對比未改進(jìn)的并行ABC算法，該算法收斂速度提高約10%。所提算法在復(fù)雜問題求解方面優(yōu)勢更加明顯。

人工蜂群算法；Spark；并行；萬有引力算法；旅行商問題

0 引言

人工蜂群(Artificial Bee Colony, ABC)算法是由土耳其埃爾吉耶斯大學(xué)Karabaga[1]于2005年提出的基于蜜蜂采蜜行為的元啟發(fā)式搜索算法，具有群智能算法的特點，和結(jié)構(gòu)簡單、收斂速度快、容易實現(xiàn)等優(yōu)點[1-2]。該算法基于蜜蜂的群體智能和自組織模型理論，具有天然的并行性特征，但也存在易早熟、收斂速度慢等問題。

人工蜂群算法具有搜索并行性，在單處理器環(huán)境下，只能以串行方式實現(xiàn)并行搜索，這種方式不適應(yīng)大數(shù)據(jù)時代大規(guī)模增長的數(shù)據(jù)集。云計算技術(shù)的興起為人工蜂群算法的并行化實現(xiàn)提供了一個很好解決思路，其融合了并行計算和分布式計算等技術(shù)，在大規(guī)模異構(gòu)數(shù)據(jù)存儲和邏輯計算具有卓越的性能表現(xiàn)[3]。本文在已有研究的基礎(chǔ)上，基于Spark框架提出并行人工蜂群改進(jìn)算法，從而解決大規(guī)模運算中ABC算法存在的時間復(fù)雜度過高的問題。

1 Spark云計算框架

1.1 Spark生態(tài)系統(tǒng)

云計算作為一種新的并行數(shù)據(jù)處理技術(shù)，融合了網(wǎng)格計算、分布式計算和并行計算的特點[3-4]。2003年起，Google公司相繼發(fā)表了3篇奠定大數(shù)據(jù)算法基礎(chǔ)的論文：Google文件系統(tǒng)(Google File System， GFS)[5]、大型結(jié)構(gòu)化數(shù)據(jù)表(BigTable)[6]及大數(shù)據(jù)分布式計算模型(MapReduce)[7]。Apache基金會根據(jù)上述論文設(shè)計推出了Hadoop分布式系統(tǒng)基礎(chǔ)架構(gòu)，從而將全球云計算的研究推向一個高潮。當(dāng)前，全球每天產(chǎn)生的數(shù)據(jù)量達(dá)到2 EB[8]，需要處理的數(shù)據(jù)量和問題規(guī)模都爆發(fā)式增長，結(jié)合云計算技術(shù)來拓展算法的數(shù)據(jù)處理和吞吐能力成為研究熱點。

Spark云計算框架是美國加州伯克利大學(xué)算法機器人(Algorithms Machine People， AMP)實驗室開發(fā)的基于內(nèi)存計算的大數(shù)據(jù)并行計算框架。Spark是MapReduce計算模型的替代方案，彌補了采用MapReduce實現(xiàn)迭代式算法或?qū)崟r性有較高要求的應(yīng)用需求時存在的CUP與數(shù)據(jù)I/O之間異步瓶頸問題[9]。圖1展示了Spark生態(tài)系統(tǒng)，整個系統(tǒng)分為3層，最核心的是Spark Runtime，它包含了Spark最核心的功能和分布式算子。底層的Cluster Manager和Data Manager分別負(fù)責(zé)集群的資源管理和數(shù)據(jù)管理。最上層為Spark提供了豐富的計算范式，涵蓋支持結(jié)構(gòu)化數(shù)據(jù)查詢與分析的查詢引擎Spark SQL、分布式機器學(xué)習(xí)庫MLlib、并行圖計算框架GraphX、流計算框架Spark Streaming四個模塊。

圖1 Spark生態(tài)系統(tǒng)

Spark技術(shù)的興起為眾多機器學(xué)習(xí)算法提供了改進(jìn)思路：Alitouka[10]實現(xiàn)了基于Spark的密度聚類算法；王桂蘭等[11]研究了Spark環(huán)境下的并行模糊C均值聚類算法，定義了在Spark上完整的矩陣操作；牛海玲等[12]基于Spark框架將Apriori算法進(jìn)行并行化處理，并與傳統(tǒng)Apriori算法和基于Hadoop的Apriori算法進(jìn)行性能上的比較。本文研究基于Spark實現(xiàn)人工蜂群算法的方法，期望與傳統(tǒng)的實現(xiàn)進(jìn)行對比，大幅提升算法性能。

1.2 Spark關(guān)鍵技術(shù)介紹

Spark將分布式數(shù)據(jù)抽象為彈性分布式數(shù)據(jù)集(Resilient Distributed Dataset， RDD)，其是分布式數(shù)據(jù)集在本地的抽象，能夠使用戶以本地操作的方式操作分布式環(huán)境中的數(shù)據(jù)集合。RDD提供了一種高度受限的共享內(nèi)存，并且只能基于在穩(wěn)定物理存儲中的數(shù)據(jù)集和其他已有的RDD上執(zhí)行確定性操作來創(chuàng)建，這些確定性操作稱之為轉(zhuǎn)換算子，如count、reduceBykey、partitionBy、union等。除了轉(zhuǎn)換算子，Spark還提供輸入算子、緩存算子和行動算子，Hadoop中提供的Map和Reduce操作也被封裝進(jìn)Spark的算子中。可以說Spark在繼承Hadoop優(yōu)秀基因的同時還提供了更為豐富的接口和操作[11]。

RDD數(shù)據(jù)同步是支持Spark集群各節(jié)點并行工作的重要保證。RDD目前提供兩個數(shù)據(jù)同步的方法：廣播(Broadcast)和累加器(Accumulator)。廣播依靠廣播變量實現(xiàn)變量共享，可以有效解決物理上隔離的兩個節(jié)點之間訪問公共數(shù)據(jù)的存儲問題，廣播變量是read-only的，變量修改后不會反饋到其他節(jié)點；累加器是一個write-only變量，用于累加各個任務(wù)中的狀態(tài)，該狀態(tài)變量可以被維護(hù)累加器的所有節(jié)點共享。

2 基于Spark的人工蜂群算法

2.1 人工蜂群算法

自然界中蜜蜂在采蜜時根據(jù)太陽位置記錄自己蜜源的方位、離蜂巢的距離等信息[1-2]。人工蜂群算法模擬蜜蜂采蜜的群體智能行為，把蜂群分為引領(lǐng)蜂、偵察蜂和跟隨蜂[13]。引領(lǐng)蜂確定蜜源的位置并指導(dǎo)蜂群的采蜜行為，待工蜂可變?yōu)楦S蜂或偵察蜂，跟隨蜂增強種群對優(yōu)良蜜源的找尋能力，偵察蜂保持種群的多樣性并最終轉(zhuǎn)換成跟隨蜂或引領(lǐng)蜂。算法主要操作有引領(lǐng)蜂搜索、偵查蜂搜索和跟隨蜂選擇[14]。

1)引領(lǐng)蜂搜索。

引領(lǐng)蜂隨機搜索區(qū)域并記憶初始蜜源位置，按式(1)對蜜源進(jìn)行鄰域搜索：

Vi,j=xi,j+φi,j·(xi,j-xk,j)

(1)

其中：Vi,j表示新的食物源，其在先前食物源xi,j和鄰近食物源xk,j比較計算的基礎(chǔ)上得到，j∈{1,2,…,D}，k∈{1,2,…,N}，D代表食物源中的參數(shù)維數(shù)，N表示食物源的數(shù)量；φi,j是[-1,1]區(qū)間的隨機數(shù)。引領(lǐng)蜂對更新后食物源采用貪婪選擇策略進(jìn)行選取。

2)偵察蜂搜索。

ABC算法中食物源的鄰域搜索次數(shù)存在一個閾值limit，是算法中控制質(zhì)量沒有改善的某個食物源的更新次數(shù)的重要參數(shù)。當(dāng)某個食物源更新次數(shù)超過limit，質(zhì)量卻沒有得到改善，該食物源將被新的食物源替換，此時引領(lǐng)蜂變?yōu)閭刹旆洳词?2)進(jìn)行隨機搜索產(chǎn)生新的食物源：

Xi,j=lbj+θ·(ubj-lbj)

(2)

其中：i代表第i個食物源，θ為(0,1)內(nèi)隨機數(shù)，ubj、lbj分別是第j維參數(shù)決定的食物源質(zhì)量的上限和下限。

3)跟隨蜂選擇。

按式(3)計算每個引領(lǐng)蜂的選擇概率，跟隨蜂以輪盤賭原則選擇引領(lǐng)蜂并跟隨：

(3)

其中fiti代表第i個食物源的質(zhì)量值，具體值由相應(yīng)的適應(yīng)度評價函數(shù)求得。蜜蜂被選中概率與自身適應(yīng)度值成正比。跟隨蜂選擇食物源后同樣按照式(1)搜索新食物源。

2.2 選擇概率的改進(jìn)

(4)

其中：mi表示蜜蜂的收益度比率；Mi表示蜜蜂的慣性質(zhì)量，也就是選擇概率；best表示最佳食物源；worst表示最差食物源；mi與蜜蜂本身的適應(yīng)度值正相關(guān)，越優(yōu)秀的個體越能保持迭代持續(xù)性，有效保證種群優(yōu)良性。

2.3 人工蜂群優(yōu)化算法的實現(xiàn)

人工蜂群算法具有天然的并行性，并行策略大致有：①并行獨立蜂群，蜂群間無交互；②并行非獨立子蜂群，子蜂群交互式并行搜索；③并行蜜蜂，即一個蜜蜂對應(yīng)一個節(jié)點，各蜜蜂并行搜索。方式①忽略了蜜蜂之間的信息交流且需要大規(guī)模集群的支持。方式②、③本質(zhì)上相同，考慮到蜂群算法中種群規(guī)模對算法的性能提升有一個閾值，種群過大反而會增加計算量，因此本文選取方式②作為Spark并行策略，提出基于Spark的人工蜂群改進(jìn)算法——GABC-Spark(Gravitation Artificial Bee Colony based on Spark)。

圖2展示了GABC-Spark算法的流程。每個子蜂群搜索解的過程并行，子蜂群內(nèi)部搜索仍然串行，子蜂群對食物源的鄰域搜索為一個獨立的并行單元，因此，假設(shè)子蜂群規(guī)模為k，則N只蜜蜂組成的蜂群構(gòu)成N/k個獨立的并行單元。每次迭代完成個體按收益度值排序，記錄子蜂群最優(yōu)與最差食物源。之后，子蜂群廣播自身最優(yōu)食物源同時接收其他子蜂群的廣播消息。當(dāng)其他蜂群最優(yōu)食物源更優(yōu)秀時，子蜂群將自身最差食物源替換為獲得的最優(yōu)食物源，引領(lǐng)本身的下一次迭代。

圖2 GABC-Spark算法流程

圖3展示了算法在Spark實現(xiàn)并行的數(shù)據(jù)流圖。通過數(shù)據(jù)流圖描述算法并行化過程如下：將蜜蜂封裝為類Bee，類中包含有Initialize()方法用于解的構(gòu)造，LocalSearch()方法用于鄰域搜索。生成蜂群就是初始化m個Bee類的實例，則蜂群規(guī)模NP的值為m。利用系統(tǒng)提供的ArrayList集合類封裝m個Bee實例，之后使用SparkContext對象的parallelize()方法將對象數(shù)組創(chuàng)建為分布式RDD，記為RDD_a。調(diào)用RDD_a.map()算子將子蜂群映射到各子節(jié)點并調(diào)用Initialize()方法并行構(gòu)造解，結(jié)果返回為格式為ArrayList[ArrayList[]]的RDD:RDD_b，然后再調(diào)用RDD_b.map()算子并行調(diào)用LoaclSearch()局部搜索方法，同樣返回格式為ArrayList[ArrayList[]]的RDD:RDD_c。最后使用RDD的collect算子將分布式的RDD_c本地化，排序得到最優(yōu)解。

需要注意的是，應(yīng)用到實際問題時算法參數(shù)、當(dāng)前最優(yōu)個體等使用多次的數(shù)據(jù)需要緩存，否則會進(jìn)行不必要的重復(fù)操作。RDD提供cache()方法來緩存共享數(shù)據(jù)。而問題求解的中間數(shù)據(jù)(如TSP中的轉(zhuǎn)移概率和路徑記錄矩陣)使用broadcast廣播機制發(fā)送廣播信息，讓蜂群所有蜜蜂可以互相交流通信。

圖3 GABC-Spark算法數(shù)據(jù)流圖

3 實驗設(shè)計與結(jié)果分析

3.1 實驗環(huán)境及算法參數(shù)

實驗集群環(huán)境為阿里云ECS云服務(wù)器實例，安裝64位Ubuntu 14.04系統(tǒng)，集群實驗環(huán)境節(jié)點屬性詳見表1。單機環(huán)境屬性為：Intel Xeon CPU，3.00 GHz四核；8 GB內(nèi)存；500 GB機械硬盤；Windows 7 64 bit操作系統(tǒng)，Matlab R2012b。為保證實驗的準(zhǔn)確性，實驗中算法參數(shù)均與文獻(xiàn)[16]一致。

表1 集群屬性

3.2 實驗方案

以旅行商問題(Traveling Salesman Problem， TSP)為例，選用標(biāo)準(zhǔn)數(shù)據(jù)集開展實驗。為了對比改進(jìn)前后算法的加速效果，選用文獻(xiàn)[17]中使用的eil51、ch130、tsp225作為實驗數(shù)據(jù)。對人工蜂群算法按照文獻(xiàn)[16]所述進(jìn)行改造編碼，該文獻(xiàn)中人工蜂群算法與TSP對應(yīng)關(guān)系如表2所示。根據(jù)文獻(xiàn)[16]所述并結(jié)合本文概率計算式(4)，得到實驗中蜜蜂的收益度計算公式如式(5)：

(5)

其中：fi代表路徑歐氏距離的倒數(shù)，min(f)、max(f)分別表示蜂群中最差解和最優(yōu)解，fibee是當(dāng)前第ibee只蜜蜂的收益。

為證明本文算法的有效性和可用性，同ABC[16]、蟻群優(yōu)化(Ant Colony Optimization， ACO)算法、基于Spark的蟻群優(yōu)化算法(Ant Colony Optimization algorithm based on Spark， ACO-Spark)[17]進(jìn)行比較實驗，實驗結(jié)果如表3所示。對實驗結(jié)果使用雙尾t-test雙樣本等方差假設(shè)檢驗[18-19]，比較ABC算法和GABC-Spark算法的解，結(jié)果如表4所示。表5為算法在節(jié)點數(shù)量不同的集群中搜索到目標(biāo)解的平均時間花費，目標(biāo)值時間是指eil51收斂到450、ch130收斂到6 500、tsp225收斂到4 500所花時間。

表2 ABC算法中蜂群覓食行為與TSP對應(yīng)關(guān)系

表3 實驗結(jié)果

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

由表3可知，ABC算法和GABC-Spark算法在尋優(yōu)能力上略好于ACO算法，其最優(yōu)解均為測試集已知的最優(yōu)解。通過表4可知在統(tǒng)計學(xué)意義上GABC-Spark算法和ABC算法具有相同的尋優(yōu)能力，證明改造前后的算法在尋優(yōu)能力上并沒有損失。

表4 雙尾t-test檢驗結(jié)果

表5給出了在不同集群環(huán)境下算法收斂到目標(biāo)值的時間，并得出了相對于單機Matlab中運行所花時間的加速比，其中eil51、ch130、tsp225單機平均運行時間分別29.10 s、151.28 s和492.22 s?？傮w來看相對于單機運行的ABC算法，GABC-Spark算法的加速比最高可達(dá)3.24且有持續(xù)增長的趨勢，且隨著問題規(guī)模的增加，加速效果愈加明顯。實驗結(jié)果表明GABC-Spark算法運行時間較基于Spark的標(biāo)準(zhǔn)人工蜂群算法(Algorithm of Artificial Bee Colony based on Spark， ABC-Spark)均有減少，在節(jié)點數(shù)為1時表現(xiàn)得尤為明顯，隨著集群規(guī)模的增加，算法總體迭代次數(shù)減少，GABC較ABC的加速效果開始減弱，因此，問題規(guī)模越大、算法迭代次數(shù)越多，GABC加速效果越顯著。對于eil51測試集，GABC-Spark算法的搜索效率反而不如單機下運行，這是因為該測試集解空間不太復(fù)雜在單機下就能很好解決。而在Spark中因其TaskScheduler任務(wù)調(diào)度采用集中式調(diào)度以保證每個節(jié)點都有Task在執(zhí)行，有一定的任務(wù)分配時間，加上算法運行中節(jié)點之間的大量通信時延所以其整體運行時間要高于Matlab下運行時間，并且隨著節(jié)點數(shù)的增加，任務(wù)調(diào)度和通信時延逐步增長，運行時間也持續(xù)增加。在集群節(jié)點數(shù)為1時，算法的運行時間普遍高于單機下運行時間，這Spark本身關(guān)系外還有高級語言運行速度低于函數(shù)型語言外的原因，因此求解時間出現(xiàn)逆增長。對于ch130測試集，算法加速比先增后減，說明集群規(guī)模增加對算法程序性能提升存在一個瓶頸，當(dāng)增加節(jié)點帶來的計算效率的提升低于通信和任務(wù)調(diào)度時間消耗時，算法加速能力開始退化。tsp225測試集因為解空間較為復(fù)雜，所以加速比一直隨著節(jié)點數(shù)增加而增長?？梢灶A(yù)見，隨著問題解空間復(fù)雜度的增大和計算規(guī)模的增加，算法加速比將會隨著節(jié)點數(shù)的增加而持續(xù)提升。

表5 不同實驗環(huán)境運行時間及加速比

4 結(jié)語

本文對人工蜂群算法結(jié)合Spark分布式計算框架實現(xiàn)并行化進(jìn)行研究。首先介紹了人工蜂群算法的思想、流程，并對人工蜂群算法的3種并行方式進(jìn)行了探討。依據(jù)子蜂群交互式并行搜索策略實現(xiàn)人工蜂群算法的Spark并行化，使其能夠運行在云計算集群中。針對算法選擇概率計算復(fù)雜的問題，引入萬有引力質(zhì)量計算，替換基本算法中的輪盤賭概率計算，減輕了計算壓力，并可以同時獲得種群中蜜蜂收益度值的排名，降低搜索時間提升算法收斂速度，為進(jìn)一步研究算法不同參數(shù)的性能表現(xiàn)和提升算法在集群下的運算效率奠定基礎(chǔ)。

References)

[1] KARABOGA D. An idea based on honey bee swarm for numerical optimization [R]. Kayseri: Erciyes University, 2005.

[2] KARABOGA D, BASTURK B. On the performance of Artificial Bee Colony (ABC) algorithm [J]. Applied Soft Computing, 2008, 8(1): 687-697.

[3] 李喬,鄭嘯.云計算研究現(xiàn)狀綜述[J].計算機科學(xué),2011,38(4):32-37.(LI Q, ZHENG X. Research survey of cloud computing [J]. Computer Science, 2011, 38(4): 32-37.)

[4] 林闖,蘇文博,孟坤,等.云計算安全:架構(gòu)、機制與模型評價[J].計算機學(xué)報,2013,36(9):1765-1784.(LIN C, SU W B, MENG K, et al. Cloud computing security: architecture, mechanism and modeling [J]. Chinese Journal of Computers, 2013, 36(9): 1765-1784.)

[5] GHEMAWAT S, GOBIOFF H, LEUNG S. The Google file system [C]// SOSP 2003: Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles. New York: ACM Press, 2003: 29-43.

[6] CHANG F, DEAM J, GHEMAWAT S, et al. Bigtable: a distributed storage system for structured data [J]. ACM Transactions on Computer Systems, 2008, 26(2): 205-218.

[7] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-117.

[8] 李建中,王宏志,高宏.大數(shù)據(jù)可用性的研究進(jìn)展[J].軟件學(xué)報,2016,27(7):1605-1625.(LI J Z, WANG H Z, GAO H. State-of-the-art of research on big data usability [J]. Journal of Software, 2016, 27(7): 1605-1625.)

[9] 宋杰,劉雪冰,朱志良,等.一種能效優(yōu)化的MapReduce資源比模型[J].計算機學(xué)報,2015,38(1):59-73.(SONG J, LIU X B, ZHU Z L, et al. An energy-efficiency optimized resource ratio model for MapReduce [J]. Chinese Journal of Computers, 2015, 38(1): 59-73.)

[10] Alitouka. Spark-DBSCAN [EB/OL]. [2016- 10- 23]. https://github.com/alitouka/spark_dbscan.

[11] 王桂蘭,周國亮,薩初日拉,等.Spark環(huán)境下的并行模糊C均值聚類算法[J].計算機應(yīng)用,2016,36(2):342-347.(WANG G L, ZHOU G L, SA C, et al. Parallel fuzzy C-means clustering algorithm in Spark [J]. Journal of Computer Applications, 2016, 36(2): 342-347.)

[12] 牛海玲,魯慧民,劉振杰.基于Spark的Apriori算法的改進(jìn)[J].東北師大學(xué)報(自然科學(xué)版),2016,48(1):84-89.(NIU H L, LU H M, LIU Z J. The improvement and research of Apriori algorithm based on Spark [J]. Journal of Northeast Normal University (Natural Science Edition), 2016, 48(1): 84-89.)

[13] SABET S, FAROKHI F, SHOKOUHIFAR M. A novel artificial bee colony algorithm for the knapsack problem [C]// INISTA 2012: Proceedings of the 2012 International Symposium on Innovations in Intelligent Systems and Applications. Piscataway, NJ: IEEE, 2012: 141-151.

[14] 楊進(jìn),馬良.蜂群優(yōu)化算法在車輛路徑問題中的應(yīng)用[J].計算機工程與應(yīng)用,2010,46(5):214-216.(YANG J, MA L. Wasp colony algorithm for vehicle routing problem [J]. Computer Engineering and Applications, 2010, 46(5): 214-216.)

[15] 張維平,任雪飛,李國強,等.改進(jìn)的萬有引力搜索算法在函數(shù)優(yōu)化中的應(yīng)用[J].計算機應(yīng)用,2013,35(5):1317-1320.(ZHANG W P, REN X F, LI G Q, et al. Improved gravitation search algorithm and its application to function optimization [J]. Journal of Computer Applications, 2013, 35(5): 1317-1320.)

[16] 胡中華,趙敏.基于人工蜂群算法的TSP仿真[J].北京理工大學(xué)學(xué)報,2009,29(11):978-982.(HU Z H, ZHAO M. Simulation on Traveling Salesman Problem (TSP) based on artificial bees colony algorithm [J]. Transaction of Beijing Institute of Technology, 2009, 29(11): 978-982.)

[17] 王詔遠(yuǎn),王宏杰,邢煥來,等.基于Spark的蟻群優(yōu)化算法[J].計算機應(yīng)用,2015,35(10):2777-2780.(WANG Z Y, WANG H J, XING H L, et al. Ant colony optimization algorithm based on Spark [J]. Journal of Computer Applications, 2015, 35(10): 2777-2780.)

[18] CUI W, LI X, ZHOU S, et al. Investigation on process parameters of electrospinning system through orthogonal experimental design [J]. Journal of Applied Polymer Science, 2007, 103(5): 3105-3112.

[19] XING H, QU R, KENDALL G, et al. A path-oriented encoding evolutionary algorithm for network coding resource minimization [J] Journal of the Operational Research Society, 2013, 65(8): 1261-1277.

This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2009AA062802), the National Natural Science Foundation of China (60473125), Youth Innovation Fund of China National Petroleum Corporation (CNPC) (05E7013), Sub-project of the National Science and Technology Major Project (G5800- 08-ZS-WX), China University of Petroleum-Beijing Karamay Campus Research Start Fund (RCYJ2016B- 03- 001).

ZHAIGuangming, born in 1993, M. S. candidate. His research interests include data mining, knowledge discovery.

LIGuohe, born in 1965, Ph. D., professor. His research interests include artificial intelligence, machine learning, knowledge discovery.

WUWeijiang, born in 1971, Ph. D. candidate, associate professor. His research interests include artificial intelligence, knowledge discovery.

HONGYunfeng, born in 1966, engineer. His research interests include ERP, data management.

ZHOUXiaoming, born in 1963, M. S., engineer. His research interests include information management system, decision support.

WANGJing, born in 1989, M. S. candidate. Her research interests include data mining, knowledge discovery.

ImprovedalgorithmofartificialbeecolonybasedonSpark

ZHAI Guangming1,2*, LI Guohe1,2,3, WU Weijiang1,2,3, HONG Yunfeng3, ZHOU Xiaoming3, WANG Jing1,2

(1.CollegeofGeophysicsandInformationEngineering,ChinaUniversityofPetroleum-Beijing,Beijing102249,China;2.BeijingKeyLabofDataMiningforPetroleumData,ChinaUniversityofPetroleum-Beijing,Beijing102249,China;3.PanPassInstituteofDigitalIdentificationManagementandInternetofThings,Beijing100029,China)

To combat low efficiency of Artificial Bee Colony (ABC) algorithm on solving combinatorial problem, a parallel ABC optimization algorithm based on Spark was presented. Firstly, the bee colony was divided into subgroups among which broadcast was used to transmit data, and then was constructed as a resilient distributed dataset. Secondly, a series of transformation operators were used to achieve the parallelization of the solution search. Finally, gravitational mass calculation was used to replace the roulette probability selection and reduce the time complexity. The simulation results in solving the Traveling Salesman Problem (TSP) prove the feasibility of the proposed parallel algorithm. The experimental results show that the proposed algorithm provides a 3.24x speedup over the standard ABC algorithm and its convergence speed is increased by about 10% compared with the unimproved parallel ABC algorithm. It has significant advantages in solving high dimensional problems.

Artificial Bee Colony (ABC) algorithm; Spark; paralleling; gravitational search algorithm; Traveling Salesman Problem (TSP)

TP301.6; TP18

:A

2017- 01- 24;

:2017- 02- 12。

國家863計劃項目(2009AA062802)；國家自然科學(xué)基金資助項目(60473125)；中國石油(CNPC)石油科技中青年創(chuàng)新基金資助項目(05E7013)；國家重大科技專項子課題(G5800- 08-ZS-WX)；中國石油大學(xué)(北京)克拉瑪依校區(qū)科研啟動基金資助(RCYJ2016B- 03- 001)。

翟光明(1993—)，男，湖南懷化人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、知識發(fā)現(xiàn)； 李國和(1965—)，男，北京人，教授，博士，主要研究方向：人工智能、機器學(xué)習(xí)、知識發(fā)現(xiàn)； 吳衛(wèi)江(1971—)，男，北京人，副教授，博士研究生，主要研究方向：人工智能、知識發(fā)現(xiàn)；洪云峰(1966—)，男，湖北武漢人，工程師，主要研究方向：ERP、數(shù)據(jù)管理； 周曉明(1963—)，男，湖北武漢人，工程師，碩士，主要研究方向：信息管理系統(tǒng)、決策支持； 汪靜(1989—)，女，山東聊城人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、知識發(fā)現(xiàn)。

1001- 9081(2017)07- 1906- 05

10.11772/j.issn.1001- 9081.2017.07.1906