Defining locality as a problem difficulty measure in genetic programming

Files in This Item:
File Description SizeFormat 
LocalityGP_Galvan2011-1.pdf3.39 MBAdobe PDFDownload
Title: Defining locality as a problem difficulty measure in genetic programming
Authors: Galván-López, Edgar
McDermott, James
O'Neill, Michael
Brabazon, Anthony
Permanent link:
Date: 2-Apr-2011
Abstract: A mapping is local if it preserves neighbourhood. In Evolutionary Computation, locality is generally described as the property that neighbouring genotypes correspond to neighbouring phenotypes. A representation has high locality if most genotypic neighbours are mapped to phenotypic neighbours. Locality is seen as a key element in performing effective evolutionary search. It is believed that a representation that has high locality will perform better in evolutionary search and the contrary is true for a representation that has low locality. When locality was introduced, it was the genotype-phenotype mapping in bitstring-based Genetic Algorithms which was of interest; more recently, it has also been used to study the same mapping in Grammatical Evolution. To our knowledge, there are few explicit studies of locality in Genetic Programming (GP). The goal of this paper is to shed some light on locality in GP and use it as an indicator of problem difficulty. Strictly speaking, in GP the genotype and the phenotype are not distinct. We attempt to extend the standard quantitative definition of genotype-phenotype locality to the genotype-fitness mapping by considering three possible definitions. We consider the effects of these definitions in both continuous- and discrete-valued fitness functions. We compare three different GP representations (two of them induced by using different function sets and the other using a slightly different GP encoding) and six different mutation operators. Results indicate that one definition of locality is better in predicting performance.
Funding Details: Science Foundation Ireland
Irish Research Council for Science, Engineering and Technology
Type of material: Journal Article
Publisher: Springer
Copyright (published version): 2011 Springer
Keywords: LocalityGenotype-phenotype mappingProblem hardnessGenetic programmingGenotype-fitness mapping
Subject LCSH: Evolutionary computation
Genetic programming (Computer science)
Gene mapping
DOI: 10.1007/s10710-011-9136-3
Language: en
Status of Item: Peer reviewed
Appears in Collections:Computer Science Research Collection
CASL Research Collection

Show full item record

Citations 10

Last Week
Last month
checked on Aug 17, 2018

Page view(s) 20

checked on May 25, 2018

Download(s) 20

checked on May 25, 2018

Google ScholarTM



This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.