The Unit Test as a Fitness Function
Extreme Programming is a concept pioneered by Kent Beck and Ward Cunningham which has gained worldwide acceptance. It is an agile software methodology that espouses fundamental goals and how best to achieve them. The precepts of XP are as follows:
-- Kent Beck, author of "Extreme Programming Explained"
Genetic programming is a model of programming which uses the ideas (and some of the terminology) of biological evolution to handle a complex problem. Of a number of possible programs (usually small program functions within a larger application), the most effective programs survive and compete or crossbreed with other programs to continually approach closer to the needed solution. Genetic programming can be viewed as an extension of the Genetic Algorithm, a model for testing and selecting the best choice among a set of results. Genetic programming goes a step farther and makes the program or "function" the unit that is tested. Two approaches are used to select the successful program - crossbreeding and the tournament or competition approach. A difficult part of using genetic programming is determining the fitness function, the degree to which a program is helping to arrive at the desired goal. A simple example of a genetic programming fitness function would be devising a program to fire a gun. The distance by which the bullet misses its target would determine the fitness function.
The commonality in these two definitions are 'unit test' and 'program' so it seems natural to consider the unit test as a fitness function and hence XP a natural methodology to advance GP.
So Genetic Programming is a Genetic Algorithm performed on a parse tree of executable program code. The fitness is determined by how well the code solves a problem. In XGP, the problem is expressed as a unit test. The unit test is the fitness function. The problems that can be solved are any problem that is solvable by the set of functions in the system, in this case anything solvable by most programming languages.
XGP is a concept that grew from discussions involving Ward Cunningham, Jonathan Groff, and Arthur Copeland.
Essentially, GP is a form of optimization toward the goal of converging upon a 'solution', using optimization processes borrowed from an old model built by a power higher and smarter than we. They can, at times, be erratic yet predicable in their inevitable march toward a goal. Part of the optimization is using a 'fitness function' to select the best candidates from a 'population' of 'individuals'. In our case the 'fitness function' is built as a unit test for a specific piece of code functionality, and we converge on the solution to those tests. The Individuals have 'chromosomes' composed of functions and terminals in a parse tree that represent an executable piece of code in the framework.
During reproduction, branches of code from the chromosomes are crossed such that they do not violate programmatic structural integrity and new code is produced. Code that passes the units tests are given varying degrees of fitness by the test. In this way the 'optimum' solution is converged upon. In reality it tends to be highly specific to the unit test, thus enforcing the design methodology espoused in XP.
To initially start the operation we take what we know about the test, the return type and the argument types or variable types, and we use those to randomly populate the starting population with all possible functions for that type. We then inject the variables. Using that set we converge on the return type, and the variables, constants, and return types of functions guide through structural integrity. In the end the code is structurally complete. Execution and check of results in unit test fitness functions, along with exception fitness reduction function, allows us to produce a final raw fitness, which, using a standardization formula, is rolled into the final fitness for that individual. The proportionally fittest individuals are selected from the population to reproduce and the next generation begins.
Write a complete unit test and the code evolves to solve it. Since humans don't write code quickly or easily, it seems like a good job for a computer. All we organics have to do is figure out how to write unit tests correctly.
In contrast to something like bridge engineering, construction of code is but a fraction of the cost of a project. Regardless, it is the adherence to the philosophy of building complete units tests and allowing them to enforce design that is the truly powerful aspect of XP and XGP.
A discussion of Extreme Programming can be found at:
A Genetic Programming FAQ can be found at: