启发式优化算法的GPU并行加速框架

doi:10.16182/j.issn1004731x.joss.23-0780

摘要/Abstract

摘要：

为解决启发式优化算法计算量大、耗时长的缺点，使用图形处理单元(GPU)以及统一计算架构(compute unified device architecture，CUDA)对启发式优化算法进行并行化。提出了一种针对启发式优化算法的GPU并行框架，设计了具有并行逻辑结构的信息交互框架、算法并行优化策略，解决了信息交互的逻辑结构在串、并行中的相异性问题，该框架可并行化各类启发式优化算法，具有一般性与高效性。为验证该框架的有效性，利用并行框架对5种常见启发式优化算法进行并行化，给出了多个测试函数下GPU并行计算与CPU串行计算的对比结果，其中差分进化算法、哈里斯鹰优化算法、灰狼优化算法、鲸鱼优化算法在种群维度为5 000时，分别加速高达179.1、178.6、74.3、358.2倍，同时保证了结果的准确性，表明所设计并行框架的高效性与实用性。

关键词: 启发式优化算法, GPU并行, CUDA模型, 并行框架, 信息交互

Abstract:

Heuristic optimization algorithm are a type of algorithm that uses large-scale populations for iterative calculations and are widely used to solve all kinds of complex optimization problems. However, such algorithm have the disadvantages of large calculation and long time consumption. To solve this problem, heuristic optimization algorithms are parallelized using GPU and compute unified device architecture (CUDA) to substantially improve computational efficiency. A GPU parallel framework for heuristic optimization algorithm is proposed, which designs an information interaction framework and algorithm parallel optimization strategy with a parallel logical structure, and solves the problem of the dissimilarity of the logical structure of information interaction in series and parallel, this framework can parallelize various heuristic optimization algorithms with generality and efficiency. In order to verify the effectiveness of this framework, five common heuristic optimization algorithms are parallelized by using the parallel framework, and the comparison results of GPU parallel computation and CPU serial computation under different multiple test functions are given. in which DE, HHO, GWO, and WOA reach the acceleration ratio of 179.1, 178.6, 74.3 and 358.2 times respectively when the population dimension is 5000, while ensuring the accuracy of the results, which verifies the high effectiveness and practicability of the designed parallel framework.

Key words: heuristic optimization algorithm, GPU parallelism, CUDA model, parallel framework, information exchange

中图分类号:

TP391.9

王东杰,温思歆,孟万植等 . 启发式优化算法的GPU并行加速框架[J]. 系统仿真学报, 2024, 36(8): 1929-1943.

Wang Dongjie,Wen Sixin,Meng Wanzhi,et al . GPU Parallel Acceleration Framework for Heuristic Optimization Algorithm[J]. Journal of System Simulation, 2024, 36(8): 1929-1943.

图/表 8

图1

图2

图3

图4

图5

表1

具有许多局部极小值的测试函数

Number	Functions	$f m i n$
$f 1$	$f 1 (x) = - ∑ j = 1 n j x j s i n x j$	0
$f 2$	$f 2 (x) = ∑ j = 1 n j {x j 2 - 10 × c o s (2 π x j) + 10}$	0
$f 3$	$f 3 (x) = 1 + f a ⋅ f a / 4 000 - c o s (f a) + ∑ j = 1 n j - 1 (1 + f b j ⋅ f b j / 4 000 - c o s (f b j))$ $f a = 100 × ((x n j + 1) 2 - (x 0 + 1)) 2 + (1 - (x n j + 1)) 2$ $f b j = 100 × ((x j + 1) 2 - (x j + 1 + 1)) 2 + (1 - (x j + 1)) 2, j = 1,2, ⋯, n j - 1$	0
$f 4$	$f 4 (x) = π n 10 × s i n 2 (π y 1) + ∑ j = 1 n j - 1 (y j - 1) 2 {1 + 10 × s i n 2 (π y j + 1)} + (y n j - 1) 2 + ∑ j = 1 n j u (x j, 10, 100, 4)$ $y j = 1 + (1 / 4) ⋅ (x j + 1)$ $u (x, a, k, m) = k ⋅ (x - a) m, x > a 0, - a ≤ x ≤ a k ⋅ (- x - a) m, x < - a$	0
$f 5$	$f 5 (x) = 0.1 s i n 2 (3 π x 1) + ∑ j = 1 n j - 1 (x j - 1) 2 {1 + s i n 2 (3 π x j + 1)} + (x n j - 1) 2 {1 + s i n 2 (2 π x n j)} + ∑ j = 1 n j u (x j, 5,100,4)$	0

