Skip to main content
Kent Academic Repository

Evolving high-level imperative program trees with genetic programming

Castle, Thomas Anthony (2012) Evolving high-level imperative program trees with genetic programming. Doctor of Philosophy (PhD) thesis, University of Kent. (doi:10.22024/UniKent/01.02.86469) (KAR id:86469)

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.

Item Type: Thesis (Doctor of Philosophy (PhD))
Thesis advisor: Johnson, Colin G.
DOI/Identification number: 10.22024/UniKent/01.02.86469
Additional information: This thesis has been digitised by EThOS, the British Library digitisation service, for purposes of preservation and dissemination. It was uploaded to KAR on 09 February 2021 in order to hold its content and record within University of Kent systems. It is available Open Access using a Creative Commons Attribution, Non-commercial, No Derivatives (https://creativecommons.org/licenses/by-nc-nd/4.0/) licence so that the thesis and its author, can benefit from opportunities for increased readership and citation. This was done in line with University of Kent policies (https://www.kent.ac.uk/is/strategy/docs/Kent%20Open%20Access%20policy.pdf). If you feel that your rights are compromised by open access to this thesis, or if you would like more information about its availability, please contact us at ResearchSupport@kent.ac.uk and we will seriously consider your claim under the terms of our Take-Down Policy (https://www.kent.ac.uk/is/regulations/library/kar-take-down-policy.html).
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
SWORD Depositor: SWORD Copy
Depositing User: SWORD Copy
Date Deposited: 30 Oct 2019 13:53 UTC
Last Modified: 17 Dec 2022 15:23 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/86469 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.