Abstract | ||
---|---|---|
We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log10 n between exponential and polynomial running times on OneMax. For any smaller value, the (1,λ) EA needs exponential time on every function that has only one global optimum. We also consider arbitrary unimodal functions and show that the threshold can shift towards larger offspring population sizes. Finally, we investigate the relationship between the offspring population size and arbitrary mutation rates on OneMax. We get sharp thresholds for λ that decrease with the mutation rate. This illustrates the balance between selection and mutation. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1145/2330163.2330350 | GECCO |
Keywords | Field | DocType |
larger offspring population size,log10 n,arbitrary unimodal function,mutation rate,non-elitist evolutionary algorithm,smaller value,exponential time,offspring population size,arbitrary mutation rate,sharp threshold,population size,theory,evolutionary algorithms,evolutionary algorithm | Population,Mathematical optimization,Combinatorics,Exponential function,Evolutionary algorithm,Polynomial,Mutation rate,Computer science,Global optimum,Offspring,Population size,Statistics | Conference |
Citations | PageRank | References |
17 | 0.91 | 9 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jonathan E. Rowe | 1 | 458 | 56.35 |
Dirk Sudholt | 2 | 1063 | 64.62 |