TY - GEN
T1 - Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets
AU - Doerr, Benjamin
AU - Johannsen, Daniel
AU - Schmidt, Martin
PY - 2011/5/20
Y1 - 2011/5/20
N2 - In this work, we investigate a (1+1) Evolutionary Algorithm for optimizing functions over the space {0,...,r}n, where r is a positive integer. We show that for linear functions over {0, 1, 2}n, the expected runtime time of this algorithm is O(n log n). This result generalizes an existing result on pseudo-Boolean functions and is derived using drift analysis. We also show that for large values of r, no upper bound for the runtime of the (1+1) Evolutionary Algorithm for linear function on {0,...,r}n can be obtained with this approach nor with any other approach based on drift analysis with weight-independent linear potential functions.
AB - In this work, we investigate a (1+1) Evolutionary Algorithm for optimizing functions over the space {0,...,r}n, where r is a positive integer. We show that for linear functions over {0, 1, 2}n, the expected runtime time of this algorithm is O(n log n). This result generalizes an existing result on pseudo-Boolean functions and is derived using drift analysis. We also show that for large values of r, no upper bound for the runtime of the (1+1) Evolutionary Algorithm for linear function on {0,...,r}n can be obtained with this approach nor with any other approach based on drift analysis with weight-independent linear potential functions.
KW - Drift analysis
KW - Evolutionary algorithm
KW - Runtime analysis
U2 - 10.1145/1967654.1967665
DO - 10.1145/1967654.1967665
M3 - Conference contribution
AN - SCOPUS:79956031033
SN - 9781450306331
T3 - FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI
SP - 119
EP - 126
BT - FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI
T2 - 11th Foundations of Genetic Algorithms Workshop, FOGA XI
Y2 - 5 January 2011 through 9 January 2011
ER -