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

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

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

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

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

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

人工蜂群算法；Spark；并行；萬(wàn)有引力算法；旅行商問(wèn)題

0 引言

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

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

1 Spark云計(jì)算框架

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

云計(jì)算作為一種新的并行數(shù)據(jù)處理技術(shù)，融合了網(wǎng)格計(jì)算、分布式計(jì)算和并行計(jì)算的特點(diǎn)[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ù)分布式計(jì)算模型(MapReduce)[7]。Apache基金會(huì)根據(jù)上述論文設(shè)計(jì)推出了Hadoop分布式系統(tǒng)基礎(chǔ)架構(gòu)，從而將全球云計(jì)算的研究推向一個(gè)高潮。當(dāng)前，全球每天產(chǎn)生的數(shù)據(jù)量達(dá)到2 EB[8]，需要處理的數(shù)據(jù)量和問(wèn)題規(guī)模都爆發(fā)式增長(zhǎng)，結(jié)合云計(jì)算技術(shù)來(lái)拓展算法的數(shù)據(jù)處理和吞吐能力成為研究熱點(diǎn)。

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

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

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

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)定物理存儲(chǔ)中的數(shù)據(jù)集和其他已有的RDD上執(zhí)行確定性操作來(lái)創(chuàng)建，這些確定性操作稱之為轉(zhuǎn)換算子，如count、reduceBykey、partitionBy、union等。除了轉(zhuǎn)換算子，Spark還提供輸入算子、緩存算子和行動(dòng)算子，Hadoop中提供的Map和Reduce操作也被封裝進(jìn)Spark的算子中?？梢哉f(shuō)Spark在繼承Hadoop優(yōu)秀基因的同時(shí)還提供了更為豐富的接口和操作[11]。

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

2 基于Spark的人工蜂群算法

2.1 人工蜂群算法

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

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

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

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

(1)

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

2)偵察蜂搜索。

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

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

(2)

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

3)跟隨蜂選擇。

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

(3)

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

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

(4)

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

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

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

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

圖2 GABC-Spark算法流程

圖3展示了算法在Spark實(shí)現(xiàn)并行的數(shù)據(jù)流圖。通過(guò)數(shù)據(jù)流圖描述算法并行化過(guò)程如下：將蜜蜂封裝為類Bee，類中包含有Initialize()方法用于解的構(gòu)造，LocalSearch()方法用于鄰域搜索。生成蜂群就是初始化m個(gè)Bee類的實(shí)例，則蜂群規(guī)模NP的值為m。利用系統(tǒng)提供的ArrayList集合類封裝m個(gè)Bee實(shí)例，之后使用SparkContext對(duì)象的parallelize()方法將對(duì)象數(shù)組創(chuàng)建為分布式RDD，記為RDD_a。調(diào)用RDD_a.map()算子將子蜂群映射到各子節(jié)點(diǎn)并調(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í)際問(wèn)題時(shí)算法參數(shù)、當(dāng)前最優(yōu)個(gè)體等使用多次的數(shù)據(jù)需要緩存，否則會(huì)進(jìn)行不必要的重復(fù)操作。RDD提供cache()方法來(lái)緩存共享數(shù)據(jù)。而問(wèn)題求解的中間數(shù)據(jù)(如TSP中的轉(zhuǎn)移概率和路徑記錄矩陣)使用broadcast廣播機(jī)制發(fā)送廣播信息，讓蜂群所有蜜蜂可以互相交流通信。

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

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

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

表1 集群屬性

3.2 實(shí)驗(yàn)方案

以旅行商問(wèn)題(Traveling Salesman Problem， TSP)為例，選用標(biāo)準(zhǔn)數(shù)據(jù)集開(kāi)展實(shí)驗(yàn)。為了對(duì)比改進(jìn)前后算法的加速效果，選用文獻(xiàn)[17]中使用的eil51、ch130、tsp225作為實(shí)驗(yàn)數(shù)據(jù)。對(duì)人工蜂群算法按照文獻(xiàn)[16]所述進(jìn)行改造編碼，該文獻(xiàn)中人工蜂群算法與TSP對(duì)應(yīng)關(guān)系如表2所示。根據(jù)文獻(xiàn)[16]所述并結(jié)合本文概率計(jì)算式(4)，得到實(shí)驗(yàn)中蜜蜂的收益度計(jì)算公式如式(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)行比較實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3所示。對(duì)實(shí)驗(yàn)結(jié)果使用雙尾t-test雙樣本等方差假設(shè)檢驗(yàn)[18-19]，比較ABC算法和GABC-Spark算法的解，結(jié)果如表4所示。表5為算法在節(jié)點(diǎn)數(shù)量不同的集群中搜索到目標(biāo)解的平均時(shí)間花費(fèi)，目標(biāo)值時(shí)間是指eil51收斂到450、ch130收斂到6 500、tsp225收斂到4 500所花時(shí)間。

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

表3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

4 結(jié)語(yǔ)

本文對(duì)人工蜂群算法結(jié)合Spark分布式計(jì)算框架實(shí)現(xiàn)并行化進(jìn)行研究。首先介紹了人工蜂群算法的思想、流程，并對(duì)人工蜂群算法的3種并行方式進(jìn)行了探討。依據(jù)子蜂群交互式并行搜索策略實(shí)現(xiàn)人工蜂群算法的Spark并行化，使其能夠運(yùn)行在云計(jì)算集群中。針對(duì)算法選擇概率計(jì)算復(fù)雜的問(wèn)題，引入萬(wàn)有引力質(zhì)量計(jì)算，替換基本算法中的輪盤賭概率計(jì)算，減輕了計(jì)算壓力，并可以同時(shí)獲得種群中蜜蜂收益度值的排名，降低搜索時(shí)間提升算法收斂速度，為進(jìn)一步研究算法不同參數(shù)的性能表現(xiàn)和提升算法在集群下的運(yù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] 李喬,鄭嘯.云計(jì)算研究現(xiàn)狀綜述[J].計(jì)算機(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] 林闖,蘇文博,孟坤,等.云計(jì)算安全:架構(gòu)、機(jī)制與模型評(píng)價(jià)[J].計(jì)算機(jī)學(xué)報(bào),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é)報(bào),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].計(jì)算機(jī)學(xué)報(bào),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] 王桂蘭,周國(guó)亮,薩初日拉,等.Spark環(huán)境下的并行模糊C均值聚類算法[J].計(jì)算機(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é)報(bào)(自然科學(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)化算法在車輛路徑問(wèn)題中的應(yīng)用[J].計(jì)算機(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] 張維平,任雪飛,李國(guó)強(qiáng),等.改進(jìn)的萬(wàn)有引力搜索算法在函數(shù)優(yōu)化中的應(yīng)用[J].計(jì)算機(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é)報(bào),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),王宏杰,邢煥來(lái),等.基于Spark的蟻群優(yōu)化算法[J].計(jì)算機(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。

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

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

1001- 9081(2017)07- 1906- 05

10.11772/j.issn.1001- 9081.2017.07.1906