Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving
Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving
复制标题
知情的下采样 Lexicase 选择：识别有效的培训案例以高效解决问题
DOI：
10.48550/arxiv.2301.01488
复制
发表时间：
2023
影响因子：
6.8
通讯作者：
L. Spector
中科院分区：
文献类型：
--
作者：
Ryan Boldi;Martin Briesch;Dominik Sobania;Alexander Lalejini;Thomas Helmuth;Franz Rothlauf;Charles Ofria;L. Spector
遗传编程(GP)通常使用大的训练集，并要求在选择过程中对所有训练案例的所有个体进行评估。随机下采样词典词库选择仅在训练案例的随机子集上评估个体，从而允许使用相同数量的程序执行来探索更多个体。然而，随机抽样可以从下样本中排除几代人中的重要案例，而衡量相同行为的案例(同义案例)可能会被过度使用。在这项工作中，我们介绍了知情下采样词典选择。这种方法利用人口统计来建立下样本，这些样本包含更多不同的培训案例，因此信息丰富。通过对两个不同的GP系统(PushGP和语法制导的GP)的实证研究，我们发现在一组当代程序综合基准问题上，知情下采样的性能显著优于随机下采样。通过对创建的下样本的分析，我们发现重要的训练案例被一致地包括在独立进化运行和系统中的下样本中。我们假设，这种改进可以归因于知情下采样词典选择在进化过程中保持更多专业个体的能力，同时仍然受益于每次评估成本的降低。
Genetic Programming (GP) often uses large training sets and requires all individuals to be evaluated on all training cases during selection. Random down-sampled lexicase selection evaluates individuals on only a random subset of the training cases allowing for more individuals to be explored with the same amount of program executions. However, sampling randomly can exclude important cases from the down-sample for a number of generations, while cases that measure the same behavior (synonymous cases) may be overused. In this work, we introduce Informed Down-Sampled Lexicase Selection. This method leverages population statistics to build down-samples that contain more distinct and therefore informative training cases. Through an empirical investigation across two different GP systems (PushGP and Grammar-Guided GP), we find that informed down-sampling significantly outperforms random down-sampling on a set of contemporary program synthesis benchmark problems. Through an analysis of the created down-samples, we find that important training cases are included in the down-sample consistently across independent evolutionary runs and systems. We hypothesize that this improvement can be attributed to the ability of Informed Down-Sampled Lexicase Selection to maintain more specialist individuals over the course of evolution, while still benefiting from reduced per-evaluation costs.
登录
查看更多内容
随机子采样提高了词典选择的性能
DOI：
10.1145/3319619.3326900
发表时间：
2019
期刊：
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference
影响因子：
--
作者：
Hernandez, Jose Guadalupe;Lalejini, Alexander;Dolson, Emily;Ofria, Charles
通讯作者：
Ofria, Charles
影响因子：
7.7
作者：
Lalejini A;Dolson E;Vostinar AE;Zaman L
通讯作者：
Zaman L
下采样解决问题的好处因选择方案而异
DOI：
10.1145/3583133.3590713
发表时间：
2023
期刊：
GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation
影响因子：
--
作者：
Boldi, Ryan;Bao, Ashley;Briesch, Martin;Helmuth, Thomas;Sobania, Dominik;Spector, Lee;Lalejini, Alexander
通讯作者：
Lalejini, Alexander
知情下样本的静态分析
DOI：
10.1145/3583133.3590751
发表时间：
2023
期刊：
Genetic and Evolutionary Computation Conference Companion
影响因子：
--
作者：
Boldi, Ryan;Lalejini, Alexander;Helmuth, Thomas;Spector, Lee
通讯作者：
Spector, Lee