基于Hadoop的分布式并行算法在最佳路徑中的研究

河南許繼智能科技股份有限公司 藺俊強(qiáng) 張長(zhǎng)煒

西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院 孫希鵬

基于Hadoop的分布式并行算法在最佳路徑中的研究

河南許繼智能科技股份有限公司 藺俊強(qiáng) 張長(zhǎng)煒

西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院 孫希鵬

隨著人們生活水平的不斷提高，對(duì)于城市中最佳路徑的選擇有了更進(jìn)一步的要求，比如，選擇兩座城市的最佳旅游路徑，不僅可以節(jié)約時(shí)間和金錢，同時(shí)也方便了人們的出行。文章主要對(duì)Hadoop分布式并行算法進(jìn)行了研究，分別在Hadoop分布式環(huán)境與單機(jī)環(huán)境下，使用att48數(shù)據(jù)集，對(duì)NP問題求解的時(shí)間與空間復(fù)雜度進(jìn)行了對(duì)比研究，并最終計(jì)算出城市中的最佳路徑。

分布式并行算法；Hadoop；NP問題

0 引言

云計(jì)算是近年來流行的一種新興計(jì)算模型，而Hadoop[1]作為一個(gè)便捷開發(fā)和并行處理巨大數(shù)據(jù)的云計(jì)算平臺(tái)，以其低成本、高效率、可靠性而備受人們關(guān)注。 T White發(fā)表的《Hadoop: The Def i nitive Guide》[3]是非常著名的Hadoop權(quán)威指南，對(duì)Hadoop的底層原來進(jìn)行了深入的剖析與講解,D Borthakur在《The hadoop distributed fi le system: Architecture and design》[4]中也闡述了他對(duì)Hadoop設(shè)計(jì)和架構(gòu)的建議。在國內(nèi)，對(duì)于Hadoop的設(shè)計(jì)應(yīng)用研究也是比較多的，這方面研究比較好的有何婕、朱珠，《基于Hadoop的數(shù)據(jù)存儲(chǔ)系統(tǒng)的分析和設(shè)計(jì)》和《基于Hadoop的海量數(shù)據(jù)處理模型研究和應(yīng)用》[5]都是比較好的研究著作。

Hadoop平臺(tái)由兩部分組成：Hadoop分布式文件系統(tǒng)(HDFS)和MapReduce計(jì)算模型[2]。HDFS采用M／S架構(gòu)，它包含一個(gè)Master管理節(jié)點(diǎn)和多個(gè)Slave數(shù)據(jù)節(jié)點(diǎn)。MapReduce是處理大量半結(jié)構(gòu)化數(shù)據(jù)集合的編程模型，它大大簡(jiǎn)化了復(fù)雜的數(shù)據(jù)處理計(jì)算。

1 主要技術(shù)簡(jiǎn)介

1.1 分布式算法簡(jiǎn)介

分布式算法，簡(jiǎn)而言之就是對(duì)一系列底層分布式算法（Low-Level Heuristics，LLH）進(jìn)行管理和操作的一種高層次分布式方法。由圖1的模型可知，分布式算法管理操作了一組LLH，提供了一種高層次的分布式方法；尋找一個(gè)最優(yōu)的算法是分布式算法的目的所在。

圖1 分布式算法的架構(gòu)

目前的分布式算法[6]一般都有兩個(gè)階段，分別為算法構(gòu)造階段和實(shí)例（問題）求解階段：前者采用的方法是對(duì)一系列LLH組合，以產(chǎn)生新的分布算法，后者就是運(yùn)行新產(chǎn)生的分布式算法對(duì)問題或者實(shí)例求解。依據(jù)分布式方法不同的機(jī)制，目前的分布式算法大致有4種類型，分別為基于隨機(jī)選擇、貪心策略、元分布式算法、學(xué)習(xí)的分布式算法。

1.2 MapReduce模型

MapReduce[7]是一款高效的用于數(shù)據(jù)處理的編程模型，它將數(shù)據(jù)處理分為兩個(gè)過程，即map過程和reduce過程。MapReduce模型各個(gè)階段的工作流程如圖2所示：

