Back to Search
Start Over
Non-existence of linear universal drift functions
- Source :
- Theoretical Computer Science, Theoretical Computer Science, Elsevier, 2012, 436, pp.71-86. ⟨10.1016/j.tcs.2012.01.048⟩
- Publication Year :
- 2012
- Publisher :
- Elsevier BV, 2012.
-
Abstract
- 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$.<br />Comment: 19 pages; This work contains parts of the GECCO 2010 and CEC 2010 papers of the same authors
- Subjects :
- FOS: Computer and information sciences
General Computer Science
F.2
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Evolutionary algorithm
Evolutionary computation
0102 computer and information sciences
02 engineering and technology
[INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE]
Mathematical proof
01 natural sciences
Upper and lower bounds
Theoretical Computer Science
Combinatorics
Bio-inspired computation
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Applied mathematics
Neural and Evolutionary Computing (cs.NE)
ComputingMilieux_MISCELLANEOUS
Mathematics
Linear function (calculus)
Probability (math.PR)
Computer Science - Neural and Evolutionary Computing
Function (mathematics)
010201 computation theory & mathematics
020201 artificial intelligence & image processing
Runtime analysis
Heuristics
Mathematics - Probability
Evolutionary programming
Computer Science(all)
Subjects
Details
- ISSN :
- 03043975 and 18792294
- Volume :
- 436
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....fbd7acdc939c89e63b657eabdbc1dca4