Population Diversity Leads to Short Running Times of Lexicase Selection
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.
Code (0)
등록된 구현이 없습니다.
Tasks
DiversityProgram SynthesisSimilar Papers 제목 키워드 기반
Average Drift Analysis and Population Scalability
This paper aims to study how the population size affects the computation time of evolutionary algorithms in a rigorous way. The computation time of an evolutionary algorithm can be measured by either the expected number …
Evolutionary AlgorithmsHow Population Diversity Influences the Efficiency of Crossover
Our theoretical understanding of crossover is limited by our ability to analyze how population diversity evolves. In this study, we provide one of the first rigorous analyses of population diversity and optimization time…
DiversityWas Tournament Selection All We Ever Needed? A Critical Reflection on Lexicase Selection
The success of lexicase selection has led to various extensions, including its combination with down-sampling, which further increased performance. However, recent work found that down-sampling also leads to significant …
AllSymbolic RegressionEscaping Local Optima using Crossover with Emergent or Reinforced Diversity
Population diversity is essential for avoiding premature convergence in Genetic Algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. W…
DiversityA Decomposition-Based Many-Objective Evolutionary Algorithm with Local Iterative Update
Existing studies have shown that the conventional multi-objective evolutionary algorithms (MOEAs) based on decomposition may lose the population diversity when solving some many-objective optimization problems. In this p…
DiversityEvolutionary Algorithms