余涛　刘泽檠

摘要：当前Spark分布式编程框架由于内存计算得到了快速发展，相对于传统MapReduce并行编程模型在迭代运算上有明显优势。针对串行遗传算法处理大规模问题能力有限的现状，提出了一种基于Spark平台的粗粒度并行遗传算法（sPGA）。该方法利用Spark框架并行实现了遗传算法的选择、交叉和变异操作，并对并行操作算子的性能进行了分析，优化了算法并行化实现方案，极大地提高了遗传算法全局搜索效率。实验结果表明，新的并行遗传算法在收敛速度上有显著的提高，能够很好地提高优化效率。

关键词：Spark；RDD；并行遗传算法；多目标优化；大规模变量

中图分类号：TP18

文献标志码：A

文章编号：1006-8228（2017）01-43-03

0.引言

遗传算法是一种模拟生物进化的随机学习方法，主要包括选择、交叉和变异三种遗传操作。面对大规模复杂优化问题时，遗传算法的寻优时间长，所以有人提出了并行遗传算法，主要将遗传算法的天然并行性跟并行编程模型相结合，加快搜索优化过程。

近年来，机器学习领域的众多专家做了许多加快并行遗传算法寻优速度的研究和探索。郭肇禄在并行遗传算法中提出了自适应迁移策略，降低了通信开销。李建明等人实现了一种基于GPU的细粒度并行遗传算法，抑制了种群的早熟，提高了搜索效率。Verma A等人则从数据处理规模的角度实现了MapReduce跟遗传算法的结合。这些基于GPU或者MapReduce实现的并行遗传算法，虽然取得了一定的进展，但是GPU可扩展能力欠佳，MapReduce的迭代速度较慢，这些缺陷都制约了并行遗传算法对大规模复杂优化问题的快速求解。近期快速发展的Spark并行计算引擎能够提供内存计算机制，被普遍认为是下一代大数据并行处理框架，但是基于Spark计算模型实现并行遗传算法需要尝试不同的Spark算子和参数来对比分析其性能。

本文深入分析了遗传算法和Spark并行编程模型，实现了一种适合Spark框架的粗粒度并行遗传算法。具体的工作有：①对Spark的部分算子和参数通过大量实验进行对比分析，优化了算法性能。②结合遗传算法跟Spark计算平台实现了一种高性能的并行遗传算法。实验表明该算法能够提高收敛效率，适合处理大规模的优化问题。

Spark是一个集流计算、数据查询、机器学习和图挖掘于一体的通用计算框架，具有可伸缩、内存计算和高可靠性等优点。弹性分布式数据集（RDD）是Spark的数据存储的核心，在迭代计算时可以高效的共享数据，目标是为基于工作集的应用提供抽象。本质上RDD是一个元数据结构，提供了一种高度受限的内存模型，记录着只读的、分区记录的集合，存储着数据分区及其逻辑结构映射关系；在Spark编程模型中RDD被表示为对象，相应的API为RDD提供转换（Transformations）和动作（Actions）两种算子，其中Transformations算子执行后创建新的RDD，从而RDD之问形成相互依赖关系，如图1所示。RDD的依赖分为窄依赖和宽依赖，其中窄依赖是子RDD的分区只依赖父RDD的某个分区，而宽依赖则指子RDD的每个分区依赖父RDD的多个分区；Action算子则真正触发程序的执行，向应用程序返回结果或者向存储系统导出数据。

2.基于Spark的并行遗传算法设计及实现

2.1SPGA算法流程

本文将标准遗传算法的并行性和RDD编程模型相结合，实现了一种粗粒度的并行遗传算法。算法整体流程如图2所示。首先是初始化种群，然后具体实现相应的并行遗传算子，这里只是在Spark上并行实现了遗传算子，并没有做任何实质改进，所以从这个角度来看SPGA算法相对标准遗传算法在求解精度上是没有任何优势的，但是SPGA算法会将整个种群划分为若干个亚种群，而后在集群所拥有的处理器上独立进行计算，这可以缩短运行时间，发挥并行算法速度优势。迁移策略是并行遗传算法跟串行遗传算法的重要不同之处，这里在亚种群之间采用随机迁移策略，能够解决遗传算法的局部最优问题。

