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.
Organisations
Publications
Castle T
(2012)
Genetic Programming
Castle T
(2012)
Evolving program trees with limited scope variable declarations
He P
(2011)
Modeling grammatical evolution by automaton
in Science China Information Sciences
Moraglio A
(2012)
Evolving recursive programs using non-recursive scaffolding
Moraglio A
(2012)
Parallel Problem Solving from Nature - PPSN XII
Otero F
(2013)
A New Sequential Covering Strategy for Inducing Classification Rules With Ant Colony Algorithms
in IEEE Transactions on Evolutionary Computation
Otero F
(2010)
A hierarchical multi-label classification ant colony algorithm for protein function prediction
in Memetic Computing
Otero F
(2013)
Genetic Programming
Pappa G
(2013)
Contrasting meta-learning and hyper-heuristic research: the role of evolutionary algorithms
in Genetic Programming and Evolvable Machines
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 |