betaFeedback

WorksComputer Science

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

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.

Introduction

Automated algorithm design (AAD) uses search instead of human effort to design algorithms. Candidate algorithms can be generated by genetic programming (GP) hyper-heuristics [4, 28, 47] or, more recently, by large language models (LLMs) [30, 42]. Generating a candidate is becoming cheaper, but evaluating it still requires running it to completion on a set of instances. Therefore, the bottleneck of AAD is shifting from designing algorithms to evaluating them [30, 23]. This paper focuses on speeding up each evaluation.

In combinatorial optimisation, evaluation is particularly expensive when the algorithm being designed is itself a population-based iterative algorithm such as ant colony optimisation (ACO). GP has been used to design the transition rules of ACO (GP-ACO) [31, 25] and its pheromone update [36]. A designed transition rule scores each candidate city of an ant, and it can read the construction state of the ant in addition to the pheromone and the distance of the edge. For example, terminals computed over the remaining candidate cities, such as their average pheromone, significantly improve the designed rules [25]. Whichever component is designed, the resulting algorithm is evaluated by simulation, which runs a complete ACO on each training instance. A complete run is necessary because the effect of a rule on the pheromone carries over to all later iterations. In addition, GP-evolved scheduling rules generalise better to unseen instances whose sizes are close to those of the training instances [27, 48]. To learn rules that work on instances of various sizes, GP-ACO therefore needs more and larger training instances. However, because of the evaluation cost, existing GP-ACO studies can only use small problem sizes and few training instances [25], and the primitive set has been reduced to save execution time [31]. Other studies reduce the evaluation cost by approximating the fitness with surrogate models or multi-fidelity evaluation [46, 45], or by using a small evaluation budget [42]. In contrast, this paper speeds up the exact fitness evaluation, and the two can be combined.

A natural way to reduce this cost is to use GPUs, and GPU methods exist for both parts of this evaluation, namely ACO [5, 41] and the program trees of GP [39]. However, the performance of an algorithm is closely tied to the hardware and software it runs on [16]. To make full use of GPU acceleration, the design of an algorithm should take into account both the characteristics of the hardware and the structure of its workload. In GP-ACO, the workload of one generation consists of many independent runs, one for each program on each instance. Each run is a long sequence of dependent construction steps, and in every step the rule designed by GP scores the candidate cities of each ant. As a result, it is not easy to apply existing GPU methods to GP-ACO, even in combination, mainly due to two reasons.

First, the transition rule cannot be precomputed. Existing GPU implementations of ACO fix the rule. For example, TensorACO [41] computes the transition weights of all edges once per iteration as a table, and the ants only read this table during construction (Figure 1(a)). Such a table can only hold a rule that depends on the edge alone. A rule designed by GP also reads the construction state of each ant and needs to be evaluated at every construction step. On a GPU, EvoGP [39] evaluates all program trees of GP on a batch of inputs in one call (Figure 1(b)). However, EvoGP runs as a kernel of its own and can only be called from outside the construction loop, once at every construction step (Figure 1(c)). In each call, the terminals, the scores and a copy of the tree for every candidate need to pass through GPU memory, and the control flow stays on the host.

Figure 1. Existing GPU methods for the two parts of the evaluation, and their combination. Blue cells denote work, dark cells denote ants falling back to the full graph, and light grey cells denote waiting. All three are parallel, but none treats a complete run as the unit of parallelism. (a) TensorACO processes the ants of one run in parallel. Its rule is fixed and is read from a table computed once per iteration, and every ant considers all cities in every step. (b) EvoGP evaluates all trees on a batch of inputs in one call. Each thread copies a tree into local memory and interprets it node by node. (c) EvoGP+TensorACO-CL executes all runs of a generation as one batch, but advances them one construction step at a time, and calls EvoGP at every step with one tree copy per candidate. Double-headed arrows are the reads and writes of the kernels, and the marks on the host line are kernel launches and the points where the host waits. All data pass through GPU memory, the host waits once in every step, and all other ants wait while some fall back. EvoGP+TensorACO executes the same steps without candidate lists, and every ant considers all cities as in (a).

Second, existing GPU methods for ACO are designed to accelerate one run, whereas a generation consists of many independent runs. GPU implementations of ACO map one run to the whole GPU [6], typically with one thread block or warp per ant [5, 10, 33], and TensorACO represents the ants of one run as tensors. The runs of a generation can be stacked into one batch, as in GPU frameworks for evolutionary computation such as EvoX [17, 24], MetaDE [7] and AutoPSO [44]. However, all ants of the batch then advance one construction step at a time. This suits algorithms such as differential evolution (DE) and particle swarm optimisation (PSO), in which a step is one generation of a whole population. In contrast, an ACO run consists of a long sequence of small steps, and every construction step becomes a synchronisation point of all runs (Figure 1(c)). Without candidate lists, as in TensorACO, every ant reads and scores all cities in every step, and the data moved, the time and the memory of a step all grow with the problem size. With candidate lists, most steps are cheap, but all ants of the batch need to wait when one of them takes a more expensive step.

To the best of our knowledge, no existing study evaluates the designed rules of an iterative algorithm on a GPU with a complete run as the unit of parallelism, and compares the results with existing GPU methods and with an equally optimised multi-core CPU program. Further related work is discussed in § 9 of the supplementary material.

Both reasons stem mainly from the movement of data. In computer systems, performance is increasingly limited by moving data rather than by arithmetic [40, 18]. GPU acceleration in evolutionary computation is usually obtained by tensorisation, which expresses every step of an algorithm as operations on whole tensors [24, 41]. Each operation is a kernel that reads its operands from GPU memory and writes its result back. In a computation with many such kernels, every intermediate result therefore passes through GPU memory [38]. Moreover, the threads of a warp execute the same instruction and wait for each other when their control flow diverges [15]. For a long sequence of small dependent steps with expensive branches, these costs can outweigh the parallelism within a step, and a GPU need not be faster than an optimised multi-core CPU [22]. To reduce the movement of data, we evaluate the programs inside the kernel that constructs the tours of a run, and we treat a complete run as the unit of parallelism, rather than an ant or a construction step (Figure 2(b)). All construction steps of an iteration are then executed in one kernel, the inputs and outputs of the programs are kept in registers, and many runs are executed simultaneously.

Figure 2. Overall framework of BlockEval. (a) One generation consists of P×BP \times B tasks, each of which runs ACO once. (b) In the GPU backend, all programs of a generation are compiled into one module by NVRTC, the runtime compilation library of CUDA. Each task is executed by a thread block on a streaming multiprocessor (SM). The ant groups in a warp are synchronised, and when one group falls back to the full graph, the other groups need to wait. The arrows between the kernels and the GPU memory are the reads and writes of a kernel, and the marks on the host line are the kernel launches and the single point where the host waits. (c) In the CPU backend, the Threading Building Blocks (TBB) library assigns the tasks dynamically to 32 cores.

However, this is not straightforward, and there are two main difficulties. First, the GP programs change at every generation. If they are compiled into the kernel, the compilation needs to be repeated at every generation, and compiling GP programs for a GPU is expensive unless the cost is amortised [3]. Second, a kernel that executes a whole run contains divergent control flow, which is known to be costly on a GPU [20]. When all cities in the candidate list of the current city have been visited, an ant needs to select the next city from all unvisited cities. We call this step the fallback to the full graph. It is much more expensive than an ordinary step, and when an ant takes this expensive branch, the other ants need to wait. With many synchronised ants, at least one of them takes this branch in a large fraction of the construction steps.

The goal of this paper is to design a batch evaluation framework for GP-ACO, named BlockEval, whose GPU backend reduces the evaluation time per generation without changing the fitness computation. Specifically, this paper has the following three objectives.

  1. To analyse why existing GPU methods are not suitable for this workload, and to verify the analysis by experiments on TensorACO and on two baselines that combine it with EvoGP, without and with candidate lists.

  1. To design a batch evaluation framework that treats one run of one program on one instance as the unit of parallelism and reduces the movement of data between the host, GPU memory and the threads. Its GPU backend should execute each run as a whole, compile all programs of a generation into one module, and make full use of the GPU by executing many runs simultaneously. We also measure its speedup over the CPU backend, the effect of each design choice, its scalability and the cost of compiling at every generation.

  1. To design a fallback to the full graph such that, when an ant takes this expensive branch, not all other ants need to wait, and to measure its effect at different problem sizes.

Although this paper uses ACO for the travelling salesman problem (TSP) as a case study, the analysis and the corresponding techniques also apply to other iterative algorithms that call a designed rule in a long sequence of dependent steps with expensive branches, such as constructive heuristics for routing or scheduling.

Background

ACO for TSP

Given NN cities and the distance dijd_{ij} between each pair of them, the TSP [2] aims to find the shortest tour that visits each city exactly once and returns to the starting city.

ACO [14] uses a colony of ants to construct tours repeatedly and records the search experience in the pheromone τij\tau_{ij}. In each iteration, each of the AA ants starts from a city, and an ant at city ii selects the next city jj with probability

Pr⁡(j∣i)=τijαηijβ∑k∈Cτikαηikβ,j∈C,(1)\Pr(j \mid i) = \frac{\tau_{ij}^{\alpha}\eta_{ij}^{\beta}}{\sum_{k\in C}\tau_{ik}^{\alpha}\eta_{ik}^{\beta}}, \qquad j \in C, \tag*{(1)}

where ηij=1/dij\eta_{ij}=1/d_{ij} is the heuristic information, and α\alpha and β\beta control the relative weights of the pheromone and the heuristic information. To reduce the computational cost, a candidate list of the KK nearest neighbours is kept for each city, and the candidate set CC contains only the unvisited cities in this list. If all cities in the candidate list have been visited, the ant selects the unvisited city with the largest transition weight [14], which requires scanning all NN cities. This step is the fallback to the full graph. This paper considers three ACO variants, namely Ant System (AS) [13], Ant Colony System (ACS) [12] and MAX–MIN Ant System (MMAS) [35]. They differ mainly in how the pheromone is updated.

GP to Learn ACO Transition Rules

GP-ACO uses GP to design the transition rules of ACO automatically [31, 25]. Each GP individual is a program tree that takes the features of a candidate city as inputs and outputs a score for the city. The ant then selects the next city based on these scores. The terminal set includes features of the candidate edge (e.g., its distance and pheromone), the construction state of the ant and the progress of the run (Table S1 in the supplementary material). The fitness of a program pp is the average gap of the resulting ACO over BB training instances,

