Functional modularity for genetic programming

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.

REFERENCES

• 1: New Oxford American Dictionary. 2008.
• 2: P. J. Angeline and J. B. Pollack. The evolutionary induction of subroutines. In Proceedings of the Fourteenth Annual Conference of the Cognitive Science Society, pages 236--241, Bloomington, Indiana, USA, 1992. Lawrence Erlbaum.
• 3: W. Banzhaf, D. Banscherus, and P. Dittrich. Hierarchical genetic programming using local modules. Technical Report 50/98, University of Dortmund, Dortmund, Germany, 1998.
• 4: L. Beadle and C. Johnson. Semantically driven crossover in genetic programming. In J. Wang, editor, Proceedings of the IEEE World Congress on Computational Intelligence, pages 111--116, Hong Kong, 1-6 June 2008. IEEE Computational Intelligence Society, IEEE Press.
• 5: R. Dawkins. The Extended Phenotype : The Long Reach of the Gene. Oxford University Press, USA, August 1999.
• 6: Edwin D. de Jong , Richard A. Watson , Dirk Thierens, A generator for hierarchical problems, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C. [doi>10.1145/1102256.1102328]
• 7: Edwin D. de Jong , Richard A. Watson , Dirk Thierens, On the complexity of hierarchical problem solving, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068207]
• 8: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 9: Georges Raif Harik, Learning gene linkage to efficiently solve problems of bounded difficulty using genetic algorithms, University of Michigan, Ann Arbor, MI, 1997
• 10: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 11: M. Looks. Competent Program Evolution. Doctor of science, Washington University, St. Louis, USA, 11 Dec. 2006.
• 12: S. Luke. ECJ evolutionary computation system, 2002. (http://cs.gmu.edu/ eclab/projects/ecj/).
• 13: N. F. McPhee, B. Ohs, and T. Hutchison. Semantic building blocks in genetic programming. In M. O'Neill, L. Vanneschi, S. Gustafson, A. I. Esparcia Alcazar, I. De Falco, A. Della Cioppa, and E. Tarantino, editors, Proceedings of the 11th European Conference on Genetic Programming, EuroGP 2008, volume 4971 of Lecture Notes in Computer Science, pages 134--145, Naples, 26-28 Mar. 2008. Springer.
• 14: Justinian P. Rosca , Dana H. Ballard, Genetic Programming with Adaptive Representations, University of Rochester, Rochester, NY, 1994
• 15: J. A. Walker and J. F. Miller. The automatic acquisition, evolution and reuse of modules in cartesian genetic programming. IEEE Transactions on Evolutionary Computation, 12(4):397--417, Aug. 2008.
• 16: Richard A. Watson , Jordan B. Pollack, Compositional evolution: interdisciplinary investigations in evolvability, modularity, and symbiosis, Brandeis University, Waltham, MA, 2002
• 17: Richard A. Watson , Jordan B. Pollack, Modular Interdependency in Complex Dynamical Systems, Artificial Life, v.11 n.4, p.445-458, December 2005 [doi>10.1162/106454605774270589]
• 18: D. Wolpert and W. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67--82, 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Theory

Keywords:
genetic programming, modularity, problem decomposition