陳元文

武警工程大學 裝備管理與保障學院，西安710086

MapReduce是由谷歌公司開發(fā)并已廣泛使用的一種并行計算編程框架，采用“分而治之”的思想，通過將一個復雜的串行任務分解為多個獨立的并行任務而提高計算效率[1]，是云計算的重要技術(shù)基石之一。MapReduce技術(shù)所具備的高度自動化和強大的容錯能力，使智能算法擺脫了以網(wǎng)格計算為代表的傳統(tǒng)并行化方案對運行環(huán)境的繁瑣設置過程，擺脫了其對高性能和高穩(wěn)定性硬件設備的依賴。

基于以MapReduce為代表的云計算技術(shù)的智能算法，因其高性價比和高容錯性，從2008年逐漸引起學術(shù)界的廣泛關(guān)注。Xu和You[2]為分析多層陶瓷基復合材料在冷卻過程中的熱殘余應力對材料壽命和材料性能的影響程度，設計了基于多次迭代的改進MapReduce的粒子群算法，并結(jié)合有限元分析法對優(yōu)化模型進行了求解。吳昊等[3]使用云計算技術(shù)將蟻群算法并行化，提出融入分治思想和模擬退火算法的基于MapReduce的蟻群算法，用于求解較大規(guī)模的旅行商問題（Traveling Salesman Problem，TSP）。文獻[4-5]針對TSP求解問題，設計了基于MapReduce技術(shù)的并行遺傳算法，并分析了不同節(jié)點下的計算加速比。Hu等[6]針對利用大規(guī)模傳感器網(wǎng)絡進行實時水污染源的識別問題，設計了基于MapReduce技術(shù)的小生境并行遺傳算法，并驗證了算法優(yōu)秀的計算性能。楊婉婧等[7]為提高BP神經(jīng)網(wǎng)絡算法的運行效率，提出了基于MapReduce的遺傳算法用于BP神經(jīng)網(wǎng)絡的并行化設計及實現(xiàn)方法。

在以上研究成果的基礎上，本研究提出了將MapReduce技術(shù)用于求解復雜物資調(diào)度及配載問題的多目標遺傳算法的具體部署方法及改進策略。

1 考慮多種約束的物資調(diào)度及配載問題及多目標遺傳算法實現(xiàn)

本研究以文獻[8]所述物資調(diào)運及配載問題為研究對象，采用基于優(yōu)先編碼的兩階段多目標遺傳算法（Two-Stage Priority-Based Multi-Objective Genetic Algorithm，TSPB-MOGA）為基礎算法進行分析。本部分僅介紹其基本問題及TSPB-MOGA算法的核心算子。

1.1 問題簡述及分析

如圖1所示，戰(zhàn)時或應急情況下指揮部門需根據(jù)物資儲備信息和可調(diào)用的運輸力量信息，結(jié)合物資需求單位（即需求點）所處地理位置與當前交通狀況，以單位物資需求為基本條件，以平均送達時間最短、途中損失最小和平均車輛重量和容量利用率為目標，制定多個物資儲備庫（即供應點）直接向多個需求點進行物資保障的詳細調(diào)度計劃，以解決每個供應點應分別向誰配送、配送什么、配送多少、用什么配送和物資如何裝車的問題。

圖1 物資調(diào)運及配載的基本實施過程

1.2 TSPB-MOGA求解算法

文獻[8]在Gen等[9]利用遺傳算法求解運輸問題的研究基礎上，設計了TSPB-MOGA算法對上述物資調(diào)運及配載問題進行求解，該算法流程框圖如圖2所示。

圖2 基于優(yōu)先編碼的兩階段多目標遺傳算法流程框圖

（1）編碼

算法采用供需節(jié)點總數(shù)+1的自然數(shù)順序編碼，其基因值代表供需節(jié)點的編號，基因位置代表供應點或需求點的保障順序。比如，對于擁有3個供應點和5個需求點的物資調(diào)運網(wǎng)絡，染色體“7 9 8 3 6 4 1 5 2”表示位于編碼首位的第7個節(jié)點（即第4個需求點）有最高的物資保障優(yōu)先權(quán)，位于編碼次位的第9個節(jié)點（即第6個需求點）擁有第二優(yōu)先權(quán)。

（2）解碼

解碼的目的是翻譯和解釋每條染色體所代表的物資調(diào)運方案（即物資由誰送、向誰送、送什么、送多少和如何裝車的具體問題）。算法解碼過程包含兩個階段：

