When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument
share
Hillclimbing is an essential part of any optimization algorithm. An important benchmark for hillclimbing algorithms on pseudo-Boolean functions f: {0,1}^n →R are (strictly) montone functions, on which a surprising number of hillclimbers fail to be efficient. For example, the (1+1)-Evolutionary Algorithm is a standard hillclimber which flips each bit independently with probability c/n in each round. Perhaps surprisingly, this algorithm shows a phase transition: it optimizes any monotone pseudo-boolean function in quasilinear time if c<1, but there are monotone functions for which the algorithm needs exponential time if c>2.2. But so far it was unclear whether the threshold is at c=1. In this paper we show how Moser's entropy compression argument can be adapted to this situation, that is, we show that a long runtime would allow us to encode the random steps of the algorithm with less bits than their entropy. Thus there exists a c_0 > 1 such that for all 0<c< c_0 the (1+1)-Evolutionary Algorithm with rate c/n finds the optimum in O(n ^2 n) steps in expectation.
READ FULL TEXT