Name (abbreviation)DefinitionDepends on / rangeChampion rulesPrograms (%)
Function set. Each node output is protected (NaN→0\mathrm{NaN}\to0, ±∞→±10\pm\infty\to\pm10, clipped to [−10,10][-10,10])
ADD, SUB, MULa+ba+b, a−ba-b, ababBinary
PDIVab/(b2+10−6)ab/(b^2+10^{-6})Binary, protected division
MIN, MAXmin⁡(a,b)\min(a,b), max⁡(a,b)\max(a,b)Binary
ABS, NEG∣a∣\lvert a\rvert, −a-aUnary
Terminals. S(xj)=tanh⁡[(xj−xˉ)/(σx+10−8)]S(x_j)=\tanh[(x_j-\bar{x})/(\sigma_x+10^{-8})] standardises a value over the feasible candidate set CC, bj=τijηijb_j=\tau_{ij}\eta_{ij} and qj=bj/∑k∈Cbkq_j=b_j/\sum_{k\in C}b_k
RTau (RT)S(log⁡max⁡(τij,ϵ))S(\log\max(\tau_{ij},\epsilon))Edge and feasible set, [−1,1][-1,1]432.4
REta (RE)S(log⁡max⁡(ηij,ϵ))S(\log\max(\eta_{ij},\epsilon))Edge and feasible set, [−1,1][-1,1]1021.1
BaseConf (BC)tanh⁡(log⁡max⁡(qj,ϵ)+log⁡∣C∣)\tanh(\log\max(q_j,\epsilon)+\log\lvert C\rvert)Edge and feasible set, [−1,1][-1,1]2076.4
DistRank (DR)1−2rj/(∣C∣−1)1-2r_j/(\lvert C\rvert-1), where rjr_j is the distance rank among the unvisited citiesEdge and feasible set, [−1,1][-1,1]916.8
Entropy (EN)2[−∑j∈Cqjlog⁡max⁡(qj,ϵ)]/log⁡∣C∣−12[-\sum_{j\in C}q_j\log\max(q_j,\epsilon)]/\log\lvert C\rvert-1Feasible set318.9
ConstructProg (CP)2s/(n−1)−12s/(n-1)-1, where ss is the construction stepConstruction step217.1
ACOProg (AP)2(t−1)/max⁡(I−1,1)−12(t-1)/\max(I-1,1)-1, where tt is the iterationIteration319.4
Stagnation (ST)2min⁡(u/I,1)−12\min(u/I,1)-1, where uu is the number of iterations without improvement of the global bestIteration415.2
MutualRank (MR)1−[(rij−1)+(rji−1)]/[2max⁡(n−2,1)]1-[(r_{ij}-1)+(r_{ji}-1)]/[2\max(n-2,1)], clipped to [0,1][0,1]Edge (fixed for an instance)327.0
TurnCos (TC)cos⁡∠(xi−xh,xj−xi)\cos\angle(x_i-x_h,x_j-x_i), or 00 if there is no previous cityEdge and previous city, [−1,1][-1,1]512.4
Constants and ERC−1,−0.5,0,0.5,1-1,-0.5,0,0.5,1, ERC drawn from U[−1,1]U[-1,1] (FP32)Scalar
At least one state-dependent terminal2093.9

Table S1. Function set and terminal set of GP. ii is the current city, hh the previous city, jj a candidate, CC the feasible candidate set, ss the construction step, tt the iteration, uu the number of iterations without improvement of the global best, and ϵ=10−12\epsilon=10^{-12}. The abbreviations in brackets are used in the rule expressions. Champion rules is the number of the 20 champion rules (10 training runs each on TSP100 and TSP500) that read the terminal. Programs is the percentage of the 25,600 programs in the recorded populations that read it, after the expressions are simplified by exact identities.

f(p)=1B∑b=1B100Lpb−Lb∗Lb∗,(2)f(p) = \frac{1}{B}\sum_{b=1}^{B}100\frac{L_{pb}-L_b^{*}}{L_b^{*}}, \tag*{(2)}

where LpbL_{pb} is the length of the best tour found on instance bb and Lb∗L_b^{*} is its reference optimal length. In each generation, the fitness needs to be computed for all PP programs, which requires P×BP \times B runs of ACO.

A rule that depends only on the edge can be precomputed as a table, as is done for the heuristic matrices of DeepACO [43] and the transition weights of TensorACO. However, seven of the ten terminals depend on the construction state of the ant, such as DistRank, the distance rank of a candidate among the unvisited cities. We trained GP 10 times each on TSP100 and TSP500, and all 20 best rules read at least one of these terminals (Table S1 in the supplementary material).

The Proposed Framework: BlockEval

Overall Framework

The evaluation of one generation consists of P×BP \times B tasks. A task (p,b)(p,b) is a complete run of the ACO controlled by program pp on instance bb. The tasks are independent of each other (Figure 2(a)). Within a task, the iterations depend on each other through the pheromone, and the construction steps depend on each other through the visited cities. Only the ants and the candidate cities in the same step can be processed in parallel, and the GP program is evaluated at the level of candidate cities. Each task therefore has about A×KA \times K parallel operations per step, whereas the I(N−1)I(N - 1) selections of each ant need to be made one after another, where II is the number of ACO iterations.

Based on this structure, BlockEval treats a task as the basic unit of parallelism and executes each run as a whole rather than step by step. As shown in Figure 2(b) and (c), it has two backends that follow the same computation rules (§ 4). In the GPU backend, each task is executed by one thread block, and the ants and candidate cities of the task are assigned to the threads of this block (§ 3.3 and § 3.4). Compared with EvoGP+TensorACO-CL (Figure 1(c)), this mapping reduces the movement of data. The instances and the compiled programs are sent to the GPU once per generation, and the host waits only once, after all iterations. In an ordinary step, an ant reads only the entries of its KK candidates, which are stored contiguously for each city. The programs are compiled into the kernel, and the terminals and the outputs of the programs stay in registers instead of passing through GPU memory. In the CPU backend, each task is executed by one core (§ 3.5).

Residual Form of the Transition Rule

The transition rule takes a residual form, which is part of the GP-ACO training problem and is the same for all implementations compared in this paper. For each candidate city jj, the program tree computes zj=tree⁡(xj)z_j = \operatorname{tree}(x_j), where xjx_j denotes the values of the terminals at candidate jj. Instead of replacing the original transition weight with zjz_j, we use zjz_j to modify it by a bounded multiplier,

wj=bj[1+γtanh⁡(zj)],bj=τijηij2,γ=13.(3)w_j = b_j \left[1 + \gamma\tanh(z_j)\right], \qquad b_j = \tau_{ij}\eta_{ij}^{2}, \qquad\gamma= \frac{1}{3}. \tag*{(3)}

Here bjb_j is the original weight with α=1\alpha= 1 and β=2\beta= 2, and wjw_j replaces the numerator of Eq. (1). A tree that always outputs 0 gives exactly the original ACO, and GP therefore modifies the original rule rather than replacing it. In addition, the evaluation cost does not decrease when GP finds a trivial tree, and the measured speedup comes from the evaluation method, not from the rule.

GPU Kernel

A thread block (Figure 2(b)) contains min⁡(A,32)\min(A, 32) ant groups, each with TT threads, so that each thread needs to read only part of the KK candidates of the current city. When A>32A > 32, the remaining ants are processed in turn. In each iteration, a construction kernel is launched, followed by an update kernel, and the iterations are synchronised at the boundary between the two kernels. During construction, each thread reads its candidates at fixed positions and masks the visited cities, which avoids branching. The full pseudo-code of the construction kernel is given in Algorithm S2 in the supplementary material.

Compiling Once per Generation. At the beginning of each generation, each program is translated into straight-line code and placed into a switch statement indexed by the program number. To amortise the compilation cost [3], all programs of the generation are compiled into one module by NVRTC [29], the runtime compilation library of CUDA. Each thread scores its candidate positions in a loop, which we call the scoring loop. The candidate list is padded to 32 positions, and each thread has 32/T32/T positions. Unrolling this loop would copy the program for each of these positions. With one more copy in the fallback, each program would appear 32/T+132/T + 1 times in the kernel. We therefore keep the loop, and each program appears only twice, once in the selection from the candidate list (the ordinary selection) and once in the fallback to the full graph.

Warp-Cooperative Fallback

The threads of a GPU warp execute the same instruction simultaneously. When one ant group enters the fallback to the full graph (§ 2.1), the other synchronised groups therefore need to wait. Let qq be the probability that an ant falls back to the full graph in a construction step, and let mm be the number of synchronised ant groups. If the groups fall back independently, the fraction of waiting steps, in which the synchronised groups need to wait, is

πm(q)=1−(1−q)m.(4)\pi_m(q) = 1 - (1-q)^m. \tag*{(4)}

To address this issue, we propose the warp-cooperative fallback (WCF), which consists of two components (Figure 2(b)). First, the TT threads of an ant group enumerate the unvisited cities cooperatively. Thread ℓ\ell handles the cities whose indices are congruent to ℓ\ell modulo TT, and the results of the threads are merged at the end. DistRank is obtained by counting bits in a bitmap (lines 6 and 9 of Algorithm 1). The rank ri(j)r_i(j) of each city jj by its distance from city ii is precomputed once per instance. The DistRank of jj is then the number of unvisited cities ranked before jj. In this way, the cost of the fallback is proportional to the number of unvisited cities rather than to NN. Second, for AS and MMAS, the construction steps are not synchronised across the whole thread block. Only the ant groups in the same warp of 32 threads are synchronised, i.e., m=32/Tm = 32/T rather than 32. The local update of ACS requires the whole thread block to be synchronised in every step, and m=32m = 32 for ACS. Algorithm 1 shows one construction step of an ant group with WCF.

Algorithm 1 One construction step with WCF

Input: thread ℓ∈{0,…,T−1}\ell\in\{0,\ldots,T-1\} of an ant group, current city ii, visited bitmap VV in shared memory Output: next city jj

  1. if the candidate list of ii contains an unvisited city then

  2. Select j∗j^* from the candidate list ▷ ordinary selection

  3. else ▷ fallback to the full graph

  4. Uℓ←{j:V[j]=0, j≡ℓ(modT)}U_\ell\leftarrow\{j : V[j] = 0,\ j \equiv\ell\pmod{T}\} ▷ read from VV

  5. Compute the mean and variance of each terminal over all unvisited cities (sums over UℓU_\ell, then over the TT threads)

  6. R←0R \leftarrow0; set bit ri(j)r_i(j) of RR for each j∈Uℓj \in U_\ell; synchronise the TT threads

  7. (wℓ,jℓ)←(−∞,none)(w_\ell,j_\ell) \leftarrow(-\infty,\mathrm{none})

  8. for j∈Uℓj \in U_\ell in increasing order do

  9. DistRank(j)←(j) \leftarrow number of set bits of RR before bit ri(j)r_i(j)

  10. Compute zjz_j and wjw_j by Eq. (3); if wj>wℓw_j > w_\ell then (wℓ,jℓ)←(wj,j)(w_\ell,j_\ell) \leftarrow(w_j,j)

  11. end for

  12. j∗←j^* \leftarrow the jℓj_\ell with the largest wℓw_\ell over the TT threads ▷ ties go to the smaller jj

  13. end if

  14. Thread 0 appends j∗j^* to the tour and sets V[j∗]←1V[j^*] \leftarrow1

  15. Synchronise only the TT threads (AS, MMAS) or the whole block (ACS, then the local update)

CPU Backend

