改进遗传算法的MapReduce并行化研究

董义明 王鹏达 李鹏 仝茵

摘要：针对遗传算法在进行海量数据搜索时，算法的收敛速度会随着数据复杂度升高和数据量的增多而变慢的问题。该文将遗传算法进行了合并优化，将合并后的算法在MapReduce架构上并行化实现。实验结果表明，改进后的遗传算法当运行在MapReduce架构上时，不仅加快了收敛速度，而且提高了加速比。

关键词：遗传算法；MapReduce；收敛速度；加速比

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2019）10-0151-02

开放科学（资源服务）标识码（OSID）：

1 引言

当今社会随着互联网技术的快速发展，数据量已经呈现出爆炸增长的趋势，数据的形式更是呈现出多样性[1]。分布式计算模型的提出为解决大数据的数据挖掘问题提供了一个新的思路，这几年以来分布式计算已经成为国内外许多专家研究的热点。程兴国，肖南峰针对粗粒度并行遗传算法的特点，给出了MapReduce编程模型实现遗传算法的方法[2]；包达尔罕在研究完Hadoop并行处理技术之后，将遗传算法实现了并行化[3]；胡涛提出基于最优个体保留策略的遗传算法并在Hadoop集群上进行了实现，进一步提高了算法的收敛速度[4]；嘉瑞玉、管玉龙等人利用遗传算法的并行化设计思想，在Hadoop平台下遗传k-means算法进行了并行化设计[5]；徐肖、胡吉明提出在编码的时候将计算资源作为操作的基本单元，由此提出了新的区域杂交法子和变异算子[6]。

但是将遗传算法在移植到并行计算模型上运行时[7]，由于算法需要对数据进行全局搜索，算法的收敛速度会随着数据复杂度升高和数据量的增多而变慢。为了提高算法的收敛速度和加速比，在总结前人工作的基础上，本文将对遗传算法进行了并行化的实现，将实现后的算法在MapReduce模型上进行类的实现。

2 MapReduce编程模型

MapReduce并行处理模型最早是由Google提出的一种分布式计算模型，该模型主要有Map和Reduce两个阶段组成，现在由Apache提供的开源框架Hadoop[8]也是在MapReduce基础上发展而来的，本实验中也采用开源架构Hadoop作为实验集群的架构。MapReduce[9]采用“拆分处理再合并”的设计思想，首先将要处理的数据集进行大量地拆分，经过拆分之后形成多个小的数据块 ，然后主节点将这些拆分后的小数据块交给各个从节点处理，各个从节点可以独立完成自己的计算任务，这样就可以将一个较大的任务拆分为多个较小的任务并行执行，从而提高了任务执行的速度。Map和Reduce的过程可以简单的描述的如式1的形式：

[map（k1，v1）→list（k2，v2）reduce（k2，list（v2））→list（v3）] （1）

在程序开始的时候， MapReduce会调用库函数UserProgram[10]，库函数能够将输入文件split为若干份小份，通常每一份大小为64M，作为Map函数的输入数据，然后由fork函数将这些拆分的split文件由主节点分配到各个从节点上。从节点上的Map函数首先对文件以（key，value）的形式读取，然后对其进行处理计算产生一个中间键值对，也就是上述的list（k2，v2）。Reduce函数会将Map函数输出的作为输入，中间还需要对其进行汇总计算，形成最后的输出结果 OutputFile。MapReduce的模型如图1所示：

3 改进遗传算法

遗传算法是现代计算机科学与传统的自然遗传学的产物，它是通过迭代过程不断搜索目标。遗传算法的迭代过程可以概括为：产生、选择优良个体、基因组合（变异）、再生、再组合。遗传算法将复杂的现象用繁殖机制结合简单的编程技术来表现，进一步得出了相对复杂问题的较好的解。遗传算法的基本执行流程如下图2所示：

4 基于MapReduce的算法实现

