Random subsampling improves performance in lexicase selection
Random subsampling improves performance in lexicase selection
复制标题
随机子采样提高了词典选择的性能
DOI：
10.1145/3319619.3326900
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Ofria, Charles
中科院分区：
文献类型：
--
作者：
Hernandez, Jose Guadalupe;Lalejini, Alexander;Dolson, Emily;Ofria, Charles
Lexicase选择已被证明非常成功地为遗传规划中的问题找到有效的解决方案，特别是对于基于测试的问题，其中有许多不同的测试用例必须全部通过。然而，lexicase（与大多数选择方案一样）要求针对每一代的大多数测试用例评估所有可能的解决方案，这在计算上可能是昂贵的。在这里，我们建议通过应用随机子抽样来减少每代评估所需的数量：使用每代测试用例的子集（下降抽样），或者通过将测试用例分配给总体的子组（队列分配）。每一代测试都是随机重新分配的，候选解决方案只在它们被分配的测试用例上进行评估，在确保每个沿袭最终遇到所有测试用例的同时，从根本上减少了所需评估的总数。我们在五个不同的程序合成问题上测试了这些lexicase变体，跨越了一系列下采样水平和队列大小。我们证明，这些简单的技术可以减少lexicase中每代评估的数量，从而大大提高等效计算工作量的整体性能。
Lexicase selection has been proven highly successful for finding effective solutions to problems in genetic programming, especially for test-based problems where there are many distinct test cases that must all be passed. However, lexicase (as with most selection schemes) requires all prospective solutions to be evaluated against most test cases each generation, which can be computationally expensive. Here, we propose reducing the number of per-generation evaluations required by applying random subsampling: using a subset of test cases each generation (down-sampling) or by assigning test cases to subgroups of the population (cohort assignment). Tests are randomly reassigned each generation, and candidate solutions are only ever evaluated on test cases that they are assigned to, radically reducing the total number of evaluations needed while ensuring that each lineage eventually encounters all test cases. We tested these lexicase variants on five different program synthesis problems, across a range of down-sampling levels and cohort sizes. We demonstrate that these simple techniques to reduce the number of per-generation evaluations in lexicase can substantially improve overall performance for equivalent computational effort.
登录
查看更多内容
大数据集中遗传编程学习者的抽样方法：比较研究
DOI：
--
发表时间：
2016
期刊：
INNS Conference on Big Data
影响因子：
--
作者：
Hmida Hmida;S. B. Hamida;A. Borgi;M. Rukoz
通讯作者：
M. Rukoz
通过遗传编程中词汇选择的差异性能评估问题模态：初步报告
影响因子：
3.9
作者：
L. Spector
通讯作者：
L. Spector
遗传规划的适应度案例抽样方法的比较
DOI：
--
发表时间：
2017
期刊：
Journal of experimental and theoretical artificial intelligence (Print)
影响因子：
--
作者：
Yuliana Martínez;Enrique Naredo;L. Trujillo;P. Legrand;Uriel López
通讯作者：
Uriel López
理解和完善遗传编程的通用程序综合基准套件
DOI：
10.1109/cec.2018.8477953
发表时间：
2018
期刊：
2018 IEEE Congress on Evolutionary Computation (CEC)
影响因子：
--
作者：
Stefan Forstenlechner;David Fagan;Miguel Nicolau;M. O’Neill
通讯作者：
M. O’Neill