The CPU backend evaluates the same tasks with Numba [21] (Figure 2(c)). The whole ACO loop is compiled into native code once. The CPU backend also compiles at every generation, one scoring function for each program structure. In the fallback, it scans all cities once to collect the unvisited ones, and obtains DistRank from the precomputed ranks, or by pairwise comparisons when few cities are unvisited. The tasks are assigned dynamically to the cores by the Threading Building Blocks (TBB) library [37].

Experiment Design

The experiments aim to answer three research questions, which correspond to the three objectives. RQ1: How much time and GPU memory do existing GPU methods need on this workload, with and without candidate lists, and is this consistent with the analysis in Section 1? RQ2: How much faster is the GPU backend of BlockEval than the CPU backend on 32 cores, and how much does each of its design choices contribute? How does the speedup change with the problem size and the numbers of programs, instances and ants, and how much does compiling at every generation cost? RQ3: How much does WCF reduce the evaluation time, and how does its effect change with the problem size?

Datasets. The experiments use Euclidean TSP instances from ML4CO-Bench-101 [26], with 50, 100, 200, 500 and 1000 cities uniformly distributed in the unit square. The optimal tour lengths of these instances are used as the reference lengths. Each ACO run has I=500I = 500 iterations and a candidate list of K=20K = 20 cities, without local search. All parameter settings are listed in Table S2.

ItemValueNote
GP (DEAP, single tree) Population size / generationsP=100P = 100, G=50G = 50 (training runs, Section S6)10% of the initial population are trees that always output 0; the rest are generated by ramped half-and-half (depth 2–4)
Tree limits / selectionAt most 31 nodes and depth at most 5; tournament (size 4), elitism 10%Offspring exceeding the limits are replaced by their parents
Crossover / mutation / reproduction0.80 / 0.15 / 0.05Mutation: subtree 0.5, node replacement 0.3, constant perturbation 0.2 (σ=0.1\sigma= 0.1). The champion is updated on the validation set every 5 generations
ACO (no local search in any variant) Ants / iterations / candidate listA=32A = 32, I=500I = 500, K=20K = 20When the candidate list is exhausted, the unvisited city with the largest weight wjw_j is selected
α\alpha, β\beta, γ\gamma1, 2, 1/3Eq. (3) of the main paper
AS / ACS / MMASρ=0.5\rho= 0.5 / ρ=0.1\rho= 0.1, ξ=0.1\xi= 0.1, q0=0.9q_0 = 0.9 / ρ=0.02\rho= 0.02, pbest=0.05p_{\mathrm{best}} = 0.05The local update of ACS is synchronised in every step; MMAS restarts after 250 iterations without improvement
GPU execution (RTX A5000) Thread organisationOne thread block per task: min⁡(A,32)\min(A, 32) ant groups ×T=8\times T = 8 threadsWhen A>32A > 32, the ants are processed in turn
Active tasks3,200 (training runs); determined by the GPU memory (scalability experiments)The remaining tasks are executed in batches, keeping 25% of the GPU memory free
Program execution / arithmeticOne CUDA module is generated and compiled per generation; FP32 without FMA contraction or fast-mathCompilation time is included in the evaluation time; the same per-node protection as on the CPU
Experiments (10 independent runs, a run as the statistical unit) Scalability (RQ2)Three variants; starting point N=100N = 100, A=32A = 32; P≤256P \le256, B≤128B \le128, A≤128A \le128 (powers of 2); N∈{50,100,200,500,1000}N \in\{50, 100, 200, 500, 1000\}Each run evaluates the recorded populations of 10 consecutive generations of a GP run with 256 programs on TSP100 (a configuration with PP programs uses PP of them in a fixed random order); a P×BP \times B grid and 6 configurations at N=500N = 500 are also included
CPU backend (RQ2)The same populations and instances as on the GPU; 32 physical cores; additionally C∈{1,…,16}C \in\{1, \ldots, 16\} at N=100N = 100Paired by run; the comparison with the sequential Python implementation uses P=4P = 4, B=8B = 8, C∈{1,8}C \in\{1, 8\}
TensorACO with its fixed rule (RQ1)The same populations and instances as on the GPU; physical cores of TensorACO, C∈{1,…,16}C \in\{1, \ldots, 16\} at $N = 100 | The same populations and instances as on the GPU; paired by run; the comparison with the sequential Python implementation uses P=4P = 4, B=8B = 8, C∈{1,8}C \in\{1, 8\}
EvoGP+TensorACO (RQ1)The transition weights of TensorACO are modified by the programs with EvoGP: evaluates every construction step (Eq. (3) of the main paper), and the result is unique among all unvisited cities; default configuration N=100N = 100, A=32A = 32, I=500I = 500, K=20K = 20; only the time is comparedThe same populations and instances as BlockEvo (Ours): all 1,024 runs of each configuration are executed together for N=200N = 200; in batches of 256 runs for N=500N = 500 and of 32 for $N = 1000 (Section S3.2); only the time is compared
EvoGP+TensorACO-CL (RQ1)The same populations and instances as the two backends of BlockEvo (Ours), paired by run (Table 1 of the main paper); the default configuration uses N=100N = 100, A=32A = 32, I=500I = 500, K=20K = 20; one run is also executed alone (Table S4)The same populations and instances as the GPU backend, paired by run; Table 3 of the main paper lists only the default configurations N=500N = 500 and 1000
Ablation: kernels (RQ2, RQ3, Section S5.3 of the main paper)Mapping: 1/4/8/161/4/8/16 ants per block, and 1 ant per blockOnly medians are reported, without statistical inference; the main paper uses a factor of 500; mapping variants construct the same tours as the GPU backend
Ablation: implementation (RQ2, RQ3, Section S5.3 of the main paper)Mapping: 1/4/8/161/4/8/16 ants per block, and 1 ant per block; execution in 4 batches (per ant group (N=100,500N = 100, 500); execution in 4 batches per ant group (N=100,500N = 100, 500))Instrumented runs record the time of each kernel and the number of candidate-list exhaustions

Table S2. Table S2. Parameters and experimental settings. In all main experiments, each configuration is run 10 times independently, and each run is a statistical unit.

Time Measurement. To compare the methods on the same workload, each of the 10 runs uses the recorded populations of 10 consecutive generations of a separate GP run (256 programs, TSP100). These populations are evaluated under every configuration, with the instances and random-number keys of that configuration. The default configuration at each problem size uses P=B=A=32P = B = A = 32 and T=8T = 8. The two backends follow the same computation rules, with the same counter-based random numbers and deterministic single-precision arithmetic, and they differ only in rounding. The average gap of the same program differs between the two backends by 0.005 percentage points on average and by at most 0.23 (Table S5). We therefore compare only the evaluation time.

CPU backend, identical tours (%)EvoGP+TensorACO-CL (AS)
NNASACSMMASIdentical tours (%)Ratio of fallbacksMean gap differenceLargest for a program
5070.799.699.669.81.00010.0020.34
10011.498.998.111.31.00000.0050.98
2005.594.895.25.51.00000.0001.36
5007.782.085.67.70.9998−0.0431.08
100034.066.772.032.40.9996−0.1161.15
Gap difference between the two backends over all 111 configurations, mean 0.005, largest absolute value 0.23

Table S5. Consistency of the implementations on the same workload under the default configuration (P=B=A=32P = B = A = 32). Identical tours is the percentage of tasks for which the CPU backend or EvoGP+TensorACO-CL constructs exactly the same tours as the GPU backend. For EvoGP+TensorACO-CL, which runs AS on the 10 runs of Table 1 of the main paper, the ratio of fallbacks is its total number of fallbacks divided by that of the GPU backend. The gap difference is the average gap of the same program minus that in the GPU backend, in percentage points, given as the mean over all programs and as the largest absolute value for a single program. The last row gives the mean and the largest absolute value of the gap difference between the two backends (GPU minus CPU) over all 111 configurations.

Compared Methods. Hardware acceleration should be measured against an optimised CPU program [8, 9]. We therefore compare the GPU backend with the CPU backend, and also with existing GPU methods. On one core, the CPU backend is 95 times faster than the sequential Python implementation used in existing GP-ACO studies [25] (Figure S1). TensorACO [41] is run with its own fixed rule and without programs, as a reference. Its released code processes one run at a time. We stack the runs of a generation into one batch, which makes it 28–88 times faster (Table S3). Two baselines, EvoGP+TensorACO and EvoGP+TensorACO-CL, evaluate the designed rules by calling EvoGP [39], the state-of-the-art GPU evaluator of GP program trees, at every construction step. EvoGP+TensorACO multiplies the precomputed weights of TensorACO by the outputs of the programs as in Eq. (3). EvoGP+TensorACO-CL (Figure 1(c)) adds candidate lists and the fallback to the full graph. It runs AS with the same candidate lists, selection probabilities and random numbers as BlockEval and evaluates the same workload. We report the fastest of its three execution modes (Table S4). The times of the existing GPU methods exclude their one-time compilation.

Evaluation time and core scaling of the CPU backend

Figure S1. (a) Evaluation time per generation of the sequential Python implementation and the CPU backend (AS, N=100N = 100, P=4P = 4, B=8B = 8, A=8A = 8), and their ratios. (b) Speedup of the CPU backend over a single core (P=B=A=32P = B = A = 32) on TSP100 (solid) and TSP500 (dotted), with the values at 32 cores. The grey dashed line shows linear speedup. Error bars show the standard deviation.

NNTensorACO (fixed rule): As released (s)TensorACO (fixed rule): Speedup of stackingTensorACO (fixed rule): Runs per batchTensorACO (fixed rule): Revisiting tours (%)EvoGP+TensorACO: Runs per batchEvoGP+TensorACO: Time / fixed ruleEvoGP+TensorACO: Revisiting tours (%)
50283.2881,0241.31,02414.01.3
100552.6571,0244.61,02417.84.5
200948.1281,02415.21,02420.514.9
500––25662.125617.961.8
1000––6495.23215.895.1

Table S3. The two methods without candidate lists under the default configuration of AS. As released is the time per generation when the released code of TensorACO executes one run at a time, measured in the first generation of three runs for N≤200N \le200 only. The speedup of stacking is this time divided by the time with the runs stacked in Table 1 of the main paper. Revisiting tours is the percentage of tours in the last iteration that visit a city more than once. Time / fixed rule is the time per generation of EvoGP+TensorACO divided by that of TensorACO with its fixed rule.

Table S4. Evaluation time per generation of EvoGP+TensorACO-CL in three execution modes (AS, P=B=A=32P = B = A = 32, RTX A5000). The values are medians over three runs and exclude the one-time cost of the first generation. The ratio is the time divided by that of the GPU backend of BlockEval, paired by run.

ExecutionN=100N = 100 (s)RatioN=500N = 500 (s)Ratio
Eager188.437.71016.324.4
CUDA graph163.532.1906.422.4
torch.compile91.9318.4512.312.8
BlockEval (Ours), GPU backend4.99140.371

Table S4.

