Abstract
We study the influence of the particular choice of operators on the running time of the recently proposed \((1+(\lambda ,\lambda ))\) genetic algorithm. In particular, we consider three choices for the mutation operator, six choices of the crossover operator, three strategies for sampling population sizes based on non-integer parameter values, and four choices of what to do when the best mutant is better than the parent.
We test all these 216 configurations on four optimization problems and in three adjustment flavours: the fixed \(\lambda \), the unlimited self-adjustment of \(\lambda \) and the logarithmically capped one. For each of these configurations, we consider both the default values of the hyperparameters and the ones produced by the irace parameter tuning tool.
The result of our experimental analysis showed that there exists a configuration that is robust on linear functions and is roughly two times faster compared to the initially proposed one and 12% faster on the OneMax problem compared to one of the similar previous studies. An even more robust configuration exists, which has a slightly worse performance on OneMax but is better on satisfiability problems. Such configurations can be the default choices for the practical evaluation of the \((1+(\lambda ,\lambda ))\) GA.
Supported by the Russian Scientific Foundation, agreement No. 17-71-20178.
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
Similar content being viewed by others
Notes
- 1.
Location: https://zenodo.org/record/3871043, DOI: 10.5281/zenodo.3871043.
References
Bassin, A., Buzdalov, M.: The 1/5-th rule with rollbacks: on self-adjustment of the population size in the \((1+(\lambda ,\lambda ))\) GA. In: Proceedings of Genetic and Evolutionary Computation Conference Companion, pp. 277–278 (2019). https://arxiv.org/abs/1904.07284
Buzdalov, M., Doerr, B.: Runtime analysis of the \((1 + (\lambda , \lambda ))\) genetic algorithm on random satisfiable 3-CNF formulas. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 1343–1350 (2017)
Carvalho Pinto, E., Doerr, C.: Towards a more practice-aware runtime analysis of evolutionary algorithms (2018). https://arxiv.org/abs/1812.00493
Dang, N., Doerr, C.: Hyper-parameter tuning for the \((1+(\lambda ,\lambda ))\) GA. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 889–897 (2019)
Doerr, B., Doerr, C.: Optimal static and self-adjusting parameter choices for the \((1+(\lambda,\lambda ))\) genetic algorithm. Algorithmica 80(5), 1658–1709 (2018). https://doi.org/10.1007/s00453-017-0354-9
Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theoret. Comput. Sci. 567, 87–104 (2015)
Doerr, B., Johannsen, D., Kötzing, T., Lehre, P.K., Wagner, M., Winzen, C.: Faster black-box algorithms through higher arity operators. In: Proceedings of Foundations of Genetic Algorithms, pp. 163–172 (2011)
Doerr, B., Neumann, F., Sutton, A.M.: Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 1415–1422 (2015)
Goldman, B.W., Punch, W.F.: Parameter-less population pyramid. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 785–792 (2014)
Kirkpatrick, S., Selman, B.: Critical behavior in the satisfiability of random Boolean expressions. Science 264(5163), 1297–1301 (1994)
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L.P., Stützle, T., Birattari, M.: The irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3, 43–58 (2016)
Sutton, A.M., Neumann, F.: Runtime analysis of evolutionary algorithms on randomly constructed high-density satisfiable 3-CNF formulas. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 942–951. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10762-2_93
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Bassin, A., Buzdalov, M. (2020). An Experimental Study of Operator Choices in the \((1+(\lambda ,\lambda ))\) Genetic Algorithm. In: Kochetov, Y., Bykadorov, I., Gruzdeva, T. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2020. Communications in Computer and Information Science, vol 1275. Springer, Cham. https://doi.org/10.1007/978-3-030-58657-7_26
Download citation
DOI: https://doi.org/10.1007/978-3-030-58657-7_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58656-0
Online ISBN: 978-3-030-58657-7
eBook Packages: Computer ScienceComputer Science (R0)