Skip to main content
SpringerLink
Log in

The Impact of Random Initialization on the Runtime of Randomized Search Heuristics

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

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 Randomized Local Search (RLS) and the (1+1) Evolutionary Algorithm on the two well-studied problems OneMax and LeadingOnes that their expected runtimes indeed deviate by at most a small additive constant from the expected runtime when started in a solution of average fitness. For RLS on OneMax, this additive discrepancy is \(-1/2 \pm o(1)\), leading to the first runtime statement for this problem that is precise apart from additive o(1) terms: The expected number of iterations until an optimal search point is found, is \(n H_{n/2} - 1/2 \pm o(1)\), where \(H_{n/2}\) denotes the (n / 2)th harmonic number when n is even, and \(H_{n/2}:= (H_{\lfloor n/2 \rfloor } + H_{\lceil n/2 \rceil })/2\) when n is odd. For this analysis and the one of the (1+1) EA optimizing OneMax we use a coupling technique, which we believe to be interesting also for the study of more complex optimization problems. For the analyses of the LeadingOnes test function, we show that one can express the discrepancy solely via the waiting times for leaving fitness level 0 and 1, which then easily yields the discrepancy, and in particular, without having to deal with so-called free-riders.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

Notes

  1. Since there is some ambiguity with respect to the term “average fitness”, we provide the following formal definition. Let \(f:S\rightarrow {\mathbb {R}}\) for some finite, non-empty search space S. We call \(a:=\sum _{s\in S}{f(s)}/|S|\) the average fitness of f. A search point s with \(f(s)=a\) is thus said to be a search point of average fitness. When we say that we regard a random search point of average fitness, we implicitly mean to take a uniformly random search point from the set \(A:=\{s \mid f(s)=a\}\) of all search points with average fitness. In many cases, A is empty, e.g., if the function values are all integer, but the average fitness is not. We therefore need to regard, in our formal definition, the two fitness levels \(a_{-}:=\min \{f(s) \mid s \in S, f(s)\le a\}\) and \(a_{+}:=\min \{f(s) \mid s \in S, f(s) \ge a\}\) of the largest fitness value smaller or equal to a and the smallest fitness value larger or equal to a, respectively. Let \(A_{-}\) and \(A_{+}\) be the respective sets of search points of fitness \(a_{-}\) and \(a_{+}\). A random search point of average fitness is a search point taken uniformly at random from the union \(A_{-} \cup A_{+}\). Note that for OneMax and even n, by Remark 2 and Lemma 1, our claims remain true if, instead of taking a random search point of average fitness, we take an arbitrary search point of fitness n / 2 as initial solution.

  2. Note that Eq. (1) also holds for our extension of the definition of the harmonic numbers to half-integral numbers. By our definition, \(H_{n + \frac{1}{2}}:=(H_n+H_{n+1})/2 = H_n + \frac{1}{2} \cdot \frac{1}{n+1}\) and a routine calculation shows that this is \(\ln (n+\frac{1}{2}) + \gamma + \frac{1}{2(n+\frac{1}{2})} \pm \varTheta ((n+\frac{1}{2})^{-2})\).

  3. In the proof of Theorem 1 we had shown that for RLS the corresponding difference is roughly \(4k^2/n\). The bound for the \((1 + 1)\) EA is thus slightly weaker than that for RLS in that we do not compute the constant terms.

References

  1. Borisovsky, P.A., Eremeev, A.V.: Comparing evolutionary algorithms to the (1+1)-EA. Theor. Comput. Sci. 403, 33–41 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  2. Böttcher, S., Doerr, B., Neumann, F.: Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In: Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN’10), pp. 1–10. Springer (2010)

  3. Doerr, B.: Analyzing randomized search heuristics: tools from probability theory. In: Auger, A., Doerr, B. (eds.) Theory of Randomized Search Heuristics, pp. 1–20. World Scientific Publishing, New York (2011)

    Chapter  Google Scholar 

  4. Doerr, B., Doerr, C.: The impact of random initialization on the runtime of randomized search heuristics. In: Proceedings of the 16th Annual Genetic and Evolutionary Computation Conference (GECCO’14), pp. 1375–1382. ACM (2014)

  5. Doerr, B., Doerr, C., Ebel, F.: Lessons from the black-box: Fast crossover-based genetic algorithms. In: Proceedings of the 15th Annual Genetic and Evolutionary Computation Conference (GECCO’13), pp. 781–788. ACM (2013)

  6. Doerr, B., Fouz, M., Witt, C.: Quasirandom evolutionary algorithms. In: Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference (GECCO’10), pp. 1457–1464. ACM (2010)

  7. Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673–697 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  8. Doerr, B., Künnemann, M.: How the (1+\(\lambda \)) evolutionary algorithm optimizes linear functions. In: Proceedings of the 15th Annual Genetic and Evolutionary Computation Conference (GECCO’13), pp. 1589–1596. ACM (2013)

  9. Droste, S., Jansen, T., Wegener, I.: A rigorous complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with Boolean inputs. Evol. Comput. 6, 185–196 (1998)

    Article  Google Scholar 

  10. Goldman, B.W., Punch, W.F.: Parameter-less population pyramid. In: Proceedings of the 2014 Conference on Genetic and Evolutionary Computation (GECCO’14), pp. 785–792. ACM (2014)

  11. He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artifi. Intell. 127, 57–85 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  12. Hwang, H., Panholzer, A., Rolin, N., Tsai, T., Chen, W.: Probabilistic analysis of the (1+1)-evolutionary algorithm. CoRR, abs/1409.4955 (2014)

  13. Ladret, V.: Asymptotic hitting time for a simple evolutionary model of protein folding. J. Appl. Prob. 42, 39–51 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica 64, 623–642 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. Lindvall, T.: Lectures on the Coupling Method. John Wiley, New York (1992)

    MATH  Google Scholar 

  16. Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)

  17. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)

  18. Oliveto, P.S., Yao, X.: Runtime analysis of evolutionary algorithms for discrete optimization. In: Auger, A., Doerr, B. (eds.) Theory of Randomized Search Heuristics, pp. 21–52. World Scientific Publishing, New York (2011)

    Chapter  Google Scholar 

  19. Qian, C., Yu, Y., Zhou, Z.-H.: On algorithm-dependent boundary case identification for problem classes. In: Proceedings of the 12th International Conference on Parallel Problem Solving from Nature (PPSN’12), vol. 7491 of LNCS, pp. 62–71. Springer (2012)

  20. Sedgewick, R.: The analysis of quicksort programs. Acta Inform. 7, 327–355 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  21. Spivey, M.Z.: Combinatorial sums and finite differences. Discret. Math. 307, 3130–3146 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  22. Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17, 418–435 (2013)

    Article  Google Scholar 

  23. Thorisson, H.: Coupling, Stationarity, and Regeneration. Springer, Berlin (2000)

  24. Wegener, I.: Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In: Sarker, R., Yao, X., Mohammadian, M. (eds.) Evolutionary Optimization, pp. 349–369. Kluwer, Alphen aan den Rijn (2002)

  25. Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Comb. Probab. Comput. 22, 294–318 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  26. Witt, C.: Fitness levels with tail bounds for the analysis of randomized search heuristics. Inf. Process. Lett. 114, 38–41 (2014)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We thank Jonathan E. Rowe for pointing out to us the alternative proof of Theorem 1 using the combinatorial equality from [21].

Author information

Authors and Affiliations

  1. École Polytechnique, Laboratoire d’Informatique (LIX), 91126, Palaiseau Cedex, France

    Benjamin Doerr

  2. Sorbonne Universités, UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005, Paris, France

    Carola Doerr

Authors
  1. Benjamin Doerr
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carola Doerr
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Carola Doerr.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Doerr, B., Doerr, C. The Impact of Random Initialization on the Runtime of Randomized Search Heuristics. Algorithmica 75, 529–553 (2016). https://doi.org/10.1007/s00453-015-0019-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-015-0019-5

Keywords

Search

Navigation