An investigation into the use of genetic programming for the induction of novice procedural programming solution algorithms in intelligent programming tutors.

Abstract

Intelligent programming tutors have proven to be an economically viable and effective means of assisting novice programmers overcome learning difficulties. However, the large-scale use of intelligent programming tutors has been impeded by the high developmental costs associated with building intelligent programming tutors. The research presented in this thesis forms part of a larger initiative aimed at reducing these costs by building a generic architecture for the development of intelligent programming tutors. One of the facilities that must be provided by the generic architecture is the automatic generation of solutions to programming problems. The study presented in the thesis examines the use of genetic programming as means of inducing solution algorithms to novice programming problems. The scope of the thesis is limited to novice procedural programming paradigm problems requiring the use of arithmetic, string manipulation, conditional, iterative and recursive programming structures. The methodology employed in the study is proof-by-demonstration. A genetic programming system for the induction of novice procedural solution algorithms was implemented and tested on randomly chosen novice procedural programming problems. The study has identified the standard and advanced genetic programming features needed for the successful generation of novice procedural solution algorithms. The outcomes of this study include the derivation of an internal representation language for representing procedural solution algorithms and a high-level programming problem specification format for describing procedural problems, in the generic architecture. One of the limitations of genetic programming is its susceptibility to converge prematurely to local optima and not find a solution in some cases. The study has identified fitness function biases against certain structural components that are needed to find a solution, as an additional cause of premature convergence in this domain. It presents an iterative structure-based algorithm as a solution to this problem. This thesis has contributed to both the fields of genetic programming and intelligent programming tutors. While genetic programming has been successfully implemented in various domains, it is usually applied to a single problem within that domain. In this study the genetic programming system must be capable of solving a number of different programming problems in different application domains. In addition to this, the study has also identified a means of overcoming premature convergence caused by fitness function biases in a genetic programming system for the induction of novice procedural programming algorithms. Furthermore, although a number of studies have addressed the student modelling and pedagogical aspects of intelligent programming tutors, none have examined the automatic generation of problem solutions as a means of reducing developmental costs. Finally, this study has contributed to the ongoing research being conducted by the artificial intelligence in education community, to test the effectiveness of using machine learning techniques in the development of different aspects of intelligent tutoring systems.