表1

表2

启发式优化算法收敛误差

函数	种群	DE		HHO		GWO		WOA		种群	MFO
函数	种群	CPU	GPU	CPU	GPU	CPU	GPU	CPU	GPU	种群	CPU	GPU
$f 1$	800	0	0	0	0	6.29×10^-5	7.43×10^-5	0	0	100	6.26×10^-8	5.07×10^-8
	1 600	0	0	0	0	5.86×10^-5	7.64×10^-5	0	0	150	2.98×10^-8	4.17×10^-8
	2 400	0	0	0	0	4.76×10^-5	9.02×10^-5	0	0	200	1.19×10^-8	2.98×10^-8
	3 200	0	0	0	0	4.09×10^-5	8.11×10^-5	0	0	250	0	0
$f 2$	800	0	0	0	0	0	0	0	0	100	0	0
	1 600	0	0	0	0	0	0	0	0	150	0	0
	2 400	0	0	0	0	0	0	0	0	200	0	0
	3 200	0	0	0	0	0	0	0	0	250	0	0
$f 3$	800	0.032	0.019	0	0	0	0	0	0	100	0.25	0.29
	1 600	0.027	0.010	0	0	0	0	0	0	150	0.22	0.28
	2 400	0.026	0.009 2	0	0	0	0	0	0	200	0.30	0.23
	3 200	0.018	0.005 4	0	0	0	0	0	0	250	0.26	0.24
$f 4$	800	5.69×10^-17	5.69×10^-17	7.68×10^-16	5.69×10^-17	2.52×10^-6	2.39×10^-7	5.69×10^-17	5.69×10^-17	100	7.54×10^-14	1.05×10^-14
	1 600	5.69×10^-17	5.69×10^-17	3.42×10^-16	5.69×10^-17	6.60×10^-6	1.64×10^-6	5.69×10^-17	5.69×10^-17	150	6.39×10^-14	2.75×10^-14
	2 400	5.69×10^-17	5.69×10^-17	1.99×10^-16	5.69×10^-17	3.85×10^-6	5.43×10^-6	5.69×10^-17	5.69×10^-17	200	7.38×10^-14	6.61×10^-14
	3 200	5.69×10^-17	5.69×10^-17	5.69×10^-17	5.69×10^-17	7.04×10^-6	9.01×10^-7	5.69×10^-17	5.69×10^-17	250	9.79×10^-15	8.98×10^-15
$f 5$	800	8.95×10^-14	8.95×10^-14	5.38×10^-13	9.70×10^-14	2.27×10^-10	4.85×10^-10	9.18×10^-14	8.95×10^-14	100	9.01×10^-14	9.57×10^-14
	1 600	8.95×10^-14	8.95×10^-14	1.52×10^-13	9.01×10^-14	1.24×10^-10	4.17×10^-10	9.29×10^-14	9.01×10^-14	150	8.95×10^-14	8.95×10^-14
	2 400	8.95×10^-14	8.95×10^-14	1.35×10^-13	8.95×10^-14	1.15×10^-10	4.38×10^-10	8.95×10^-14	8.95×10^-14	200	8.95×10^-14	1.23×10^-13
	3 200	8.95×10^-14	8.95×10^-14	1.08×10^-13	8.95×10^-14	1.30×10^-10	5.21×10^-10	9.01×10^-14	8.95×10^-14	250	8.95×10^-14	8.95×10^-14
$f 6$	800	1.20×10^-6	4.12×10^-7	1.37×10^-5	1.29×10^-5	5.49×10^-6	1.14×10^-6	6.74×10^-7	6.71×10^-7	100	6.41×10^-5	8.49×10^-5
	1 600	1.04×10^-6	4.12×10^-7	1.31×10^-5	1.11×10^-5	3.89×10^-6	4.68×10^-6	6.27×10^-7	6.37×10^-7	150	7.65×10^-5	2.52×10^-5
	2 400	1.03×10^-6	4.12×10^-7	3.78×10^-6	9.71×10^-6	5.04×10^-6	1.97×10^-6	8.01×10^-7	6.81×10^-7	200	6.87×10^-5	1.07×10^-5
	3 200	9.82×10^-7	4.12×10^-7	1.84×10^-6	5.79×10^-6	1.61×10^-6	1.73E-06	7.64×10^-7	6.75×10^-7	250	5.74×10^-5	1.79×10^-5

表2

表3

测试函数f1~f6不同种群维度算法运行时间与加速比

