Top

Published in:

2023 | OriginalPaper | Chapter

Context Matters: Adaptive Mutation for Grammars

Authors : Pedro Carvalho, Jessica Mégane, Nuno Lourenço, Penousal Machado

Published in: Genetic Programming

Publisher: Springer Nature Switzerland

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

search-config

AI-assisted search

Off

Abstract

This work proposes Adaptive Facilitated Mutation, a self-adaptive mutation method for Structured Grammatical Evolution (SGE), biologically inspired by the theory of facilitated variation. In SGE, the genotype of individuals contains a list for each non-terminal of the grammar that defines the search space. In our proposed mutation, each individual contains an array with a different, self-adaptive mutation rate for each non-terminal. We also propose Function Grouped Grammars, a grammar design procedure to enhance the benefits of the propose mutation. Experiments were conducted on three symbolic regression benchmarks using Probabilistic Structured Grammatical Evolution (PSGE), a variant of SGE. Results show our approach is similar or better when compared with the standard grammar and mutation.

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 Small Solutions for Real-World Symbolic Regression Using Denoising Autoencoder Genetic Programming

next chapter A Boosting Approach to Constructing an Ensemble Stack

Whigham, P.A., Science, D.O.C.: Grammatically-based genetic programming (1995)

Ryan, C., Collins, J.J., Neill, M.O.: Grammatical evolution: evolving programs for an arbitrary language. In: Banzhaf, W., Poli, R., Schoenauer, M., Fogarty, T.C. (eds.) EuroGP 1998. LNCS, vol. 1391, pp. 83–96. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055930CrossRef

McKay, R.I., Hoai, N.X., Whigham, P.A., Shan, Y., O’Neill, M.: Grammar-based genetic programming: a survey. Genet. Program. Evolvable Mach. 11(3–4), 365–396 (2010). https://doi.org/10.1007/s10710-010-9109-yCrossRef

Whigham, P.A., Dick, G., Maclaurin, J., Owen, C.A.: Examining the “best of both worlds” of grammatical evolution. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 1111–1118. ACM (2015)

Lourenço, N., Assunção, F., Pereira, F.B., Costa, E., Machado, P.: Structured grammatical evolution: a dynamic approach. In: Ryan, C., O’Neill, M., Collins, J.J. (eds.) Handbook of Grammatical Evolution, pp. 137–161. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78717-6_6CrossRef

Lourenço, N., Ferrer, J., Pereira, F.B., Costa, E.: A comparative study of different grammar-based genetic programming approaches. In: McDermott, J., Castelli, M., Sekanina, L., Haasdijk, E., García-Sánchez, P. (eds.) EuroGP 2017. LNCS, vol. 10196, pp. 311–325. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55696-3_20CrossRef

Medvet, E.: A comparative analysis of dynamic locality and redundancy in grammatical evolution. In: McDermott, J., Castelli, M., Sekanina, L., Haasdijk, E., García-Sánchez, P. (eds.) EuroGP 2017. LNCS, vol. 10196, pp. 326–342. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55696-3_21CrossRef

Lourenço, N., Pereira, F.B., Costa, E.: Unveiling the properties of structured grammatical evolution. Genet. Program. Evolvable Mach. 17(3), 251–289 (2016). https://doi.org/10.1007/s10710-015-9262-4CrossRef

Gerhart, J., Kirschner, M.: The theory of facilitated variation. Proc. Natl. Acad. Sci. 104(1), 8582–8589 (2007). https://doi.org/10.1073/pnas.0701035104CrossRef

10.

Nicolau, M., Agapitos, A.: Understanding grammatical evolution: grammar design. In: Ryan, C., O’Neill, M., Collins, J.J. (eds.) Handbook of Grammatical Evolution, pp. 23–53. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78717-6_2CrossRef

11.

Nicolau, M.: Automatic grammar complexity reduction in grammatical evolution. In: The 3rd Grammatical Evolution Workshop: A Workshop of the 2004 Genetic and Evolutionary Computation Conference (GECCO 2004), Seattle, Washington, USA, 26–30 June 2004. Seattle, Washington, USA (2004)

12.

Dick, G., Whigham, P.A.: Initialisation and grammar design in grammar-guided evolutionary computation. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO 2022), pp. 534–537. Association for Computing Machinery, New York, NY, USA (2022). https://doi.org/10.1145/3520304.3529051

13.

Hemberg, E.: Pre-, in-and postfix grammars for symbolic regression in grammatical evolution (2008)

14.

Ryan, C., O’Neill, M., Collins, J.J. (eds.): Handbook of Grammatical Evolution. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78717-6CrossRefMATH

15.

Megane, J., Lourenco, N., Machado, P.: Probabilistic structured grammatical evolution. In: 2022 IEEE Congress on Evolutionary Computation (CEC), pp. 991–999. IEEE (2022). https://doi.org/10.1109/cec55065.2022.9870397

16.

Thorhauer, A.: On the non-uniform redundancy in grammatical evolution. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 292–302. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_27CrossRef

17.

Thorhauer, A., Rothlauf, F.: On the locality of standard search operators in grammatical evolution. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 465–475. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10762-2_46CrossRef

18.

Rothlauf, F., Oetzel, M.: On the locality of grammatical evolution. In: Collet, P., Tomassini, M., Ebner, M., Gustafson, S., Ekárt, A. (eds.) EuroGP 2006. LNCS, vol. 3905, pp. 320–330. Springer, Heidelberg (2006). https://doi.org/10.1007/11729976_29CrossRef

19.

