Krzysztof Krawiec
ABSTRACT
We investigate semantic properties of linear programs, both internally, by analyzing the memory states they produce during execution, and externally, by inspecting program outcomes. The main concept of the formalism we propose is program trace, which reflects the behavior of program in semantic space. It allows us to characterize programming tasks in terms of traces of programs that solve them, and to propose certain measures that reveal their properties. We are primarily interested in measures that quantitatively characterize functional (semantic, behavioral) modularity of programming tasks. The experiments conducted on large samples of linear programs written in Push demonstrate that semantic structure varies from task to task, and reveal patterns of different forms of modularity. In particular, we identify interesting relationships between task modularity, task complexity, and program length, and conclude that a great share of programming tasks are modular.
- L. Altenberg. Modularity in evolution: Some low-level questions. In D. Rasskin-Gutman and W. Callebaut, editors, Modularity: Understanding the Development and Evolution of Complex Natural Systems, chapter 5, pages 99--128. MIT Press, Cambridge, MA, USA, June 2005.Google Scholar
- N. Kashtan and U. Alon. Spontaneous evolution of modularity and network motifs. Proceedings of the National Academy of Sciences, 102(39):13773--13778, Sept. 27 2005.Google ScholarCross Ref
- S. A. Kauffman. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, USA, 1 edition, June 1993.Google Scholar
- K. Krawiec and B. Wieloch. Analysis of semantic modularity for genetic programming. Foundations of Computing and Decision Sciences, 34(4):265--285, 2009.Google Scholar
- W. Langdon and R. Poli. Foundations of Genetic Programming. Springer-Verlag, 2002. Google ScholarDigital Library
- H. Majeed, C. Ryan, and R. M. A. Azad. Evaluating GP schema in context. In H.-G. Beyer et al., editors, GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, volume 2, pages 1773--1774, Washington DC, USA, 25-29 June 2005. ACM Press. Google ScholarDigital Library
- N. F. McPhee, B. Ohs, and T. Hutchison. Semantic building blocks in genetic programming. In M. O'Neill, L. Vanneschi, S. Gustafson, A. I. E. Alcázar, I. D. Falco, A. D. Cioppa, and E. Tarantino, editors, Genetic Programming, volume 4971 of LNCS, pages 134--145. Springer, 2008. Google ScholarDigital Library
- A. Moraglio. Geometry of evolutionary algorithms. In D. Whitley, editor, GECCO 2011 Tutorials, pages 1439--1468, Dublin, Ireland, 12-16 July 2011. ACM. Google ScholarDigital Library
- A. Moraglio, K. Krawiec, and C. Johnson. Geometric semantic genetic programming. In C. Igel, P. K. Lehre, and C. Witt, editors, The 5th workshop on Theory of Randomized Search Heuristics, ThRaSH'2011, Copenhagen, Denmark, July 8--9 2011.Google Scholar
- M. O'Neill, A. Brabazon, and E. Hemberg. Tracer spectrum: a visualisation method for distributed evolutionary computation. Genetic Programming and Evolvable Machines, 12(2):161--171, June 2011. Google ScholarDigital Library
- S. C. Roberts, D. Howard, and J. R. Koza. Evolving modules in genetic programming by subtree encapsulation. In J. F. Miller, M. Tomassini, P. L. Lanzi, C. Ryan, A. G. B. Tettamanzi, and W. B. Langdon, editors, Genetic Programming, Proceedings of EuroGP'2001, volume 2038 of LNCS, pages 160--175, Lake Como, Italy, 18-20 Apr. 2001. Springer-Verlag. Google ScholarDigital Library
- H. Simon. The Sciences of the Artificial. MIT Press, Cambridge, MA, 1969.Google ScholarDigital Library
- L. Spector, C. Perry, J. Klein, and M. Keijzer. Push 3.0 programming language description. Technical Report HC-CSTR-2004-02, School of Cognitive Science, Hampshire College, USA, 10 Sept. 2004.Google Scholar
- J. M. Swafford, E. Hemberg, M. O'Neill, M. Nicolau, and A. Brabazon. A non-destructive grammar modification approach to modularity in grammatical evolution. In N. Krasnogor et al., editors, GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation, pages 1411--1418, Dublin, Ireland, 12-16 July 2011. ACM. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- R. A. Watson. Compositional Evolution: The impact of Sex, Symbiosis and Modularity on the Gradualist Framework of Evolution, volume NA of Vienna series in theoretical biology. MIT Press, February 2006. Google ScholarDigital Library
Index Terms
- On relationships between semantic diversity, complexity and modularity of programming tasks
Recommendations
Semantic enrichment for medical ontologies
The Unified Medical Language System (UMLS) contains two separate but interconnected knowledge structures, the Semantic Network (upper level) and the Metathesaurus (lower level). In this paper, we have attempted to work out better how the use of such a ...
Tag-based modules in genetic programming
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computationIn this paper we present a new technique for evolving modular programs with genetic programming. The technique is based on the use of "tags" that evolving programs may use to label and later to refer to code fragments. Tags may refer inexactly, ...
Goal-oriented modularity in agent programming
AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systemsModularization is widely recognized as a central issue in software engineering. In this paper we address the issue of modularization in cognitive agent programming languages. We discuss existing approaches to modularity in cognitive agent programming. ...
Comments