[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Learning Grammar Rules in Probabilistic Grammar-Based Genetic Programming

  • Conference paper
  • First Online:
Theory and Practice of Natural Computing (TPNC 2016)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10071))

Included in the following conference series:

  • 649 Accesses

Abstract

Grammar-based Genetic Programming (GBGP) searches for a computer program in order to solve a given problem. Grammar constrains the set of possible programs in the search space. It is not obvious to write an appropriate grammar for a complex problem. Our proposed Bayesian Grammar-Based Genetic Programming with Hierarchical Learning (BGBGP-HL) aims at automatically designing new rules from existing relatively simple grammar rules during evolution to improve the grammar structure. The new grammar rules also reflects the new understanding of the existing grammar under the given fitness evaluation function. Based on our case study in asymmetric royal tree problem, our evaluation shows that BGBGP-HL achieves the best performance among the competitors. Compared to other algorithms, search performance of BGBGP-HL is demonstrated to be more robust against dependencies and the changes in complexity of programs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Anthony, W.: Learning to discover rules by discovery. J. Educ. Psychol. 64(3), 325 (1973)

    Article  Google Scholar 

  2. Attias, H.: Inferring parameters and structure of latent variable models by variational bayes. In: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pp. 21–30. Morgan Kaufmann Publishers Inc. (1999)

    Google Scholar 

  3. Booth, T.L., Thompson, R.A.: Applying probability measures to abstract languages. Comput. IEEE Trans. 100(5), 442–450 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cooper, G.F., Herskovits, E.: A bayesian method for the induction of probabilistic networks from data. Mach. Learn. 9(4), 309–347 (1992)

    MATH  Google Scholar 

  5. Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the EM algorithm. J. Royal Stat. Soc. Series B (Methodological) 39, 1–38 (1977)

    MathSciNet  MATH  Google Scholar 

  6. Hasegawa, Y., Iba, H.: Estimation of bayesian network for program generation. In: Proceedings 3rd Asian-Pacific Workshop on Genetic Programming, p. 35 (2006)

    Google Scholar 

  7. Hasegawa, Y., Iba, H.: A bayesian network approach to program generation. IEEE Trans. Evol. Comput. 12(6), 750–764 (2008)

    Article  Google Scholar 

  8. Hasegawa, Y., Iba, H.: Latent variable model for estimation of distribution algorithm based on a probabilistic context-free grammar. IEEE Trans. Evol. Comput. 13(4), 858–878 (2009)

    Article  Google Scholar 

  9. Hasegawa, Y., Ventura, S.: Programming with annotated grammar estimation. In: Genetic Programming-New Approaches and Successful, pp. 49–74 (2012)

    Google Scholar 

  10. Kim, K., Shan, Y., Nguyen, X.H., McKay, R.I.: Probabilistic model building in genetic programming: A critical review. Genet. Program. Evolvable Mach. 15(2), 115–167 (2014)

    Article  Google Scholar 

  11. Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. MIT Press, Oxford (2009)

    MATH  Google Scholar 

  12. Koza, J.R.: Genetic Programming: vol. 1, On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)

    MATH  Google Scholar 

  13. Mckay, R.I., Hoai, N.X., Whigham, P.A., Shan, Y.: ONeill, M.: Grammar-based genetic programming: a survey. Genet. Program. Evol. Mach. 11(3–4), 365–396 (2010)

    Article  Google Scholar 

  14. O’Neill, M., Brabazon, A.: Grammatical differential evolution. In: IC-AI, pp. 231–236 (2006)

    Google Scholar 

  15. O’Neill, M., Ryan, C.: Grammatical evolution. IEEE Trans. Evol. Comput. 5(4), 349–358 (2001)

    Article  Google Scholar 

  16. O’Neill, M., Ryan, C.: Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Springer, Heidelberg (2003)

    Book  MATH  Google Scholar 

  17. O’Neill, M., Ryan, C.: Grammatical evolution by grammatical evolution: the evolution of grammar and genetic code. In: Keijzer, M., O’Reilly, U.-M., Lucas, S., Costa, E., Soule, T. (eds.) EuroGP 2004. LNCS, vol. 3003, pp. 138–149. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24650-3_13

    Chapter  Google Scholar 

  18. Punch, W.F.: How effective are multiple populations in genetic programming. Genet. Program. 98, 308–313 (1998)

    Google Scholar 

  19. Regolin, E.N., Pozo, A.T.R.: Bayesian automatic programming. In: Keijzer, M., Tettamanzi, A., Collet, P., Hemert, J., Tomassini, M. (eds.) EuroGP 2005. LNCS, vol. 3447, pp. 38–49. Springer, Heidelberg (2005). doi:10.1007/978-3-540-31989-4_4

    Chapter  Google Scholar 

  20. Sabar, N.R., Ayob, M., Kendall, G., Qu, R.: Grammatical evolution hyper-heuristic for combinatorial optimization problems. Evol. Comput. IEEE Trans. 17(6), 840–861 (2013)

    Article  Google Scholar 

  21. Salustowicz, R., Schmidhuber, J.: Probabilistic incremental program evolution. Evol. Comput. 5(2), 123–141 (1997)

    Article  Google Scholar 

  22. Sastry, K., Goldberg, D.E.: Probabilistic model building and competent genetic programming. In: Riolo, R., Worzel, B. (eds.) Genetic Programming Theory and Practice. Genetic Programming Series, vol. 6, pp. 205–220. Springer, Heidelberg (2003). doi:10.1007/978-1-4419-8983-3_13

    Chapter  Google Scholar 

  23. Tanev, I.: Incorporating learning probabilistic context-sensitive grammar in genetic programming for efficient evolution and adaptation of snakebot. In: Keijzer, M., Tettamanzi, A., Collet, P., Hemert, J., Tomassini, M. (eds.) EuroGP 2005. LNCS, vol. 3447, pp. 155–166. Springer, Heidelberg (2005). doi:10.1007/978-3-540-31989-4_14

    Chapter  Google Scholar 

  24. Whigham, P.A.: Grammatically-based genetic programming. In: Proceedings of the Workshop on Genetic Programming: from Theory to Real-World Applications. vol. 16, pp. 33–41 (1995)

    Google Scholar 

  25. Wong, M.L., Leung, K.S.: Applying logic grammars to induce sub-functions in genetic programming. In: IEEE International Conference on Evolutionary Computation, 1995, vol. 2, pp. 737–740. IEEE (1995)

    Google Scholar 

  26. Wong, P.K., Lo, L.Y., Wong, M.L., Leung, K.S.: Grammar-based genetic programming with dependence learning and bayesian network classifier. In: Proceedings of GECCO 2014, pp. 959–966. ACM (2014)

    Google Scholar 

