Top

Published in:

2020 | OriginalPaper | Chapter

Hybridizing the 1/5-th Success Rule with Q-Learning for Controlling the Mutation Rate of an Evolutionary Algorithm

Authors : Arina Buzdalova, Carola Doerr, Anna Rodionova

Published in: Parallel Problem Solving from Nature – PPSN XVI

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

It is well known that evolutionary algorithms (EAs) achieve peak performance only when their parameters are suitably tuned to the given problem. Even more, it is known that the best parameter values can change during the optimization process. Parameter control mechanisms are techniques developed to identify and to track these values.

Recently, a series of rigorous theoretical works confirmed the superiority of several parameter control techniques over EAs with best possible static parameters. Among these results are examples for controlling the mutation rate of the \((1+\lambda )\) EA when optimizing the OneMax problem. However, it was shown in [Rodionova et al., GECCO’19] that the quality of these techniques strongly depends on the offspring population size \(\lambda \).

We introduce in this work a new hybrid parameter control technique, which combines the well-known one-fifth success rule with Q-learning. We demonstrate that our HQL mechanism achieves equal or superior performance to all techniques tested in [Rodionova et al., GECCO’19] and this – in contrast to previous parameter control methods – simultaneously for all offspring population sizes \(\lambda \). We also show that the promising performance of HQL is not restricted to OneMax, but extends to several other benchmark problems.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Optimality-Based Analysis of XCSF Compaction in Discrete Reinforcement Learning

next chapter Fitness Landscape Features and Reward Shaping in Reinforcement Learning Policy Spaces

Aleti, A., Moser, I.: Entropy-based adaptive range parameter control for evolutionary algorithms. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2013), pp. 1501–1508 (2013)

Bäck, T.: The interaction of mutation rate, selection, and self-adaptation within a genetic algorithm. In: Proceedings of Parallel Problem Solving from Nature (PPSN 1992), pp. 87–96. Elsevier (1992)

Bartz-Beielstein, T., Flasch, O., Koch, P., Konen, W.: SPOT: a toolbox for interactive and automatic tuning in the R environment. In: Proceedings of the 20th Workshop on Computational Intelligence, pp. 264–273. Universitätsverlag Karlsruhe (2010)

Belkhir, N., Dréo, J., Savéant, P., Schoenauer, M.: Per instance algorithm configuration of CMA-ES with limited budget. In: Proceedings of Genetic and Evolutionary Conference (GECCO 2017), pp. 681–688. ACM (2017)

Buzdalova, A., Doerr, C., Rodionova, A.: Hybridizing the 1/5-th success rule with Q-learning for controlling the mutation rate of an evolutionary algorithm (2020). http://arxiv.org/abs/2006.11026

Carvalho Pinto, E., Doerr, C.: Towards a more practice-aware runtime analysis of evolutionary algorithms (2018). https://arxiv.org/abs/1812.00493

Costa, L.D., Fialho, Á., Schoenauer, M., Sebag, M.: Adaptive operator selection with dynamic multi-armed bandits. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2008), pp. 913–920. ACM (2008)

Derrac, J., Garcia, S., Molina, D., Herrera, F.: A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol. Comput. 1(1), 3–18 (2011)CrossRef

Devroye, L.: The compound random search. Ph.D. dissertation, Purdue University, West Lafayette, IN (1972)

10.

Doerr, B., Doerr, C.: Theory of parameter control for discrete black-box optimization: provable performance gains through dynamic parameter choices. Theory of Evolutionary Computation. NCS, pp. 271–321. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4_6. Also available online at https://arxiv.org/abs/1804.05650CrossRefMATH

11.

Doerr, B.: Analyzing randomized search heuristics via stochastic domination. Theor. Comput. Sci. 773, 115–137 (2019)MathSciNetCrossRef

12.

Doerr, B., Doerr, C., Lengler, J.: Self-adjusting mutation rates with provably optimal success rules. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2019). ACM (2019)

13.

Doerr, B., Doerr, C., Yang, J.: k-bit mutation with self-adjusting k outperforms standard bit mutation. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 824–834. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_77CrossRef

14.

Doerr, B., Doerr, C., Yang, J.: Optimal parameter choices via precise black-box analysis. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2016), pp. 1123–1130. ACM (2016)

15.

Doerr, B., Gießen, C., Witt, C., Yang, J.: The \((1+\lambda )\) evolutionary algorithm with self-adjusting mutation rate. Algorithmica 81, 593–631 (2019). https://doi.org/10.1007/s00453-018-0502-xMathSciNetCrossRefMATH

16.

Doerr, C., Wagner, M.: On the effectiveness of simple success-based parameter selection mechanisms for two classical discrete black-box optimization benchmark problems. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2018), pp. 943–950. ACM (2018)

17.

Doerr, C., Ye, F., Horesh, N., Wang, H., Shir, O.M., Bäck, T.: Benchmarking discrete optimization heuristics with IOHprofiler. Appl. Soft Comput. 88, 106027 (2020)CrossRef

18.

Doerr, C., Ye, F., van Rijn, S., Wang, H., Bäck, T.: Towards a theory-guided benchmarking suite for discrete black-box optimization heuristics: profiling (1 + \(\lambda \)) EA variants on onemax and leadingones. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2018), pp. 951–958. ACM (2018)

19.

Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51–81 (2002)MathSciNetCrossRef

20.

