任 剛,吳長茂,魏 勇,劉小杰,郜廣蘭,王鮮芳

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

0 引言

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

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

1 相關(guān)工作

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

2 多種群并行進化SPGA

2.1 Spark計算模型

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

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

2.2 遺傳算法基本理論

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

2.3 多種群并行進化機制

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

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

圖2 多種群并行進化機制

2.4 多種群并行進化SPGA

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

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

individual=〈code,fitness〉

(1)

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

(3)

(4)

…,

(5)

(6)

…,

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

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

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

(7)

{optimalIndividual}—

{randomIndividual}

(8)

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

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

3 性能驗證

3.1 集群主要參數(shù)

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

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

3.2 實驗方案及結(jié)果分析

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

3.2.1 實驗1:計算精度分析

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

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

3.2.2 實驗2:收斂速度分析

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

3.2.3 實驗3:計算時間分析

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

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

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

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

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

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

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

表4 收斂速度對比

表5 運行時間對比

4 總結(jié)

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

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