Learning grammar rules in probabilistic Grammar-based Genetic Programming

Pak-Kan WONG, Man Leung WONG, Kwong-Sak LEUNG

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

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.
Original languageEnglish
Title of host publicationTheory and practice of natural computing : 5th international conference, TPNC 2016, Sendai, Japan, December 12-13, 2016, proceedings
PublisherSpringer
Pages208-220
Number of pages13
ISBN (Print)9783319490007
DOIs
Publication statusPublished - 1 Jan 2016

Fingerprint

Genetic programming
Function evaluation
Computer program listings

Bibliographical note

Paper presented at the 5th International Conference on the Theory and Practice of Natural Computing (TPNC), Dec 12-13, 2016, Sendai, Japan.

Keywords

  • Adaptive grammar
  • Bayesian network
  • Estimation of distribution programming
  • Genetic programming

Cite this

WONG, P-K., WONG, M. L., & LEUNG, K-S. (2016). Learning grammar rules in probabilistic Grammar-based Genetic Programming. In Theory and practice of natural computing : 5th international conference, TPNC 2016, Sendai, Japan, December 12-13, 2016, proceedings (pp. 208-220). Springer. https://doi.org/10.1007/978-3-319-49001-4_17
WONG, Pak-Kan ; WONG, Man Leung ; LEUNG, Kwong-Sak. / Learning grammar rules in probabilistic Grammar-based Genetic Programming. Theory and practice of natural computing : 5th international conference, TPNC 2016, Sendai, Japan, December 12-13, 2016, proceedings. Springer, 2016. pp. 208-220
@inproceedings{24783be06bb0418db882e30eb57f01f3,
title = "Learning grammar rules in probabilistic Grammar-based Genetic Programming",
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.",
keywords = "Adaptive grammar, Bayesian network, Estimation of distribution programming, Genetic programming",
author = "Pak-Kan WONG and WONG, {Man Leung} and Kwong-Sak LEUNG",
note = "Paper presented at the 5th International Conference on the Theory and Practice of Natural Computing (TPNC), Dec 12-13, 2016, Sendai, Japan.",
year = "2016",
month = "1",
day = "1",
doi = "10.1007/978-3-319-49001-4_17",
language = "English",
isbn = "9783319490007",
pages = "208--220",
booktitle = "Theory and practice of natural computing : 5th international conference, TPNC 2016, Sendai, Japan, December 12-13, 2016, proceedings",
publisher = "Springer",

}

WONG, P-K, WONG, ML & LEUNG, K-S 2016, Learning grammar rules in probabilistic Grammar-based Genetic Programming. in Theory and practice of natural computing : 5th international conference, TPNC 2016, Sendai, Japan, December 12-13, 2016, proceedings. Springer, pp. 208-220. https://doi.org/10.1007/978-3-319-49001-4_17

Learning grammar rules in probabilistic Grammar-based Genetic Programming. / WONG, Pak-Kan; WONG, Man Leung; LEUNG, Kwong-Sak.

Theory and practice of natural computing : 5th international conference, TPNC 2016, Sendai, Japan, December 12-13, 2016, proceedings. Springer, 2016. p. 208-220.

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

TY - GEN

T1 - Learning grammar rules in probabilistic Grammar-based Genetic Programming

AU - WONG, Pak-Kan

AU - WONG, Man Leung

AU - LEUNG, Kwong-Sak

N1 - Paper presented at the 5th International Conference on the Theory and Practice of Natural Computing (TPNC), Dec 12-13, 2016, Sendai, Japan.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

KW - Adaptive grammar

KW - Bayesian network

KW - Estimation of distribution programming

KW - Genetic programming

UR - http://commons.ln.edu.hk/sw_master/5493

U2 - 10.1007/978-3-319-49001-4_17

DO - 10.1007/978-3-319-49001-4_17

M3 - Conference paper (refereed)

SN - 9783319490007

SP - 208

EP - 220

BT - Theory and practice of natural computing : 5th international conference, TPNC 2016, Sendai, Japan, December 12-13, 2016, proceedings

PB - Springer

ER -

WONG P-K, WONG ML, LEUNG K-S. Learning grammar rules in probabilistic Grammar-based Genetic Programming. In Theory and practice of natural computing : 5th international conference, TPNC 2016, Sendai, Japan, December 12-13, 2016, proceedings. Springer. 2016. p. 208-220 https://doi.org/10.1007/978-3-319-49001-4_17