Top

Published in:

2021 | OriginalPaper | Chapter

Getting a Head Start on Program Synthesis with Genetic Programming

Authors : Jordan Wick, Erik Hemberg, Una-May O’Reilly

Published in: Genetic Programming

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

We explore how to give Genetic Programming (GP) a head start to synthesize a programming problem. Our method uses a related problem and introduces a schedule that directs GP to solve the related problem first either fully or to some extent first, or at the same time. In addition, if the related problem’s solutions are written by students or evolved by GP, we explore the extent to which initializing the GP population with some of these solutions provides a head start. We find that having a population solve one programming problem before working to solve a related programming problem helps to a greater extent as the targeted problems and the intermediate problems themselves are selected to be more challenging.

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 Mining Feature Relationships in Data

Agapitos, A., Lucas, S.M.: Learning recursive functions with object oriented genetic programming. In: Collet, P., Tomassini, M., Ebner, M., Gustafson, S., Ekárt, A. (eds.) EuroGP 2006. LNCS, vol. 3905, pp. 166–177. Springer, Heidelberg (2006). https://doi.org/10.1007/11729976_15CrossRef

Arcuri, A., White, D.R., Clark, J., Yao, X.: Multi-objective improvement of software using co-evolution and smart seeding. In: Li, X., et al. (eds.) SEAL 2008. LNCS, vol. 5361, pp. 61–70. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89694-4_7CrossRef

Bajwa, A., Bell, A., Hemberg, E., O’Reilly, U.M.: Analyzing student code trajectories in an introductory programming MOOC. In: 2019 IEEE Learning With MOOCS (LWMOOCS), pp. 53–58. IEEE (2019)

Bengio, Y., Louradour, J., Collobert, R., Weston, J.: Curriculum learning. In: Proceedings of the 26th Annual International Conference on Machine Learning, pp. 41–48 (2009)

Bladek, I., Krawiec, K.: Simultaneous synthesis of multiple functions using genetic programming with scaffolding. In: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion, pp. 97–98 (2016)

Dempsey, I., O’Neill, M., Brabazon, A.: Foundations in Grammatical Evolution for Dynamic Environments, vol. 194. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00314-1CrossRef

Fenton, M., McDermott, J., Fagan, D., Forstenlechner, S., Hemberg, E., O’Neill, M.: PonyGE2: grammatical evolution in Python. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 1194–1201 (2017)

Gerules, G., Janikow, C.: A survey of modularity in genetic programming. In: 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 5034–5043. IEEE (2016)

Helmuth, T., Pantridge, E., Woolson, G., Spector, L.: Transfer learning of genetic programming instruction sets. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, pp. 241–242 (2020)

10.

Helmuth, T., Spector, L.: Detailed problem descriptions for general program synthesis benchmark suite. School of Computer Science, University of Massachusetts Amherst, Technical report (2015)

11.

Helmuth, T., Spector, L.: General program synthesis benchmark suite. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 1039–1046. ACM (2015)

12.

Hemberg, E., Kelly, J., O’Reilly, U.M.: On domain knowledge and novelty to improve program synthesis performance with grammatical evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1039–1046 (2019)

13.

Hoang, T.H., Essam, D., McKay, R.I.B., Hoai, N.X.: Developmental evaluation in genetic programming: the TAG-based frame work. Int. J. Knowl.-Based Intell. Eng. Syst. 12(1), 69–82 (2008). https://doi.org/10.3233/KES-2008-12106. http://content.iospress.com/articles/international-journal-of-knowledge-based-and-intelligent-engineering-systems/kes00142CrossRef

14.

Jaśkowski, W., Krawiec, K., Wieloch, B.: Multitask visual learning using genetic programming. Evol. Comput. 16(4), 439–459 (2008)CrossRef

15.

Kelly, J., Hemberg, E., O’Reilly, U.-M.: Improving genetic programming with novel exploration - exploitation control. In: Sekanina, L., Hu, T., Lourenço, N., Richter, H., García-Sánchez, P. (eds.) EuroGP 2019. LNCS, vol. 11451, pp. 64–80. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-16670-0_5CrossRef

16.

Koza, J.R.: Evolution of subsumption using genetic programming. In: Proceedings of the First European Conference on Artificial Life, pp. 110–119 (1992)

17.

Krawiec, K.: Behavioral Program Synthesis with Genetic Programming, vol. 618. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-27565-9CrossRef

18.

Krawiec, K., Wieloch, B.: Functional modularity for genetic programming. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 995–1002 (2009)

19.

Krawiec, K., Wieloch, B.: Automatic generation and exploitation of related problems in genetic programming. In: IEEE Congress on Evolutionary Computation, pp. 1–8. IEEE (2010)

20.

Langdon, W.B., Nordin, J.P.: Seeding genetic programming populations. In: Poli, R., Banzhaf, W., Langdon, W.B., Miller, J., Nordin, P., Fogarty, T.C. (eds.) EuroGP 2000. LNCS, vol. 1802, pp. 304–315. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-540-46239-2_23CrossRef

21.

Lopez, U., Trujillo, L., Silva, S., Vanneschi, L., Legrand, P.: Unlabeled multi-target regression with genetic programming. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 976–984 (2020)

22.

Lucas, S.M.: Exploiting reflection in object oriented genetic programming. In: Keijzer, M., O’Reilly, U.-M., Lucas, S., Costa, E., Soule, T. (eds.) EuroGP 2004. LNCS, vol. 3003, pp. 369–378. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24650-3_35CrossRef

23.

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

24.

Ryan, C., Keijzer, M., Cattolico, M.: Favourable biasing of function sets using run transferable libraries. In: O’Reilly, U.M., Yu, T., Riolo, R., Worzel, B. (eds.) Genetic Programming Theory and Practice II. Genetic Programming, pp. 103–120. Springer, Boston (2005). https://doi.org/10.1007/0-387-23254-0_7CrossRef

25.

Sasanka, R., Krommydas, K.: An evolutionary framework for automatic and guided discovery of algorithms. arXiv preprint arXiv:1904.02830 (2019)

26.

Scott, E.O., De Jong, K.A.: Automating knowledge transfer with multi-task optimization. In: 2019 IEEE Congress on Evolutionary Computation (CEC), pp. 2252–2259. IEEE (2019)

27.

Soderlund, J., Vickers, D., Blair, A.: Parallel hierarchical evolution of string library functions. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 281–291. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_26CrossRef

28.

Tanev, I., Kuyucu, T., Shimohara, K.: GP-induced and explicit bloating of the seeds in incremental GP improves evolutionary success. Genet. Program. Evolvable Mach. 15(1), 37–60 (2014). https://doi.org/10.1007/s10710-013-9192-yCrossRef

29.

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

30.

Thrun, S.: Explanation-Based Neural Network Learning. Springer, Boston (1996). https://doi.org/10.1007/978-1-4613-1381-6CrossRefMATH

31.

Wan, M., Weise, T., Tang, K.: Novel loop structures and the evolution of mathematical algorithms. In: Silva, S., Foster, J.A., Nicolau, M., Machado, P., Giacobini, M. (eds.) EuroGP 2011. LNCS, vol. 6621, pp. 49–60. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20407-4_5CrossRef

32.

Henrik Westerberg, C., Levine, J.: Investigation of different seeding strategies in a genetic planner. In: Boers, E.J.W. (ed.) EvoWorkshops 2001. LNCS, vol. 2037, pp. 505–514. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45365-2_52CrossRefMATH

33.

Yu, T., Clack, C.: Recursion, lambda-abstractions and genetic programming. In: Poli, R., Langdon, W.B., Schoenauer, M., Fogarty, T., Banzhaf, W. (eds.) Late Breaking Papers at EuroGP 1998: the First European Workshop on Genetic Programming, pp. 26–30. CSRP-98-10, The University of Birmingham, UK, Paris, France, 14–15 April 1998

34.

Zheng, X., Qin, A., Gong, M., Zhou, D.: Self-regulated evolutionary multi-task optimization. IEEE Trans. Evol. Comput. 24, 16–28 (2019) CrossRef

Title: Getting a Head Start on Program Synthesis with Genetic Programming
Authors: Jordan Wick
Erik Hemberg
Una-May O’Reilly
Publisher: Springer International Publishing
Book: Genetic Programming
Print ISBN: 978-3-030-72811-3

Electronic ISBN: 978-3-030-72812-0

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-72812-0_17

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