函数	种群	DE			HHO			GWO			WOA			种群	MFO
函数	种群	CPU/ ms	GPU/ ms	加速比	CPU/ ms	GPU/ ms	加速比	CPU/ ms	GPU/ ms	加速比	CPU/ ms	GPU/ ms	加速比	种群	CPU/ ms	GPU/ ms		加速比
$f 1$	800	882.3	15.1	58.3	2 827.6	109.5	25.8	2 560.4	271.0	9.4	639.3	21.6	29.5	100	298.6		133.9	2.2
	1 600	1 758.3	26.3	66.8	5 655.6	133.3	42.4	5 139.7	443.4	11.6	1 279.5	24.2	52.9	150	498.8		215.9	2.3
	2 400	2 638.4	52.7	50.1	8 487.4	153.6	55.2	7 720.3	693.6	11.1	1 921.4	25.5	75.3	200	733.5		300.3	2.4
	3 200	3 526.5	97.0	36.4	11 352.5	184.5	61.5	10 976.2	1 036.9	10.6	2 560.4	29.8	85.9	250	985.7		449.7	2.2
$f 2$	800	1 040.8	16.9	61.5	4 365.4	142.5	30.6	2 710.0	271.1	10.0	1 359.5	25.2	53.9	100	487.9		204.4	2.4
	1 600	2 073.5	27.8	74.7	8 730.9	159.0	54.9	5 420.0	422.6	12.8	2 719.0	30.0	90.5	150	795.1		315.8	2.5
	2 400	3 117.3	51.8	60.2	13 109.3	175.0	74.9	8 116.5	618.3	13.1	4 091.1	33.3	122.9	200	1 140.4		447.7	2.5
	3 200	4 184.0	94.8	44.1	17 495.3	205.0	85.3	10 846.3	1 017.3	10.7	5 445.8	38.8	140.4	250	1 504.2		615.7	2.4
$f 3$	800	1 324.6	33.2	39.9	5 484.2	237.1	23.1	2 849.2	314.9	9.0	1 911.0	48.0	39.8	100	576.6		253.6	2.3
	1 600	2 580.9	48.1	53.7	11 039.5	294.7	37.5	5 707.4	477.9	11.9	3 836.6	56.6	67.8	150	937.3		375.7	2.5
	2 400	3 855.6	56.2	68.6	16 427.6	353.0	46.5	8 799.1	717.3	12.3	5 735.4	70.0	81.9	200	1 323.0		562.5	2.4
	3 200	5 180.6	79.9	64.8	22 006.0	435.5	50.5	11 579.8	1 066.6	10.9	7 659.8	89.8	85.3	250	1 756.2		812.6	2.2
$f 4$	800	1 896.6	33.5	56.5	9 778.3	228.0	42.9	4 123.1	314.6	13.1	4 298.9	46.8	91.8	100	830.8		181.5	4.6
	1 600	3 687.7	38.6	95.5	19 487.1	262.1	74.4	7 592.4	469.3	16.2	8 586.7	45.9	187.3	150	1 307.2		288.5	4.5
	2 400	5 769.2	46.7	123.4	29 233.0	305.6	95.7	11 511.3	724.5	15.9	12 721.5	51.1	249.0	200	1 773.7		403.6	4.4
	3 200	7 584.9	77.8	97.5	38 952.6	339.2	114.8	15 235.2	1 067.7	14.3	17 057.9	54.4	313.8	250	2 325.6		616.6	3.8
$f 5$	800	2 003.5	37.2	53.9	10 146.4	246.3	41.2	3 891.5	305.2	12.8	4 399.2	49.5	88.8	100	823.2		183.8	4.5
	1 600	3 996.5	42.2	94.7	20 151.7	285.5	70.6	7 805.9	472.1	16.5	8 727.3	50.3	173.5	150	1 309.3		298.0	4.4
	2 400	5 998.1	48.1	124.8	30 161.1	334.4	90.2	11 775.4	714.1	16.5	13 055.5	55.1	236.8	200	1 805.7		421.7	4.3
	3 200	8 029.1	72.0	111.5	40 053.3	369.9	108.3	16 529.8	1 064.2	15.5	17 396.9	61.3	283.9	250	2 377.5		629.4	3.8
