Refactoring and Neutrality in Genetic Programming

Lead Research Organisation: University of Kent
Department Name: Sch of Computing

Abstract

Computer programming is difficult. Despite many years of experience, certain problems are very difficult for programmers to solve. To address this, researchers have developed methods where computers automatically create program code from a description of the problem to be solved. One of the most popular forms of automated program creation is called Genetic Programming (GP). In GP, a population of potential solutions is created, tested on the problem, and a new population created by processes inspired by biological evolution, such as genetic mutation and the crossover of genes between individuals. This process is repeated until an effective program is found.GP has proven effective in a number of areas: GP systems have created programs that are as good or better than those created by human programmers in a number of areas, such as robot control, bio-medical data analysis, and the design of electronic circuits. It has been applied in real-world technologies such as the design of antennas for satellites, the analysis of currency markets, improving the design of chemical engineering systems, and the detection of unexploded devices such as landmines. The aim of this project is to make GP more effective by including in the evolutionary process a technique that has risen to prominence in human-based software engineering, known as refactoring. Refactoring means changing the structure of computer programs without changing what they actually do. This is important in the development of software because it means that programs can be simplified and their structure made clearer before programmers work on changing the behaviour. By separating out these two aspects, the programming process is made clearer. These techniques have not been systematically applied to GP in the past.An important reason why this idea is likely to succeed is because it has already been shown that something called neutrality is important for evolution. Neutrality means that there are many more possible genes than there are proteins that can be created by those genes, and therefore one protein can be encoded for by many genes. During evolutionary history, many of the changes that occur are these neutral changes-changes to the genetic encoding, rather than the behaviour that results from that encoding. As part of the project we want to understand how this idea of neutrality can be used to understand the development of these computer programs during their evolution.Overall, we want to rigorously test whether this enhancement - refactoring - is capable of improving the efficiency and effectiveness of this increasingly important technology for the automated creation of computer programs.

Planned Impact

Genetic Programming is at present the only technology that has demonstrated the ability to automatically generate software, and similar executable structures, across a wide variety of application domains. It has produced results comparable to that of human programmers and designers in a breadth of areas of application, and has been incorporated into, or used to design, a number of products that have been used to solve real problems or to produce commercial products. As problems get more complex, and as more problems require the production of bespoke on-demand software for areas where there is no expert knowledge that could guide human programmers, the demand for automated software creation is increasing. Genetic Programming is in a position to be the technology of choice for such applications. The development of better GP systems will therefore be of benefit to the creators of software, other executable structures, and software-hardware co-designs. As such technologies become mainstream, we expect the automated design of part of a software system to become a normal part of software design practice. Our plan for making GP the technology of choice for automated software creation consists of two elements. Firstly, we plan to incorporate our enhancements to GP into an existing open-source GP system, so that the improvements will be readily available. Secondly, we aim to publicize this technology to a wide audience within the traditional software engineering practice community, and open up a dialogue with that community to share ideas. This will be done by talks at relevant events, articles in practitioner-focused media, the development of online resources, and engagement in online communities.

Publications

10 25 50
 
Description We have developed new methods to enable computer programs to be created automatically from descriptions of what those programs should do.
Exploitation Route They could be incorporated into larger systems to support the increased automation of software development.
Sectors Digital/Communication/Information Technologies (including Software)

 
Description Ideas from the projects have begun to be taken up in the development of new optimisation and program synthesis systems.
First Year Of Impact 2012
Sector Digital/Communication/Information Technologies (including Software)
 
Description Cafe Scientifique talk (Canterbury) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? Yes
Geographic Reach Local
Primary Audience Public/other audiences
Results and Impact Gave a talk to the general public about artificial intelligence and led a discussion.

Invited to give further public talks elsewhere.
Year(s) Of Engagement Activity 2012
 
Description Cafe Scientifique talk (Dartford) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? Yes
Geographic Reach Local
Primary Audience Public/other audiences
Results and Impact Gave a talk to the general public about artificial intelligence and led a discussion.

Was invited to give further talks to the public.
Year(s) Of Engagement Activity 2011