基于SPark的并行遗传算法研究.docVIP

基于SPark的并行遗传算法研究 　　摘要：当前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算子代替ma