Platform and Statistics. Unless otherwise stated, the GPU experiments are conducted on an NVIDIA RTX A5000, and the CPU experiments on a node of an AMD EPYC 9634 cluster with 32 physical cores used exclusively. The evaluation time per generation is the wall-clock time from when the input of a generation is ready to when the fitness values are obtained, including compilation, data transfer and search. The cost per transition (ns) is the evaluation time divided by the PBAI(N−1)PBAI(N-1) city selections in a generation. Each configuration is run 10 times independently, and we report the mean and the standard deviation, with speedups computed from paired runs.

Results and Discussions

Evaluation Time and Memory

Table 1 shows the evaluation time per generation and the peak GPU memory under the default configuration of AS. The GPU backend is the fastest at all five problem sizes and uses the least GPU memory. For RQ1, the GPU backend is 14.6–156× faster than EvoGP+TensorACO and 11.2–17.8× faster than EvoGP+TensorACO-CL. Neither of these two baselines is faster than the CPU backend on 32 cores. Even TensorACO with its own fixed rule, which only reads a precomputed table, is not faster than the GPU backend. At N=50N = 50, the two take a similar time, but at N=1000N = 1000 the GPU backend is 9.9× faster. For RQ2, the GPU backend is 7.4–14.8× faster than the CPU backend on 32 cores for AS. The time of the GPU backend includes 1.6–1.8 s of compilation per generation, which is more than half of the evaluation time at N=50N = 50 but only 1.4% at N=1000N = 1000. Figure 3(a) shows the same pattern for ACS and MMAS, for which the GPU backend is 4.1–11.8× and 8.2–16.5× faster, respectively. Table S8 and Table S11 give the paired ratios and the results on six other GPUs.

NNExisting GPU methodsBlockEval (Ours)
TensorACO (fixed rule)EvoGP+TensorACOEvoGP+TensorACO-CLCPU (32 cores)GPU
TimeMem.TimeMem.TimeMem.TimeTimeComp.Mem.
503.21 ± 0.051.7344.83 ± 1.943.0444.33 ± 1.671.6643.34 ± 2.743.07 ± 0.171.770.69
1009.67 ± 0.174.91172.5 ± 8.67.1892.77 ± 5.371.7877.23 ± 8.015.23 ± 0.231.820.76
20033.84 ± 0.4117.66694.3 ± 34.020.63192.4 ± 11.72.15129.0 ± 8.611.27 ± 0.411.611.03
500250.2 ± 1.817.66†4477.6 ± 198.320.04†514.6 ± 18.96.35351.0 ± 34.139.57 ± 2.381.642.79
10001117.7 ± 2.017.66†17,691.7 ± 856.911.64†1265.5 ± 25.919.79839.0 ± 76.1113.8 ± 7.11.588.95

Table 1. Evaluation time per generation (s) and peak GPU memory (GB) under the default configuration of AS (P=B=A=32P = B = A = 32). TensorACO runs its own fixed rule without programs as a reference. The times are the mean ± standard deviation over 10 runs and exclude the one-time compilation of the existing GPU methods. Comp. is the compilation time per generation of the GPU backend (s), which is included in its time. The memory is the sampled peak held by the process, and for a generation executed in batches (†) it is that of one batch. The best value in each row is in bold.

Evaluation time per generation against TSP size, number of ants, and tasks per generation

Figure 3. Evaluation time per generation against (a) the problem size NN and (b) the number of ants AA. (c) Throughput against the number of tasks per generation PBPB (N=100N = 100, A=32A = 32). Solid lines correspond to varying BB and dotted lines to varying PP (only BB for the CPU backend). The vertical line is the number of resident tasks S=192S = 192. Colours denote the ACO variants. Dashed lines show the CPU backend on 32 cores, and the other coloured lines the GPU backend. The grey line with crosses shows EvoGP+TensorACO-CL for AS, excluding its one-time compilation, with medians over three runs in (b) and (c). Error bars show the standard deviation over 10 runs.

NNTensorACO (fixed rule)EvoGP+ TensorACOEvoGP+ TensorACO-CLCPU backend (32 cores)CPU backend (32 cores)CPU backend (32 cores)
501.0514.6114.4514.1410.7613.94
1001.8533.0417.7614.7811.8016.52
2003.0161.6517.0911.458.9513.94
5006.34113.513.048.886.1410.20
10009.86156.011.167.394.088.19
All configurations of Figure 38.8–55.61.70–18.0

Table S8. Evaluation time per generation of each method divided by that of the GPU backend of BlockEval under the default configuration (P=B=A=32P = B = A = 32). The ratios are paired by run and averaged over 10 runs, and the ratios of the CPU backend on 32 cores are the speedups of the GPU backend. The last row gives the ranges over all configurations of Figure 3 of the main paper, with medians over three runs for EvoGP+TensorACO-CL.

Table S11. Speed of each GPU relative to the RTX A5000 under the default configuration (P=B=A=32P = B = A = 32), as medians over the three variants, sorted by the speed at N=1000N = 1000. The speed is the device time on the A5000 divided by that on the GPU, and a value greater than 1 means faster. Arch. is the architecture and BW the memory bandwidth. The numbers of SMs, the L2 cache and the bandwidth are obtained from the CUDA device properties.

GPUArch.SMsL2 (MB)BW (GB/s)Relative speed N=100N=100Relative speed N=500N=500Relative speed N=1000N=1000
L4Ada58483000.920.830.74
RTX A5000Ampere6467681.001.001.00
A40Ampere8466961.121.131.11
RTX A6000Ampere8467681.261.201.21
RTX PRO 5000Blackwell110961,3441.301.301.46
L40SAda142968642.622.071.97
RTX 6000 AdaAda142969602.642.331.97

Table S11.

Why Existing GPU Methods Are Slower

Without Candidate Lists. To explain these results (RQ1), we measure the time of one construction step, in which each of the 32,768 ants of a generation selects one city (Table 2). For TensorACO, which has no candidate lists, the time per step grows in proportion to NN, from 0.13 ms to 2.2 ms. In every step, each of its ants reads the weights and the visited flags of all NN cities, 8N8N bytes in total, which is N/K=2.5N/K = 2.5–50 times as much data as with candidate lists. In contrast, a step of the GPU backend takes 0.11–0.23 ms and a step of the CPU backend 1.3–1.8 ms from N=50N = 50 to 1000. TensorACO is therefore faster than the CPU backend up to N=500N = 500 but slower at N=1000N = 1000, although it evaluates no program (Table 1). EvoGP+TensorACO moves even more data, since the terminals, the scores and a copy of the program pass through GPU memory for every city in every step. A generation of EvoGP+TensorACO takes 14.0–20.5 times longer than one of TensorACO with its fixed rule (Table 1), and most of this time does not depend on what the programs compute. At N=1000N = 1000, a batch whose program is a single terminal still needs 23.5 ms per step (Table S6), against 35.4 ms on average.

N=50N = 501002005001000
Time per construction step (ms)
TensorACO (fixed rule)0.1310.1950.3401.002.24
EvoGP+TensorACO1.833.496.9817.935.4
EvoGP+TensorACO-CL1.811.871.932.062.53
BlockEval (Ours), CPU backend (32 cores)1.771.561.301.411.68
BlockEval (Ours), GPU backend0.1250.1060.1130.1590.228
Share of the time of a step of EvoGP+TensorACO-CL (%)
GPU idle, waiting for the host to launch the next kernel46.446.136.422.310.1
Computing the terminals10.410.311.210.78.9
Programs evaluated by EvoGP27.025.726.223.819.0
Fallback to the full graph5.58.715.831.851.6
Other kernels10.89.210.411.410.4
EvoGP+TensorACO-CL, steps with a fallback (%)59.279.889.995.997.9

Table 2. One construction step under the default configuration of AS. The time per step is the time per generation divided by the I(N−1)I(N - 1) construction steps of a run, as means over 10 runs. The shares are measured in one generation, as the time for which the kernels run on the GPU divided by the time of a step (Table S7). The last row is the percentage of steps in which at least one ant of EvoGP+TensorACO-CL falls back.

Nodes of the programBatchesTime per step (ms)
18223.5
2–431526.9
5–8109630.4
9–1281535.6
13–1652040.8
17–2428249.8
25–319059.9
Linear fitN=50N = 501002005001000
Intercept (ms)1.172.124.1911.321.7
Slope per node (ms)0.0650.1360.2770.6611.364
Share of the intercept (%)64.160.760.163.061.3
R2R^{2}0.950.970.980.970.96

Table S6. Time per construction step of EvoGP+TensorACO against the size of the programs. The upper part groups the batches at N=1000N = 1000 by the number of nodes of their program. At this size, a batch contains the 32 runs of one program, and the time of a batch is converted to the time in which all 1,024 runs advance one step. The lower part gives a linear fit of the time of a batch to the mean number of nodes of its programs at each problem size, with the intercept, which does not depend on the program, the slope per node and the share of the intercept at the mean program size.

With Candidate Lists. EvoGP+TensorACO-CL scores the same 655,360 rows in every step regardless of NN, and a step takes 1.8–2.5 ms. On the same GPU, the GPU backend makes the same selections in less than a tenth of this time, including its compilation. As shown in the lower part of Table 2, the GPU is idle for 36–46% of a step of EvoGP+TensorACO-CL for N≤200N \le200, waiting for the host to launch the next kernel. This is because the host can launch the kernels of the fallback only after the GPU has reported how many ants have exhausted their candidate lists. In addition, the call to EvoGP takes 19–27% of a step, and computing its inputs takes 9–11%. The call alone takes longer than a complete step of the GPU backend. Moreover, all 32,768 ants advance in lockstep, and 59–98% of the steps contain a fallback, during which all other ants wait. This fallback takes 5.5% of a step at N=50N = 50 and 51.6% at N=1000N = 1000. In the GPU backend, the host waits only once per generation, and a fallback stalls only one warp.

Comparison with the CPU Backend. Although EvoGP+TensorACO-CL runs on a GPU, the CPU backend on 32 cores is at least as fast at all five problem sizes (Table 2). Each core of the CPU backend executes complete runs by itself with the rule compiled into its loop. The terminals and scores stay in registers, and no data are passed between separate tools or between the host and a GPU. A fallback delays only the ant that takes it. This indicates that executing complete runs is more effective for this workload than executing the steps of all runs on a GPU. The GPU backend applies the same principle with one run per thread block.

Ablation Study

We change one design choice of the GPU backend at a time on TSP500, under the default configuration of AS, and Table 3 shows the results. For the design choices of objective 2 (RQ2), executing one ant per thread block instead of one run takes 1.70 times as long. The interpreter kernel avoids compilation but takes 1.38 times as long. It still evaluates the rule inside the construction kernel. EvoGP+TensorACO-CL evaluates the same rule outside this kernel, and the GPU backend is 13.0×13.0 \times faster than it at this problem size (Table 1). This indicates that the gain comes mainly from where the rule is evaluated rather than from compiling it. Unrolling the scoring loop (§ 3.3) makes each program appear five times in the kernel instead of twice, which slows down the compilation and can reduce the number of resident tasks per SM from three to two, and this variant takes 1.15 times as long. When the runs are executed one at a time, as in existing GPU implementations of ACO [11, 34], the GPU backend is 40×40 \times faster, because each kernel launch then uses only a small part of the GPU.

