Map Reduce技術(shù)在物資調(diào)運(yùn)與配載問(wèn)題中的應(yīng)用

陳元文

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

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

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

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

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

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

1.1 問(wèn)題簡(jiǎn)述及分析

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

圖1 物資調(diào)運(yùn)及配載的基本實(shí)施過(guò)程

1.2 TSPB-MOGA求解算法

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

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

（1）編碼

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

（2）解碼

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

第一階段：基于優(yōu)先保障序列的物資分配過(guò)程。此階段對(duì)應(yīng)圖2中的“物資分配階段”，提出了基于最大滿足和非占優(yōu)排序的物資分配算法，以全局配送時(shí)間最低和風(fēng)險(xiǎn)最低為目標(biāo)為每個(gè)物資供應(yīng)點(diǎn)提供詳細(xì)的物資分配計(jì)劃（不涉及物資配載優(yōu)化）。

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

（3）交叉算子

設(shè)計(jì)采用面向優(yōu)先保持的單點(diǎn)交叉算子[8]。

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

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

2.1 總體運(yùn)行過(guò)程

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

圖3 MRTSPB-MOGA算法流程圖

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

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

（1）初始化和Splitter

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

（2）Map過(guò)程

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

（3）Shuffle

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

（4）Reduce過(guò)程

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

（5）遷移過(guò)程

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

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

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

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

此過(guò)程的主要任務(wù)是將位于各計(jì)算節(jié)點(diǎn)的子種群的Pareto最優(yōu)解匯集到一個(gè)獨(dú)立的單機(jī)節(jié)點(diǎn)，對(duì)匯集后的種群重新進(jìn)行非占優(yōu)排序，并輸出最終的Pareto最優(yōu)解。

3 案例計(jì)算及分析

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

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

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

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

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

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

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

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

表1 單機(jī)配置信息

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

（2）時(shí)效性分析

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

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

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

圖7 算法在不同運(yùn)行環(huán)境下的耗時(shí)對(duì)比

（3）迭代性能對(duì)比

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

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

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

4 結(jié)束語(yǔ)

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

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