Speeding up Automated Algorithm Design by Batch Evaluation: A Case Study of Genetic Programming for Ant Colony Optimisation

Bo-Cheng Lin, Yi Mei, Mengjie ZhangarXiv 2026 · arXiv

TL;DR

Automated Algorithm Design (AAD) is often bottlenecked by the grueling process of evaluating thousands of candidate heuristics. This paper introduces BlockEval, a framework that accelerates this process by parallelizing entire algorithm runs on GPUs, achieving up to a 16.5x speedup over a 32-core CPU for Genetic Programming-designed Ant Colony Optimization (ACO) rules.

What Problem Does This Paper Address?

In the world of Automated Algorithm Design, we use meta-heuristics like Genetic Programming (GP) or even Large Language Models (LLMs) to "evolve" or "write" better algorithms. However, generating a candidate algorithm is now much faster than testing it. To see if a new rule for Ant Colony Optimization (ACO) actually works, you have to run a full simulation—thousands of iterations across multiple problem instances.

The challenge is that these rules are often state-dependent. An ant doesn't just look at pheromones; it looks at its own construction state (e.g., "how many cities have I visited?"). Existing GPU accelerations for ACO typically assume a fixed, precomputed rule or parallelize the ants within a single run. When you try to evaluate a whole population of different rules, these traditional methods fall apart due to massive data movement overhead between the CPU and GPU and synchronization bottlenecks.

Methods

The authors propose BlockEval, a batch evaluation framework designed to treat a complete algorithm run as the unit of parallelism.

  • One Run per Thread Block: Instead of spreading one ACO run across the whole GPU, BlockEval maps one program running on one instance to a single GPU thread block. This keeps the entire simulation "local" to the multiprocessor.
  • Runtime Compilation (NVRTC): Since GP rules change every generation, BlockEval uses the CUDA Runtime Compilation library to bake the entire population of GP trees into a single CUDA module at the start of each generation. This allows the rules to be executed directly inside the GPU kernel without constant communication with the host.
  • Warp-Cooperative Fallback (WCF): In ACO, ants usually pick from a "candidate list" of nearby cities. If those are all visited, the ant must "fallback" and scan every city in the graph—a computationally expensive and divergent branch. WCF allows threads within a GPU warp to handle this scan cooperatively, ensuring that one ant's expensive fallback doesn't stall the entire thread block.
  • CPU Backend: For a fair comparison, they also developed a high-performance CPU backend using Numba (JIT compilation) and Threading Building Blocks (TBB) for multi-core scaling.

Datasets

The framework was evaluated using Euclidean Traveling Salesman Problem (TSP) instances from the ML4CO-Bench-101 benchmark.

  • Problem Sizes: 50, 100, 200, 500, and 1000 cities.
  • Workload: 256 GP programs evaluated on 32 instances per generation.

Key Insights and Ideas

  • Data Movement is the Bottleneck: The "Aha!" moment here is realizing that arithmetic is cheap, but moving data is expensive. By keeping the entire ACO loop, the pheromone updates, and the GP rule evaluation inside a single kernel, BlockEval drastically reduces the "memory wall" effect.
  • Granularity Shift: Moving the unit of parallelism from the "ant" level to the "run" level is a better fit for the high-throughput requirements of evolutionary computation.
  • The Cost of Divergence: The paper quantifies how much "waiting" occurs when ants take different paths. Their WCF mechanism proves that even highly divergent iterative algorithms can be made GPU-friendly if the synchronization is handled at the warp level rather than the block level.

Key Results

  • Vs. Optimized CPU: The GPU backend was 4.1x to 16.5x faster than the 32-core CPU backend.
  • Vs. Existing GPU Methods: It outperformed the state-of-the-art baseline (EvoGP + TensorACO-CL) by 11.2x to 17.8x.
  • Compilation Efficiency: While compiling at every generation sounds slow, it only accounted for about 1.4% of the total evaluation time for larger (1000-city) problems.
  • Throughput: The system reaches 90% of its maximum throughput at approximately 1,024 simultaneous tasks, showing excellent scalability for large GP populations.

Limitations and Future Work

  • Memory Constraints: As problem sizes grow beyond 1000 cities, the pheromone matrices and candidate lists may eventually exceed the shared memory or L2 cache limits of a single thread block/SM, potentially degrading performance.
  • Algorithm Scope: This study focused on ACO for TSP. While the authors suggest the techniques apply to other iterative algorithms (like job shop scheduling or routing), those specific cases haven't been tested yet.
  • Multi-GPU Scaling: The current work focuses on a single GPU; extending BlockEval to distribute tasks across a cluster of GPUs is a logical next step for even larger-scale automated design.

Summary updated

Abstract

Evaluation is becoming the bottleneck of automated algorithm design, especially for iterative algorithms such as ant colony optimisation (ACO), which must run to completion on multiple instances. A transition rule designed by genetic programming reads the construction state of each ant and must be evaluated at every step. However, existing GPU methods for ACO precompute a fixed rule and parallelise the ants of one run. To address this issue, we propose BlockEval, a batch evaluation framework with GPU and CPU backends. The GPU backend executes many runs simultaneously, each as a whole in one thread block, and compiles one module per generation. When an ant has visited all its candidate cities, a warp-cooperative fallback stalls only its warp where possible. On travelling salesman problems with 50--1000 cities, the GPU backend is 4.1--16.5 times faster than the CPU backend on 32 cores and 11.2--17.8 times faster than EvoGP+TensorACO-CL.
BibTeX
@misc{lin2026speeding,
  author = {Bo-Cheng Lin and Yi Mei and Mengjie Zhang},
  title = {{Speeding up Automated Algorithm Design by Batch Evaluation: A Case Study of Genetic Programming for Ant Colony Optimisation}},
  year = {2026},
  eprint = {2611.19751},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19751},
}
Figure