Design choice of the GPU backendVariantTime ratio
One run per thread blockOne ant per thread block1.70
Programs compiled into the kernelInterpreter1.38
Scoring loop keptUnrolled scoring loop1.15
All runs executed simultaneouslyOne run at a time40.0
WCFDirect port8.30
8 threads per ant group4 threads per ant group1.60

Table 3. Ablation study on TSP500 (AS, P=B=A=32P = B = A = 32, RTX A5000). Each variant changes one design choice of the GPU backend, and the time ratio is its evaluation time per generation divided by that of the GPU backend. All variants are listed in Table S9.

Design choiceVariantTime ratioThreads per blockRegisters per threadBlocks per SM
GPU backend–125678–803
All tasks at onceOne run at a time40.08128–15912–16
Batches of 256 tasks1.22256803
Batches of 512 tasks1.07256803
One task per block1 ant per block1.708128–15912–16
4 ants per block1.1932115–12816
8 ants per block1.116494–1168–10
16 ants per block1.0512880–965–6
WCFDirect port8.3025664–942–4
Compiling onceUnrolled scoring loop1.1525680–1282–3
Interpreter1.38256803
8 threads per ant group4 threads per ant group1.60128146–1683
16 threads per ant group1.34512403

Table S9. Table S9. All variants of the ablation study on TSP500 (AS, P=B=A=32P = B = A = 32, RTX A5000). The time ratio is the evaluation time per generation of the variant divided by that of the GPU backend, as the mean over paired runs for the direct port and the unrolled scoring loop, and as the median over three runs for the others. The last three columns give the number of threads per thread block, the number of registers per thread and the number of thread blocks that can reside on an SM for the construction kernel of each variant. A range is given when the number of registers changes with the programs of a generation.

For the fallback to the full graph (RQ3), the GPU backend is 8.30× faster than the direct port, which implements the sequential program on the GPU without WCF (§ 6.2). With four threads per ant group, each thread reads more candidates and more ant groups are synchronised. This variant takes 1.60 times as long.

Further Analysis

Scalability in Each Dimension

For RQ2, we change one dimension at a time, starting from N=100N = 100 and P=B=A=32P = B = A = 32 (Figure 3). The three ACO variants show the same pattern. As NN increases, the evaluation time of both backends grows roughly in proportion to the workload (Figure 3(a)). When the number of programs PP, instances BB or ants AA increases, the CPU time grows roughly linearly. In contrast, the GPU time stays almost constant for small values and then grows gradually, because the compilation time does not depend on the number of instances or ants, and the GPU is not yet fully used. As shown in Figure 3(c), the throughput of the GPU increases with the number of tasks per generation PBPB and then levels off. It reaches 90% of its maximum at about 1,024 tasks. This is about five times the S=192S = 192 tasks that can reside on the A5000 simultaneously. The 32 cores of the CPU backend are fully used with tens of tasks per generation, whereas the A5000 needs about a thousand. Over all 111 configurations, the GPU backend is 1.70–18.0× faster than the CPU backend. At all points of the grey line, it is 8.8–55.6× faster than EvoGP+TensorACO-CL (Table S8).

Effect of WCF at Different Problem Sizes

To investigate how much WCF helps (RQ3), we compare the GPU backend with the direct port (§ 5.3), which also executes each run in one thread block. Figure 4a shows that, from N=50N = 50 to 1000, the cost per transition of the direct port grows by a factor of 26, whereas that of the GPU backend grows by a factor of only 1.8. Compared with the CPU backend, the direct port is faster up to N=500N = 500 but slower at N=1000N = 1000. This shows that executing each run as a whole is not sufficient.

Cost per transition and fraction of waiting steps

Figure 4. Effect of the fallback to the full graph (RTX A5000, P=B=A=32P = B = A = 32). (a) Cost per transition of AS. The shading shows the standard deviation, and the numbers give the increase from N=50N = 50 to 1000. (b) Fraction of waiting steps. The grey lines show Eq. (4) for mm synchronised ant groups. The markers show the measured fraction of steps in which a warp (m=4m = 4) or a thread block (m=32m = 32) contains a fallback, over three generations of one run, against the measured qq. Colours denote the method and the ACO variant, and shapes denote NN.

This difference is mainly due to the fallback to the full graph. For AS, an ant falls back in q=1.9q = 1.9–3.1%3.1\% of its construction steps. Since the direct port synchronises the whole thread block in every step (m=32m = 32), 25–43% of the steps of a thread block contain a fallback, and all ants in the block need to wait (Figure 4(b)). In addition, the direct port scans all NN cities in each fallback. WCF synchronises only within a warp (m=4m = 4), which reduces the fraction of waiting steps to 6.5–10.4%, and the time of each wait is proportional only to the number of unvisited cities. For ACS, the local update synchronises the whole thread block in every step, and 17–39% of its steps are still waiting steps even with WCF. This explains why ACS has the lowest speedup (Table S8).

Conclusions and Future Work

The goal of this paper was to speed up evaluation in AAD when the algorithm being designed is itself an iterative algorithm, with GP for designing the transition rules of ACO as the case study. The main contributions are as follows. First, we analysed why existing GPU methods are not suitable for this workload. They precompute a fixed rule, and all ants of a batch advance one construction step at a time. Second, we proposed BlockEval, a batch evaluation framework that treats each run of one program on one instance as the unit of parallelism. Its GPU backend executes each run as a whole in one thread block, compiles all programs of a generation into one module in which each program appears only twice, and makes full use of the GPU by executing many runs simultaneously. Third, we proposed the warp-cooperative fallback (WCF), which enumerates the unvisited cities with the threads of an ant group and, for AS and MMAS, synchronises only within a warp, so that a fallback stalls only one warp.

For RQ1, under the default configuration, the GPU backend is 14.6–156 times faster than EvoGP+TensorACO and 11.2–17.8 times faster than EvoGP+TensorACO-CL, and neither of the two is faster than the CPU backend on 32 cores. Even TensorACO with its fixed rule is not faster than the GPU backend, because it scores all cities in every step. In EvoGP+TensorACO-CL, the GPU is idle for 36–46% of a step for N≤200N \le200, waiting for the host to launch the next kernel. The GPU backend makes the same selections in less than a tenth of the time. For RQ2, the GPU backend is 4.1–16.5 times faster than the CPU backend on 32 cores under the default configuration, and it is 40 times faster than executing the runs one at a time on TSP500. The A5000 is fully used with about a thousand tasks per generation, and compiling at every generation takes only 1.6–1.8 s in the GPU backend. For RQ3, WCF is particularly effective on large problems. The GPU backend is 8.3 times faster than the direct port on TSP500, and the direct port is slower than the CPU backend on TSP1000.

The techniques of BlockEval should also apply to other iterative algorithms with learned components, such as constructive heuristics designed by GP for scheduling and routing, and code generated by LLMs. We will verify these techniques on such algorithms, extend BlockEval to multiple GPUs, and study how more training instances and larger problems affect the learned rules.

Supplementary Material

This supplementary material provides details and additional results that support the main paper.

  • Section S1 discusses further related work and supports the introduction in § 1.

  • Section S2 gives the function set and terminal set of GP, the training process, the construction kernel and the computation rules of the two backends, and supports § 2 and § 3.

  • Section S3 gives the parameter settings and the details of the compared methods, and supports the experiment design in § 4.

  • Section S4 reports additional measurements of the existing GPU methods and supports the answer to RQ1 in § 5.2.

  • Section S5 reports the paired time ratios, all variants of the ablation study, the cost of compiling and the results on other GPUs, and supports the answers to RQ2 and RQ3 in § 5.1, § 5.3 and § 6.

  • Section S6 shows an example of a learned transition rule.

Extended Related Work

This section extends the discussion of related work in § 1 of the main paper.

Evaluation in AAD. In AAD, a search method such as GP maintains a population of candidate algorithms and improves it generation by generation [4, 28, 47]. In each generation, every candidate is run on a set of training instances, and its performance is aggregated into a fitness value. The evaluation time of one generation is the product of the number of candidates, the number of instances and the time of one run. When a candidate is a dispatching rule or a formula, one run is one pass over an instance. When a candidate is an algorithm such as ACO, one run is itself a search of hundreds of iterations, and evaluation dominates the training time. Surrogate models and multi-fidelity evaluation [46, 45] have been widely used to reduce the number of individuals that need exact evaluation. Other studies reduce the cost of one run by using small instances, few ants and few iterations [25, 42]. For example, learning-based and LLM-based ACO design methods [43, 42, 19] compute a heuristic matrix once per instance, run ACO step by step as tensor operations and use a small evaluation budget. These methods save time by approximating the fitness or by reducing the evaluation budget, which may affect the accuracy of the fitness values. In contrast, BlockEval speeds up the exact fitness evaluation, and it can be used together with these methods.

Evolutionary Computation on GPUs. EvoX [17] and work on tensorised evolutionary multi-objective optimisation [24] represent populations and operators as tensors and execute them in batches on GPUs. EvoGP [39] evaluates GP program trees in batches, and a simulation that uses the trees calls it once per step. MetaDE [7] and AutoPSO [44] run designed DE and PSO variants in batches, and one iteration of these algorithms consists of a few dense tensor operations. These frameworks parallelise across the candidates and leave the control flow of the algorithm on the host. However, each ant of an ACO run makes N−1N-1 dependent selections in every iteration, and each selection scores only KK candidate cities. Executed in this way, ACO needs at least one kernel launch in every construction step (Figure 1(c) of the main paper).

ACO on GPUs. GPU implementations of ACO map one run to the whole GPU. Cecilia et al. [5] assigned each ant of AS to a thread block, and their implementation was up to 20 times faster than the sequential one. Delévacq et al. [11] found this mapping much faster than assigning each ant to a thread in MMAS. Dawson and Stewart [10] used four warps for each ant of AS and reported a speedup of up to 82 over a CPU implementation. Skinderowicz [33, 34] implemented ACS and MMAS with one thread block per ant, candidate lists of 32 cities and as many ants as cities. Cecilia et al. [6] further sped up AS with CUDA vectorisation and atomic operations. TensorACO [41] replaces branches with precomputed weights and masks and uses independent roulette wheels to increase parallelism, which changes the selection probabilities. All these studies parallelise one ACO run on one instance. Ayral and Albayrak [3] compiled GP individuals for the GPU and found the compilation cost prohibitive unless it is amortised.

CPUs and GPUs. A CPU core is designed to complete a single task quickly. It predicts branches, executes instructions out of order and has large caches, which allow each core to follow its own control flow. A GPU trades single-thread performance for throughput [22]. Its threads are grouped into warps that execute the same instruction, and when the threads of a warp take different branches, some of them are idle [15]. After both platforms were optimised, a GPU was on average only 2.5 times faster than a multi-core CPU over a set of throughput computing kernels [22]. A GPU need not be faster for computations with many branches and many dependent steps. It is most effective when it executes a very large number of similar threads. The GPU backend of BlockEval executes the runs of a generation as many similar thread blocks and limits the cost of divergent branches to one warp.

