The linear hidden subset problem for the (1 + 1) EA with scheduled and adaptive mutation rates

ABSTRACT

We study unbiased (1 + 1) evolutionary algorithms on linear functions with an unknown number n of bits with non-zero weight. Static algorithms achieve an optimal runtime of O(n(ln n)^2+ε), however, it remained unclear whether more dynamic parameter policies could yield better runtime guarantees. We consider two setups: one where the mutation rate follows a fixed schedule, and one where it may be adapted depending on the history of the run. For the first setup, we give a schedule that achieves a runtime of (1±o(1))βn ln n, where β ≈ 3.552, which is an asymptotic improvement over the runtime of the static setup. Moreover, we show that no schedule admits a better runtime guarantee and that the optimal schedule is essentially unique. For the second setup, we show that the runtime can be further improved to (1 ± o(1))en ln n, which matches the performance of algorithms that know n in advance.

Finally, we study the related model of initial segment uncertainty with static position-dependent mutation rates, and derive asymptotically optimal lower bounds. This answers a question by Doerr, Doerr, and Kötzing.

References

1. Stephan Cathabard, Per Kristian Lehre, and Xin Yao. 2011. Non-uniform mutation rates for problems with unknown solution lengths. In Foundations of Genetic Algorithms (FOGA). ACM, 173--180.
2. Thomas H. Cormen, Charles E. Leiserson, Robert L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms (2. ed.). MIT Press.
3. Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2015. Solving problems with unknown solution length at (almost) no extra cost. In Genetic and Evolutionary Computation Conference (GECCO). ACM, 831--838.
4. Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2017. Unknown solution length problems with no asymptotically optimal run time. In Genetic and Evolutionary Computation Conference (GECCO). ACM, 1367--1374.
5. Benjamin Doerr, Carola Doerr, and Jing Yang. 2016. Optimal parameter choices via precise black-box analysis. In Genetic and Evolutionary Computation Conference (GECCO). ACM, 1123--1130.
6. Carola Doerr and Johannes Lengler. 2017. OneMax in black-box models with several restrictions. Algorithmica 78, 2 (2017), 610--640.
7. Ágoston E Eiben, Robert Hinterding, and Zbigniew Michalewicz. 1999. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computations, 2 (1999), 124--141.
8. Giorgos Karafotias, Mark Hoogendoorn, and Ágoston E Eiben. 2015. Parameter control in evolutionary algorithms: Trends and challenges. IEEE Transactions on Evolutionary Computation 19, 2 (2015), 167--187.
9. Elias Koutsoupias and Christos Papadimitriou. 1999. Worst-case equilibria. In Symposium on Theoretical Aspects of Computer Science (STACS), Vol. 99. Springer, 404--413.
10. Per Kristian Lehre and Xin Yao. 2014. Runtime analysis of the (1+ 1) EA on computing unique input output sequences. Information Sciences 259 (2014), 510--531.
11. Tim Roughgarden and Éva Tardos. 2002. How bad is selfish routing? Journal of the ACM (JACM) 49, 2 (2002), 236--259.
12. Carsten Witt. 2012. Optimizing linear functions with randomized search heuristics-the robustness of mutation. In Symposium on Theoretical Aspects of Computer Science (STACS), Vol. 14. LIPIcs, 420--431.
13. Carsten Witt. 2013. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability and Computing 22, 2 (2013), 294--318.

Index Terms

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization

      • Discrete optimization

        • Optimization with randomized search heuristics

          • Evolutionary algorithms

  • Theory and algorithms for application domains

    • Theory of randomized search heuristics