任 刚,吴长茂,魏 勇,刘小杰,郜广兰,王鲜芳

(1. 河南工学院 计算机学院,河南 新乡 453003; 2. 中国科学院软件研究所 并行软件实验室,北京 100190;3. 河南省生产制造物联大数据工程技术研究中心,河南 新乡 453003)

0 引言

遗传算法(Genetic Algorithm,GA)是一种借鉴生物自然选择机制的全局随机搜索算法,该算法通过选择、交叉和变异等遗传算子来搜索问题最优解。相较于传统搜索算法,该算法不需要专门领域的知识,仅用适应度评估函数来指导搜索过程,求解过程较为简单,同时最终结果不依赖于初始种群,具有较强的鲁棒性,从而在多个领域得到应用[1-3]。但是,由于传统GA中包含较多的遗传操作,当问题规模较大时,其性能降低,因此,通过并行方法来提高传统GA的性能成为该领域研究热点之一[4]。在众多并行遗传算法(Parallel Genetic Algorithm, PGA)中,基于MPI消息传递集群系统[5]的多种群并行进化PGA[6-8]被证明是一种有效提升PGA性能的机制。多种群并行进化PGA将整个种群平均分配到集群节点上,形成多个具有不同进化参数的并行进化子种群,并定期交换各自计算成果,从而提高了传统GA的收敛速度和计算效率,为用户提供了一套性价比较高的并行计算环境。

随着大数据时代的到来,以Spark为代表的计算模型由于其出色的数据并行能力被广泛应用。基于Spark计算模型的PGA (Spark-based Parallel Genetic Algorithm,SPGA)由于综合了Spark模型在数据并行上的优势和PGA在全局搜索上的优势,在多个领域受到欢迎[9]。然而,由于该算法缺乏多种群并行进化机制,当问题规模较大时,计算效率偏低。……