On averaging the best samples in evolutionary computation

2020/04/24 by Meunier, Laurent, Chevaleyre, Yann, Rapin, Jeremy +2
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Neural and Evolutionary Computing (cs.NE)

paper · doi:10.48550/arxiv.2004.11685

Abstract

Choosing the right selection rate is a long standing issue in evolutionary computation. In the continuous unconstrained case, we prove mathematically that a single parent μ=1 leads to a sub-optimal simple regret in the case of the sphere function. We provide a theoretically-based selection rate μ/λ that leads to better progress rates. With our choice of selection rate, we get a provable regret of order O(λ^-1) which has to be compared with O(λ^-2/d) in the case where μ=1. We complete our study with experiments to confirm our theoretical claims.

Related

• On Steady-State Evolutionary Algorithms and Selective Pressure: Why Inverse Rank-Based Allocation of Reproductive Trials is Best
• The quasispecies regime for the simple genetic algorithm with ranking selection
• Tournament versus Fitness Uniform Selection
• A geometric speed limit for acceleration by natural selection in evolutionary processes
• On the Impact of Mutation-Selection Balance on the Runtime of Evolutionary Algorithms