Analysis of semantic modularity for genetic programming

• Autorzy: Krawiec K. , Wieloch B.
• Języki publikacji: EN

Abstrakty

EN

In this paper we analyze the properties of functional modularity, a concept introduced in [14] for detecting and measuring modularity in problems of automatic program synthesis, in particular by means of genetic programming. The basic components of functional modularity approach are subgoals - entities that embody module's semantic - and monotonicity, a measure for assessing subgoals' potential utility for searching for good modules. For a given subgoal and a sample of solutions decomposed into parts and contexts according to module definition, monotonicity measures the correlation of distance between semantics of solution's part and the fitness of the solution. The central tenet of this approach is that highly monotonous subgoals can be used to decompose the task and improve search convergence. In the experimental part we investigate the properties of functional modularity using eight instances of problems of Boolean function synthesis. The results show that monotonicity varies depending on problem's structure of modularity and correctly identifies good subgoals, potentially enabling automatic program decomposition.

Słowa kluczowe

EN

automatic program synthesis; modularity; problem decomposition; evolutionary computations; genetic programming

PL

synteza programowa automatyczna; modułowość; rozkład problemu; ewolucyjne obliczenia; programowanie genetyczne

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2009
• Tom: Vol. 34, No. 4
• Strony: 265--285
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Krawiec K.

autor

Wieloch B.

• Institute of Computing Science, Poznan University of Technology, Piotrowo, Poznań, Poland

Bibliografia

• [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] E. D. de Jong, R. A. Watson, and D. Thierens. A generator for hierarchical problems. In GECCO '05: Proceedings of the 2005 workshops on Genetic and evolutionary computation, pages 321-326, New York, NY, USA, 2005. ACM.
• [7] E. D. de Jong, R. A. Watson, and D. Thierens. On the complexity of hierarchical problem solving. In GECCO '05: Proceedings of the 2005 conference on Genetic and evolutionary computation, pages 1201-1208, New York, NY, USA, 2005. ACM.
• [8] D. Goldberg. Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading, 1989.
• [9] D. E. Goldberg. The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Norwell, MA, USA, 2002.
• [10] G. Harik. Learning Gene Linkage to Efficiently Solve Problems of Bounded Difficulty Using Genetic Algorithms. PhD thesis, University of Illinois at Urbana-Champaign, 1997.
• [11] J. Holland. Adaptation in natural and artificial systems, volume 1. University of Michigan Press, Ann Arbor, 1975.
• [12] J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.
• [13] J. R. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge Massachusetts, May 1994.
• [14] K. Krawiec and B. Wieloch. Functional modularity for genetic programming. In G. Raidl, F. Rothlauf, G. Squillero, R. Drechsler, T. Stuetzle, M. Birattari, C. B. Congdon, M. Middendorf, C. Blum, C. Cotta, P. Bosman, J. Gralil, J. Knowles, D. Corne, H.-G. Beyer, K. Stanley, J. F. Miller, J. van Hemert, T. Lenaerts, M. Ebner, J. Bacardit, M. O'Neill, M. Di Penta, B. Doerr, T. Jansen, R. Poli, and E. Alba, editors, GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 995-1002, Montreal, 8-12 July 2009. ACM.
• [15] M. Looks. Competent Program Evolution. Doctor of science, Washington University, St. Louis, USA, 11 Dec. 2006.
• [16] S. Luke. ECJ evolutionary computation system, 2002. (http://cs.gmu.edu/ eclab/projects/ecj /).
• [17] 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. Delia 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.
• [18] Z. Michalewicz. Genetic algorithms + data structures = evolution programs. Springer-Verlag, Berlin, 1994.
• [19] J. P. Rosea and D. H. Ballard. Genetic programming with adaptive representations. Technical Report TR 489, University of Rochester, Computer Science Department, Rochester, NY, USA, Feb. 1994.
• [20] 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.
• [21] R. Watson. Compositional Evolution: Interdisciplinary Investigations in Evolvability, Modularity, and Symbiosis. PhD thesis, Brandeis University, 2002.
• [22] R. A. Watson and J. B. Pollack. Modular interdependency in complex dynamical systems. Artif. Life, 11 (4):445-458, 2005.
• [23] D. Wolpert and W. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, l(l):67-82, 1997.