Representation and structural biases in CGP
Authors:
- 1 May 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1089778X,p. 1064-1071
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 ldquoregularrdquo structures appear to be easier to evolve than more common ldquoirregularrdquo ones.Keywords
This publication has 10 references indexed in Scilit:
- Crossover Bias in Genetic Programming2007
- Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of GraphsJournal of Graph Algorithms and Applications, 2007
- Redundancy and computational efficiency in Cartesian genetic programmingIEEE Transactions on Evolutionary Computation, 2006
- Finding needles in haystacks is harder with neutrality2005
- RASCAL: Calculation of Graph Similarity using Maximum Common Edge SubgraphsThe Computer Journal, 2002
- Foundations of Genetic Programming2002
- On a relation between graph edit distance and maximum common subgraphPattern Recognition Letters, 1997
- A distance measure between attributed relational graphs for pattern recognitionIEEE Transactions on Systems, Man, and Cybernetics, 1983
- Backtrack search algorithms and the maximal common subgraph problemSoftware: Practice and Experience, 1982
- Individual Comparisons by Ranking MethodsBiometrics Bulletin, 1945