Recursion-Based Biases in Stochastic Grammar Model Genetic Programming

Kangil Kim, R. I. Bob McKay, Nguyen Xuan Hoai

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

The estimation of distribution algorithms (EDAs) applied to genetic programming (GP) have been studied by a number of authors. Like all EDAs, they suffer from biases induced by the model building and sampling process. However, the biases are amplified in the algorithms for GP. In particular, many systems use stochastic grammars as their model representation, but biases arise due to grammar recursion. We define and estimate the bias due to recursion in grammar-based EDAs in GP, using methods derived from computational linguistics. We confirm the extent of bias in some simple experimental examples. We then propose some methods to repair this bias. We apply the estimation of bias, and its repair, to some more practical applications. We experimentally demonstrate the extent of bias arising from recursion, and the performance improvements that can result from correcting it.

Original languageEnglish
Article number7091890
Pages (from-to)81-95
Number of pages15
JournalIEEE Transactions on Evolutionary Computation
Volume20
Issue number1
DOIs
Publication statusPublished - Feb 2016
Externally publishedYes

Fingerprint

Dive into the research topics of 'Recursion-Based Biases in Stochastic Grammar Model Genetic Programming'. Together they form a unique fingerprint.

Cite this