由MapReduce运行的形可知，Map阶段和Reduce阶段的计算可以独立进行，在算法的运行过程中相互之间没有关联，故在实现基于MapReduce的改进遗传算法时，需要每个从节点的计算都能单独运行。

4.1 Map函数的设计

Map函数主要完成，从HDFS的文件中读取数据，对种群进行初始化，更新粒子群的速度与方向，对种群中的个体进行杂交、变异、计算其适应度，生成新一代种群，并输出给Reduce函数。Map函数的伪代码描述如下：

5 实验和结果分析

5.1 实验环境

实验运行在由7台计算机运行的集群上，集群框架采用Apache开源框架Hadoop。在这7台机器中，将其中1台机器作为NameNode，其余6台机器作为DataNode。每台机器的硬件配置如下：CPU型号为AMD Trinity APU A8-5800B、頻率为3.2GHz，内存大小为8G，硬盘大小为1T，操作系统为Ubuntu 13.10、JDK 1.7、Hadoop 2.2.0。

5.2 集群性能实验

实验分为两次，在相同的配置集群下，第一次运行未改进的遗传算法，第二次运行改进后的遗传算法，设置它们的最大进化次数为100次，交叉概率为0.7，变异概率为0.01，假设算法在10次迭代中所用的时间并没有改变，则认为该算法趋于收敛，算法结束。实验比较从数据读入到完成算法收敛所需要的时间。实验结果如图3示：

图3 性能比较试验结果

实验二选取数据量大小分别为512M，1.0G和1.5G的数据集，集群节点数由1个节点逐步增加到6个，比较它们的所用时间的加速比，实验结果如图4示。由图可以看出该集群具有良好的加速比。

6 结束语

当今社会已经加入大数据的时代，在这个时代要善于从数据中寻找机会。如何从海量的数据中挖掘出具有价值的信息，是现在研究的一个热点，许多学者和大型机构也一直致力于这方面的研究。本文针对传统的遗传算法在MapReduce并行化时出现的收敛速度以及加速比慢的问题，对遗传算法的并行化改进中，改进后的算法进行了并行化的设计，使其在MapReduce并行编程模型上实现。实验运行结果表明：改进后的遗传算法，在MapReduce模型上進行运算时，算法的加速比提高，算法的收敛速度加快。

参考文献：

[1] 陈吉荣，乐嘉锦.基于Hadoop生态系统的大数据解决方案综述[J.]计算机工程与科学，2013，35（10）：25-35.

[2] 程兴国，肖南峰.粗粒度并行遗传算法的MapReduce并行化实现[J].重庆理工大学学报，2013，10（27）：66-74.

[3] 包达尔罕.基于Hadoop的改进 遗传算法[J]内蒙古师范大学学报，2015，44（1）：62-65.

[4] 胡涛.基于MapReduce模型遗传算法的一种改进与实现[J].电子设计工程，2013，5（21）：32-39.

[5] 贾瑞玉，管玉勇，李亚龙.基于MapReduce模型的并行遗传k-means聚类算法[J].计算机工程与设计，2014，2（35）：657-660.

[6] 徐肖，胡吉明.一种Hadoop中基于改进遗传算法的作业调度算法[J].计算机技术与发展，2013，3（23）：10-18.

[7] 李建江，崔健.MapReduce并行编程模型研究综述[J].电子学报，2013，11（11）：2635-2642.

[8] 许丞，刘洪，谭良.Hadoop云平台的一种新的任务调度和监控机制[J].计算机科学，2013，40（1）：112-117.

[9] Jimmy Lin， ChrisDyer. Data-Intensive Text Progressing with MapReduce[J].Morgan & Claypool Publishers， 2011，22（5）： 26-28.

[10] 武森，冯小东，杨杰，等.基于MapReduce的大规模文本聚类并行化[J].北京科技大学学报，2014，36（10）：1411-1419.

【通联编辑：代影】