Nicolau, M.: Understanding grammatical evolution: initialisation. Genet. Program. Evolvable Mach. 18(4), 467–507 (2017). https://doi.org/10.1007/s10710-017-9309-9CrossRef

20.

O’Neill, M., Brabazon, A., Nicolau, M., Garraghy, S.M., Keenan, P.: \(\pi \)grammatical evolution. In: Deb, K. (ed.) GECCO 2004. LNCS, vol. 3103, pp. 617–629. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24855-2_70CrossRef

21.

Fagan, D., O’Neill, M., Galván-López, E., Brabazon, A., McGarraghy, S.: An analysis of genotype-phenotype maps in grammatical evolution. In: Esparcia-Alcázar, A.I., Ekárt, A., Silva, S., Dignum, S., Uyar, A.Ş (eds.) EuroGP 2010. LNCS, vol. 6021, pp. 62–73. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12148-7_6CrossRef

22.

Mégane, J., Lourenço, N., Machado, P.: Probabilistic grammatical evolution. In: Hu, T., Lourenço, N., Medvet, E. (eds.) EuroGP 2021. LNCS, vol. 12691, pp. 198–213. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-72812-0_13CrossRef

23.

Mégane, J., Lourenço, N., Machado, P.: Co-evolutionary probabilistic structured grammatical evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 991–999. ACM (2022). https://doi.org/10.1145/3512290.3528833

24.

Beyer, H., Schwefel, H.: Evolution strategies - a comprehensive introduction. Nat. Comput. 1, 3–52 (2004). https://doi.org/10.1023/A:1015059928466MathSciNetCrossRefMATH

25.

Hinterding, R.: Gaussian mutation and self-adaption for numeric genetic algorithms. In: Proceedings of 1995 IEEE International Conference on Evolutionary Computation, vol. 1, p. 384. IEEE (1995)

26.

Teo, J.: Self-adaptive mutation for enhancing evolutionary search in real-coded genetic algorithms. In: 2006 International Conference on Computing & Informatics, pp. 1–6. IEEE (2006)

27.

Libelli, S.M., Alba, P.: Adaptive mutation in genetic algorithms. Soft Comput. 4(2), 76–80 (2000). https://doi.org/10.1007/s005000000042CrossRef

28.

Lis, J.: Genetic algorithm with the dynamic probability of mutation in the classification problem. Pattern Recogn. Lett. 16(12), 1311–1320 (1995)CrossRef

29.

Stark, N., Minetti, G.F., Salto, C.: A new strategy for adapting the mutation probability in genetic algorithms (2012)

30.

Cruz-Salinas, A.F., Perdomo, J.G.: Self-adaptation of genetic operators through genetic programming techniques. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 913–920. ACM (2017)

31.

Gomez, J.: Self adaptation of operator rates in evolutionary algorithms. In: Deb, K. (ed.) GECCO 2004. LNCS, vol. 3102, pp. 1162–1173. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24854-5_113CrossRef

32.

Gómez, J., León, E.: On the class of hybrid adaptive evolutionary algorithms (chavela). Nat. Comput. 20(3), 377–394 (2021). https://doi.org/10.1007/s11047-021-09843-5MathSciNetCrossRef

33.

Montero, E., Riff, M.C.: Calibrating strategies for evolutionary algorithms. In: 2007 IEEE Congress on Evolutionary Computation. IEEE (2007)

34.

Montero, E., Riff, M.-C.: Self-calibrating strategies for evolutionary approaches that solve constrained combinatorial problems. In: An, A., Matwin, S., Raś, Z.W., Ślȩzak, D. (eds.) ISMIS 2008. LNCS (LNAI), vol. 4994, pp. 262–267. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68123-6_29

35.

Coelho, V.N., et al.: Hybrid self-adaptive evolution strategies guided by neighborhood structures for combinatorial optimization problems. Evol. Comput. 24(4), 637–666 (2016)CrossRef

36.

Fagan, D., Hemberg, E., Nicolau, M., O’Neill, M., McGarraghy, S.: Towards adaptive mutation in grammatical evolution. In: Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference Companion (GECCO Companion 2012). ACM Press (2012)

37.

Manzoni, L., Bartoli, A., Castelli, M., Goncalves, I., Medvet, E.: Specializing context-free grammars with a (1 + 1)-EA. IEEE Trans. Evol. Comput. 24(5), 960–973 (2020)CrossRef

38.

Tiso, S., Carvalho, P., Lourenço, N., Machado, P.: Structured mutation inspired by evolutionary theory enriches population performance and diversity. arXiv preprint arXiv:2302.00559 (2023)

39.

White, D.R., et al.: Better GP benchmarks: community survey results and proposals. Genet. Program. Evolvable Mach. 14(1), 3–29 (2012). https://doi.org/10.1007/s10710-012-9177-2MathSciNetCrossRef

40.

McDermott, J., et al.: Genetic programming needs better benchmarks. In: Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference (GECCO 2012), , pp. 791–798. ACM Press (2012)

41.

Harrison, D., Jr., Rubinfeld, D.L.: Hedonic housing prices and the demand for clean air. J. Environ. Econ. Manag. 5(1), 81–102 (1978)CrossRefMATH

Title: Context Matters: Adaptive Mutation for Grammars
Authors: Pedro Carvalho
Jessica Mégane
Nuno Lourenço
Penousal Machado
Publisher: Springer Nature Switzerland
Book: Genetic Programming
Print ISBN: 978-3-031-29572-0

Electronic ISBN: 978-3-031-29573-7

Copyright Year: 2023
DOI: https://doi.org/10.1007/978-3-031-29573-7_8

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