Modularity Metrics for Genetic Programming

With improvements in selection methods and genetic operators, Genetic Programming (GP) has been able to solve many software synthesis problems. However, so far, the primary focus of GP has been on improving success rates (fraction of the runs that succeeds in finding a solution). Less attention has been paid to other important characteristics and quality measures of human-written programs. One such quality measure is modularity. Since the introduction of Automatically Defined Functions (ADFs) by John Koza, most of efforts involving modularity in GP have been directed towards pre-programming modularity into the GP system, rather than measuring it for evolved programs. Modularity has played a central role in evolutionary biology. To study its effects on the evolution of software, however, we need a quantitative formulation of modularity. In this paper, we present two platform-independent modularity metrics, namely, reuse and repetition, that make use of the information contained in the execution traces of the programs. We describe the process of calculating these metrics for any evolved program, using problems that have been solved with the PushGP system as examples. We also discuss some mechanisms for integrating these metrics into the evolution framework itself.