Skip to main content
Contribution to Book
Hierarchical knowledge in self-improving Grammar-Based Genetic Programming
Parallel Problem Solving from Nature: PPSN XIV: 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings
  • Pak-Kan WONG, The Chinese University of Hong Kong
  • Man Leung WONG, Lingnan University, Hong Kong
  • Kwong-Sak LEUNG, The Chinese University of Hong Kong
Document Type
Book chapter
Publication Date
  • Genetic Programming,
  • Hierarchical knowledge learning,
  • Estimation of distribution programming,
  • Adaptive grammar,
  • Bayesian network

Structure of a grammar can influence how well a Grammar-Based Genetic Programming system solves a given problem but it is not obvious to design the structure of a grammar, especially when the problem is large. In this paper, our proposed Bayesian Grammar-Based Genetic Programming with Hierarchical Learning (BGBGP-HL) examines the grammar and builds new rules on the existing grammar structure during evolution. Once our system successfully finds the good solution(s), the adapted grammar will provide a grammar-based probabilistic model to the generation process of optimal solution(s). Moreover, our system can automatically discover new hierarchical knowledge (i.e. how the rules are structurally combined) which composes of multiple production rules in the original grammar. In the case study using deceptive royal tree problem, our evaluation shows that BGBGP-HL achieves the best performance among the competitors while it is capable of composing hierarchical knowledge. Compared to other algorithms, search performance of BGBGP-HL is shown to be more robust against deceptiveness and complexity of the problem.

Publisher Statement
Copyright © Springer International Publishing AG 2016. Access to external full text or publisher's version may require subscription.
Additional Information

Paper presented at the 14th International Conference on Parallel Problem Solving from Nature (PPSN), Sep 17-21, 2016, Edinburgh, England.

ISBN of the source publication: 9783319458229

Full-text Version
Publisher’s Version
Citation Information
Wong, P.-K., Wong, M.-L. & Leung, K.-S. (2016). Hierarchical knowledge in self-improving Grammar-Based Genetic Programming. In J. Handl, E. Hart, P. R. Lewis, M. López-Ibáñez, G. Ochoa & B. Paechter (Eds.), Parallel problem solving from nature: PPSN XIV: 14th international conference, Edinburgh, UK, September 17-21, 2016, proceedings (pp. 270-280). Cham: Springer. doi: 10.1007/978-3-319-45823-6_25