胡涛

（武汉科技大学 信息科学与工程学院，湖北 武汉 430081）

遗传算法自Holland教授于1975年提出后，经Goldberg等人归纳总结形成一类模拟进化算法[1]。作为一种自适应全局优化搜索算法，其自组织、自适应和智能性，对所求解问题的未知特点有很强的鲁棒性。简单通用，适于并行处理及高效特点，该类算法广泛应用于自动控制，故障诊断，模式识别，计算机科学等领域，尤其是近年来发展迅速的机器学习和数据挖掘领域，也体现了该类算法在大规模问题上的适用性。

互联网的快速发展促进了各个学科面临的大容量的信息高效处理的可能性，数据密集型的的架构是一种切实可行的方案[2]。传统的基于MPI架构的并行GA算法在处理问题域时需要详细地了解处理计算机的构造，受到函数式语言中map和reduce原语的启发，Google提出了易于解决大规模问题的MapReduce抽象模型[3]。底层实现细节掩盖于分布式文件系统（DFS）的MapReduce框架使得实现大规模并行计算变得较容易[4]，同时传统GA算法处理大规模复杂问题在运行速度上难以接受。运用MapReduce并行计算框架改进传统的GA算法在解决复杂性和难度增大的问题上能改善运行速度，并使采用GA处理更大规模的数据密集型问题成为可能，使其能够作为针对海量数据的机器学习和数据挖掘的一种方法[5]，比如聚类分析中聚类中心的寻找。本文通过简单遗传算法求解单值最大问题说明了该算法在MapReduce下的并行算法实现，并对实验结果进行了性能分析和讨论。……