Online progress in search and optimization is often hindered by neutrality in the fitness landscape, when many genotypes map to the same fitness value. We propose a method for imposing a gradient on the fitness function of a metaheuristic (in this case, Genetic Programming) via a metric (Minimum Description Length) induced from patterns detected in the trajectory of program execution. These patterns are induced via a decision tree classifier. We apply this method to a range of integer and boolean-valued problems, significantly outperforming the standard approach. The method is conceptually straightforward and applicable to virtually any metaheuristic that can be appropriately instrumented.
@INPROCEEDINGS { Krawiec:2013:PGP:2463372.2463496,
ABSTRACT = { Online progress in search and optimization is often hindered by neutrality in the fitness landscape, when many genotypes map to the same fitness value. We propose a method for imposing a gradient on the fitness function of a metaheuristic (in this case, Genetic Programming) via a metric (Minimum Description Length) induced from patterns detected in the trajectory of program execution. These patterns are induced via a decision tree classifier. We apply this method to a range of integer and boolean-valued problems, significantly outperforming the standard approach. The method is conceptually straightforward and applicable to virtually any metaheuristic that can be appropriately instrumented. },
ACMID = { 2463496 },
ADDRESS = { New York, NY, USA },
AUTHOR = { Krawiec, Krzysztof and Swan, Jerry },
BOOKTITLE = { Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference },
DOI = { 10.1145/2463372.2463496 },
ISBN = { 978-1-4503-1963-8 },
KEYWORDS = { genetic programming, mdl, neutrality, program trace, push },
LOCATION = { Amsterdam, The Netherlands },
NUMPAGES = { 8 },
PAGES = { 949--956 },
PUBLISHER = { ACM },
SERIES = { GECCO '13 },
TITLE = { Pattern-guided genetic programming },
URL = { http://doi.acm.org/10.1145/2463372.2463496 },
YEAR = { 2013 },
1 = { http://doi.acm.org/10.1145/2463372.2463496 },
2 = { https://doi.org/10.1145/2463372.2463496 },
}