Evolving High-Level Imperative Program Trees with Genetic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.3963

  author =       "Thomas Anthony Castle",
  title =        "Evolving High-Level Imperative Program Trees with
                 Genetic Programming",
  school =       "University of Kent",
  year =         "2012",
  type =         "PhD Thesis",
  address =      "UK",
  month =        jun,
  keywords =     "genetic algorithms, genetic programming, SBSE, STGP,
                 Verification, local variables, loops, software metrics,
                 computer programming",
  URL =          "http://kar.kent.ac.uk/34799/",
  URL =          "http://kar.kent.ac.uk/34799/1/thesis.pdf",
  URL =          "http://ethos.bl.uk/OrderDetails.do?did=48&uin=uk.bl.ethos.580157",
  owner =        "Yuanyuan",
  timestamp =    "2013.10.10",
  category =     "Software/Program Verification",
  country =      "UK",
  size =         "106 pages",
  abstract =     "Genetic Programming (GP) is a technique which uses an
                 evolutionary metaphor to automatically generate
                 computer programs. Although GP proclaims to evolve
                 computer programs, historically it has been used to
                 produce code which more closely resembles mathematical
                 formulae than the well structured programs that modern
                 programmers aim to produce. The objective of this
                 thesis is to explore the use of GP in generating
                 high-level imperative programs and to present some
                 novel techniques to progress this aim.

                 A novel set of extensions to Montana's Strongly Typed
                 Genetic Programming system are presented that provide a
                 mechanism for constraining the structure of program
                 trees. It is demonstrated that these constraints are
                 sufficient to evolve programs with a naturally
                 imperative structure and to support the use of many
                 common high-level imperative language constructs such
                 as loops. Further simple algorithm modifications are
                 made to support additional constructs, such as variable
                 declarations that create new limited-scope variables.
                 Six non-trivial problems, including sorting and the
                 general even parity problem, are used to experimentally
                 compare the performance of the systems and
                 configurations proposed.

                 Software metrics are widely used in the software
                 engineering process for many purposes, but are largely
                 unused in GP. A detailed analysis of evolved programs
                 is presented using seven different metrics, including
                 cyclomatic complexity and Halstead's program effort.
                 The relationship between these metrics and a program's
                 fitness and evaluation time is explored. It is
                 discovered that these metrics are poorly suited for
                 application to improve GP performance, but other
                 potential uses are proposed.",
  notes =        "Yuanyuan Zhang Thu, Oct 10, 2013 at 12:34 PM

                 3.4.1 Factorial, 3.4.2 Fibonacci, 3.4.3 Even-n-parity,
                 3.4.4 Reverse List, 3.4.5 Sort List, 3.4.6

                 6.4.2 Program Tree Length, 6.4.3 Program Tree Depth,
                 6.4.4 Number of Statements, 6.4.5 Cyclomatic
                 Complexity, 6.4.6 Halstead's Effort, 6.4.7 Prather's
                 Measure \mu, 6.4.8 NPATH Complexity

                 p150-151 'Our results confirmed previous findings that
                 many complexity metrics correlate highly with program
                 size and there was also high correlation with each
                 other, suggesting that they are measuring similar
                 properties. Little consistency was seen in the trends
                 between the complexity metrics and the fitness. It was
                 concluded that the complexity metrics used in this
                 study do not have qualities that would make them
                 suitable for applications to improve fitness or
                 evaluation time in GP.'


Genetic Programming entries for Tom Castle