一种适用于大规模变量的并行遗传算法研究  

Research on Parallel Genetic Algorithms Based on MapReduce

作　　者：李东[1] 潘志松[1] 

机构地区：[1]解放军理工大学指挥自动化学院,南京210007

出　　处：《计算机科学》2012年第7期182-184,204,共4页Computer Science

基　　金：国家自然科学基金(60603029)资助

摘　　要：当前MapReduce并行编程模型得到了广泛的应用。相对于传统的基于PVM或者MPI的并行编程方式,它在执行时间和处理问题规模等方面有明显优势。针对并行遗传算法的特点,提出基于MapReduce实现一种典型的并行遗传算法——粗粒度并行算法的方法,用以解决大规模变量问题。实验平台采用Hadoop,硬件条件为普通的服务器集群。在多目标优化问题测试中,当问题规模达到一定、处理变量数超过10E+7时,并行算法效率比串行提高数倍,并且能突破内存瓶颈。根据MapReduce自身特点调整其参数,改变并行程度,分析其对并行执行时间的影响。MapReduce programming model enjoys widespread application and becomes new popular parallel program- ming paradigm nowadays. It uses MapReduce model to parallelize coarse-grained genetic algorithms, and takes muir-ob- jective optimization problem as the benchmark. All the experiments are made under hadoop and a cluster which consists of commodity servers. When the number of variable reach to 10E＋7, the efficiency of parallel algorithm can be multi- plied several times without introducing any bottlenecks revolved memory. Finally we studied how the parallel degree affects the performance.

关 键 词：大规模变量 MAPREDUCE 并行遗传算法 多目标优化问题 性能分析 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]