SCIENCE@home

Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets

Benjamin Doerr,Daniel Johannsen,Martin Schmidt

Published 2011 in Foundations of Genetic Algorithms

ABSTRACT

In this work, we investigate a (1+1) Evolutionary Algorithm for optimizing functions over the space {0,...,<i>r</i>} <sup><i>n</i></sup>, where <i>r</i> is a positive integer. We show that for linear functions over {0,1,2}<sup><i>n</i></sup>, the expected runtime time of this algorithm is O(<i>n</i> log <i>n</i>). This result generalizes an existing result on pseudo-Boolean functions and is derived using drift analysis. We also show that for large values of <i>r</i>, no upper bound for the runtime of the (1+1) Evolutionary Algorithm for linear function on {0,...,<i>r</i>}<sup><i>n</i></sup> can be obtained with this approach nor with any other approach based on drift analysis with weight-independent linear potential functions.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-19 of 19 references · Page 1 of 1

CITED BY

Showing 1-17 of 17 citing papers · Page 1 of 1