Superpolynomial Lower Bounds for the $$(1+1)$$ EA on Some Easy Combinatorial Problems | Algorithmica Skip to main content
Springer Nature Link
Log in

Superpolynomial Lower Bounds for the \((1+1)\) EA on Some Easy Combinatorial Problems

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

The (\(1+1\)) EA is a simple evolutionary algorithm that is known to be efficient on linear functions and on some combinatorial optimization problems. In this paper, we rigorously study its behavior on three easy combinatorial problems: finding the 2-coloring of a class of bipartite graphs, solving a class of satisfiable 2-CNF formulas, and solving a class of satisfiable propositional Horn formulas. We prove that it is inefficient on all three problems in the sense that the number of iterations the algorithm needs to minimize the cost functions is superpolynomial with high probability. Our motivation is to better understand the influence of problem instance structure on the runtime character of a simple evolutionary algorithm. We are interested in what kind of structural features give rise to so-called metastable states at which, with probability \(1 - o(1)\), the (\(1+1\)) EA becomes trapped and subsequently has difficulty leaving. Finally, we show how to modify the (\(1+1\)) EA slightly in order to obtain a polynomial-time performance guarantee on all three problems.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Apsvall, B., Plass, M.F., Tarjan, R.E.: A linear time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Process. Lett. 8(3), 121–123 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  2. Auger, A., Doerr, B. (eds.): Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific, Singapore (2011)

    MATH  Google Scholar 

  3. Briest, P., Brockhoff, D., Degener, B., Englert, M., Gunia, C., Heering, O., Jansen, T., Leifhelm, M., Plociennik, K., Röglin, H., Schweer, A., Sudholt, D., Tannenbaum, S., Wegener, I.: The Ising model: simple evolutionary algorithms as adaptation schemes. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.P. (eds.) Parallel Problem Solving from Nature (PPSN VIII). Lecture Notes in Computer Science, vol. 3242, pp. 31–40. Springer, Heidelberg (2004)

  4. Cook, S., Nguyen, P.: Logical Foundations of Proof Complexity. Cambridge University Press, Cambridge (2010)

    Book  MATH  Google Scholar 

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

  6. Doerr, B., Hebbinghaus, N., Neumann, F.: Speeding up evolutionary algorithms through asymmetric mutation operators. Evol. Comput. 15(4), 401–410 (2007)

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  8. Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Theory Comput. Syst. 39(4), 525–544 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Feller, W.: Generalization of a probability limit theorem of Cramér. Trans. Am. Math. Soc. 54(3), 361–372 (1943)

    MathSciNet  MATH  Google Scholar 

  10. Fischer, S.: A polynomial upper bound for a mutation-based algorithm on the two-dimensional Ising model. In: Deb, K. (ed.) Proceedings of the Genetic and Evolutionary Computation (GECCO). Lecture Notes in Computer Science, vol. 3102, pp. 1100–1112. Springer, Heidelberg (2004)

  11. Fischer, S., Wegener, I.: The one-dimensional Ising model: mutation versus recombination. Theor. Comput. Sci. 344, 208–225 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  12. Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, vol. 2607, pp. 415–426. Springer (2003)

  13. Hoyweghen, C.V., Goldberg, D.E., Naudts, B.: From twomax to the Ising model: easy and hard symmetrical problems. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 626–633. Morgan Kaufmann Publishers Inc. (2002)

  14. Jansen, T., Sudholt, D.: Analysis of an asymmetric mutation operator. Evol. Comput. 18(1), 1–26 (2010)

    Article  Google Scholar 

  15. Matoušek, J., Vondrák, J.: The probabilistic method (lecture notes) (2008). http://kam.mff.cuni.cz/~matousek/prob-ln.ps.gz

  16. McDiarmid, C.: A random recolouring method for graphs and hypergraphs. Comb. Probab. Comput. 2, 363–365 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  17. Neumann, F., Reichel, J., Skutella, M.: Computing minimum cuts by randomized search heuristics. Algorithmica 59(3), 323–342 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  18. Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization: Algorithms and their Computational Complexity. Springer, Berlin (2010)

    Book  MATH  Google Scholar 

  19. Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59(3), 369–386 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  20. Oliveto, P.S., Witt, C.: Erratum: Simplified drift analysis for proving lower bounds in evolutionary computation (2012) arXiv:1211.7184 [cs.NE]

  21. Papadimitriou, C.H., Schäffer, A.A., Yannakakis, M.: On the complexity of local search. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC), pp. 438–445. ACM (1990)

  22. Raidl, G.R., Koller, G., Julstrom, B.A.: Biased mutation operators for subgraph-selection problems. IEEE Trans. Evol. Comput. 10(2), 145–156 (2006)

    Article  Google Scholar 

  23. Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (STOC), pp. 216–226. ACM (1978)

  24. Sudholt, D.: Crossover is provably essential for the Ising model on trees. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 1161–1167. ACM (2005)

  25. Sutton, A.M.: Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 1431–1438. ACM (2014)

  26. Van Hoyweghen, C., Naudts, B., Goldberg, D.E.: Spin-flip symmetry and synchronization. Evol. Comput. 10(4), 317–344 (2002)

    Article  Google Scholar 

  27. Williams, D.: Probability with Martingales. Cambridge Mathematical Textbooks. Cambridge University Press, Cambridge (1991)

    Book  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under Grant Agreement No. 618091 (SAGE), and from the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under Grant No. FA9550-11-1-0088. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.

Author information

Authors and Affiliations

  1. Institut für Informatik, Theoretische Informatik I, Friedrich-Schiller-Universität Jena, 07743, Jena, Germany

    Andrew M. Sutton

Authors
  1. Andrew M. Sutton
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrew M. Sutton.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sutton, A.M. Superpolynomial Lower Bounds for the \((1+1)\) EA on Some Easy Combinatorial Problems. Algorithmica 75, 507–528 (2016). https://doi.org/10.1007/s00453-015-0027-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

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

Keywords

Search

Navigation