Abstract
We evolve floating point Sextic polynomial populations of genetic programming binary trees for up to a million generations. Programs with almost four hundred million instructions are created by crossover. To support unbounded Long-Term Evolution Experiment (LTEE) GP, we use both SIMD parallel AVX 512-bit instructions and 48 threads to yield performance of up to 139 billion GP operations per second (139 Giga GPOps) on a single Intel Xeon Gold 6126 2.60GHz server.
Introduction
In biological systems, evolution is a marathon, not a sprint. Richard Lenski’s famous Long-Term Evolution Experiment (LTEE) has tracked E. coli for over 70,000 generations, finding that beneficial mutations continue to appear even after decades.
In contrast, most Genetic Programming (GP) experiments are "sprints," typically running for only a few hundred generations. Researchers often assume that evolution eventually stalls due to "bloat" (uncontrolled growth of non-functional code) or reaching a fitness plateau. The challenge in testing this is computational: evaluating massive populations of giant program trees over millions of generations is prohibitively slow on standard hardware. This research seeks to bridge that gap by creating a high-performance GP engine capable of simulating "unbounded" evolution.
Methods
The system is built on GPQUICK, a memory-efficient C++ framework that stores GP trees using just one byte per node. To achieve the necessary speed, two major technical enhancements were introduced:
- SIMD Acceleration (AVX-512): The evaluation engine uses Intel’s Advanced Vector Extensions. Instead of processing one test case at a time, the system uses 512-bit registers to process 16 floating-point operations in parallel. By using 48 test cases (a multiple of 16), hardware utilization is maximized.
- Multicore Parallelism: PTHREADS distribute both fitness evaluations and crossover operations across 48 CPU cores.
- Cache Optimization: Traditionally, GP evaluates a tree by traversing it for every test case. This system processes all test cases for a single opcode at once before moving to the next node, significantly improving data locality and reducing cache misses for giant trees.
Datasets
The study uses the Sextic Polynomial benchmark ($y = x^6 - 2x^4 + x^2$), a standard symbolic regression problem.
- Training Data: 48 fixed test cases with inputs ($x$) randomly selected from the interval [-1, +1].
- Terminal Set: The variable $x$ and 250 random constants.
- Function Set: Basic arithmetic (+, -, ×, and protected division).
Results and Insights
The modernized GP engine achieved a peak performance of 139 billion GP operations per second (GPOps). This throughput allowed for runs extending to 1,000,000 generations, far exceeding standard GP literature.
Continual Innovation and the Bloat Paradox
Unlike Boolean problems where evolution often hits a hard ceiling, the continuous (floating-point) domain allows for "tiny, increasingly small steps" of improvement. Even after 100,000 generations, the system continued to find better solutions. In larger populations (4,000), the system consistently found approximations with mean absolute errors below $10^{-4}$, with some runs reaching errors as low as $10^{-9}$.
However, this long-term evolution also leads to massive program growth. The authors evolved programs containing nearly 400,000,000 instructions.
In small populations (e.g., 48 individuals), the entire population often converges to the exact same fitness. When there is no fitness differential, selection becomes random, which drives bloat because larger trees act as "shields"—crossover is more likely to hit a non-functional "intron" in a large tree than to disrupt the functional core. Despite this growth, evolved trees follow the "Flajolet limit," where tree depth grows roughly as the square root of the tree size ($depth \approx \sqrt{2\pi|size|}$), suggesting a "randomly shaped" architecture.
Conclusion
While the study demonstrates that evolution can sustain innovation over extreme timescales, it also highlights physical limits. Seven of the "extended" runs crashed due to memory exhaustion (46GB RAM) from the sheer size of the evolved trees. It remains an open question whether bloat will eventually stifle innovation by making it statistically impossible for crossover to produce meaningful changes in the functional core of a billion-node tree. Future work may involve more sophisticated memory management to push these boundaries even further.
Summary updated