面向申威众核处理器的并行SaNSDE算法

Parallel SaNSDE for Many-Core Sunway Processor

演化算法作为解决大规模优化问题的重要方法,被广泛应用于机器学习、过程控制、工程优化、管理科学和社会科学等领域。然而在求解高维度、高计算密度问题时,程序性能很难得到保证。在高性能计算机上实现并行化是问题的一个热门解决方案。针对申威众核处理器的硬件特征,提出了采用二级并行策略的自适应邻域搜索的差分进化算法(SaNSDE)。第一级为进程并行,实现了合作协同进化模型和池模型,将大规模问题划分为多个低维子问题并分布在不同进程上;第二级为线程并行,使用从核加速了适应度的计算过程。实验结果表明,采用合作协同进化模型和池模型的算法与传统的并行算法相比,经过多核扩展之后收敛效果提升更加明显。相较于串行版本算法,二级并行的SaNSDE算法在四个测试函数上分别获得了134.29、186.05、239.01和189.80的最大加速比。

Evolutionary algorithm is an important method for solving large-scale optimization problems,which is widely applied to machine learning,process control,engineering optimization,management science,and social sciences.However,when the traditional evolutionary algorithms are used to high-dimensional and computing-density task,the performance of corresponding applications is difficult to be satisfactory.Parallelization on supercomputer is a popular solution to solve this problem.This paper proposes a two-level parallel self-adaptive differential evolution algorithm with neighborhood search(SaNSDE)on the Sunway TaihuLight,which implements process-level and thread-level parallelism.In the process-level parallelism,the cooperative co-evolution model and pool model are implemented,which divide large-scale problems into multiple low-dimensional problems and distribute them in different processes.In the thread-level parallelism,fitness calculation is accelerated.Experimental results show that the algorithm using the cooperative co-evolution model and the pool model,compared with the traditional parallel algorithm,improves the convergence effect more obviously after multi-core expansion.Compared with the serial algorithm,the two-level parallel SaNSDE algorithm achieves the maximum speedup of 134.29,186.05,239.01 and 189.80 in the four benchmark functions,respectively.