计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (17): 35-40.DOI: 10.3778/j.issn.1002-8331.1708-0051

• 理论与研发 • 上一篇    下一篇

申威众核处理器的并行NSGA-II算法

沈焕学1,2,郑  凯1,2,刘  垚1,2,王  肃1,2,刘  艳1,2,赵瑞祥1,2,周谦豪3   

  1. 1.华东师范大学 计算机与软件工程学院,上海 200062
    2.数学工程与先进计算国家重点实验室,江苏 无锡 214215
    3.华东师范大学 经济与管理学部,上海 200062
  • 出版日期:2018-09-01 发布日期:2018-08-30

Parallel NSGA-II on Sunway many-core processor

SHEN Huanxue1,2, ZHENG Kai1,2, LIU Yao1,2, WANG Su1,2, LIU Yan1,2, ZHAO Ruixiang1,2, ZHOU Qianhao3   

  1. 1. College of Computer and Software Engineering, East China Normal University, Shanghai 200062, China
    2. State Key Laboratory of Mathematical Engineering and Advanced Computing, Wuxi, Jiangsu 214215, China
    3. Faculty of Economics and Management, East China Normal University, Shanghai 200062, China
  • Online:2018-09-01 Published:2018-08-30

摘要: 非支配排序遗传算法(NSGA-II)在多目标优化领域有着广泛的应用,但在处理复杂问题时运行时间相当长。并行化是提高算法执行速度的有效途径。众核处理器的出现,为实现高度并行奠定了物质基础。基于国产超算“神威·太湖之光”的申威众核处理器平台设计了并行NSGA-II算法(PNSGA-II),实现了算法基于主核的一级并行和基于主/从核的二级并行。在典型测试函数集上的实验表明,在不影响解的质量前提下,PNSGA-II算法不仅大大加快了执行速度,同时算法的收敛速度也更快。

关键词: 非支配排序遗传算法, 多目标优化, 并行遗传算法, 众核处理器, 神威·, 太湖之光

Abstract: Non-dominated Sorting Genetic Algorithm-II(NSGA-II) is commonly used in multi-objective optimization, but featured with long time when dealing with complex problems. Algorithm parallelization can enhance the efficiency obviously, while the many-core processors provide the high-level parallelism. In this paper, a Parallel NSGA-II algorithm(PNSGA-II) based on Sunway many-core processor is proposed, which implements the level-1 parallelism based on master cores, and level-2 parallelism based on cooperative master / slave cores. Experimental results on typical test function sets indicate that the PNSGA-II algorithm improves both the processing time and the convergence speed under the same accuracy.

Key words: Non-dominated Sorting Genetic Algorithm-II(NSGA-II), multi-objective optimization, parallel genetic algorithm, many-core processors, Sunway Taihulight