Runtime phylogenetic analysis enables extreme subsampling for test-based problems
View at Publisher
| Authors | Alexander Lalejini, Marcos Sanson, Jack Garbus, Matthew Andres Moreno, Emily Dolson |
| Date | February 2nd, 2024 |
| DOI | 10.48550/arXiv.2402.01610 |
| Venue | The Genetic and Evolutionary Computation Conference |
Abstract
A phylogeny describes the evolutionary history of an evolving population. Evolutionary search algorithms can perfectly track the ancestry of candidate solutions, illuminating a population’s trajectory through the search space. However, phylogenetic analyses are typically limited to post-hoc studies of search performance. We introduce phylogeny-informed subsampling, a new class of subsampling methods that exploit runtime phylogenetic analyses for solving test-based problems. Specifically, we assess two phylogeny-informed subsampling methods – individualized random subsampling and ancestor-based subsampling – on three diagnostic problems and ten genetic programming (GP) problems from program synthesis benchmark suites. Overall, we found that phylogeny-informed subsampling methods enable problem-solving success at extreme subsampling levels where other subsampling methods fail. For example, phylogeny-informed subsampling methods more reliably solved program synthesis problems when evaluating just one training case per-individual, per-generation. However, at moderate subsampling levels, phylogeny-informed subsampling generally performed no better than random subsampling on GP problems. Our diagnostic experiments show that phylogeny-informed subsampling improves diversity maintenance relative to random subsampling, but its effects on a selection scheme’s capacity to rapidly exploit fitness gradients varied by selection scheme. Continued refinements of phylogeny-informed subsampling techniques offer a promising new direction for scaling up evolutionary systems to handle problems with many expensive-to-evaluate fitness criteria.
BibTeX
@misc{lalejini2024runtime,
doi = {10.48550/arXiv.2402.01610},
url = {https://arxiv.org/abs/2402.01610},
title={Runtime phylogenetic analysis enables extreme subsampling for test-based problems},
author={Alexander Lalejini and Marcos Sanson and Jack Garbus and Matthew Andres Moreno and Emily Dolson},
year={2024},
publisher= {Association for Computing Machinery},
address = {New York, NY, USA},
booktitle= {Proceedings of the Genetic and Evolutionary Computation Conference},
numpages = {4},
location = {Melbourne, VIC, Australia},
series = {GECCO '24}
}
Citation
Alexander Lalejini, Marcos Sanson, Jack Garbus, Matthew Andres Moreno, and Emily Dolson. 2024. Runtime phylogenetic analysis enables extreme subsampling for test-based problems. In Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO ‘24). Association for Computing Machinery, New York, NY, USA. https://doi.org/10.48550/arXiv.2402.01610