On Runtime of Non-Elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau
Abstract
The expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions Plateaur on the search space of binary strings of length nisconsideredasymptotically withunboundedn. Thefunctionsofthisfamilyhave a plateau of second-best fitness in a Hamming ball of a constant radius r around a unique global optimum, while belowtheplateau the fitness equals the number of one-bits. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for non-elitist EAs with tournament selection, (µ, λ)-selection and proportionate selection. We assume that these EAs are based on an unbiased mutation, in particular, the bitwise mutation. In the case of proportionate selection, the mutation probability is of order 1/n2. On the other hand, we show that the EA with fitness proportionate selection is inefficient even to search for approximate solutions if the bitwise mutation is used with the mutation probability greater than ln(2)/n.
References
P. A. Borisovsky and M. S. Zavolovskaya, “Experimental comparison of two evolutionary algorithms for the independent set problem,” in Applications of Evolutionary Computing, S. Cagnoni, C. G. Johnson, J. J. R. Cardalda, E. Marchiori, D. W. Corne, J.-A. Meyer, J. Gottlieb, M. Middendorf, A. Guillot, G. R. Raidl, and E. Hart, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 154–164.
A. M. Sutton, A. E. Howe, and L. D. Whitley, “Directed plateau search for Max-k-Sat,” in Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, USA, July 8-10, 2010, 2010.
D. Whitley, A. Howe, and D. Hains, “Greedy or not? best improving versus first improving stochastic local search for MaxSat,” in Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, ser. AAAI’13. AAAI Press, 2013, pp. 940–946.
E.F. de Souza, C. LeGoues, and C.G. Camilo-Junior, “A novel fitness function for automated program repair based on source code checkpoints,” in Proceedings of the Genetic and Evolutionary Computation Conference, ser. GECCO’18. New York, NY, USA: Association for Computing Machinery, 2018, pp. 1443–1450.
I. O. Oduntan, M. Toulouse, R. Baumgartner, C. Bowman, R. L. Somorjai, and T. G. Crainic, “A multilevel tabu search algorithm for the feature selection problem in biomedical data,” Comput. Math. Appl., vol. 55, pp. 1019–1033, 2008.
F. A. Kondrashov, I. B. Rogozin, Y. I. Wolf, and E. V. Koonin, “Selection in the evolution of gene duplications,” Genome biology, vol. 3, no. 2, pp. 427–427, 2002.
D. Antipov and B. Doerr, “Precise runtime analysis for plateau functions,” ACM Trans. Evol. Learn. Optim., vol. 1, no. 4, Oct. 2021. doi: 10.1145/3469800
T. Jansen and I. Wegener, “Evolutionary algorithms- how to cope with plateaus of constant fitness and when to reject strings of the same fitness,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 6, pp. 589–599, 2001. doi: 10.1109/4235.974841
A. Lissovoi, D. Sudholt, M. Wagner, and C. Zarges, “Theoretical results on bet-and-run as an initialisation strategy,” in Proceedings of the Genetic and Evolutionary Computation Conference, ser. GECCO ’17. New York, NY, USA: Association for Computing Machinery, 2017. doi: 10.1145/3071178.3071329 pp. 857–864.
E.van Nimwegenand, J. Crutchfield, “Optimizing epocha levolutionary search population-size independent theory,” Computer Methods in Applied Mech. and Engineering, vol. 186, no. 2-4, pp. 171–194, 2000.
P. K. Lehre and C. Witt, “Tail bounds on hitting times of randomized search heuristics using variable drift analysis,” Combinatorics, Probability and Computing, vol. 30, no. 4, pp. 550569, 2021. doi: 10.1017/S0963548320000565
T. Jansen and C. Zarges, “Performance analysis of randomised search heuristics operating with a fixed budget,” Theoretical Computer Science, vol. 545, pp. 39–58, 2014. doi: https://doi.org/10.1016/j.tcs.2013.06.007
P. K. Lehre and C. Witt, “Black-box search by unbiased variation,” Algorithmica, vol. 64, pp. 623–642, 2012.
B. Doerr and A. J. Kelley, “Fourier analysis meets runtime analysis: Precise runtimes on plateaus,” Algorithmica, vol. 86, no. 8, pp. 2479–2518, 2024. doi: 10.1007/S00453-02401232-5
J. Jägerskupper and T. Storch, “When the plus strategy outperforms the comma strategy and when not,” in 2007 IEEE Symposium on Foundations of Computational Intelligence, 2007, pp. 25–32.
J. Jorritsma, J. Lengler, and D. Sudholt, “Comma selection outperforms plus selection on OneMax with randomly planted optima,” Algorithmica, 2025. doi: 10.1007/s00453-02501330-y Early access.
D. Corus, D. Dang, A. V. Eremeev, and P. K. Lehre, “Level-based analysis of genetic algorithms and other search processes,” IEEE Transactions on Evolutionary Computation, vol. 22, no. 5, pp. 707–719, Oct 2018.
A. Eremeev, “Hitting times of local and global optima in genetic algorithms with very high selection pressure,” Yugosl. J. Oper. Res., vol. 27, no. 3, pp. 323–339, 2017.
B. Doerr and T. Kötzing, “Multiplicative up-drift,” Algorithmica, vol. 83, pp. 1–42, 10 2021. doi: 10.1007/s00453-020-00775-7
P. K. Lehre, “Negative drift in populations,” in Proc. of PPSN’10, 2010, pp. 244–253.
B. Doerr, “Lower bounds for non-elitist evolutionary algorithms via negative multiplicative drift,” Evolutionary Computation, vol. 29, no. 2, pp. 305–329, 06 2021.
P. K. Lehre, “Fitness-levels for non-elitist populations,” in Proc. of GECCO’11, 2011, pp. 2075–2082.
A. Eremeev, “On proportions of fit individuals in population of mutation-based evolutionary algorithm with tournament selection,” Evolutionary Computation, vol. 26, no. 2, pp. 269–297, 2018.
A. V. Eremeev, “On non-elitist evolutionary algorithms optimizing fitness functions with a plateau,” in Mathematical Optimization Theory and Operations Research, A. Kononov, M.Khachay, V. A. Kalyagin, and P. Pardalos, Eds. Cham: Springer International Publishing, 2020, pp. 329–342.
D.-C. Dang and P. K. Lehre, “Runtime analysis of non-elitist populations: From classical optimisation to partial information,” Algorithmica, vol. 75, no. 3, pp. 428–461, 2016.
S. Droste, T. Jansen, and I. Wegener, “Upper and lower bounds for randomized search heuristics in black-box optimization,” Theory of Computing Systems, vol. 39, no. 4, pp. 525–544, Jul. 2006. doi: 10.1007/s00224-004-1177-z
P. Borisovsky and A. Eremeev, “Comparing evolutionary algorithms to the (1+1)-EA,” Theoretical Computer Science, vol. 403, no. 1, pp. 33–41, 2008.
A. V. Eremeev and A. V. Spirov, “Modeling SELEX for regulatory regions using royal road and royal staircase fitness functions,” Biosystems, vol. 200, p. 104312, 2021. doi: 10.1016/j.biosystems.2020.104312
D.-C. Dang, A.Eremeev, andP.K.Lehre, “Runtimeanalysis of fitness-proportionate selection on linear functions,” ArXiv, vol. 1908.08686 [cs.NE], 2019.
B. Doerr and T. Kötzing, “Multiplicative up-drift,” in Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, Prague, Czech Republic, July 13-17, 2019, 2019, pp. 1470–1478.
D.-C. Dang and P. K. Lehre, “Self-adaptation of mutation rates in non-elitist populations,” in Proc. of PPSN XIV. Springer, 2016, pp. 803–813, (arXiv:1606.05551).
B. V. Gnedenko, Theory of probability. Gordon and Breach, 1997.
D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., 1989.
C. Witt, “Tight bounds on the optimization time of a randomized search heuristic on linear functions,” Combinatorics, Probability and Computing, vol. 22, pp. 294–318, 3 2013.
A. M. Sutton, A. E. Howe, and L. D. Whitley, “Directed plateau search for Max-k-Sat,” in Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, USA, July 8-10, 2010, 2010.
D. Whitley, A. Howe, and D. Hains, “Greedy or not? best improving versus first improving stochastic local search for MaxSat,” in Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, ser. AAAI’13. AAAI Press, 2013, pp. 940–946.
E.F. de Souza, C. LeGoues, and C.G. Camilo-Junior, “A novel fitness function for automated program repair based on source code checkpoints,” in Proceedings of the Genetic and Evolutionary Computation Conference, ser. GECCO’18. New York, NY, USA: Association for Computing Machinery, 2018, pp. 1443–1450.
I. O. Oduntan, M. Toulouse, R. Baumgartner, C. Bowman, R. L. Somorjai, and T. G. Crainic, “A multilevel tabu search algorithm for the feature selection problem in biomedical data,” Comput. Math. Appl., vol. 55, pp. 1019–1033, 2008.
F. A. Kondrashov, I. B. Rogozin, Y. I. Wolf, and E. V. Koonin, “Selection in the evolution of gene duplications,” Genome biology, vol. 3, no. 2, pp. 427–427, 2002.
D. Antipov and B. Doerr, “Precise runtime analysis for plateau functions,” ACM Trans. Evol. Learn. Optim., vol. 1, no. 4, Oct. 2021. doi: 10.1145/3469800
T. Jansen and I. Wegener, “Evolutionary algorithms- how to cope with plateaus of constant fitness and when to reject strings of the same fitness,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 6, pp. 589–599, 2001. doi: 10.1109/4235.974841
A. Lissovoi, D. Sudholt, M. Wagner, and C. Zarges, “Theoretical results on bet-and-run as an initialisation strategy,” in Proceedings of the Genetic and Evolutionary Computation Conference, ser. GECCO ’17. New York, NY, USA: Association for Computing Machinery, 2017. doi: 10.1145/3071178.3071329 pp. 857–864.
E.van Nimwegenand, J. Crutchfield, “Optimizing epocha levolutionary search population-size independent theory,” Computer Methods in Applied Mech. and Engineering, vol. 186, no. 2-4, pp. 171–194, 2000.
P. K. Lehre and C. Witt, “Tail bounds on hitting times of randomized search heuristics using variable drift analysis,” Combinatorics, Probability and Computing, vol. 30, no. 4, pp. 550569, 2021. doi: 10.1017/S0963548320000565
T. Jansen and C. Zarges, “Performance analysis of randomised search heuristics operating with a fixed budget,” Theoretical Computer Science, vol. 545, pp. 39–58, 2014. doi: https://doi.org/10.1016/j.tcs.2013.06.007
P. K. Lehre and C. Witt, “Black-box search by unbiased variation,” Algorithmica, vol. 64, pp. 623–642, 2012.
B. Doerr and A. J. Kelley, “Fourier analysis meets runtime analysis: Precise runtimes on plateaus,” Algorithmica, vol. 86, no. 8, pp. 2479–2518, 2024. doi: 10.1007/S00453-02401232-5
J. Jägerskupper and T. Storch, “When the plus strategy outperforms the comma strategy and when not,” in 2007 IEEE Symposium on Foundations of Computational Intelligence, 2007, pp. 25–32.
J. Jorritsma, J. Lengler, and D. Sudholt, “Comma selection outperforms plus selection on OneMax with randomly planted optima,” Algorithmica, 2025. doi: 10.1007/s00453-02501330-y Early access.
D. Corus, D. Dang, A. V. Eremeev, and P. K. Lehre, “Level-based analysis of genetic algorithms and other search processes,” IEEE Transactions on Evolutionary Computation, vol. 22, no. 5, pp. 707–719, Oct 2018.
A. Eremeev, “Hitting times of local and global optima in genetic algorithms with very high selection pressure,” Yugosl. J. Oper. Res., vol. 27, no. 3, pp. 323–339, 2017.
B. Doerr and T. Kötzing, “Multiplicative up-drift,” Algorithmica, vol. 83, pp. 1–42, 10 2021. doi: 10.1007/s00453-020-00775-7
P. K. Lehre, “Negative drift in populations,” in Proc. of PPSN’10, 2010, pp. 244–253.
B. Doerr, “Lower bounds for non-elitist evolutionary algorithms via negative multiplicative drift,” Evolutionary Computation, vol. 29, no. 2, pp. 305–329, 06 2021.
P. K. Lehre, “Fitness-levels for non-elitist populations,” in Proc. of GECCO’11, 2011, pp. 2075–2082.
A. Eremeev, “On proportions of fit individuals in population of mutation-based evolutionary algorithm with tournament selection,” Evolutionary Computation, vol. 26, no. 2, pp. 269–297, 2018.
A. V. Eremeev, “On non-elitist evolutionary algorithms optimizing fitness functions with a plateau,” in Mathematical Optimization Theory and Operations Research, A. Kononov, M.Khachay, V. A. Kalyagin, and P. Pardalos, Eds. Cham: Springer International Publishing, 2020, pp. 329–342.
D.-C. Dang and P. K. Lehre, “Runtime analysis of non-elitist populations: From classical optimisation to partial information,” Algorithmica, vol. 75, no. 3, pp. 428–461, 2016.
S. Droste, T. Jansen, and I. Wegener, “Upper and lower bounds for randomized search heuristics in black-box optimization,” Theory of Computing Systems, vol. 39, no. 4, pp. 525–544, Jul. 2006. doi: 10.1007/s00224-004-1177-z
P. Borisovsky and A. Eremeev, “Comparing evolutionary algorithms to the (1+1)-EA,” Theoretical Computer Science, vol. 403, no. 1, pp. 33–41, 2008.
A. V. Eremeev and A. V. Spirov, “Modeling SELEX for regulatory regions using royal road and royal staircase fitness functions,” Biosystems, vol. 200, p. 104312, 2021. doi: 10.1016/j.biosystems.2020.104312
D.-C. Dang, A.Eremeev, andP.K.Lehre, “Runtimeanalysis of fitness-proportionate selection on linear functions,” ArXiv, vol. 1908.08686 [cs.NE], 2019.
B. Doerr and T. Kötzing, “Multiplicative up-drift,” in Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, Prague, Czech Republic, July 13-17, 2019, 2019, pp. 1470–1478.
D.-C. Dang and P. K. Lehre, “Self-adaptation of mutation rates in non-elitist populations,” in Proc. of PPSN XIV. Springer, 2016, pp. 803–813, (arXiv:1606.05551).
B. V. Gnedenko, Theory of probability. Gordon and Breach, 1997.
D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., 1989.
C. Witt, “Tight bounds on the optimization time of a randomized search heuristic on linear functions,” Combinatorics, Probability and Computing, vol. 22, pp. 294–318, 3 2013.
Published
2025-12-03
How to Cite
EREMEEV, Anton.
On Runtime of Non-Elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau.
Yugoslav Journal of Operations Research, [S.l.], dec. 2025.
ISSN 2334-6043.
Available at: <https://yujor.fon.bg.ac.rs/index.php/yujor/article/view/1374>. Date accessed: 20 dec. 2025.
doi: https://doi.org/10.2298/YJOR250715042E.
Issue
Section
Research Articles
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