Eiben, A.E., Horvath, M., Kowalczyk, W., Schut, M.C.: Reinforcement learning for online control of evolutionary algorithms. In: Proceedings of the 4th International Conference on Engineering Self-Organising Systems, pp. 151–160 (2006)

21.

Eiben, A.E., Hinterding, R., Michalewicz, Z.: Parameter control in evolutionary algorithms. IEEE Trans. Evol. Comput. 3, 124–141 (1999)CrossRef

22.

Falkner, S., Klein, A., Hutter, F.: BOHB: robust and efficient hyperparameter optimization at scale. In: Proceedings of International Conference on Machine Learning (ICML 2018), pp. 1436–1445 (2018)

23.

Fialho, Á., Costa, L.D., Schoenauer, M., Sebag, M.: Analyzing bandit-based adaptive operator selection mechanisms. Ann. Math. Artif. Intell. 60, 25–64 (2010)MathSciNetCrossRef

24.

Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 507–523. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25566-3_40CrossRef

25.

Karafotias, G., Eiben, Á.E., Hoogendoorn, M.: Generic parameter control with reinforcement learning. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2014), pp. 1319–1326 (2014)

26.

Karafotias, G., Hoogendoorn, M., Eiben, A.E.: Evaluating reward definitions for parameter control. In: Mora, A.M., Squillero, G. (eds.) EvoApplications 2015. LNCS, vol. 9028, pp. 667–680. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16549-3_54CrossRef

27.

Karafotias, G., Hoogendoorn, M., Eiben, A.: Parameter control in evolutionary algorithms: trends and challenges. IEEE Trans. Evol. Comput. 19, 167–187 (2015)CrossRef

28.

Kern, S., Müller, S.D., Hansen, N., Büche, D., Ocenasek, J., Koumoutsakos, P.: Learning probability distributions in continuous evolutionary algorithms - a comparative review. Nat. Comput. 3, 77–112 (2004)MathSciNetCrossRef

29.

Lässig, J., Sudholt, D.: Adaptive population models for offspring populations and parallel evolutionary algorithms. In: Proceedings of Foundations of Genetic Algorithms (FOGA 2011), pp. 181–192. ACM (2011)

30.

Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., Talwalkar, A.: Hyperband: a novel bandit-based approach to hyperparameter optimization. arXiv preprint arXiv:1603.06560 (2016)

31.

Lobo, F.G., Lima, C.F., Michalewicz, Z. (eds.): Parameter Setting in Evolutionary Algorithms. Studies in Computational Intelligence, vol. 54. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-69432-8CrossRefMATH

32.

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)MathSciNetCrossRef

33.

Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C., Rudolph, G.: Exploratory landscape analysis. In: Proceedings of Genetic and Evolutionary Conference (GECCO 2011), pp. 829–836. ACM (2011)

34.

Müller, S.D., Schraudolph, N.N., Koumoutsakos, P.D.: Step size adaptation in evolution strategies using reinforcement learning. In: Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002), pp. 151–156 (2002)

35.

Pushak, Y., Hoos, H.: Algorithm configuration landscapes: more benign than expected? In: Auger, A., Fonseca, C.M., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds.) PPSN 2018. LNCS, vol. 11102, pp. 271–283. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99259-4_22CrossRef

36.

Rechenberg, I.: Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Fromman-Holzboorg Verlag, Stuttgart (1973)

37.

Rodionova, A., Antonov, K., Buzdalova, A., Doerr, C.: Offspring population size matters when comparing evolutionary algorithms with self-adjusting mutation rates. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2019), pp. 855–863. ACM (2019)

38.

Rost, A., Petrova, I., Buzdalova, A.: Adaptive parameter selection in evolutionary algorithms by reinforcement learning with dynamic discretization of parameter range. In: Proceedings of Genetic and Evolutionary Computation Conference Companion (GECCO 2016), pp. 141–142 (2016)

39.

Schumer, M.A., Steiglitz, K.: Adaptive step size random search. IEEE Trans. Autom. Control 13, 270–276 (1968)CrossRef

40.

Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (1998)MATH

41.

Vérel, S.: Apport à l’analyse des paysages de fitness pour l’optimisation mono-objective et multiobjective: Science des systèmes complexes pour l’optimisation par méthodes stochastiques. (Contributions to fitness landscapes analysis for single- and multi-objective optimization: Science of complex systems for optimization with stochastic methods) (2016). https://tel.archives-ouvertes.fr/tel-01425127

42.

Wang, H., Emmerich, M., Bäck, T.: Cooling strategies for the moment-generating function in Bayesian global optimization. In: Proceedings of Congress on Evolutionary Computation (CEC 2018), pp. 1–8 (2018)

43.

Weise, T., Wu, Z.: Difficult features of combinatorial optimization problems and the tunable w-model benchmark problem for simulating them. In: Proceeding of Genetic and Evolutionary Computation Conference Companion (GECCO 2018), pp. 1769–1776 (2018)

Title: Hybridizing the 1/5-th Success Rule with Q-Learning for Controlling the Mutation Rate of an Evolutionary Algorithm
Authors: Arina Buzdalova
Carola Doerr
Anna Rodionova
Publisher: Springer International Publishing
Book: Parallel Problem Solving from Nature – PPSN XVI
Print ISBN: 978-3-030-58114-5

Electronic ISBN: 978-3-030-58115-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-58115-2_34

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner