TY - GEN
T1 - Adaptive drift analysis
AU - Doerr, Benjamin
AU - Goldberg, Leslie Ann
PY - 2010/11/12
Y1 - 2010/11/12
N2 - We show that the (1+1) evolutionary algorithm using an arbitrary mutation rate p = c/n, c a constant, finds the optimum of any n-bit pseudo-Boolean linear function f in expected time Θ(n log n). Since previous work shows that universal drift functions cannot exist for c larger than a certain constant, we define drift functions depending on p and f. This seems to be the first time in the theory of evolutionary algorithms that drift functions are used that take into account the particular problem instance.
AB - We show that the (1+1) evolutionary algorithm using an arbitrary mutation rate p = c/n, c a constant, finds the optimum of any n-bit pseudo-Boolean linear function f in expected time Θ(n log n). Since previous work shows that universal drift functions cannot exist for c larger than a certain constant, we define drift functions depending on p and f. This seems to be the first time in the theory of evolutionary algorithms that drift functions are used that take into account the particular problem instance.
UR - https://www.scopus.com/pages/publications/78149238060
U2 - 10.1007/978-3-642-15844-5_4
DO - 10.1007/978-3-642-15844-5_4
M3 - Conference contribution
AN - SCOPUS:78149238060
SN - 3642158439
SN - 9783642158438
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 32
EP - 41
BT - Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings
T2 - 11th International Conference on Parallel Problem Solving from Nature, PPSN 2010
Y2 - 11 September 2010 through 15 September 2010
ER -