Download references

Acknowledgments

This research is supported by General Research Fund LU310111 from the Research Grant Council of the Hong Kong Special Administrative Region and the Lingnan University Direct Grant DR16A7.

Author information

Authors and Affiliations

  1. The Chinese University of Hong Kong, Sha Tin, Hong Kong

    Pak-Kan Wong

  2. Lingnan University, Tuen Mun, Hong Kong

    Man-Leung Wong

  3. The Chinese University of Hong Kong, Sha Tin, Hong Kong

    Kwong-Sak Leung

Authors
  1. Pak-Kan Wong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Man-Leung Wong
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kwong-Sak Leung
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pak-Kan Wong .

Editor information

Editors and Affiliations

  1. Rovira i Virgili University, Tarragona, Spain

    Carlos Martín-Vide

  2. Tohoku University, Sendai, Japan

    Takaaki Mizuki

  3. University of Extremadura, Cáceres, Spain

    Miguel A. Vega-Rodríguez

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing AG

About this paper

Cite this paper

Wong, PK., Wong, ML., Leung, KS. (2016). Learning Grammar Rules in Probabilistic Grammar-Based Genetic Programming. In: Martín-Vide, C., Mizuki, T., Vega-Rodríguez, M. (eds) Theory and Practice of Natural Computing. TPNC 2016. Lecture Notes in Computer Science(), vol 10071. Springer, Cham. https://doi.org/10.1007/978-3-319-49001-4_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-49001-4_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-49000-7

  • Online ISBN: 978-3-319-49001-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics