|Authors||D. White, A. Arcuri and J. Clark|
|Title||Evolutionary Improvement of Programs|
|Afilliation||Software Engineering, Software Engineering|
|Publication Type||Journal Article|
|Year of Publication||2009|
|Journal||IEEE Transactions on Evolutionary Computation|
Most applications of Genetic Programming (GP) involve the creation of an entirely new function, program or expression to solve a specific problem. In this paper we propose a new approach that applies GP to improve existing software by optimising its nonfunctional properties such as execution time, memory usage or power consumption. In general, satisfying non-functional requirements is a difficult task and often achieved in part by optimising compilers. However, modern compilers are in general not always able to produce semantically equivalent alternatives that optimise non-functional properties, even if such alternatives are known to exist: this is usually due to the limited local nature of such optimisations. In this paper we discuss how best to combine and extend the existing evolutionary methods of GP, Multi-Objective Optimisation and coevolution in order to improve existing software. Given as input the implementation of a function, we attempt to evolve a semantically equivalent version, in this case optimised to reduce execution time subject to a given probability distribution of inputs. We demonstrate that our framework is able to produce non-obvious optimisations that compilers are not yet able to generate on eight example functions. We employ a coevolved population of test cases to encourage the preservation of the function's semantics. We exploit the original program both through seeding of the population in order to focus the search, and as an oracle for testing purposes. As well as discussing the issues that arise when attempting to improve software, we employ rigorous experimental method to provide interesting and practical insights to suggest how to address these issues.