(1)Input：這個(gè)階段進(jìn)行的主要工作就是對(duì)Map和Reduce函數(shù)的輸入、輸出位置以及一些運(yùn)行參數(shù)進(jìn)行錄入，此外還會(huì)把輸入目錄下的大數(shù)據(jù)文件劃分為若干獨(dú)立的數(shù)據(jù)塊。

(2)Map：在Map這個(gè)階段，對(duì)(key，value)鍵值對(duì)進(jìn)行處理，因?yàn)镸apReduce框架把應(yīng)用的輸入當(dāng)作鍵值對(duì)，同時(shí)會(huì)產(chǎn)生新的中間(key，value)鍵值對(duì)，兩組鍵值對(duì)類型可能不一致。

(3)Shuffle：這個(gè)階段的作用是為了確保Reduce的輸入有序，按照Map中排好的輸出次序，MapReduce框架采用HTTP機(jī)制，為Reduce獲取所有與Map輸出的與之相關(guān)的(key，value)鍵值對(duì)，然后按照key值對(duì)Reduce階段的輸入進(jìn)行分組。

(4)Reduce：這個(gè)階段主要是對(duì)中間數(shù)據(jù)進(jìn)行遍歷，對(duì)每一個(gè)唯一的key都會(huì)采取相關(guān)操作。執(zhí)行用戶自定定義的Reduce函數(shù)。輸入?yún)?shù)是(key，{listof values})，輸出是新的(key，value)鍵對(duì)。

(5)Output：此階段會(huì)把Reduce輸出的結(jié)果寫入到輸出目錄指定的位置。這樣，一個(gè)典型的MapReduce過程就完成了。

圖2 MapReduce的處理過程

2 解決的關(guān)鍵問題

在分布算法運(yùn)行時(shí)，LLH的迭代不僅僅是由HLS輸送的局部解，并且為了平衡LLH算法[8]運(yùn)行時(shí)間差異，我們并不放棄LLH自身的迭代，因?yàn)橛锌赡茉诘贜次迭代時(shí)結(jié)果不是最優(yōu)解而在N+1次時(shí)卻會(huì)產(chǎn)生最優(yōu)解。所以每個(gè)LLH在運(yùn)行結(jié)束后會(huì)產(chǎn)生2N-1個(gè)HLS因子而不是N個(gè)，這樣會(huì)進(jìn)一步擴(kuò)大粒子群算法的粒子數(shù)，依據(jù)粒子群算法的特征，會(huì)進(jìn)一步優(yōu)化其最終結(jié)果。且由于粒子群算法本來就是一個(gè)分布式算法，所以這種迭代因子的輸入方式不會(huì)大幅拉低其時(shí)間性能。

與單機(jī)相比，本實(shí)驗(yàn)體系的時(shí)間復(fù)雜度為：MAX（O（Ln））+O（HLS）而不是單機(jī)運(yùn)行時(shí)的乘法級(jí)。這樣就可以解決優(yōu)化分布算法的時(shí)間效率與結(jié)果優(yōu)劣的矛盾。

3 實(shí)驗(yàn)設(shè)計(jì)及運(yùn)行結(jié)果

3.1 實(shí)驗(yàn)設(shè)計(jì)

本次實(shí)驗(yàn)采用對(duì)比實(shí)驗(yàn)，即在Hadoop平臺(tái)與Windows平臺(tái)在同等環(huán)境壓力及其他條件下運(yùn)行分布式算法，以對(duì)比其時(shí)間開銷和空間開銷。分布式算法設(shè)計(jì)如圖3所示，低層分布式算法由貪心算法、模擬退火算法、禁忌搜索算法組成。

圖3 分布式算法實(shí)驗(yàn)架構(gòu)圖

3.2 實(shí)驗(yàn)的部分關(guān)鍵實(shí)現(xiàn)代碼

