Article ID: | iaor20162553 |
Volume: | 75 |
Issue: | 3 |
Start Page Number: | 529 |
End Page Number: | 553 |
Publication Date: | Jul 2016 |
Journal: | Algorithmica |
Authors: | Doerr Benjamin, Doerr Carola |
Keywords: | optimization, heuristics |
Analyzing the runtime of a Randomized Search Heuristic (RSH) by theoretical means often turns out to be rather tricky even for simple optimization problems. The main reason lies in the randomized nature of these algorithms. Both the optimization routines and the initialization of RSHs are typically based on random samples. It has often been observed, though, that the expected runtime of RSHs does not deviate much from the expected runtime when starting in an initial solution of average fitness. Having this information a priori could greatly simplify runtime analyses, as it reduces the necessity of analyzing the influence of the random initialization. Most runtime bounds in the literature, however, do not profit from this observation and are either too pessimistic or require a rather complex proof. In this work we show for the two search heuristics