程兴国，肖南峰

(华南理工大学计算机科学与工程学院，广州 510006)

遗传算法(genetic algorithm，GA)是一类借鉴生物界自然选择和遗传机制的启发式随机搜索算法，它是将生物学中的遗传进化原理和优化理论相结合的产物。遗传算法的基本思想很简单，它通过模拟生物界“物竞天择，适者生存，优胜劣汰”的策略获取种群全局最优解。

遗传算法作为一种应用广泛的高效智能搜索算法，己经成功地应用于工程设计、工商管理、科学实验等领域中的复杂优化问题的求解。随着信息技术的进步以及信息化社会的发展，遗传算法的种群规模和迭代代数显著增加，导致串行计算方法的时间复杂度比较高，处理能力存在局限性。传统高性能计算中的并行编程模型(如PThread、MPI和OpenMP等)抽象度不高，开发人员需要熟悉底层的配置和并行实现细节［1］。MapReduce模型是Google实验室提出的分布式并行编程模型或框架，它能在普通的PC机上构建集群来处理大规模数据集，成为云计算平台主流的并行数据处理模型。Apache开源社区的Hadoop项目用Java语言实现了该模型，同时Hadoop项目还设计了开放源代码的云计算技术平台［2］。本文在基于Hadoop技术的云计算基础平台上研究了粗粒度并行遗传算法的MapReduce并行编程实现方法，并进行了相关实验。

1 MapReduce编程模型

MapReduce编程模型的基本思路是将大数据集分解为成百上千的小数据集splits，每个(或若干个)数据集分别由集群中的1个节点(一般是1台普通计算机)并行执行Map计算任务(指定了映射规则)，并生成中间结果，然后这些中间结果又由大量的节点并行执行Reduce计算任务(指定了归约规则)，形成最终结果。……