Granularity of Parallelism. Parallel evolutionary algorithms have long been classified by the level at which they are parallelised, from master–slave models that evaluate the fitness in parallel to coarse-grained and fine-grained population models [1]. Tensorisation [24] parallelises at the finest level, within each operation of an algorithm. BlockEval is a master–slave model in which the unit of work is a complete run. On GPUs, a kernel that executes a whole task is known to suffer from divergent control flow, and Laine et al. [20] found that executing path tracing stage by stage is faster, partly for this reason. WCF reduces this cost for the fallback of ACO.

GP-ACO and the Two Backends

This section gives the details of GP-ACO and of the two backends that are omitted from § 2 and § 3 of the main paper.

Function Set and Terminal Set

Table S1 lists the function set and the terminal set of GP. Seven of the ten terminals depend on the construction state of the ant. RTau, REta, BaseConf, DistRank and Entropy depend on the feasible set, ConstructProg depends on the construction step, and TurnCos depends on the previous city. The other three do not change within an iteration. As shown in the last two columns, all 20 champion rules, from 10 training runs each on TSP100 and TSP500, read at least one state-dependent terminal, and all of them read BaseConf. In the recorded populations used for the time measurements, 93.9% of the 25,600 programs read at least one such terminal.

Training Process

Algorithm S1 gives the training process of GP. In each generation, BB instances are sampled from the training pool, and all PP programs are evaluated on them in one batch. Every five generations, the champion is updated on the validation set.

Algorithm S1 Training process of GP for designing the transition rules of ACO

Input: Population size PP, number of generations GG, number of instances per generation BB, training pool, validation set

Output: Champion rule p⋆p^\star

  1. Initialise the population: 10% are trees that always output 0 (i.e., the original ACO), and the rest are generated by ramped half-and-half

  2. for g=1,…,Gg = 1,\ldots,G do

  3. Sample BB instances from the training pool without replacement, and evaluate all PP programs in a batch (§ 3.1 of the main paper)

  4. if g mod 5=0g \bmod5 = 0 then

  5. Evaluate the current top 5 individuals and the champion p⋆p^\star on the validation set, and update p⋆p^\star by the validation gap

  6. end if

  7. Generate the next population by elitism, tournament selection, crossover, mutation and reproduction

  8. end for

  9. return p⋆p^\star

Construction Kernel on the GPU

Algorithm S2 gives the work of one ant group in one iteration of the construction kernel. It implements the techniques described in § 3.3 and § 3.4 of the main paper.

Algorithm S2 One iteration of an ant group in the construction kernel

Input: task (p,b)(p,b), iteration tt, thread ℓ∈{0,…,T−1}\ell\in\{0,\ldots,T-1\} of an ant group Output: tours constructed by the ants of this group in iteration tt

  1. for each ant aa of this group do

  2. Select the start city of ant aa with the random number of counter (t,a,0)(t,a,0), and clear its visited bitmap

  3. end for

  4. for s=1,…,N−1s=1,\ldots,N-1 do

  5. for each ant aa of this group, at its current city ii do

  6. Thread ℓ\ell loads entries ℓ,ℓ+T,ℓ+2T,…\ell,\ell+T,\ell+2T,\ldots of the candidate list of city ii and masks them with the bitmap ▹\triangleright no branch

  7. if the masks of all threads are empty then ▹\triangleright fallback to the full graph

  8. Select j∗j^{*} by WCF (Algorithm 1 of the main paper)

  9. else

  10. Reduce to obtain the mean and variance of each terminal over CC; thread ℓ\ell computes zjz_j and wjw_j (Eq. (3) of the main paper)

  11. Select j∗j^{*} by prefix sums and merging across threads (counter (t,a,s)(t,a,s); ACS takes the maximum with probability q0q_0)

  12. end if

  13. Set bit j∗j^{*} and i←j∗i \leftarrow j^{*}

  14. end for

  15. ACS performs the local update and synchronises the thread block

  16. end for

Computation Rules of the Two Backends

In each generation, the evaluator generates code for all programs and prepares the coordinates, nearest-neighbour lists and random-number keys of each instance. It then passes the P×BP \times B tasks to a backend and computes the fitness by Eq. (2) of the main paper. Both backends follow the same computation rules. Random numbers are generated by the counter-based generator Philox4x32-10 [32], whose keys depend only on the root seed, the phase, the generation and the instance, and not on the program. All programs of a generation therefore use the same random numbers on the same instance, and the differences in fitness come only from the rules themselves. In terms of arithmetic, both backends use deterministic single-precision floating point, with FMA contraction and fast-math disabled, and protect the output of each function node in the same way (Table S1). However, the two backends do not guarantee the same order of floating-point reductions, and over 500 iterations tiny rounding differences grow into different tours. We therefore compare the time only on the same populations and instances (§ 11.4).

Compared Methods and Settings

This section gives the parameter settings and the details of the compared methods, and supports the experiment design in § 4 of the main paper. Table S2 lists all parameters and experimental settings.

Speed of the CPU Backend

The CPU backend is much faster than the sequential Python implementation used in existing GP-ACO studies [25] (Figure S1). On one core, it is 95 times

faster than this implementation, and on eight cores it is 34 times faster, because every selection of the Python implementation goes through the interpreter. Figure S1 shows the speedup of the CPU backend over a single core. On TSP100, 32 cores are 19.3–20.1 times faster than one core.

TensorACO and EvoGP+TensorACO

TensorACO [41] represents the ants of a run as tensors. At the beginning of an iteration, it computes the transition weights τijαηijβ\tau_{ij}^{\alpha}\eta_{ij}^{\beta} of all edges as an N×NN \times N table. In each construction step, each ant reads the row of its current city from this table, masks the visited cities and selects the next city with the adaptive independent roulette of TensorACO. There are no candidate lists, and each ant selects among all unvisited cities in every step. After the last step, the pheromone is updated from the tours of all ants.

We run TensorACO with its own fixed rule on a workload of the same shape as the default configuration. A generation consists of 1,024 runs with 32 ants and 500 iterations, in which each of the 32 instances is solved 32 times with different random numbers. Its released code processes one run at a time. We stack the runs of a generation along a new axis of the tensors and execute them together, in batches of the size given in Table S3. For N≤200N \le200, stacking makes the released code 28–88 times faster.

EvoGP+TensorACO keeps the procedure of TensorACO and changes only the rule. In each construction step, the terminals of Table S1 are computed for all cities of each ant, with all unvisited cities as the feasible set. EvoGP then evaluates the program of each run on these rows, and the weight of each city is multiplied by 1+γtanh⁡(zj)1 + \gamma\tanh(z_j) as in Eq. (3) of the main paper. The selection and the pheromone update are those of TensorACO, and the runs are stacked in the same way. Since its feasible set and selection differ from those of BlockEval, we compare only the evaluation time.

In long runs, both methods return tours that visit a city more than once, because the pheromone of rarely used edges underflows in single precision. For TensorACO, the share of such tours in the last iteration rises from 1.3% at N=50N = 50 to 95.2% at N=1000N = 1000 (Table S3). This does not change the amount of computation in a step.

In Table 1 of the main paper, the GPU memory is the peak memory held by the process, sampled during the run. TensorACO is written in JAX, which reserves GPU memory in blocks and by default uses at most 75% of the available memory, or 17.66 GB on the A5000. TensorACO reaches this limit from N=200N = 200. Its pheromone update builds an N×NN \times N matrix for each ant, which takes 4AN24AN^{2} bytes per run. For the 1,024 runs of a generation, these matrices alone exceed the 24 GB of the A5000 when N≥500N \ge500, and the runs are executed in batches in turn. EvoGP+TensorACO also stores one row of terminals for each city of each ant and needs 20.6 GB at N=200N = 200 (Table 1 of the main paper).

EvoGP+TensorACO-CL

EvoGP+TensorACO-CL adds candidate lists and the fallback to the full graph to EvoGP+TensorACO. Its candidate lists, terminals, transition rule, roulette wheel, fallback rule, pheromone update and random numbers are the same as in the two backends of BlockEval, and it evaluates the same workload (§ 11.4). All P×B×AP \times B \times A ants advance one construction step together. In each step, the terminals of the KK candidates of all ants are computed as tensors, EvoGP evaluates the programs on these PBAKPBAK rows, and the roulette wheel selects the next city. Next, the host waits until the GPU reports how many ants have exhausted their candidate lists, and these ants are gathered. Since all ants are at the same step, these ants have the same number of unvisited cities. Their terminals are computed on a compact array of these cities, followed by a second call to EvoGP. After each iteration, the pheromone is updated ant by ant, as in the two backends.

EvoGP evaluates each row of inputs with one thread, which interprets the tree stored with the row. We added the protected division and the protection of every node output (Table S1) to its tree-evaluation kernel. Calling EvoGP at every construction step is consistent with its use in control problems, where it is called once per simulation step.

We execute the tensor operations in three modes. The eager mode executes them one by one, the CUDA graph mode captures the ordinary selection and the update of the tours as CUDA graphs, and the torch.compile mode compiles them. As shown in Table S4, the torch.compile mode is the fastest of the three, and it is the one reported in the main paper. As in Table 1 of the main paper, the times exclude the one-time cost of the first generation, which is the compilation of torch.compile or the warm-up of the other two modes. CUDA graphs reduce the eager time by only 11–13%, since the host still waits for the GPU in every step before it launches the fallback.

Workload Consistency

Table S5 compares the tours and fitness values of the implementations on the same workload. The two backends construct identical tours in 5.5–70.7% of the tasks for AS and in 66.7–99.6% for ACS and MMAS, and the tours of the other tasks differ because of rounding (§ 10.4). Over all 111 configurations, the average gap of the same program differs between the two backends by 0.005 percentage points on average and by at most 0.23. EvoGP+TensorACO-CL constructs identical tours in about the same share of tasks as the CPU backend for AS. Its total number of fallbacks differs from that of the GPU backend by less than 0.05%, and the mean difference in the average gap of the same program is at most 0.12 percentage points at each size. For a single program, the difference is at most 1.4 percentage points. On small instances, its three execution modes construct the same tours as the CPU backend.

Conditions of the Comparison

All methods run on the same RTX A5000, with no other process on the GPU. EvoGP+TensorACO and EvoGP+TensorACO-CL evaluate the same recorded populations and instances as the two backends of BlockEval, and EvoGP+TensorACO-CL also uses the same random-number keys and is paired by run. The existing GPU methods are compiled once, and this one-time compilation is excluded from their time per generation. For EvoGP+TensorACO-CL, it takes 33.2–39.8 s per problem size (Table S10). Both backends of BlockEval compile at every generation, and their times include this compilation.

Table S10. Compilation time under AS. The upper part gives the one-time compilation of EvoGP+TensorACO-CL by torch.compile, the compilation time per generation of the CPU backend on 32 cores, its share of the evaluation time, and the speedup of the GPU backend when the compilation is excluded from the CPU time only (P=B=A=32P = B = A = 32, means over 10 runs). The compilation time of the GPU backend is given in Table 1 of the main paper. The lower part gives the number of copies of each program in three kernels and their compilation time per generation at P=1P = 1, 32 and 256, as means over all configurations with the same PP.

