2016/08/10 by Duc-Cuong Dang, Tobias Friedrich, Dang, Duc-Cuong +13
Biochemistry, Genetics and Molecular Biology · Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #FOS: Biological sciences #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #Populations and Evolution (q-bio.PE) #cs.CC #cs.NE #q-bio.PE
paper · pdf · doi:10.48550/arxiv.1608.03123
arxiv created 2016/08/10 · openalex publication_date 2016/08/10 · arxiv updated 2016/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for the (μ+1) GA and the Jumpk test function. We show that the interplay of crossover and mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to improvements of the expected optimisation time of order Ω(n/log n) compared to mutation-only algorithms like (1+1) EA. Moreover, increasing the mutation rate by an arbitrarily small constant factor can facilitate the generation of diversity, leading to speedups of order Ω(n). We also compare seven commonly used diversity mechanisms and evaluate their impact on runtime bounds for the (μ+1) GA. All previous results in this context only hold for unrealistically low crossover probability pc=O(k/n), while we give analyses for the setting of constant pc < 1 in all but one case. For the typical case of constant k > 2 and constant pc, we can compare the resulting expected runtimes for different diversity mechanisms assuming an optimal choice of μ: O(nk-1) for duplicate elimination/minim., O(n2log n) for maximising the convex hull, O(nlog n) for deterministic crowding (assuming pc = k/n), O(nlog n) for maximising Hamming distance, O(nlog n) for fitness sharing, O(nlog n) for single-receiver island model. This proves a sizeable advantage of all variants of the (μ+1) GA compared to (1+1) EA, which requires time Θ(nk). Experiments complement our theoretical findings and further highlight the benefits of crossover and diversity on Jumpk.