In this paper we introduce, formalize, and experimentally validate a novel concept of functional modularity for Genetic Programming (GP). We rely on module definition that is most natural for GP: a piece of program code (subtree). However, as opposed to syntax-based approaches that abstract from the actual computation performed by a module, we analyze also its semantic using a set of fitness cases. In particular, the central notion of this approach is subgoal, an entity that embodies module's desired semantic and is used to evaluate module candidates. As the cardinality of the space of all subgoals is exponential with respect to the number of fitness cases, we introduce monotonicity to assess subgoals' potential utility for searching for good modules. For a given subgoal and a sample of modules, monotonicity measures the correlation of subgoal's distance from module's semantics and the fitness of the solution the module is part of. In the experimental part we demonstrate how these concepts may be used to describe and quantify the modularity of two simple problems of Boolean function synthesis. In particular, we conclude that monotonicity usefully differentiates two problems with different nature of modularity, allows us to tell apart the useful subgoals from the other ones, and may be potentially used for problem decomposition and enhance the efficiency of evolutionary search. #2009GECCOModulesBib
@INPROCEEDINGS { 2009GECCOModules,
ABSTRACT = { In this paper we introduce, formalize, and experimentally validate a novel concept of functional modularity for Genetic Programming (GP). We rely on module definition that is most natural for GP: a piece of program code (subtree). However, as opposed to syntax-based approaches that abstract from the actual computation performed by a module, we analyze also its semantic using a set of fitness cases. In particular, the central notion of this approach is subgoal, an entity that embodies module's desired semantic and is used to evaluate module candidates. As the cardinality of the space of all subgoals is exponential with respect to the number of fitness cases, we introduce monotonicity to assess subgoals' potential utility for searching for good modules. For a given subgoal and a sample of modules, monotonicity measures the correlation of subgoal's distance from module's semantics and the fitness of the solution the module is part of. In the experimental part we demonstrate how these concepts may be used to describe and quantify the modularity of two simple problems of Boolean function synthesis. In particular, we conclude that monotonicity usefully differentiates two problems with different nature of modularity, allows us to tell apart the useful subgoals from the other ones, and may be potentially used for problem decomposition and enhance the efficiency of evolutionary search. },
ADDRESS = { Montreal },
AUTHOR = { Krzysztof Krawiec and Bartosz Wieloch },
BIBSOURCE = { DBLP, http://dblp.uni-trier.de },
BOOKTITLE = { GECCO 09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation },
COMMENT = { ProjectELP },
EDITOR = { Guenther Raidl and Franz Rothlauf and Giovanni Squillero and Rolf Drechsler and Thomas Stuetzle and Mauro Birattari and Clare Bates Congdon and Martin Middendorf and Christian Blum and Carlos Cotta and Peter Bosman and Joern Grahl and Joshua Knowles and David Corne and Hans-Georg Beyer and Ken Stanley and Julian F. Miller and Jano {van Hemert} and Tom Lenaerts and Marc Ebner and Jaume Bacardit and Michael O'Neill and Massimiliano {Di Penta} and Benjamin Doerr and Thomas Jansen and Riccardo Poli and Enrique Alba },
ISBN13 = { 978-1-60558-325-9 },
KEYWORDS = { genetic algorithms, genetic programming },
MONTH = { {8-12 } # jul },
NOTES = { GECCO-2009 A joint meeting of the eighteenth international conference on genetic algorithms (ICGA-2009) and the fourteenth annual genetic programming conference (GP-2009). ACM Order Number 910092. },
ORGANISATION = { SigEvo },
PAGES = { 995--1002 },
PUBLISHER = { ACM },
PUBLISHER_ADDRESS = { New York, NY, USA },
TITLE = { Functional modularity for genetic programming },
URL = { http://doi.acm.org/10.1145/1569901.1570037 },
YEAR = { 2009 },
1 = { http://doi.acm.org/10.1145/1569901.1570037 },
}