NNEvoGP+TensorACO-CL compiled once (s)CPU backend compile (s)CPU backend compile share (%)Speedup without CPU compilation
5033.216.037.08.92
10034.518.023.411.33
20037.415.812.310.05
50035.816.94.88.46
100039.816.82.07.24
KernelCopiesP=1P = 1 (s)P=32P = 32 (s)P=256P = 256 (s)
Direct port10.661.094.19
BlockEval (Ours)20.881.6510.49
Unrolled scoring loop50.822.8634.97

Table S10.

Why Existing GPU Methods Are Slower

This section reports additional measurements of the existing GPU methods and supports the answer to RQ1 in § 5.2 of the main paper.

Without Candidate Lists

Without candidate lists, each of the PBA=32,768PBA = 32{,}768 ants scores all NN cities in every step. For TensorACO and EvoGP+TensorACO, the time per construction step therefore grows in proportion to NN, and the time per generation grows with N2N^{2} (Tables 1 and 2 of the main paper). Although the two methods differ only in the rule, EvoGP+TensorACO takes 14.0–20.5 times longer than TensorACO with its fixed rule (Table S3).

To investigate how much of this time is spent on computing the programs, we relate the time of EvoGP+TensorACO to the size of its programs (Table S6). The programs of the recorded populations have 1–31 nodes. At N=1000N = 1000, a batch contains the 32 runs of one program. A batch whose program is a single terminal requires no arithmetic but still needs 23.5 ms per step, against 59.9 ms for programs with 25–31 nodes. At all five problem sizes, the time of a batch grows linearly with the mean number of nodes of its programs (R2≥0.95R^{2} \ge0.95). The intercept of the fit does not depend on the program and accounts for 60–64% of the time at the mean program size. This indicates that most of the time of EvoGP+TensorACO is spent on computing the terminals of all cities, passing them to EvoGP, returning the scores and selecting the next city, rather than on computing the programs.

With Candidate Lists

For EvoGP+TensorACO-CL, the GPU is idle, waiting for the host to launch the next kernel, for 37–43% of the time for N≤200N \le200, 21% at N=500N = 500 and 7% at N=1000N = 1000 (upper part of Table S7). For TensorACO and EvoGP+TensorACO, this share is at most 5.3%, and their time is spent in kernels. For the GPU backend, the GPU is idle only while the host compiles the programs, and this share differs from the share of the compilation measured by the timers by at most 0.6 percentage points.

N=50N = 501002005001000
GPU idle, waiting for the host to launch the next kernel, in the runs of Table 1 (%)
TensorACO (fixed rule)5.32.81.21.40.5
EvoGP+TensorACO0.60.30.00.00.1
EvoGP+TensorACO-CL43.143.137.420.77.2
BlockEval (Ours), GPU backend57.935.013.74.31.4
Share of compilation, GPU backend (timers)57.534.914.34.11.4
Kernel time per construction step of EvoGP+TensorACO-CL (ms)
Computing the terminals0.1930.2000.2090.2180.231
EvoGP in the ordinary selection0.5030.4990.4890.4880.492
Roulette wheel0.0470.0530.0670.0920.107
Fallback to the full graph0.1010.1700.2950.6501.337
of which calls to EvoGP0.0140.0230.0360.0840.161
Writing the tours0.0260.0270.0280.0300.031
Candidate tables and pheromone update0.1270.0990.0980.1120.131
All kernels0.9981.0481.1861.5892.329
Time per step of this generation1.861.941.862.042.59
GPU idle, waiting for the host to launch the next kernel0.8630.8960.6780.4560.261
Kernels per step7570686767
Host waits per step1.061.031.021.011.00
Bytes copied to the host per step44444
Its calls to EvoGP alone (ms per step)0.4610.4620.4620.4630.462

Table S7. A construction step of EvoGP+TensorACO-CL under the default configuration of AS (P=B=A=32P = B = A = 32, torch.compile mode, RTX A5000). The upper part is the share of the time in which the GPU is idle, waiting for the host to launch the next kernel, in the runs of Table 1 of the main paper. The driver reports once per second the share of the last period in which at least one kernel was running, and the table gives its complement, averaged over the measured generations of each run and then over the runs. The last row of this part is the share of the compilation in the evaluation time of the GPU backend, measured by the timers. The middle part is the kernel time per construction step by stage, from one generation at each problem size in which every kernel is recorded in 10 evenly sampled iterations. The time per step of this generation is taken from the same generation of the runs of Table 1, and its difference to the time of all kernels is the time in which the GPU is idle. The lower part gives the kernels launched, the waits of the host and the bytes copied to the host per step, and the time per step when only the calls to EvoGP of a generation are executed (means over 10 runs).

To measure the kernel time of each stage, we record the start and the end of every kernel in 10 evenly sampled iterations of one generation of EvoGP+TensorACO-CL at each problem size (middle part of Table S7). The kernels run for 1.00–2.33 ms per step, and the GPU is idle for the remaining 0.26–0.90 ms, which agrees with the upper part. Of the kernel time, EvoGP takes 0.49–0.50 ms per step regardless of NN, and computing the terminals takes 0.19–0.23 ms. The kernel time of the fallback grows with NN, from 0.10 ms to 1.34 ms.

A step launches 67–75 kernels, and the host waits for the GPU about once per step, when four bytes are copied to the host (lower part of Table S7). When the I(N−1)I(N - 1) calls to EvoGP of a generation are executed alone, a call takes 0.46 ms, which is longer than a complete step of the GPU backend (Table 2 of the main paper). Each of the 655,360 rows of a call carries its own copy of the program in 32 node slots of 8 bytes. This copy takes 256 bytes, whereas the 10 single-precision terminals of the row take 40 bytes.

Comparison with the CPU Backend

Fig. 3(c) of the main paper shows that EvoGP+TensorACO-CL comes closer to the CPU backend as the number of runs per generation increases. Its time grows slowly with the number of runs, whereas that of the CPU backend grows roughly linearly. Its throughput reaches that of the CPU backend at about 2,048 runs per generation. However, the GPU backend is still at least 8.8 times faster than EvoGP+TensorACO-CL at all points of Fig. 3 (Table S8).

Additional Results of BlockEval

This section supports the answers to RQ2 and RQ3 in Sections 5.1, 5.3 and 6 of the main paper.

Paired Time Ratios

Table S8 gives the evaluation time per generation of each method divided by that of the GPU backend, paired by run. The times of AS are those in Table 1 of the main paper, and those of ACS and MMAS are plotted in Fig. 3(a). For all three variants, the speedup of the GPU backend over the CPU backend is highest at N=100N = 100 and decreases as NN increases further. ACS has the lowest speedup at all five problem sizes, because its local update synchronises the whole thread block in every step (Section 6.2 of the main paper). The last row gives the ranges over all configurations of Fig. 3. Over the 111 configurations, the GPU backend is 1.70–18.0 times faster than the CPU backend, and at the 23 points of the grey line, it is 8.8–55.6 times faster than EvoGP+TensorACO-CL.

Ablation Study: All Variants

Table S9 lists all variants of the ablation study, of which Table 3 of the main paper shows six. Each variant changes one design choice of the GPU backend on TSP500 under the default configuration of AS. In the first group, the tasks are not all executed at once. When the runs are executed one at a time with one ant per thread block, as in existing GPU implementations of ACO [11, 34], each kernel launch uses only 32 thread blocks of 8 threads. These blocks occupy at most 32 of the 64 SMs of the A5000, and the 1,024 runs of a generation are executed one after another. The GPU backend is 40.0 times faster than this variant. Batches of 256 or 512 tasks take 1.22 and 1.07 times as long as executing all tasks at once, respectively.

In the second group, the ants of a task are spread over several thread blocks. A block executes A′∈{1,4,8,16}A^{\prime} \in\{1, 4, 8, 16\} ants of one task with 8A′8A^{\prime} threads, a task occupies A/A′A/A^{\prime} consecutive blocks, and the arrays in shared memory are allocated for the ants of the block only. The candidate lists, terminals, selection, fallback, pheromone update and random numbers are unchanged, and these variants construct the same tours as the GPU backend at every generation. They still take 1.05–1.70 times as long. The GPU backend asks the compiler to keep three resident blocks per SM, whereas the smaller blocks are compiled without this requirement and use more registers per thread. Fewer ants can then reside on an SM. For example, at most 16 blocks of one ant reside on an SM, against three blocks of 32 ants in the GPU backend, and with one ant per block, three quarters of each warp are empty. This mapping is not available for ACS, whose local update synchronises all ants of a task after every step.

The direct port scans all NN cities in the fallback, computes DistRank by pairwise comparisons and synchronises the whole thread block in every step. Its cost per transition and its fraction of waiting steps are shown in Figure 4 of the main paper. The unrolled scoring loop uses up to 128 registers per thread, against at most 80 in the GPU backend, which reduces the resident tasks per SM from three to two in most generations. With 16 threads per ant group, most threads are idle during the ordinary selection. All variants follow the same computation rules as the GPU backend. These results indicate that the speedup of the GPU backend comes from how the runs are executed rather than from details of the implementation.

Cost of Compiling at Every Generation

The CPU backend compiles one scoring function for each program structure and needs 15.8–18.0 s per generation under the default configuration of AS (Table S10). This is 37.0% of its evaluation time at N=50N = 50 and 2.0% at N=1000N = 1000. If the compilation is excluded from the CPU time only, the GPU backend is still 7.24–11.33 times faster. The compilation time also grows with the number of programs and with the number of copies of each program in the kernel. At P=256P = 256, the direct port with one copy compiles in 4.19 s, the GPU backend with two copies in 10.49 s and the unrolled scoring loop with five copies in 34.97 s.

Results on Other GPUs

Table S11 gives the speed of six other GPUs relative to the A5000 on the same workload, measured by the device time. The speed grows mainly with the number of SMs, on each of which three tasks reside. The A40 and RTX A6000 have 1.3 times as many SMs as the A5000 and are 1.11–1.26 times faster. The L40S and RTX 6000 Ada have 2.2 times as many SMs and are 1.97–2.64 times faster, and the L4, which has fewer SMs, is slower. The L2 cache and the memory bandwidth affect the speed at different problem sizes. At N=100N = 100, the pheromone matrix of a task takes 4N24N^{2} bytes, or 40 KB, and the 48–96 MB L2 cache of the Ada GPUs holds the pheromone of all resident tasks. This is consistent with their largest advantage at N=100N = 100. At N=1000N = 1000, each task needs 4 MB, and the bandwidth has a larger effect. The relative speed of the L4, with 300 GB/s, drops from 0.92 to 0.74, whereas that of the RTX PRO 5000, with 1,344 GB/s, rises from 1.30 to 1.46. The RTX PRO 5000 has the same L2 cache as the L40S and RTX 6000 Ada but is only as fast as the RTX A6000 at N=100N = 100, which suggests that the architecture itself also has an effect.