public class MPGreedyAlgorithm {

static int cityNum；// 城市數(shù)量

static int[][] distance；// 距離矩陣

static int[] colable;//列，表示是否走過，走過置0

static int[] row;//行，選過置0

Static class MyMapper extends Mapper〈KEYIN,VALUEIN，KEYOUT,VALUEOUT>{

private static IntWritable one=new IntWritable(1);

private Text word=new Text();

@Override

protected void map() throws IOException，InterruptedException{

// 讀取數(shù)據(jù)

int[] x，y;

String strbuff;

distance = new int[cityNum][cityNum];

x = new int[cityNum];

y = new int[cityNum];

for (int i = 0；i 〈 cityNum；i++) {

// 讀取一行數(shù)據(jù)，數(shù)據(jù)格式1 6734 1453

strbuff = data.readLine();

String[] strcol = strbuff.split(“ “);

x[i] = Integer.valueOf(strcol[1]);// x坐標(biāo)

y[i] = Integer.valueOf(strcol[2]);// y坐標(biāo)

}

data.close();

// 此處用att48作為案例

for (int i = 0；i 〈 cityNum - 1；i++) { distance[i][i] = 0；// 對(duì)角線為0

for (int j = i + 1；j 〈 cityNum；j++) {

double rij = Math.sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) / 10.0);

int tij = (int) Math.round(rij);

if (tij 〈 rij) {

distance[i][j] = tij + 1;

distance[j][i] = distance[i][j];

} else {

distance[i][j] = tij;

distance[j][i] = distance[i][j];

}

3.3 實(shí)驗(yàn)過程與結(jié)果

本實(shí)驗(yàn)先對(duì)att48數(shù)據(jù)集的48個(gè)城市坐標(biāo)信息進(jìn)行運(yùn)算生成48城市之間的距離矩陣，其結(jié)果如圖4所示：

圖4 att48數(shù)據(jù)集距離矩陣

然后再對(duì)初始化的距離在Windows平臺(tái)通過分布式算法進(jìn)行求解，得出本次的最佳路徑，Windows運(yùn)行結(jié)果如圖5所示：

圖5 Windows環(huán)境下TSP問題尋優(yōu)結(jié)果

最后再對(duì)上述的距離矩陣在Hadoop環(huán)境下通過分布式算法進(jìn)行求解法進(jìn)行求解，其運(yùn)行結(jié)果如圖6所示：

圖6 在Hadoop平臺(tái)的運(yùn)行結(jié)果

4 總結(jié)

本次實(shí)驗(yàn)通過java編程和MapReduce編程分別在Windows下和Hadoop下實(shí)現(xiàn)了分布式算法，并使用它們處理運(yùn)算了att48數(shù)據(jù)集，然后進(jìn)行了對(duì)比實(shí)驗(yàn)。本實(shí)驗(yàn)體系時(shí)間復(fù)雜度為：MAX（O（Ln））+O（HLS），而不是單機(jī)運(yùn)行時(shí)的乘法級(jí)，進(jìn)而解決優(yōu)化分布算法的時(shí)間效率與結(jié)果優(yōu)劣的矛盾，最終找到兩城市間最佳路徑。

[1]Kendall G.,Mohamad M.Channel assignment in cellular communication using a great deluge hyper-heuristic.In:Proceedings of IEEE International Conference on Network (ICON2004),2004:769-773.

[2]Ayob M.,Kendall G.A Monte Carlo hyper-heuristic to optimise component placement sequencing for multi.

[3]楊宸鑄.基于Hadoop的數(shù)據(jù)挖掘研究[D].重慶:重慶大學(xué),2010.

[4]丁寧.多關(guān)系關(guān)聯(lián)規(guī)則挖掘研究[D].合肥:安徽大學(xué),2010.

[5]劉淑英.一種基于MapReduce的最近似k對(duì)數(shù)據(jù)搜索方案[J].計(jì)算機(jī)與現(xiàn)代化,2014,211(08):36-40.

[6]何軍,劉紅巖,杜小勇.挖掘多關(guān)系關(guān)聯(lián)規(guī)則[J].軟件學(xué)報(bào),2007,311(11): 1062-1068.

藺俊強(qiáng)（1987—），男，河南許昌人，碩士，主要研究方向：分布式系統(tǒng)。

張長(zhǎng)煒（1991—），男，河南臨潁人，大學(xué)本科，主要研究方向：電氣工程及其自動(dòng)化。

孫希鵬（1990—），男，山東青島人，碩士，主要研究方向：大數(shù)據(jù)技術(shù)數(shù)據(jù)挖掘。