Genetic Programming Bias with Software Performance Analysis

Abstract

The complexities of modern software systems make their engineering costly and time consuming. This thesis explores and develops techniques to improve software by automating re-design. Source code can be randomly modified and subsequently tested for correctness to search for improvements in existing software. By iteratively selecting useful programs for modification a randomised search of program variants can be guided toward improved programs. Genetic Programming (GP) is a search algorithm which crucially relies on selection to guide the evolution of programs. Applying GP to software improvement represents a scalability challenge given the number of possible modification locations in even the smallest of programs.

The problem addressed in this thesis is locating performance improvements within programs. By randomly modifying a location within a program and measuring the change in performance and functionality we determine the probability of finding a performance improvement at that location under further modication.

Locating performance improvements can be performed during GP as GP relies on mutation. A probabilistic overlay of bias values for modification emerges as GP progresses and the software evolves. Measuring different aspects of program change can fine-tune the GP algorithm to focus on code which is particularly relevant to the measured aspect. Measuring execution cost reduction can indicate where an improvement is likely to exist and increase the chances of finding an improvement during GP.