Enabling Population-Level Parallelism in Tree-Based Genetic Programming for GPU Acceleration

摘要

Tree-based Genetic Programming (TGP) is a widely used evolutionary algorithm for tasks such as symbolic regression, classification, and robotic control. Due to the intensive computational demands of running TGP, GPU acceleration is crucial for achieving scalable performance. However, efficient GPU-based execution of TGP remains challenging, primarily due to three core issues: (1) the structural heterogeneity of program individuals, (2) the complexity of integrating multiple levels of parallelism, and (3) the incompatibility between high-performance CUDA execution and flexible Python-based environments. To address these issues, we propose EvoGP, a high-performance framework tailored for GPU acceleration of TGP via population-level parallel execution. First, EvoGP introduces a tensorized representation that encodes variable-sized trees into fixed-shape, memory-aligned arrays, enabling uniform memory access and parallel computation across diverse individuals. Second, EvoGP adopts an adaptive parallelism strategy that dynamically combines intra- and inter-individual parallelism based on dataset size, ensuring high GPU utilization across a broad spectrum of tasks. Third, EvoGP embeds custom CUDA kernels into the PyTorch runtime, achieving seamless integration with Python-based environments such as Gym, MuJoCo, Brax, and Genesis. Experimental results demonstrate that EvoGP achieves a peak throughput exceeding $10^{11}$ GPops/s. Specifically, this performance represents a speedup of up to $304\times$ over existing GPU-based TGP implementations and $18\times$ over state-of-the-art CPU-based libraries. Furthermore, EvoGP maintains comparable accuracy and exhibits improved scalability across large population sizes. EvoGP is open source and accessible at: https://github.com/EMI-Group/evogp.