$f 6$	800	24 800.0	454.2	54.6	87 272.0	1 235.8	70.6	28 577.0	762.7	37.5	52 439.2	463.1	113.2	100	3 566.8		672.8	5.3
	1 600	49 536.9	486.0	101.9	172 596.4	1 479.3	116.7	57 565.1	925.8	62.2	104 504.1	512.7	203.8	150	5 445.8		795.1	6.8
	2 400	74 420.2	502.5	148.1	262 271.5	1 717.4	152.7	84 221.4	1 138.4	74.0	148 271.4	486.0	305.1	200	7 330.2		956.1	7.7
	3 200	99 287.5	554.3	179.1	351 528.8	1 967.9	178.6	112 004.3	1 506.7	74.3	199 616.9	557.2	358.2	250	9 241.3		1 261.7	7.3

表3

参考文献 31

1	范衠, 朱贵杰, 李文姬, 等. 进化计算在复杂机电系统设计自动化中的应用综述[J]. 自动化学报, 2021, 47(7): 1495-1515.
	Fan Zhun, Zhu Guijie, Li Wenji, et al. Applications of Evolutionary Computation in the Design Automation of Complex Mechatronic System: A Survey[J]. Acta Automatica Sinica, 2021, 47(7): 1495-1515.
2	丁进良, 杨翠娥, 陈远东, 等. 复杂工业过程智能优化决策系统的现状与展望[J]. 自动化学报, 2018, 44(11): 1931-1943.
	Ding Jinliang, Yang Cuie, Chen Yuandong, et al. Research Progress and Prospects of Intelligent Optimization Decision Making in Complex Industrial Process[J]. Acta Automatica Sinica, 2018, 44(11): 1931-1943.
3	韩红桂, 张璐, 卢薇, 等. 城市污水处理过程动态多目标智能优化控制研究[J]. 自动化学报, 2021, 47(3): 620-629.
	Han Honggui, Zhang Lu, Lu Wei, et al. Research on Dynamic Multiobjective Intelligent Optimal Control for Municipal Wastewater Treatment Process[J]. Acta Automatica Sinica, 2021, 47(3): 620-629.
4	李晓苏, 晁涛, 王松艳. 基于鱼群算法的运载火箭上升段弹道优化设计[J]. 系统仿真学报, 2018, 30(12): 4747-4753, 4759.
	Li Xiaosu, Chao Tao, Wang Songyan. Trajectory Optimization Design of Ascending Phase for Solid Launch Vehicle Based on Fish-swarm Algorithm[J]. Journal of System Simulation, 2018, 30(12): 4747-4753, 4759.
