The Effects of Population Size on the Performance of BEAGLE GPU-Based Genetic Programming Runs

1. Problem Statement

Genetic Programming (GP) is a heuristic search technique used for symbolic regression, but it faces significant computational bottlenecks, primarily during the fitness evaluation phase. Historically, the adoption of Graphics Processing Units (GPUs) to accelerate GP has lagged behind their success in Deep Learning due to several hardware and architectural incompatibilities:

• Structural Mismatch: Traditional Tree-Based GP representations involve irregular, dynamic tree structures that are difficult to map onto the rigid, linear memory architecture of GPUs (SIMD).
• Warp Divergence: Conditional branches (e.g., IF/ELSE statements) cause thread divergence in GPU warps, leading to performance degradation.
• Memory Overhead: Existing frameworks often rely on padding trees with "NaN" values to fit tensor requirements or use complex workarounds (like algebraic masking) that introduce redundant calculations and memory bloat.
• Garbage Collection (GC): Frequent memory allocation and deallocation in CPU-based evolutionary algorithms consume significant resources, a problem exacerbated in Tree-Based GP.

These limitations have prevented researchers from utilizing the massive parallelism of GPUs to explore population sizes in the millions, forcing a trade-off between search breadth (large populations) and search depth (many generations).

2. Methodology

The authors utilized Beagle, an open-source symbolic regression framework developed by Noblis, Inc., specifically designed to overcome the aforementioned GPU bottlenecks.

The Beagle Framework Architecture

• Linear Genetic Programming (LGP): Instead of tree-based structures, Beagle uses a custom Genome Computer Language (GCL) based on Reverse Polish Notation (RPN). This linear structure is heap-free, making it highly compatible with GPU memory models and eliminating GC overhead.
• GPU Execution Model:
  • Mapping: Each CUDA block represents a single organism (individual), and each thread within the block represents a single fitness case evaluation. This 1-to-1 mapping eliminates warp divergence.
  • Batching: To minimize CPU-GPU data transfer overhead, individuals are sent to the GPU once per generation to evaluate a batch of fitness cases (e.g., 512 or 1024 cases) before returning aggregate results.
  • No Crossover: The current implementation relies on mutation and selection, avoiding the structural recombination complexities that hinder GPU performance.
• CPU Optimization:
  • Memory Recycling: Beagle avoids deallocation. "Dead" individuals are placed in a pool and recycled for new individuals, effectively eliminating Garbage Collection and memory fragmentation.
  • Selection: A novel, high-performance Monte-Carlo-inspired selection process is used. Instead of sorting the entire population (which does not scale), it sorts a random sample (e.g., 100 individuals) to estimate fitness percentiles for the whole population, enabling selection for populations in the tens of millions.
• Fitness Function: Uses a correlation-based metric ($r^4$) adapted to handle invalid numbers (NaNs) by rewarding/punishing based on whether the model produces invalid outputs where the target is invalid.

Experimental Setup

• Benchmarks: 7 problems from the Feynman Symbolic Regression Benchmark (Equations 7, 14, 31, 56, 57, 86, 91).
• Constraints: Each run was limited to 15 minutes.
• Strategies Tested:
  1. Constant Population Sizes: Ranging from 100 to 100 million individuals.
  2. Stepped Population Sizes: Starting with a large population (e.g., 5M or 1M) and dropping to a smaller size (e.g., 100K, 10K, 1K, 100) after a set number of generations to balance breadth and depth.
• Success Criteria: A problem was considered solved if the error on the test set (128 points) was less than 0.1%.

3. Key Contributions

1. Quantifying Scaling Limits: The study demonstrates that GPU-accelerated GP can effectively manage population sizes up to 100 million individuals with negligible computational overhead, a scale previously unattainable.
2. Characterizing Breadth vs. Depth Trade-offs: The authors empirically proved that the optimal population size is problem-dependent.
   • Some problems (e.g., Eq 56) require "narrow and deep" searches (small populations, many generations).
   • Others (e.g., Eq 57) require "broad and shallow" searches (massive populations, few generations) to navigate rugged fitness landscapes.
3. Dynamic Population Management: The paper introduces and validates "stepped" strategies. Starting with a large population to explore the search space and then reducing it to focus on promising regions allows the system to benefit from both high diversity and high selection pressure.

4. Results

• Population Stability: The Beagle framework maintains target population sizes with a Gaussian distribution (mostly within ±20% of the target), confirming the stability of the Monte-Carlo selection approach.
• Constant Population Performance:
  • 10 Million was the most successful constant size overall (solving 112/210 total problem instances).
  • 1,000 individuals performed exceptionally well for specific problems (like Eq 56) that require deep iteration.
  • 100 Million showed diminishing returns for some problems, likely due to the time limit allowing fewer generations, though it solved the most problems overall.
  • 100 individuals performed poorly due to communication overhead relative to the small compute load.
• Stepped Population Performance:
  • The 5M $\to$ 100K strategy was the most robust, solving the highest number of problems (102/210) and successfully solving difficult equations (like Eq 57) that constant small populations missed.
  • The 1M $\to$ 100 strategy excelled at problems requiring deep search (Eq 56), solving it nearly 100% of the time.
• Scaling Efficiency: There is an inverse-proportional relationship between population size and the number of generations completed. A 10x increase in population size results in a 10x decrease in generations, confirming that Beagle scales linearly without significant overhead up to 100M individuals.

5. Significance

This work fundamentally shifts the paradigm for Genetic Programming by proving that massive population sizes are not only feasible but often necessary for solving complex symbolic regression problems.

• Hardware Utilization: It resolves the historical "occupancy" and divergence issues of GP on GPUs, allowing researchers to fully leverage modern GPU clusters.
• New Solution Space: By enabling populations in the millions, Beagle makes previously intractable problems accessible to evolutionary algorithms.
• Strategic Insight: The findings suggest that a "one-size-fits-all" population size is suboptimal. Instead, dynamic strategies that adapt population size based on the specific topology of the fitness landscape (rugged vs. smooth) yield superior results.
• Open Source Impact: By releasing Beagle as open-source, the authors provide the community with a tool to experiment with these massive scales, potentially accelerating the discovery of symbolic models in physics, engineering, and data science.