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

河南许继智能科技股份有限公司 蔺俊强 张长炜

西南交通大学信息科学与技术学院 孙希鹏

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

河南许继智能科技股份有限公司 蔺俊强 张长炜

西南交通大学信息科学与技术学院 孙希鹏

随着人们生活水平的不断提高，对于城市中最佳路径的选择有了更进一步的要求，比如，选择两座城市的最佳旅游路径，不仅可以节约时间和金钱，同时也方便了人们的出行。文章主要对Hadoop分布式并行算法进行了研究，分别在Hadoop分布式环境与单机环境下，使用att48数据集，对NP问题求解的时间与空间复杂度进行了对比研究，并最终计算出城市中的最佳路径。

分布式并行算法；Hadoop；NP问题

0 引言

云计算是近年来流行的一种新兴计算模型，而Hadoop[1]作为一个便捷开发和并行处理巨大数据的云计算平台，以其低成本、高效率、可靠性而备受人们关注。 T White发表的《Hadoop: The Def i nitive Guide》[3]是非常著名的Hadoop权威指南，对Hadoop的底层原来进行了深入的剖析与讲解,D Borthakur在《The hadoop distributed fi le system: Architecture and design》[4]中也阐述了他对Hadoop设计和架构的建议。在国内，对于Hadoop的设计应用研究也是比较多的，这方面研究比较好的有何婕、朱珠，《基于Hadoop的数据存储系统的分析和设计》和《基于Hadoop的海量数据处理模型研究和应用》[5]都是比较好的研究著作。

Hadoop平台由两部分组成：Hadoop分布式文件系统(HDFS)和MapReduce计算模型[2]。HDFS采用M／S架构，它包含一个Master管理节点和多个Slave数据节点。MapReduce是处理大量半结构化数据集合的编程模型，它大大简化了复杂的数据处理计算。

1 主要技术简介

1.1 分布式算法简介

分布式算法，简而言之就是对一系列底层分布式算法（Low-Level Heuristics，LLH）进行管理和操作的一种高层次分布式方法。由图1的模型可知，分布式算法管理操作了一组LLH，提供了一种高层次的分布式方法；寻找一个最优的算法是分布式算法的目的所在。

图1 分布式算法的架构

目前的分布式算法[6]一般都有两个阶段，分别为算法构造阶段和实例（问题）求解阶段：前者采用的方法是对一系列LLH组合，以产生新的分布算法，后者就是运行新产生的分布式算法对问题或者实例求解。依据分布式方法不同的机制，目前的分布式算法大致有4种类型，分别为基于随机选择、贪心策略、元分布式算法、学习的分布式算法。

1.2 MapReduce模型

MapReduce[7]是一款高效的用于数据处理的编程模型，它将数据处理分为两个过程，即map过程和reduce过程。MapReduce模型各个阶段的工作流程如图2所示：

(1)Input：这个阶段进行的主要工作就是对Map和Reduce函数的输入、输出位置以及一些运行参数进行录入，此外还会把输入目录下的大数据文件划分为若干独立的数据块。

(2)Map：在Map这个阶段，对(key，value)键值对进行处理，因为MapReduce框架把应用的输入当作键值对，同时会产生新的中间(key，value)键值对，两组键值对类型可能不一致。

(3)Shuffle：这个阶段的作用是为了确保Reduce的输入有序，按照Map中排好的输出次序，MapReduce框架采用HTTP机制，为Reduce获取所有与Map输出的与之相关的(key，value)键值对，然后按照key值对Reduce阶段的输入进行分组。

(4)Reduce：这个阶段主要是对中间数据进行遍历，对每一个唯一的key都会采取相关操作。执行用户自定定义的Reduce函数。输入参数是(key，{listof values})，输出是新的(key，value)键对。

(5)Output：此阶段会把Reduce输出的结果写入到输出目录指定的位置。这样，一个典型的MapReduce过程就完成了。

图2 MapReduce的处理过程

2 解决的关键问题

在分布算法运行时，LLH的迭代不仅仅是由HLS输送的局部解，并且为了平衡LLH算法[8]运行时间差异，我们并不放弃LLH自身的迭代，因为有可能在第N次迭代时结果不是最优解而在N+1次时却会产生最优解。所以每个LLH在运行结束后会产生2N-1个HLS因子而不是N个，这样会进一步扩大粒子群算法的粒子数，依据粒子群算法的特征，会进一步优化其最终结果。且由于粒子群算法本来就是一个分布式算法，所以这种迭代因子的输入方式不会大幅拉低其时间性能。

与单机相比，本实验体系的时间复杂度为：MAX（O（Ln））+O（HLS）而不是单机运行时的乘法级。这样就可以解决优化分布算法的时间效率与结果优劣的矛盾。

3 实验设计及运行结果

3.1 实验设计

本次实验采用对比实验，即在Hadoop平台与Windows平台在同等环境压力及其他条件下运行分布式算法，以对比其时间开销和空间开销。分布式算法设计如图3所示，低层分布式算法由贪心算法、模拟退火算法、禁忌搜索算法组成。

图3 分布式算法实验架构图

3.2 实验的部分关键实现代码

public class MPGreedyAlgorithm {

static int cityNum；// 城市数量

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{

// 读取数据

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++) {

// 读取一行数据，数据格式1 6734 1453

strbuff = data.readLine();

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

x[i] = Integer.valueOf(strcol[1]);// x坐标

y[i] = Integer.valueOf(strcol[2]);// y坐标

}

data.close();

// 此处用att48作为案例

for (int i = 0；i 〈 cityNum - 1；i++) { distance[i][i] = 0；// 对角线为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 实验过程与结果

本实验先对att48数据集的48个城市坐标信息进行运算生成48城市之间的距离矩阵，其结果如图4所示：

图4 att48数据集距离矩阵

然后再对初始化的距离在Windows平台通过分布式算法进行求解，得出本次的最佳路径，Windows运行结果如图5所示：

图5 Windows环境下TSP问题寻优结果

最后再对上述的距离矩阵在Hadoop环境下通过分布式算法进行求解法进行求解，其运行结果如图6所示：

图6 在Hadoop平台的运行结果

4 总结

本次实验通过java编程和MapReduce编程分别在Windows下和Hadoop下实现了分布式算法，并使用它们处理运算了att48数据集，然后进行了对比实验。本实验体系时间复杂度为：MAX（O（Ln））+O（HLS），而不是单机运行时的乘法级，进而解决优化分布算法的时间效率与结果优劣的矛盾，最终找到两城市间最佳路径。

[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的数据挖掘研究[D].重庆:重庆大学,2010.

[4]丁宁.多关系关联规则挖掘研究[D].合肥:安徽大学,2010.

[5]刘淑英.一种基于MapReduce的最近似k对数据搜索方案[J].计算机与现代化,2014,211(08):36-40.

[6]何军,刘红岩,杜小勇.挖掘多关系关联规则[J].软件学报,2007,311(11): 1062-1068.

蔺俊强（1987—），男，河南许昌人，硕士，主要研究方向：分布式系统。

张长炜（1991—），男，河南临颍人，大学本科，主要研究方向：电气工程及其自动化。

孙希鹏（1990—），男，山东青岛人，硕士，主要研究方向：大数据技术数据挖掘。