2.2SPGA算法优化设计

mapPartitions和map是RDD上的两个并行操作算子，mapPartitions的功能是作用一个函数到RDD的每一个分片（partition）上，map则是对RDD的每个元素应用一个函数，两者运算后都返回一个新的RDD。由于遗传算法的适应度计算及变异过程是一种粗粒度操作，种群中的个体单独计算互不干扰，所以很容易想到使用map算子。然而在考虑性能时我们发现，map算子需要为所有的个体都初始化一个测试函数，在大规模种群时产生了大量不必要的内存和计算开销。为了避免这种冗余开销，我们考虑使用mapPartitions算子代替map算子，因为mapPartitios算子是以RDD的partition作为处理函数的输入，也就是把partition作为整体来处理，只需要在每个partition开始计算时初始化一个测试函数，节省了很多内存和计算资源，提高了算法的整体运算效率。

3.实验与结果分析

3.1实验环境和测试函数

本实验使用7台Dell服务器构建了—个Spark集群，分为1个主控节点和6个受控节点，集群的任务调度模式为standalone。硬件配置：服务器拥有8G内存，四核处理器。软件配置：集群搭建使用spark-1.2.0-bin-hadoopl和Hadoop-1.2.1稳定版，Java选用JDKl.7.0_71（Linux版），操作系统选择ubuntul2.04Server版。

首先初始化8个不同大小的种群，然后在相同条件下使用mapPartitions和map算子实现的SPGA算法在初始种群上优化求解ZDTl函数的Pareto最优前沿，并对运行时间进行对比分析。图3评价了mapPartitions和map算子实现的SPGA算法性能，从中可以看出由mapPartitions算子編写的算法对所有种群的运行时间都明显优低于map算子，且随着种群规模的增大，mapPartitions和map算子的运行时间都在增加，同时两者的时间差距也越来越大，这是因为个体数目增多的同时partition的数目没有变，所以mapPartitions算子没有增加初始化资源的时间，只是因为种群变大增加了计算时间，实现的算法效率更高。由于mapPartitions算子的性能优异，所以最终选择使用mapPartitions算子实现SPGA算法的变异和适应度。

3.2.2算法运行时间对比

本次实验对比了串行遗传算法、基于MapReduce的并行遗传算法（MRPGA）和基于Spark的并行遗传算法在不同种群规模下求解ZDTl多目标优化问题的运行时问。从图4可以看出，在种群规模较小，个体数量小于o.2*10时，串行遗传算法执行时间最短，其次是SPGA算法，运行时间最长的是MRPGA算法，这是因为Spark集群和MapReduce建立作业以及系统通信需要消耗一定的时问，而且MapReduce作业的初始化耗时大于Spark作业。当种群规模增大到中等规模时我们发现，SPGA算法用时最少，串行次之，MRPGA还是用时最多，在这个阶段串行遗传算法的运行时间上升最快并且超过了SPGA算法，这是因为相对于串行算法而言，并行算法会将增加的数据分散到各个节点并行计算，能够大量节省了计算时间，同时MRPGA算法由于作业启动和磁盘I/O耗时太多所以整体运行速度还是最。随着种群增长达到大规模，其数量大于9*10⁵时，集群上并行程序的优势就明显大于串行程序，SPGA和MRPGA算法的耗时都小于串行遗传算法，而且SPGA算法优于MRPGA算法，这是因为Spark框架是基于内存运算，不需要大量读写磁盘，所以SPGA算法运行更快。

4.结束语

在spark上实现了粗粒度并行遗传算法，其收敛速度有很大优势，但是由于该算法并没有对标准遗传算子进行改进，所以在求解精度上没有明显进步。在以后的工作中，我们将在spark平台上重点改进标准遗传算法的算子结构以提高求解精度；对spark的参数调优以及如何利用基于spark的并行遗传算法解决实际问题也是我们未来研究的重点。