Abstract:

An evolutionary algorithm automatically discovers suitable solutions to a problem, which may lie anywhere in a large search space of candidate solutions. In the case of Genetic Programming, this means performing an efficient search of all possible computer programs represented as trees. Exploration of the search space appears to be constrained by structural mechanisms that exist in Genetic Programming as a consequence of using trees to represent solutions. As a result, programs with certain structures are more likely to be evolved, and others extremely unlikely.

We investigate whether the graph representation used in Cartesian Genetic Programming causes an analogous biasing effect, imposing natural limitations on the class of solution structures that are likely to be evolved. Representation bias and structural bias are identified: the rarer "regular" structures appear to be easier to evolve than more common "irregular" ones.

@inproceedings(SS-CEC09-cgp,
  author = "Andrew J. Payne and Susan Stepney",
  title = "Representation and Structural biases in {CGP}",
  pages = "1064-1071",
  crossref = "CEC09"
)

@proceedings(CEC09,
  title = "CEC 2009, Trondheim, Norway, May 2009",
  booktitle = "CEC 2009, Trondheim, Norway, May 2009",
  publisher = "IEEE Press",
  year = 2009
)