Non-Existence of Linear Universal Drift Functions

Details Non-Existence of Linear Universal Drift Functions Non-Existence of Linear Universal Drift Functions

2010-11-15

arxiv.org/abs/1011.3466v1

Computer Science

Neural and Evolutionary Computing

19 pages; This work contains parts of the GECCO 2010 and CEC 2010 papers of the same authors

Scientific paper

Drift analysis has become a powerful tool to prove bounds on the runtime of randomized search heuristics. It allows, for example, fairly simple proofs for the classical problem how the (1+1) Evolutionary Algorithm (EA) optimizes an arbitrary pseudo-Boolean linear function. The key idea of drift analysis is to measure the progress via another pseudo-Boolean function (called drift function) and use deeper results from probability theory to derive from this a good bound for the runtime of the EA. Surprisingly, all these results manage to use the same drift function for all linear objective functions. In this work, we show that such universal drift functions only exist if the mutation probability is close to the standard value of $1/n$.

Affiliated with

Also associated with

No associations

Rating

Non-Existence of Linear Universal Drift Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Non-Existence of Linear Universal Drift Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-Existence of Linear Universal Drift Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-299521