第一階段：基于優(yōu)先保障序列的物資分配過程。此階段對應圖2中的“物資分配階段”，提出了基于最大滿足和非占優(yōu)排序的物資分配算法，以全局配送時間最低和風險最低為目標為每個物資供應點提供詳細的物資分配計劃（不涉及物資配載優(yōu)化）。

第二階段：面向裝載利用率最大化的物資配載。此過程對應圖2中的“配載求解階段”。該階段的重點是獲得詳細的物資配載計劃（對于各供應點而言，就是決定每輛車輛上應該配載各類物資的數(shù)量及其運往目的地）。

（3）交叉算子

設計采用面向優(yōu)先保持的單點交叉算子[8]。

2 TSPB-MOGA算法在云計算環(huán)境下的設計

鑒于TSPB-MOGA算法具有較高的復雜度，而云計算技術(shù)具有很高的計算性能和運算可靠性，因此可對TSPB-MOGA算法利用MapReduce技術(shù)進行并行化編程和改進，形成基于MapReduce的TSPB-MOGA算法（MapReduce for Two-Stage Priority-Based Multi-Objective Genetic Algorithm，MPTSPB-MOGA），該算法具有并行運行、多目標求解、粗粒度模式和高可靠性等特點。

2.1 總體運行過程

圖3是MPTSPB-MOGA算法的流程框圖（為簡化流程，本流程框圖未對計算過程中的HDFS分布式文件存儲和讀取過程進行展示）。如圖所示，遺傳算法的并行化計算總體上是通過Hadoop各集群中的PC來協(xié)同完成的，在這一過程中，MapReduce主要起到了任務管理與并發(fā)計算的作用。首先，在初始化過程中讀入相關(guān)數(shù)據(jù)并完成種群初始化；在Splitter過程中將種群分為多個相對獨立的子種群（Islands）并傳輸于相應的Mapper；Map過程是實現(xiàn)遺傳算法并行化的核心步驟，該過程可承擔具有大量計算需求的計算任務，所有Mapper將同步完成各子種群個體的解碼、適應值計算、非占優(yōu)排序和新的子種群個體產(chǎn)生；Shuffle是匯總計算結(jié)果并重新分配個體到Reducer的過程；在Reducer中，若滿足繼續(xù)迭代的條件，各Reducer將完成所負責的所有個體間的交叉及變異任務，并執(zhí)行各子種群間的個體遷移，準備進行下一次MapReduce的過程，若迭代終止，則根據(jù)相關(guān)條件篩選出當前的Pareto最優(yōu)解并完成輸出。

圖3 MRTSPB-MOGA算法流程圖

2.2 主要流程模塊功能及實現(xiàn)方法

圖3 中各主要流程模塊的功能及實現(xiàn)方法介紹如下。

（1）初始化和Splitter

該初始化過程除需完成數(shù)據(jù)讀入、參數(shù)設置外，還需按順序地將種群存儲于分布式文件系統(tǒng)HDFS中。Splitter的主要作用是將種群分割為P個子種群，并完成各個體的映射。此外，Splitter還會將各目標函數(shù)適應值的計算式也一并添加到各個Mapper中。

（2）Map過程

Map過程是該算法的核心，是實現(xiàn)并行計算的關(guān)鍵。在此過程中，位于各個Mapper的子種群并行、獨立地實現(xiàn)所有個體的解碼、適應值計算、非占優(yōu)排序和子代種群的產(chǎn)生。鑒于各子種群會順序執(zhí)行解碼和適應值計算等遺傳算子，因此本文考慮采用Hadoop技術(shù)的ChainMapper和ChainReducer類[10]來實現(xiàn)多個Mapper的串行執(zhí)行。

（3）Shuffle

總的來說，Shuffle就是完成整理并輸出的過程，是將Map過程中所得結(jié)果進行匯總、排序等操作，然后按照設定規(guī)則傳向Reducer的過程。而作為Shuffle過程的重要組成內(nèi)容，Partitioner負責將結(jié)果分發(fā)傳送到各個Reducer，是實現(xiàn)各Reducer負載均衡的關(guān)鍵。默認情況下，Partitioner會將指定key值的鍵值對送往指定的Reducer，但在遺傳算法中，隨著迭代的進行，種群逐漸向Pareto前沿靠近，這導致大量鍵值對被送往同一個Reducer而造成負載失衡。此外，由于具有相同或類似顯性的個體大量聚集于相同的Reducer，這勢必會影響迭代的性能，造成收斂速度大大降低。最后，Partitioner的默認設置為子種群的相對獨立的進化過程造成了阻礙。為避免這種情況的發(fā)生，本研究設定Partitioner為固定對象分配模式，如圖3所示，將Mapper所得結(jié)果固定地分配于與其對應的Reducer，使各MapReduce過程能完整保持位于不同集群的各子種群能獨立地進化，直至達到最大迭代次數(shù)。