An Example of a Learned Transition Rule

Figure S2 shows the champion rule with the lowest validation gap among the 10 independent runs on TSP500. Ellipses are function nodes and rounded rectangles are terminals (defined in Table S1). The output zjz_j of the tree modifies the selection weight of the candidate by Eq. (3) of the main paper.

Figure S2. Expression tree of the GP-ACO champion rule with the lowest validation gap (12.324%) among the 10 independent runs on TSP500.

References

  1. [1]Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Transactions on Evolutionary Computation 6(5), 443–462 (2002)DOI
  2. [2]Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton, NJ (2006)
  3. [3]Ayral, H., Albayrak, S.: Parallel and in-process compilation of individuals for genetic programming on GPU. arXiv:1705.07492 (2017)arxiv.org/abs/1705.07492
  4. [4]Burke, E.K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., Qu, R.: Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society 64(12), 1695–1724 (2013)DOI
  5. [5]Cecilia, J.M., García, J.M., Nisbet, A., Amos, M., Ujaldón, M.: Enhancing data parallelism for ant colony optimization on GPUs. Journal of Parallel and Distributed Computing 73(1), 42–51 (2013)DOI
  6. [6]Cecilia, J.M., Llanes, A., Abellán, J.L., Gómez-Luna, J., Chang, L.W., Hwu, W.M.W.: High-throughput ant colony optimization on graphics processing units. Journal of Parallel and Distributed Computing 113, 261–274 (2018)DOI
  7. [7]Chen, M., Feng, C., Cheng, R.: MetaDE: Evolving differential evolution by differential evolution. IEEE Transactions on Evolutionary Computation 30(1), 141–155 (2026)DOI
  8. [8]Chitty, D.M.: Fast parallel genetic programming: Multi-core CPU versus many-core GPU. Soft Computing 16(10), 1795–1814 (2012)DOI
  9. [9]Crary, C., Piard, W., Stitt, G., Hicks, B., Bean, C., Burlacu, B., Banzhaf, W.: Using FPGA devices to accelerate the evaluation phase of tree-based genetic programming: An extended analysis. Genetic Programming and Evolvable Machines 26(1), 8 (2025)DOI
  10. [10]Dawson, L., Stewart, I.A.: Improving ant colony optimization performance on the GPU using CUDA. In: 2013 IEEE Congress on Evolutionary Computation. pp. 1901–1908 (2013)DOI
  11. [11]Delévac, A., Delisle, P., Gravel, M., Kraječki, M.: Parallel ant colony optimization on graphics processing units. Journal of Parallel and Distributed Computing 73(1), 52–61 (2013)
  12. [12]Dorigo, M., Gambardella, L.M.: Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1(1), 53–66 (1997)DOI
  13. [13]Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B 26(1), 29–41 (1996)pubmed.ncbi.nlm.nih.gov/18263004
  14. [14]Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge, MA (2004)
  15. [15]Fung, W.W.L., Sham, I., Yuan, G., Aamodt, T.M.: Dynamic warp formation and scheduling for efficient GPU control flow. In: Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). pp. 407–420 (2007)
  16. [16]Hooker, S.: The hardware lottery. Communications of the ACM 64(12), 58–65 (2021)arxiv.org/abs/2009.06489
  17. [17]Huang, B., Cheng, R., Li, Z., Jin, Y., Tan, K.C.: EvoX: A distributed GPU-accelerated framework for scalable evolutionary computation. IEEE Transactions on Evolutionary Computation 29(5), 1649–1662 (2025)arxiv.org/abs/2301.12457
  18. [18]Ivanov, A., Dryden, N., Ben-Nun, T., Li, S., Hoefler, T.: Data movement is all you need: A case study on optimizing transformers. In: Proceedings of Machine Learning and Systems (MLSys). vol. 3, pp. 711–732 (2021)arxiv.org/abs/2007.00072
  19. [19]Kim, M., Choi, S., Kim, H., Son, J., Park, J., Bengio, Y.: Ant colony sampling with GFlowNets for combinatorial optimization. In: Proceedings of the 28th International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 258, pp. 469–477 (2025)arxiv.org/abs/2403.07041
  20. [20]Laime, S., Karras, T., Aila, T.: Megakernels considered harmful: Wavefront path tracing on GPUs. In: Proceedings of the 5th High-Performance Graphics Conference (HPG). pp. 137–143 (2013)
  21. [21]Lam, S.K., Pitrou, A., Seibert, S.: Numba: A LLVM-based Python JIT compiler. In: Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC (LLVM ’15). pp. 7:1–7:6 (2015)DOI
  22. [22]Lee, V.W., Kim, C., Chhugani, J., Deisher, M., Kim, D., Nguyen, A.D., Satish, N., Smelyanskiy, M., Chennupaty, S., Hammarlund, P., Singhal, R., Dubey, P.: Debunking the 100X GPU vs. CPU myth: An evaluation of throughput computing on CPU and GPU. In: Proceedings of the 37th Annual International Symposium on Computer Architecture (ISCA). pp. 451–460 (2010)
  23. [23]Li, H.T., Pletzer, A., Tian, Y., Mei, Y., Zhang, M.: Accelerated genetic programming hyper-heuristics for simulation-based scheduling via agentic AI. arXiv:2608.19487 (2026)arxiv.org/abs/2608.19487
  24. [24]Liang, Z., Li, H., Yu, N., Sun, K., Cheng, R.: Bridging evolutionary multiobjective optimization and GPU acceleration via tensorization. IEEE Transactions on Evolutionary Computation 30(1), 420–434 (2026)DOI
  25. [25]Lin, B.C., Mei, Y., Zhang, M.: Automated design of state transition rules in ant colony optimization by genetic programming: A comprehensive investigation. Memetic Computing 17(1), 2 (2025)
  26. [26]Ma, J., Pan, W., Li, Y., Yan, J.: ML4CO-Bench-101: Benchmark machine learning for classic combinatorial problems on graphs. In: Advances in Neural Information Processing Systems (NeurIPS), Datasets and Benchmarks Track. vol. 38 (2025)DOI
  27. [27]Mei, Y., Zhang, M.: A comprehensive analysis on reusability of GP-evolved job shop dispatching rules. In: 2016 IEEE Congress on Evolutionary Computation. pp. 3590–3597 (2016)DOI
  28. [28]Nguyen, S., Mei, Y., Zhang, M.: Genetic programming for production scheduling: A survey with a unified framework. Complex & Intelligent Systems 3(1), 41–66 (2017)
  29. [29]NVIDIA Corporation: NVRTC documentation. https://docs.nvidia.com/cuda/nvrtc/ (2026), accessed 2026-10-29
  30. [30]Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M.P., Dupont, E., Ruiz, F.J.R., Ellenberg, J.S., Wang, P., Fawzi, O., Kohli, P., Fawzi, A.: Mathematical discoveries from program search with large language models. Nature 625(7995), 468–475 (2024)
  31. [31]Runka, A.: Evolving an edge selection formula for ant colony optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2009). pp. 1075–1082. ACM (2009)DOI
  32. [32]Salmon, J.K., Moraes, M.A., Dror, R.O., Shaw, D.E.: Parallel random numbers: As easy as 1, 2, 3. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’11). pp. 16:1–16:12 (2011)
  33. [33]Skinderowicz, R.: The GPU-based parallel ant colony system. Journal of Parallel and Distributed Computing 98, 48–60 (2016)DOI
  34. [34]Skinderowicz, R.: Implementing a GPU-based parallel MAX–MIN ant system. Future Generation Computer Systems 106, 277–295 (2020)DOI
  35. [35]Stützle, T., Hoos, H.H.: MAX–MIN ant system. Future Generation Computer Systems 16(8), 889–914 (2000)
  36. [36]Tavares, J., Pereira, F.B.: Evolving strategies for updating pheromone trails: A case study with the TSP. In: Parallel Problem Solving from Nature (PPSN XI). Lecture Notes in Computer Science, vol. 6239, pp. 523–532. Springer (2010)DOI
  37. [37]Voss, M., Asenjo, R., Reinders, J.: Pro TBB: C++ Parallel Programming with Threading Building Blocks. Apress (2019). https://doi.org/10.1007/978-1-4842-4398-5
  38. [38]Wahib, M., Maruyama, N.: Scalable kernel fusion for memory-bound GPU applications. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC). pp. 191–202 (2014)DOI
  39. [39]Wu, Z., Wang, L., Sun, K., Li, Z., Cheng, R.: Enabling population-level parallelism in tree-based genetic programming for GPU acceleration. IEEE Transactions on Evolutionary Computation (2026). https://doi.org/10.1109/TEVC.2026.3663396, Early Access
  40. [40]Wulf, W.A., McKee, S.A.: Hitting the memory wall: Implications of the obvious. ACM SIGARCH Computer Architecture News 23(1), 20–24 (1995)
  41. [41]Yang, L., Jiang, T., Cheng, R.: Tensorized ant colony optimization for GPU acceleration. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO ’24 Companion). pp. 755–758 (2024)arxiv.org/abs/2404.04895
  42. [42]Ye, H., Wang, J., Cao, Z., Berto, F., Hua, C., Kim, H., Park, J., Song, G.: ReEvo: Large language models as hyper-heuristics with reflective evolution. In: Advances in Neural Information Processing Systems. vol. 37 (2024)arxiv.org/abs/2402.01145
  43. [43]Ye, H., Wang, J., Cao, Z., Liang, H., Li, Y.: DeepACO: Neural-enhanced ant systems for combinatorial optimization. In: Advances in Neural Information Processing Systems. vol. 36 (2023)arxiv.org/abs/2309.14032
  44. [44]Yu, X., Gao, J., Zhang, J., Jiang, D., Cheng, R.: AutoPSO: A meta-framework for automated particle swarm optimization. IEEE Transactions on Evolutionary Computation (2026). https://doi.org/10.1109/TEVC.2026.3718908, Early Access
  45. [45]Zhang, F., Mei, Y., Nguyen, S., Zhang, M.: Collaborative multifidelity-based surrogate models for genetic programming in dynamic flexible job shop scheduling. IEEE Transactions on Cybernetics 52(8), 8142–8156 (2022)DOI
  46. [46]Zhang, F., Mei, Y., Nguyen, S., Zhang, M., Tan, K.C.: Surrogate-assisted evolutionary multitask genetic programming for dynamic flexible job shop scheduling. IEEE Transactions on Evolutionary Computation 25(4), 651–665 (2021)DOI
  47. [47]Zhang, F., Nguyen, S., Mei, Y., Zhang, M.: Genetic Programming for Production Scheduling: An Evolutionary Learning Approach. Machine Learning: Foundations, Methodologies, and Applications, Springer, Singapore (2021). https://doi.org/10.1007/978-981-16-4859-5
  48. [48]Zhu, L., Zhang, F., Mei, Y., Zhang, M.: Investigation of the generalisation ability of genetic programming-evolved scheduling rules in dynamic flexible job shop scheduling. arXiv:2601.15717 (2026)arxiv.org/abs/2601.15717

Paper details

vlnc:W_6rd6hmt2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents