Abstract
The hardness of optimizing monotone functions using the \((1+1)\)-EA has been an open problem for a long time. By introducing a more pessimistic stochastic process, the partially-ordered evolutionary algorithm (PO-EA) model, Jansen proved a runtime bound of \(O(n^{3/2})\). In 2019, Lengler, Martinsson and Steger improved this upper bound to \(O(n \log ^2 n)\) leveraging an entropy compression argument. We continue this line of research by analyzing monotone functions that may vary at each step, so-called dynamic monotone functions. We introduce the function Switching Dynamic BinVal (SDBV) and prove, using a combinatorial argument, that for the \((1+1)\)-EA, SDBV is drift minimizing within the class of dynamic monotone functions. We further show that the \((1+1)\)-EA optimizes SDBV in \(\varTheta (n^{3/2})\) generations. Therefore, our construction provides the first explicit example which realizes the pessimism of the PO-EA model. Our simulations demonstrate matching runtimes for both static and self-adjusting \((1,\lambda )\) and \((1+\lambda )\)-EA. We additionally demonstrate, devising an example of fixed dimension, that drift minimization does not equal maximal runtime.
M. Kaufmann—The author was supported by the Swiss National Science Foundation [grant number 200021_192079].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
That is, either the offspring dominates the parent, or vice-versa.
- 2.
- 3.
We note that due to page limitations, we omit many of the proofs. The full version is provided in the supplementary material.
- 4.
Here the \(\tilde{O}(n)\) hides potential polylogarithmic factors of n.
- 5.
Note that there are several ways of choosing \(\sigma _A, \sigma _F\) satisfying those properties, as we may permute any \(0\)-bit with another \(0\)-bit, and similarly for the \(1\)-bits. As properties we study hold regardless of the precise selection of \(\sigma _A, \sigma _F\), we make a slight abuse of notation and talk of the function ADBV and the function FDBV.
- 6.
For readability, the final results are then rounded to 4 digits. The code is available at https://github.com/OliverSieberling/SDBV-EA.
- 7.
Actually, the PO-EA\(^-\); see [2] for the details.
- 8.
One should consider \(\tilde{t}\) to be chosen as a very small multiple of \(n^{3/2}\), so that progress towards the optimum is small in expectation.
- 9.
The code is available at https://github.com/OliverSieberling/SDBV-EA.
References
Buskulic, N., Doerr, C.: Maximizing drift is not optimal for solving OneMax. Evol. Comput. 29(4), 521–541 (2021)
Colin, S., Doerr, B., Férey, G.: Monotonic functions in EC: anything but monotone! In: Genetic and Evolutionary Computation Conference (GECCO), pp. 753–760 (2014)
Corus, D., He, J., Jansen, T., Oliveto, P.S., Sudholt, D., Zarges, C.: On easiest functions for mutation operators in bio-inspired optimisation. Algorithmica 78(2), 714–740 (2017)
Doerr, B., Doerr, C., Yang, J.: Optimal parameter choices via precise black-box analysis. Theor. Comput. Sci. 801, 1–34 (2020)
Doerr, B., Gießen, C., Witt, C., Yang, J.: The (1+ \(\lambda \)) evolutionary algorithm with self-adjusting mutation rate. Algorithmica 81, 593–631 (2019)
Doerr, B., Jansen, T., Sudholt, D., Winzen, C., Zarges, C.: Optimizing monotone functions can be difficult. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 42–51. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15844-5_5
Doerr, B., Jansen, T., Sudholt, D., Winzen, C., Zarges, C.: Mutation rate matters even when optimizing monotonic functions. Evol. Comput. 21(1), 1–27 (2013)
Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673–697 (2012)
Doerr, B., Künnemann, M.: How the (1+ \(\lambda \)) evolutionary algorithm optimizes linear functions. Theor. Comput. Sci. 561, 3–23 (2015)
Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Genetic and Evolutionary Computation Conference (GECCO) (2017)
Doerr, B., Lissovoi, A., Oliveto, P.S., Warwicker, J.A.: On the runtime analysis of selection hyper-heuristics with adaptive learning periods. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 1015–1022 (2018)
Doerr, C., Janett, D.A., Lengler, J.: Tight runtime bounds for static unary unbiased evolutionary algorithms on linear functions. In: Genetic and Evolutionary Computation Conference (GECCO) (2023)
Doerr, C., Wagner, M.: Simple on-the-fly parameter selection mechanisms for two classical discrete black-box optimization benchmark problems. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 943–950 (2018)
He, J., Chen, T., Yao, X.: On the easiest and hardest fitness functions. IEEE Trans. Evol. Comput. 19(2), 295–305 (2014)
Hevia Fajardo, M.A., Sudholt, D.: Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter. Algorithmica 86, 526–565 (2024)
Jägersküpper, J., Storch, T.: When the plus strategy outperforms the comma strategy and when not. In: Foundations of Computational Intelligence (FOCI), pp. 25–32. IEEE (2007)
Janett, D., Lengler, J.: Two-dimensional drift analysis: optimizing two functions simultaneously can be hard. Theor. Comput. Sci. 971, 114072 (2023)
Jansen, T.: On the brittleness of evolutionary algorithms. In: Stephens, C.R., Toussaint, M., Whitley, D., Stadler, P.F. (eds.) FOGA 2007. LNCS, vol. 4436, pp. 54–69. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73482-6_4
Jansen, T., Jong, K.A.D., Wegener, I.: On the choice of the offspring population size in evolutionary algorithms. Evol. Comput. 13(4), 413–440 (2005)
Jorritsma, J., Lengler, J., Sudholt, D.: Comma selection outperforms plus selection on OneMax with randomly planted optima. In: Genetic and Evolutionary Computation Conference (GECCO) (2023)
Kaufmann, M., Larcher, M., Lengler, J., Zou, X.: Self-adjusting population sizes for the \((1, \lambda )\)-EA on monotone functions. In: Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tušar, T. (eds.) PPSN 2022. LNCS, vol. 13399, pp. 569–585. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-14721-0_40
Kaufmann, M., Larcher, M., Lengler, J., Zou, X.: OneMax is not the easiest function for fitness improvements. In: Pérez Cáceres, L., Stützle, T. (eds.) EvoCOP 2023. LNCS, vol. 13987, pp. 162–178. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30035-6_11
Kaufmann, M., Larcher, M., Lengler, J., Zou, X.: Self-adjusting population sizes for the (1, \(\lambda \))-EA on monotone functions. Theor. Comput. Sci. 979, 114181 (2023)
Lässig, J., Sudholt, D.: General scheme for analyzing running times of parallel evolutionary algorithms. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 234–243. Springer, Cham (2010). https://doi.org/10.1007/978-3-642-15844-5_24
Lässig, J., Sudholt, D.: Adaptive population models for offspring populations and parallel evolutionary algorithms. In: Foundations of Genetic Algorithms (FOGA), pp. 181–192 (2011)
Lengler, J.: A general dichotomy of evolutionary algorithms on monotone functions. IEEE Trans. Evol. Comput. 24(6), 995–1009 (2019)
Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation. NCS, pp. 89–131. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4_2
Lengler, J., Martinsson, A., Steger, A.: When does hillclimbing fail on monotone functions: an entropy compression argument. In: Analytic Algorithmics and Combinatorics (ANALCO), pp. 94–102. SIAM (2019)
Lengler, J., Meier, J.: Large population sizes and crossover help in dynamic environments. In: Bäck, T., et al. (eds.) PPSN 2020. LNCS, vol. 12269, pp. 610–622. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-58112-1_42
Lengler, J., Riedi, S.: Runtime analysis of the \((\mu + 1)\)-EA on the dynamic BinVal function. In: Zarges, C., Verel, S. (eds.) EvoCOP 2021. LNCS, vol. 12692, pp. 84–99. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-72904-2_6
Lengler, J., Schaller, U.: The \((1+1)\)-EA on noisy linear functions with random positive weights. In: Symposium Series on Computational Intelligence (SSCI), pp. 712–719. IEEE (2018)
Lengler, J., Steger, A.: Drift analysis and evolutionary algorithms revisited. Comb. Probab. Comput. 27(4), 643–666 (2018)
Lengler, J., Zou, X.: Exponential slowdown for larger populations: the \((\mu + 1)\)-EA on monotone functions. Theor. Comput. Sci. 875, 28–51 (2021)
Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 835–842 (2009)
Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the (1, \(\lambda \)) evolutionary algorithm. Theor. Comput. Sci. 545, 20–38 (2014)
Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17(3), 418–435 (2012)
Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Comb. Probab. Comput. 22(2), 294–318 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kaufmann, M., Larcher, M., Lengler, J., Sieberling, O. (2024). Hardest Monotone Functions for Evolutionary Algorithms. In: Stützle, T., Wagner, M. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2024. Lecture Notes in Computer Science, vol 14632. Springer, Cham. https://doi.org/10.1007/978-3-031-57712-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-57712-3_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-57711-6
Online ISBN: 978-3-031-57712-3
eBook Packages: Computer ScienceComputer Science (R0)