2022/04/13 by Helmuth, Thomas, Lengler, Johannes, La Cava, William
#FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE)
paper · doi:10.48550/arxiv.2204.06461
In this paper we investigate why the running time of lexicase parent selection is empirically much lower than its worst-case bound of O(N*C). We define a measure of population diversity and prove that high diversity leads to low running times O(N + C) of lexicase selection. We then show empirically that genetic programming populations evolved under lexicase selection are diverse for several program synthesis problems, and explore the resulting differences in running time bounds.