GPU Parallel Acceleration Framework for Heuristic Optimization Algorithm

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

Abstract

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

CLC Number:

TP391.9

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

Figures/Tables 8

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 1

Test function with many local minima

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

Table 1

Table 2

Convergence error of heuristic optimization algorithm

函数	种群	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

Table 2

Table 3

Running time (ms) and acceleration ratio of algorithms with different dimensions under the test function 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

Table 3

References 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.