Exponential upper bounds for the runtime of randomized search heuristics

摘要: Abstract We argue that proven exponential upper bounds on runtimes, an established area in classic algorithms, are interesting also heuristic search and we prove several such results. show any of the algorithms randomized local search, Metropolis algorithm, simulated annealing, (1+1) evolutionary algorithm can optimize pseudo-Boolean weakly monotonic function under a large set noise assumptions runtime is at most problem dimension n. This drastically extends previous result, limited to EA, LeadingOnes function, one-bit or bit-wise prior with probability 1/2, same time simplifies its proof. With general argument, among others, derive sub-exponential bound for ( 1 , λ ) OneMax when offspring population size logarithmic, but below efficiency threshold. To our approach deal non-trivial parent sizes, mutation-based version simple genetic benchmark, matching known lower bound.