Evolvability in grammatical evolution
Authors:
Open Access
- 1 July 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 977-984
Abstract
Evolvability is a measure of the ability of an Evolutionary Algorithm (EA) to improve the fitness of an individual when applying a genetic operator. Other than the specific problem, many aspects of the EA may impact on the evolvability most notably the genetic operators and, if present, the genotype-phenotype mapping function. Grammatical Evolution (GE) is an EA in which the mapping function plays a crucial role since it allows to map any binary genotype into a program expressed in any user-provided language, defined by a context-free grammar. While GE mapping favored a successful application of GE to many different problems, it has also been criticized for scarcely adhering to the variational inheritance principle, which itself may hamper GE evolvability. In this paper, we experimentally study GE evolvability in different conditions, that is, problems, mapping functions, genotype sizes, and genetic operators. Results suggest that there is not a single factor determining GE evolvability: in particular, the mapping function alone does not deliver better evolvability regardless of the problem. Instead, GE redundancy, which itself is the result of the combined effect of several factors, has a strong impact on the evolvability.Keywords
Funding Information
- Engineering and Physical Sciences Research Council (EP/J017515/1)
This publication has 15 references indexed in Scilit:
- Benchmarking Grammar-Based Genetic Programming Algorithms2014
- On the Locality of Standard Search Operators in Grammatical Evolution2014
- A survey of techniques for characterising fitness landscapes and some possible ways forwardInformation Sciences, 2013
- On the roles of semantic locality of crossover in genetic programmingInformation Sciences, 2013
- Better GP benchmarks: community survey results and proposalsGenetic Programming and Evolvable Machines, 2012
- An Analysis of Genotype-Phenotype Maps in Grammatical EvolutionLecture Notes in Computer Science, 2010
- Positional Effect of Crossover and Mutation in Grammatical EvolutionLecture Notes in Computer Science, 2010
- Evolutionary computation2007
- On the Locality of Grammatical EvolutionLecture Notes in Computer Science, 2006
- On the Futility of Blind Search: An Algorithmic View of “No Free Lunch”Evolutionary Computation, 1998