（4）Reduce過程

因為TSPB-MOGA算法的交叉和變異操作的計算復雜度和計算資源需求相對較低，所以將其放在Reduce階段完成。當然，如圖3所示，在此過程中還有一個迭代結(jié)束的條件判斷符。若已達到遺傳算法的最大迭代次數(shù)，則不再進行交叉和變異操作（也不再進行后續(xù)的種群遷移），將位于各集群的子種群進行匯總，進行Pareto最優(yōu)解集篩選。

（5）遷移過程

通過各子種群間的個體遷移，相對獨立和封閉的子種群得以完成遺傳信息的交換和流動，該過程促進了種群的多樣性，擴大解的搜索空間的同時提升了收斂速度。如圖4所示（圖中藍色實心點代表個體，灰色橢圓代表子種群），本研究采用環(huán)形遷移的方法。為加快收斂速度，應加大種群間的遷移率，特別是優(yōu)勢個體的遷移，但遷移率的加大勢必增加各種群（計算節(jié)點）間的通信開銷。如圖5所示，各子種群在進行遷移前，可參照NSGA II算法的思想[11]按照Rank優(yōu)先、擁擠距離其次的順序?qū)Ω髯臃N群的個體進行排序，將排序靠前的占優(yōu)群體和靠后的劣勢群體（數(shù)量為遷移率×子種群數(shù)量）遷移至下一個子種群，并按同樣方法將下一個子種群的占優(yōu)群體和劣勢群體遷移至另一個子種群，最終實現(xiàn)全部子種群的個體遷移。

圖4 環(huán)形遷移過程示意圖

圖5 環(huán)形遷移過程示意圖

（6）Pareto最優(yōu)解匯集

此過程的主要任務是將位于各計算節(jié)點的子種群的Pareto最優(yōu)解匯集到一個獨立的單機節(jié)點，對匯集后的種群重新進行非占優(yōu)排序，并輸出最終的Pareto最優(yōu)解。

3 案例計算及分析

為詳細說明MRTSPB-MOGA算法的綜合性能，下面將從計算耗時、收斂情況、種群多樣性保持和并行計算能力等角度分別介紹采用不同運行環(huán)境和運行架構(gòu)的多庫物資協(xié)同調(diào)運算法。

3.1 TSPB-MOGA在單機環(huán)境下的計算性能

設置算法的種群數(shù)量為pop=100，最大迭代次數(shù)maxgen=90，交叉概率p c=0.7,變異概率pm=0.25。算法采用Matlab 2015b編程并運行于裝有Win7系統(tǒng)（64 bit），配置2.33 GHz的4核處理器和4 GB內(nèi)存的PC上。

程序經(jīng)過20次運行，平均耗時639.7（s均方差25.6 s），其中各主要算子的耗時占比如圖6所示。從圖中可以看出，該算法的解碼過程約占計算總耗時的98.7%（分析可知，造成該算子耗時過多的主要原因在于對其的多次調(diào)用以及算子本身的計算復雜度），而適應值計算、非占優(yōu)排序、交叉、變異等算子所耗費的計算資源之和不足2%（計算耗時不足10 s）。因此TSPB-MOGA算法具備并行化部署的基本特征。

圖6 各遺傳算子耗時占比圖（TSPB-MOGA）

3.2 MRTSPB-MOGA在Hadoop環(huán)境下的計算性能

（1）部署環(huán)境及參數(shù)介紹

雖然Hadoop可部署于Windows或Linux等系統(tǒng)環(huán)境下，但目前技術(shù)條件下Windows平臺上的部署需借助Cygwin等模擬軟件虛擬Unix系統(tǒng)。因此，本文考慮直接在Linux系統(tǒng)下部署Hadoop系統(tǒng)。實驗環(huán)境由6臺配置相同的PC搭建，每臺PC的主要軟硬件配置信息如表1所示。

表1 單機配置信息

