Analysis of the (1+1) EA for a dynamically changing ONEMAX-variant

Although evolutionary algorithms (EAs) are often successfully used for dynamically changing problems, there are only few theoretical results about EAs for dynamic objective functions. Here, the runtime of the (1+1) EA is theoretically analyzed for a dynamic variant of ONEMAX. The main focus lies on determining the degree of change of the fitness function, where the expected runtime of the (1+1) EA rises from polynomial to super-polynomial. The proofs presented show methods of how to rigorously analyze EAs on dynamically changing objective functions