Parallel NSGA-II on Sunway many-core processor

doi:10.3778/j.issn.1002-8331.1708-0051

Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (17): 35-40.DOI: 10.3778/j.issn.1002-8331.1708-0051

Previous Articles Next Articles

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. 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算法

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

1.华东师范大学计算机与软件工程学院，上海 200062
2.数学工程与先进计算国家重点实验室，江苏无锡 214215
3.华东师范大学经济与管理学部，上海 200062

Abstract

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

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

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

SHEN Huanxue1，2, ZHENG Kai1，2, LIU Yao1，2, WANG Su1，2, LIU Yan1，2, ZHAO Ruixiang1，2, ZHOU Qianhao3. Parallel NSGA-II on Sunway many-core processor[J]. Computer Engineering and Applications, 2018, 54(17): 35-40.

沈焕学1，2，郑凯1，2，刘垚1，2，王肃1，2，刘艳1，2，赵瑞祥1，2，周谦豪3. 申威众核处理器的并行NSGA-II算法[J]. 计算机工程与应用, 2018, 54(17): 35-40.

[1]	YANG Wei, WU Yingying, WANG Ting. Research on Configuration Optimization Problems of Shuttle-Carrier Storage and Retrieval System [J]. Computer Engineering and Applications, 2021, 57(4): 258-265.
[2]	CHEN Wanfen, WANG Yujia, LIN Weixing. Heterogeneous Ensemble Surrogate Assisted Multi-objective Particle Swarm Optimization Algorithm [J]. Computer Engineering and Applications, 2021, 57(23): 71-80.
[3]	HU Xiaobing, CHEN Shunian, ZHANG Yingfei, GU Shenghao. New Ripple-Spreading Algorithm for Multi-objective Path Optimization [J]. Computer Engineering and Applications, 2021, 57(23): 81-90.
[4]	LI Qian, JIANG Li, LIANG Changyong. Multi-objective Cold Chain Distribution Optimization Based on Fuzzy Time Window [J]. Computer Engineering and Applications, 2021, 57(23): 255-262.
[5]	LI Dahai, AI Zhigang, WANG Zhendong. Improved Yin-Yang-Pair Multi-objective Optimization Algorithm Based on Full-Combination Strategy [J]. Computer Engineering and Applications, 2021, 57(22): 110-124.
[6]	CUI Caixia, BI Chaochao, FAN Qinqin. Self-Adaptive MODE Based on Hidden Markov Chain and Application [J]. Computer Engineering and Applications, 2021, 57(14): 83-94.
[7]	WANG Lili, ZHANG Linjuan, SHANG Xuening, GAO Deyun. Survey on Application of Intelligence Computing in Deployment of Electric Vehicle Charging Stations [J]. Computer Engineering and Applications, 2020, 56(2): 1-10.
[8]	TU Jingke, LIANG Junbin, JIANG Chan, WANG Tianshu. Research Progress of Mobile Internet of Things Monitoring in Large-Scale Acyclic Directed Pipe Network [J]. Computer Engineering and Applications, 2020, 56(17): 1-11.
[9]	WANG Yadong, SHI Quan, YOU Zhifeng, SONG Weixing. Differential Evolutionary Quasi-Oppositional Multi-objective Ant Lion Optimizer [J]. Computer Engineering and Applications, 2020, 56(13): 156-163.
[10]	GUO Yuhan, HU Dejia. Vehicle Multiplication Solution Based on Random Forest and Variable Neighborhood Decline [J]. Computer Engineering and Applications, 2020, 56(13): 243-253.
[11]	LIU Qing, WANG Yang, LI Xing, LI Hongye. Gene-Pool Based Genetic Algorithm for Optimizing Application Layer Multicast [J]. Computer Engineering and Applications, 2019, 55(21): 142-150.
[12]	YUE Chunyu，MA Yizhong，ZHANG Jianxia. Multi-Objective Surrogate Optimization Algorithm Combining Kriging and Physical Programming [J]. Computer Engineering and Applications, 2019, 55(21): 240-246.
[13]	YAN Taishan, WEN Yiting, LI Wenbin, YANG Bo. Research on Multi-Objective Optimization Method of Combined-Taxi [J]. Computer Engineering and Applications, 2019, 55(20): 222-226.
[14]	WANG Yulei1，2, QIU Gang3. Artificial Physics Multi-Objective Algorithm for Spectrum Detection of Cognitive Internet of Things [J]. Computer Engineering and Applications, 2019, 55(14): 83-86.
[15]	JU Luyan1, YANG Jianjun2, ZHANG Jianbing1, GUO Longlong1, LI Suobin1. Improved NSGA for Multi-Objective Flexible Job-Shop Scheduling Problem [J]. Computer Engineering and Applications, 2019, 55(13): 260-265.

Parallel NSGA-II on Sunway many-core processor

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics