Abstract
Genetic Programming (GP) often faces a trade-off between the high solution quality and population diversity of Lexicase selection and the computational efficiency of traditional tournament selection. This paper introduces Batch Tournament Selection (BTS) and its shuffled variant (BTSS), which group test cases into batches to maintain specialist-friendly selection pressure at significantly reduced computational costs. Experimental results on eight regression benchmarks demonstrate that BTS achieves up to a 25x speedup over state-of-the-art Lexicase methods while maintaining competitive or superior accuracy.
Introduction
In Genetic Programming, the selection process is vital for evolving effective computer programs. Traditional Tournament Selection averages performance across all test cases, which often favors "generalist" programs and loses "specialists" that excel at specific, difficult parts of a problem. Lexicase Selection addresses this by considering test cases individually, preserving diversity but at a high computational cost ($O(N^2 \times T)$ complexity). As datasets scale, Lexicase becomes a significant bottleneck. This research proposes Batch Tournament Selection (BTS) to provide the benefits of Lexicase with the speed of traditional tournament methods.
Methods
The proposed methods, Batch Tournament Selection (BTS) and Shuffled Batch Tournament Selection (BTSS), find a middle ground by partitioning training data into small groups.
- Batching: Training data is divided into batches of a specified size.
- BTS (Ordered): Test cases are ordered by difficulty, with the most challenging cases in the first batch.
- BTSS (Shuffled): Test cases are randomly shuffled before batching.
- Selection Loop: A standard tournament is held for each batch. Randomly selected individuals are compared based on their average performance on that specific batch, and the winner is chosen as a parent.
By adjusting the batch size, the algorithm can transition between the behavior of Lexicase (batch size of 1) and traditional tournament selection (all cases in one batch).
Experimental Setup
The methods were evaluated on eight standard symbolic regression benchmarks, including physical engineering datasets (Airfoil, Concrete, Yacht), energy loads, and real-world social data (TowerData, Wine quality). These datasets range from 5 to 25 features and up to 4,000 training instances, providing a diverse testing environment for both accuracy and computational efficiency.
Results and Discussion
The primary advantage of BTS is its computational efficiency. By utilizing the logic of tournament selection, BTS achieves a lower complexity ($O(N \times T)$) and is easily parallelizable. In empirical tests, BTS and BTSS provided up to a 25x speedup in total execution time compared to Adaptive $\epsilon$-Lexicase (Ae-Lex).
In terms of accuracy, BTS variants proved highly competitive. On the towerData dataset, several BTS configurations outperformed the Lexicase baseline. On other datasets, such as airfoil, the performance was statistically tied, demonstrating that the speedup does not come at the cost of solution quality.
The study also revealed that batches act as "niches," encouraging programs to specialize in different subsets of the problem space. This "phenotypic" diversity was found to be nearly identical to that of Lexicase, suggesting that the core benefit of Lexicase is the multi-objectivization of the problem rather than the specific ordering of individual cases.
Conclusion
Batch Tournament Selection offers a scalable alternative to Lexicase selection for Genetic Programming. It maintains high population diversity and competitive accuracy while delivering massive speedups. Future research will explore the impact of BTS on structural diversity (code bloat) and investigate automated methods for determining optimal batch sizes for new problem domains.
Summary updated