基于Spark大數(shù)據(jù)計(jì)算模型的多種群并行進(jìn)化遺傳算法*

任 剛,吳長(zhǎng)茂,魏 勇,劉小杰,郜廣蘭,王鮮芳

(1. 河南工學(xué)院 計(jì)算機(jī)學(xué)院,河南 新鄉(xiāng) 453003; 2. 中國(guó)科學(xué)院軟件研究所 并行軟件實(shí)驗(yàn)室,北京 100190;3. 河南省生產(chǎn)制造物聯(lián)大數(shù)據(jù)工程技術(shù)研究中心,河南 新鄉(xiāng) 453003)

0 引言

遺傳算法(Genetic Algorithm,GA)是一種借鑒生物自然選擇機(jī)制的全局隨機(jī)搜索算法,該算法通過(guò)選擇、交叉和變異等遺傳算子來(lái)搜索問(wèn)題最優(yōu)解。相較于傳統(tǒng)搜索算法,該算法不需要專門領(lǐng)域的知識(shí),僅用適應(yīng)度評(píng)估函數(shù)來(lái)指導(dǎo)搜索過(guò)程,求解過(guò)程較為簡(jiǎn)單,同時(shí)最終結(jié)果不依賴于初始種群,具有較強(qiáng)的魯棒性,從而在多個(gè)領(lǐng)域得到應(yīng)用[1-3]。但是,由于傳統(tǒng)GA中包含較多的遺傳操作,當(dāng)問(wèn)題規(guī)模較大時(shí),其性能降低,因此,通過(guò)并行方法來(lái)提高傳統(tǒng)GA的性能成為該領(lǐng)域研究熱點(diǎn)之一[4]。在眾多并行遺傳算法(Parallel Genetic Algorithm, PGA)中,基于MPI消息傳遞集群系統(tǒng)[5]的多種群并行進(jìn)化PGA[6-8]被證明是一種有效提升PGA性能的機(jī)制。多種群并行進(jìn)化PGA將整個(gè)種群平均分配到集群節(jié)點(diǎn)上,形成多個(gè)具有不同進(jìn)化參數(shù)的并行進(jìn)化子種群,并定期交換各自計(jì)算成果,從而提高了傳統(tǒng)GA的收斂速度和計(jì)算效率,為用戶提供了一套性價(jià)比較高的并行計(jì)算環(huán)境。

隨著大數(shù)據(jù)時(shí)代的到來(lái),以Spark為代表的計(jì)算模型由于其出色的數(shù)據(jù)并行能力被廣泛應(yīng)用?；赟park計(jì)算模型的PGA (Spark-based Parallel Genetic Algorithm,SPGA)由于綜合了Spark模型在數(shù)據(jù)并行上的優(yōu)勢(shì)和PGA在全局搜索上的優(yōu)勢(shì),在多個(gè)領(lǐng)域受到歡迎[9]。然而,由于該算法缺乏多種群并行進(jìn)化機(jī)制,當(dāng)問(wèn)題規(guī)模較大時(shí),計(jì)算效率偏低。因此,急需將多種群并行進(jìn)化機(jī)制引入經(jīng)典SPGA中。由于消息傳遞集群的并行機(jī)制與Spark并行機(jī)制相差較大,現(xiàn)有的基于消息傳遞集群的多種群并行進(jìn)化機(jī)制不適用于具有特定并行機(jī)制的Spark模型。為此,深入研究Spark模型的并行機(jī)制與多種群并行進(jìn)化機(jī)制之間的關(guān)系,將多種群并行進(jìn)化機(jī)制引入經(jīng)典SPGA,以提高其收斂速度和計(jì)算效率,具體研究成果有:(1)將多種群并行進(jìn)化機(jī)制引入經(jīng)典SPGA,形成一種具有多種群并行進(jìn)化功能的SPGA——多種群并行進(jìn)化SPGA (Multi-population Parallel Evolutionary SPGA, MPE-SPGA);(2)將新算法應(yīng)用到旅行商問(wèn)題(Travelling Salesman Problem, TSP)上,通過(guò)3組實(shí)驗(yàn)驗(yàn)證該算法具有較高的計(jì)算效率。

1 相關(guān)工作

由于GA的遺傳算子計(jì)算量較大,在解決大規(guī)模組合優(yōu)化問(wèn)題時(shí),其計(jì)算性能往往成為該算法的瓶頸。因此,GA的并行化一直是該領(lǐng)域的研究熱點(diǎn)之一。以Spark為代表的大數(shù)據(jù)并行計(jì)算模型由于其出色的數(shù)據(jù)并行能力而得到廣泛應(yīng)用。隨之,基于大數(shù)據(jù)并行計(jì)算模型的PGA成為一個(gè)研究熱點(diǎn)。Spark是一種基于內(nèi)存計(jì)算的計(jì)算模型,較之傳統(tǒng)的基于磁盤文件系統(tǒng)的MapReduce模型[10],更適宜像GA這類的迭代計(jì)算[9]。該模型在兩次迭代之間,數(shù)據(jù)文件無(wú)需在磁盤上落地,可直接進(jìn)入下次迭代計(jì)算過(guò)程,因此,節(jié)省了大量的磁盤I/O時(shí)間。因此,基于Spark計(jì)算模型的PGA成為一個(gè)新的研究熱點(diǎn)。文獻(xiàn)[11]提出了一種可以將適應(yīng)度評(píng)估、交叉和變異等操作并行化的SPGA,并將此算法應(yīng)用在測(cè)試案例生成問(wèn)題中。文獻(xiàn)[12]將SPGA引入傳感器鋪設(shè)問(wèn)題,取得良好效果。文獻(xiàn)[13]將SPGA應(yīng)用到TSP問(wèn)題中,結(jié)果說(shuō)明SPGA具有較好的全局尋優(yōu)性能。文獻(xiàn)[14]將SPGA引入多峰函數(shù)極值問(wèn)題,實(shí)驗(yàn)結(jié)果表明SPGA有較好的收斂性?？梢钥闯?由于具有良好的性能,SPGA成為一種流行的基于大數(shù)據(jù)計(jì)算平臺(tái)的PGA。但是,傳統(tǒng)SPGA缺乏多種群并行進(jìn)化機(jī)制,在問(wèn)題規(guī)模較大的情況下,性能還不是太理想。因此,急需將多種群并行進(jìn)化機(jī)制引入經(jīng)典SPGA,以滿足快速增長(zhǎng)的計(jì)算需求。

2 多種群并行進(jìn)化SPGA

2.1 Spark計(jì)算模型

Spark是一種以彈性分布式數(shù)據(jù)集(Resilient Distributed Dataset, RDD)為核心的并行計(jì)算模型,其并行架構(gòu)如圖1所示。RDD是基于內(nèi)存的只讀數(shù)據(jù)集合,通過(guò)轉(zhuǎn)換(Transformation)和動(dòng)作(Action)兩類操作完成RDD處理。轉(zhuǎn)換操作主要包括Map、flatMap和join等操作符。動(dòng)作操作主要包括Reduce、count等操作符。較之傳統(tǒng)的MapReduce模型,Spark操作符更豐富,有更強(qiáng)的表達(dá)能力。另外,基于RDD的編程方式效率更高。

圖1 Spark并行架構(gòu)

2.2 遺傳算法基本理論

GA是模仿生物進(jìn)化理論而提出的一種優(yōu)化計(jì)算模型,該算法通過(guò)模擬生物基因自然進(jìn)化過(guò)程在全局問(wèn)題空間里搜索近似最優(yōu)解。整個(gè)解題過(guò)程如圖3所示,包括種群初始化、評(píng)估、選擇、交叉、變異等過(guò)程。該算法具有較強(qiáng)的魯棒性。遺傳算法面臨的主要挑戰(zhàn)是傳個(gè)體數(shù)量與求解質(zhì)量的關(guān)系。如果個(gè)體數(shù)量較少,整個(gè)種群收斂速度會(huì)很快,但是求解質(zhì)量會(huì)很低。如果個(gè)體數(shù)量較多,其求解質(zhì)量會(huì)升高,但是收斂速度會(huì)很慢。因此,在解決大規(guī)模數(shù)據(jù)樣本的優(yōu)化組合問(wèn)題時(shí),如何提高遺傳算法性能成為關(guān)鍵因素。

2.3 多種群并行進(jìn)化機(jī)制

多種群并行進(jìn)化機(jī)制是提高傳統(tǒng)GA性能的有效手段之一,其基本思想是用多個(gè)子種群代替原單一種群,每個(gè)子種群采用不同交叉概率Pc和變異概率Pm獨(dú)立進(jìn)化。在每代進(jìn)化結(jié)束并生成新的種群后,找出所有子種群中的全局最優(yōu)個(gè)體,將之重新分配到各子種群中,以促進(jìn)各個(gè)子種群的進(jìn)化。該機(jī)制可提高計(jì)算速度,避免單種群進(jìn)化過(guò)程中出現(xiàn)的過(guò)早收斂現(xiàn)象

圖1顯示了一個(gè)基于消息傳遞集群的多種群并行進(jìn)化遺傳算法實(shí)例。該集群包含4個(gè)計(jì)算節(jié)點(diǎn),其中3個(gè)節(jié)點(diǎn)分別對(duì)應(yīng)子種群0,子種群1和子種群2,另外1個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn)。Sub-population0j表示子種群0的第j代個(gè)體,將該子種群的Pc和Pm設(shè)置為較大的值,用于在總的進(jìn)化過(guò)程中不斷探測(cè)新的解空間,因此,該子種群稱為探測(cè)子種群。Sub-population1j表示子種群1的第j代個(gè)體,該子種群的Pc和Pm兩值較小,稱為開(kāi)發(fā)子種群,用于在局部范圍內(nèi)尋找優(yōu)秀個(gè)體,并將其保持下來(lái);Sub-population2j的表示子種群2的第j代個(gè)體,其Pc和Pm兩值處于中間,因此,該子種群兼具上述兩個(gè)子種群的功能,稱為探測(cè)開(kāi)發(fā)子種群。在算法經(jīng)過(guò)1次迭代后,各子種群首先搜索到本地最優(yōu)解,然后發(fā)送到主節(jié)點(diǎn),由主節(jié)點(diǎn)查找全局最優(yōu)解,最后再發(fā)送回各子種群,形成下一代種群。可以看出,該算法通過(guò)具有不同進(jìn)化參數(shù)的多個(gè)子種群的協(xié)作配合,完成全局尋優(yōu)。

圖2 多種群并行進(jìn)化機(jī)制

2.4 多種群并行進(jìn)化SPGA

圖3顯示了基于Spark模型的PGA實(shí)現(xiàn)總體架構(gòu)?？梢钥闯?經(jīng)典SPGA一次迭代由Map和Reduce二個(gè)階段構(gòu)成。Map階段多個(gè)集群節(jié)點(diǎn)同時(shí)啟動(dòng)多個(gè)Map任務(wù),實(shí)現(xiàn)選擇、交叉和變異這三個(gè)遺傳算子,Reduce操作負(fù)責(zé)計(jì)算結(jié)果匯總和輸出。Map操作1次處理輸入數(shù)據(jù)文件的1行,每行包含多個(gè)遺傳個(gè)體,這些遺傳個(gè)體使用相同的交叉和變異概率進(jìn)化。這實(shí)際上是一種單種群進(jìn)化算法,其收斂速度和精度較之多種群并行進(jìn)化算法來(lái)說(shuō),相對(duì)偏低。為了解決這個(gè)問(wèn)題,將多種群并行進(jìn)化機(jī)制引入經(jīng)典SPGA,其關(guān)鍵點(diǎn)在于,本文將數(shù)據(jù)文件的1行看做1個(gè)子種群,每個(gè)子種群有多個(gè)遺傳個(gè)體。每個(gè)子種群具有單獨(dú)的交叉概率,種群個(gè)體形式化定義為:

圖3 基于Spark模型的PGA架構(gòu)

individual=〈code,fitness〉

(1)

其中,code為個(gè)體編碼,fitness為個(gè)體適應(yīng)度。多個(gè)individual個(gè)體構(gòu)成1個(gè)子種群,這樣,具有n個(gè)個(gè)體的子種群可形式化表示為式(2):

(3)

(4)

…,

(5)

(6)

…,

該鍵值對(duì)被發(fā)送到Reduce,由Spark負(fù)責(zé)連接為(key2Sub-populationi(j+1), list(value2Sub-populationi(j+1)))。

Reduce負(fù)責(zé)匯總各子種群的所有個(gè)體,并找出全局最優(yōu)解optimalIndividual,并將此解發(fā)送給各子種群。Reduce的輸出鍵值對(duì)可表示為(key3Sub-populationi(j+1),value3Sub-populationi(j+1)),如式(7) (8)所示:

key3Sub-populationi(j+1)=Sub-populationi(j+1)

(7)

{optimalIndividual}—

{randomIndividual}

(8)

通過(guò)上述步驟,多個(gè)遺傳個(gè)體形成若干個(gè)并行進(jìn)化子種群,每個(gè)子種群都有不同的交叉概率和變異概率,并在進(jìn)化過(guò)程中交換最優(yōu)個(gè)體,共享計(jì)算成果。

圖4 基于Spark的多種群并行進(jìn)化PGA實(shí)現(xiàn)

3 性能驗(yàn)證

3.1 集群主要參數(shù)

算法所用集群包含12個(gè)計(jì)算節(jié)點(diǎn),主要參數(shù)如表1所示。

表1 集群主要參數(shù)

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

旅行商問(wèn)題是典型的NP問(wèn)題,隨著問(wèn)題規(guī)模的增加,其計(jì)算復(fù)雜度呈指數(shù)級(jí)增長(zhǎng),因此本文選取旅行商問(wèn)題驗(yàn)證算法性能。采用TSPLIB庫(kù)[15]中EIL51、CHl30和TSP225這3組數(shù)據(jù)集,它們分別代表小型、中型和大型3種問(wèn)題規(guī)模。本文算法標(biāo)記為MPE-SPGA,文獻(xiàn).[16]提出的算法記為SPGA。每個(gè)算法在3個(gè)數(shù)據(jù)集上運(yùn)行20次,并記錄平均運(yùn)行時(shí)間及計(jì)算結(jié)果。

3.2.1 實(shí)驗(yàn)1:計(jì)算精度分析

計(jì)算節(jié)點(diǎn)數(shù)為3,每計(jì)算節(jié)點(diǎn)啟動(dòng)3個(gè)Map任務(wù),每個(gè)Map任務(wù)分別對(duì)應(yīng)開(kāi)發(fā)、探測(cè)和探測(cè)開(kāi)發(fā)3個(gè)子種群,共9個(gè)子種群。開(kāi)發(fā)子種群的Pc和Pm為(0.3, 0.3),探測(cè)開(kāi)發(fā)子種群的Pc和Pm為(0.6, 0.6),探測(cè)子種群的Pc和Pm為(0.9, 0.9)。最大迭代次數(shù)400,期望誤差值4%。

結(jié)果展示在表2,可知兩算法都能找到理論最優(yōu)解,說(shuō)明經(jīng)過(guò)改造后的新算法尋優(yōu)能力沒(méi)有減弱。兩算法平均解略有差異,采用雙尾t-test雙樣本等方差假設(shè)檢驗(yàn)[17, 18],自由度為138,顯著度為0.05,比較兩算法的平均解,其結(jié)果如表3所示。結(jié)果說(shuō)明,這兩種算法的平均解在統(tǒng)計(jì)學(xué)上無(wú)差異,證明改造后的算法在尋優(yōu)能力上沒(méi)有損失。

3.2.2 實(shí)驗(yàn)2:收斂速度分析

迭代次數(shù)取100,200,300,400,500,600,其他參數(shù)與實(shí)驗(yàn)1相同,其結(jié)果如表4所示。對(duì)于小問(wèn)題規(guī)模EIL51數(shù)據(jù)集,兩算法都能在100代以內(nèi)達(dá)到收斂。對(duì)于中等問(wèn)題規(guī)模CH130數(shù)據(jù)集,原算法在400代以內(nèi)收斂,而本文算法在300代以內(nèi)就能收斂。對(duì)于大問(wèn)題規(guī)模,原算法在600代以內(nèi)收斂,而本文算法在400代達(dá)到收斂。可以看出,隨著數(shù)據(jù)集的增大,本文算法的優(yōu)勢(shì)越來(lái)越明顯,說(shuō)明本文算法在大問(wèn)題規(guī)模數(shù)據(jù)集上有一定優(yōu)勢(shì)。