5	Eberhart R, Kennedy J. A New Optimizer Using Particle Swarm Theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science(MHS'95). Piscataway: IEEE, 1995: 39-43.
6	Storn Rainer, Price K. Differential Evolution—A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces[J]. Journal of Global Optimization, 1997, 11(4): 341-359.
7	Blum Christian. Ant Colony Optimization: Introduction and Recent Trends[J]. Physics of Life Reviews, 2005, 2(4): 353-373.
8	Mirjalili S, Seyed Mohammad Mirjalili, Lewis A. Grey Wolf Optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61.
9	Mirjalili S. Moth-flame Optimization Algorithm: A Novel Nature-inspired Heuristic Paradigm[J]. Knowledge-Based Systems, 2015, 89: 228-249.
10	Mirjalili S, Lewis A. The Whale Optimization Algorithm[J]. Advances in Engineering Software, 2016, 95: 51-67.
11	Ali Asghar Heidari, Mirjalili S, Faris Hossam, et al. Harris Hawks Optimization: Algorithm and Applications[J]. Future Generation Computer Systems, 2019, 97: 849-872.
12	Li Shimin, Chen Huiling, Wang Mingjing, et al. Slime Mould Algorithm: A New Method for Stochastic Optimization[J]. Future Generation Computer Systems, 2020, 111: 300-323.
13	Wang Zhiheng, Liu Jianhua. Flamingo Search Algorithm: A New Swarm Intelligence Optimization Algorithm[J]. IEEE Access, 2021, 9: 88564-88582.
14	Zhao Weiguo, Wang Liying, Mirjalili S. Artificial Hummingbird Algorithm: A New Bio-inspired Optimizer with Its Engineering Applications[J]. Computer Methods in Applied Mechanics and Engineering, 2022, 388: 114194.
15	Xue Bing, Zhang Mengjie, Browne W N. Particle Swarm Optimization for Feature Selection in Classification: A Multi-objective Approach[J]. IEEE Transactions on Cybernetics, 2013, 43(6): 1656-1671.
16	Sun Yifan, Agostini N B, Dong Shi, et al. Summarizing CPU and GPU Design Trends with Product Data[EB/OL]. (2020-07-13) [2023-01-10]. .
17	龚春叶, 刘杰, 包为民, 等. 后摩尔时代国产高性能并行应用软件生态建设综述[J]. 系统仿真学报, 2022, 34(10): 2107-2118.
	Gong Chunye, Liu Jie, Bao Weimin, et al. Review on Ecological Construction of Domestic High-performance Parallel Application Software in Post Moore Era[J]. Journal of System Simulation, 2022, 34(10): 2107-2118.
18	Surendra Kumar Shukla, Pant Bhaskar. Characterization of SPEC2006 Benchmarks Under Multicore Platform to Identify Critical Architectural Aspects[C]//International Conference on IoT, Intelligent Computing and Security. Singapore: Springer Nature Singapore, 2023: 199-206.
19	陈国军, 刘岩. 基于并行遗传算法的公路线形优化[J]. 系统仿真学报, 2013, 25(10): 2332-2336.
	Chen Guojun, Liu Yan. Optimization of Road Alignment Using Parallel Genetic Algorithms[J]. Journal of System Simulation, 2013, 25(10): 2332-2336.
20	Han Wencheng, Li Hao, Gong Maoguo, et al. Multi-swarm Particle Swarm Optimization Based on CUDA for Sparse Reconstruction[J]. Swarm and Evolutionary Computation, 2022, 75: 101153.
21	Lucas de P Veronese, Krohling Renato A. Differential Evolution Algorithm on the GPU with C-CUDA[C]//IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2010: 1-7.
22	Roberge V, Tarbouchi M. Hybrid Deterministic Non-deterministic Data-parallel Algorithm for Real-time Unmanned Aerial Vehicle Trajectory Planning in CUDA[J]. e-Prime-Advances in Electrical Engineering, Electronics and Energy, 2022, 2: 100085.
23	Jayapriya J, Arock Michael. A Parallel GWO Technique for Aligning Multiple Molecular Sequences[C]//2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI). Piscataway: IEEE, 2015: 210-215.
24	Ueda Satoshi, Ogawa Hideaki. Multi-fidelity Approach for Global Trajectory Optimization Using GPU-based Highly Parallel Architecture[J]. Aerospace Science and Technology, 2021, 116: 106829.
25	Tan Ying, Ding Ke. A Survey on GPU-based Implementation of Swarm Intelligence Algorithms[J]. IEEE Transactions on Cybernetics, 2016, 46(9): 2028-2041.
26	张国, 王锐, 雷洪涛, 等. 并行智能优化算法研究进展[J]. 控制理论与应用, 2023, 40(1): 1-11.
	Zhang Guo, Wang Rui, Lei Hongtao, et al. Survey on Parallel Intelligent Optimization Algorithms[J]. Control Theory & Applications, 2023, 40(1): 1-11.
27	姜洋洋. 基于卷积神经网络与CUDA加速计算的手势识别算法应用研究[J]. 系统仿真技术, 2020, 16(1): 22-26.
	Jiang Yangyang. Development of Gesture Recognition Algorithm Based on Convolutional Neural Network and CUDA Accelerated Calculation[J]. System Simulation Technology, 2020, 16(1): 22-26.
28	Li Yan. Implementation of CUDA and Hadoop Based System for Intelligent Guiding Evaluation Algorithm Based on Data Center Data Mining[C]//2022 International Conference on Inventive Computation Technologies (ICICT). Piscataway: IEEE, 2022: 1119-1125.
29	Cheng J, Grossman M, McKercher T. Professional CUDA C Programming[M]. Indianapolis: John Wiley & Sons, 2014.
30	Zhuo Yanhong, Zhang Tao, Du Feng, et al. A Parallel Particle Swarm Optimization Algorithm Based on GPU/CUDA[J]. Applied Soft Computing, 2023, 144: 110499.
31	Elbes Mohammed, Alzubi Shadi, Kanan Tarek, et al. A Survey on Particle Swarm Optimization with Emphasis on Engineering and Network Applications[J]. Evolutionary Intelligence, 2019, 12(2): 113-129.

[1]	王宁, 梁晓龙, 张佳强, 侯岳奇, 杨爱武. 跨域无人集群协同反潜搜索方法研究[J]. 系统仿真学报, 2024, 36(4): 817-824.
[2]	周昆, 刘箴, 何高奇, 陈田, 刘婷婷, 刘翠娟. 基于模块划分的GPU加速布料动画[J]. 系统仿真学报, 2016, 28(10): 2476-2484.
[3]	冯丽萍, 彭其渊, 文超. 基于OOPN的高速铁路行车指挥信息交互过程建模[J]. 系统仿真学报, 2015, 27(4): 697-705.