MapReduce的過程是一個相對較為復雜的過程，集群通信、數(shù)據(jù)讀寫和后臺資源調(diào)度占有不可忽略的時間消耗（文獻[6，12-14]均已證實），因此MRTSPB-MOGA算法參數(shù)的選擇應考慮減少集群通信和頻繁數(shù)據(jù)讀寫的占比。設計MRTSPB-MOGA算法的主要參數(shù)如表2所示。設置較大的種群總量的原因在于加大單次迭代的計算量，提高有效計算的時間占比；子種群的數(shù)量等于種群總量與CPU數(shù)量的比值（均勻分配原則）；遷移率(mr)是進行遷移的個體與子種群數(shù)的比例，一般情況下，遷移率越高，通信消耗越高，但算法收斂性能越好；遷移間隔為2表示算法每迭代兩次，進行一次遷移，較低的遷移率有利于通信頻率的降低。

（2）時效性分析

時效高低是衡量分布式計算算法性能的主要指標。本研究對以下4組實驗進行了對比分析：（1）TSPBMOGA算法的串行執(zhí)行。采用表2中的主要參數(shù)，將其運行于單機串行環(huán)境下。（2）MRTSPB-MOGA算法的偽分布式并行執(zhí)行。采用MRTSPB-MOGA算法的運行環(huán)境（表1所示），但采用單機運行和串行執(zhí)行的方式，只設置一個Mapper和一個Reducer。（3）MRTSPB-MOGA算法的分布式執(zhí)行（有3臺PC的集群）。這是真正意義上的MRTSPB-MOGA算法執(zhí)行，只是在較小的集群規(guī)模下（6個Map-Reduce過程）。（4）MRTSPB-MOGA算法的分布式執(zhí)行（有6臺PC的集群）。不同環(huán)境下的算法運行耗時如圖7所示。

總的來說，MRTSPB-MOGA算法能取得較好的加速比（相比于串行執(zhí)行的TSPB-MOGA算法，6核和12核下的算法加速比達到了1.77和2.61）。此外，從圖7可知，偽分布式并行執(zhí)行的算法時耗遠大于串行執(zhí)行的情況，這是由于采用了Hadoop的GFS系統(tǒng)和MapReduce架構(gòu)的原因，文件的頻繁讀寫和MapReduce協(xié)調(diào)過程是造成這一耗時增加的主要原因。通過6核集群并行計算，將單個Mapper的計算負載分擔于6個Mapper，實現(xiàn)了真正意義的分布式計算，使計算耗時大幅下降。沒有使得計算耗時成Mapper數(shù)量下降的原因在于PC間通信、GFS文件系統(tǒng)讀寫、MapReduce過程中任務的協(xié)調(diào)和同步帶來的時間消耗或延遲。

表2 MRTSPB-MOGA主要參數(shù)設置

圖7 算法在不同運行環(huán)境下的耗時對比

（3）迭代性能對比

為跟蹤和驗證MRTSPB-MOGA算法的迭代性能，本文對TSPB-MOGA算法和MRTSPB-MOGA算法迭代過程中的Pareto前沿演變情況進行了對比研究。圖8為初始種群(iter=1)、中期種群(iter=maxgen/2)和末代種群(iter=maxgen)的Pareto前沿的分布及進化情況。圖中加注“MR”符號的為MRTSPB-MOGA算法所得的結(jié)果，圖8（a）為Pareto前沿三維視圖，圖8（b）～圖8（d）為平面視圖。從圖中可知，盡管進行了分布式架構(gòu)的改造并采用了子種群間個體遷移的方式彌補多樣性的保持，但MRTSPB-MOGA算法仍取得與TSPB-MOGA相似的迭代性能（圖中前沿解具有較高重合度），特別是從圖8（a）和圖8（b）中可以看出，MRTSPB-MOGA取得了更為靠前的Pareto前沿。

（4）求解結(jié)果分析

TSPB-MOGA算法和MRTSPB-MOGA算法采用大體相同的多目標遺傳算法核心算子（包括編碼、解碼、適應值計算、交叉、變異和選擇等），區(qū)別主要在于算法運行環(huán)境和是否采用基于MapReduce技術(shù)的并行化處理，因此，在最終求解結(jié)果上具有近乎相同的體現(xiàn)，圖8也正好驗證了這一推斷。

4 結(jié)束語

本研究結(jié)合云計算的MapReduce技術(shù)，對物資調(diào)運算法及部署進行了較為深入的研究。實驗證明，MRTSPBMOGA算法具有更為優(yōu)異的求解性能，對其他并行算子有高耗時的遺傳算法的改進或性能提升有一定借鑒意義。

圖8 TSPB-MOGA和MRTSPB-MOGA算法Pareto前沿演變對比圖