3.2.3 實(shí)驗(yàn)3:計(jì)算時(shí)間分析

計(jì)算節(jié)點(diǎn)數(shù)取2,4,6,8,10,12,最大迭代次數(shù)600,期望誤差值4%,其他參數(shù)與實(shí)驗(yàn)1相同,其結(jié)果如表5所示?？梢钥闯?對(duì)于各數(shù)據(jù)集,各計(jì)算節(jié)點(diǎn)數(shù),本文算法的計(jì)算時(shí)間都要少于原算法,這說(shuō)明經(jīng)過(guò)改進(jìn)的算法能夠提高計(jì)算效率。

具體來(lái)說(shuō),對(duì)于EIL51數(shù)據(jù)集,隨著計(jì)算節(jié)點(diǎn)的增加,計(jì)算時(shí)間反而增加。原算法的平均計(jì)算時(shí)間是50.35秒,本文算法平均計(jì)算時(shí)間為48.64秒,計(jì)算時(shí)間縮短了3%。這說(shuō)明本文算法在小規(guī)模數(shù)據(jù)集上,優(yōu)勢(shì)并不明顯。其原因在于,該數(shù)據(jù)集規(guī)模較少,運(yùn)算量不大,大部分時(shí)間消耗在集群的通信和調(diào)度上。

對(duì)于CH130,兩算法的計(jì)算時(shí)間都呈現(xiàn)先減少后增加的趨勢(shì),其原因在于當(dāng)問(wèn)題規(guī)模確定后,隨著節(jié)點(diǎn)數(shù)的增加,并發(fā)度逐漸升高,計(jì)算時(shí)間會(huì)逐漸減小。但是,當(dāng)節(jié)點(diǎn)數(shù)增加到一定規(guī)模,其節(jié)點(diǎn)間的通信和調(diào)度成本會(huì)逐步上升,超過(guò)節(jié)點(diǎn)增加帶來(lái)的收益。原算法平均計(jì)算時(shí)間為103.39秒,本文算法平均計(jì)算時(shí)間為80.71秒,提高了22%左右。這說(shuō)明本文算法在中規(guī)模數(shù)據(jù)集上有一定優(yōu)勢(shì)。

對(duì)于TSP225數(shù)據(jù)集,由于該問(wèn)題規(guī)模非常大,所以隨著計(jì)算節(jié)點(diǎn)逐步增加,兩算法的計(jì)算時(shí)間都持續(xù)減小。原算法平均計(jì)算時(shí)間為167.12秒,本文算法的計(jì)算時(shí)間為114.84秒,計(jì)算時(shí)間提高了31%。

可見(jiàn),本文算法對(duì)于大數(shù)據(jù)集具有特有的優(yōu)勢(shì)。可以預(yù)見(jiàn),隨著問(wèn)題解空間的增大和計(jì)算復(fù)雜度的提升,運(yùn)行時(shí)間隨著節(jié)點(diǎn)數(shù)增加而減少的效果會(huì)逐步明顯。

表2 計(jì)算結(jié)果對(duì)比

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

表4 收斂速度對(duì)比

表5 運(yùn)行時(shí)間對(duì)比

4 總結(jié)

將多種群并行進(jìn)化機(jī)制引入經(jīng)典SPGA,形成了一種新的SPGA——MPE-SPGA;將提出的方法應(yīng)用在TSP上,并選擇小型、中型和大型三種不同的TSP問(wèn)題數(shù)據(jù)集進(jìn)行試驗(yàn),實(shí)驗(yàn)結(jié)果表明,提出的算法能夠提高SPGA的收斂速度和計(jì)算效率。今后的工作是將該算法應(yīng)用到相關(guān)領(lǐng)域解決具體問(wèn)題。

(責(zé)任編輯 王 磊)