Unknown solution length problems with no asymptotically optimal run time
Benjamin Doerr, Carola Doerr, Timo Kötzing · Proceedings of the Genetic and Evolutionary Computation Conference · 2017
We revisit the problem of optimizing a fitness function of unknown dimension; that is, we face a function defined over bit-strings of large length N, but only n ≪ N of them have an influence on the fitness. Neither the position of these relevant bits nor their number is known. In previous work, variants of the (1 + 1) evolutionary algorithm (EA) have been developed that solve, for arbitrary s ∈ ℕ, such OneMax and LeadingOnes instances, simultaneously for all n ∈ ℕ, in expected time O(n(log(n))2 log log(n) ... log(s−1)(n)(log(s)(n))1+ε) and O(n2 log(n) log log(n) ... log(s−1)(n)(log(s)(n))1+ε), respectively; that is, in almost the same time as if n and the relevant bit positions were known.