Money for nothing: Speeding up evolutionary algorithms through better initialization

That the initialization can have a significant impact on the performance of evolutionary algorithms (EAs) is a well known fact in the empirical evolutionary computation literature. Surprisingly, it has nevertheless received only little attention from the theoretical community. We bridge this gap by providing a thorough runtime analysis for a simple iterated random sampling initialization. In the latter, instead of starting an EA with a random sample, it is started in the best of k search points that are taken from the search space uniformly at random. Implementing this strategy comes at almost no cost, neither in the actual coding work nor in terms of wall-clock time. Taking the best of two random samples already decreases the (n log n) expected runtime of the (1+1) EA and Randomized Local Search on OneMax by an additive term of order √n. The optimal gain that one can achieve with iterated random sampling is an additive term of order √ n log n. This also determines the best possible mutation-based EA for OneMax, a question left open in.