Genetic programming is an approach to arbitrary problems where the goal is not so much to optimize a particular function, but to produce a program that optimally solves a more general problem. That is, find a program that maps an input space to an output space as accurately as possible. While the idea has been kicking around since the 1950's, the work of Koza in the late 1980's.
Notes:
Genetic programs typically store their algorithm as a tree. The tree may represent an arithmetic expression, a classification scheme, or any other logical structure where operations are applied sequentially based on the results of prior operations.
Fitness is assessed via supervised learning. That is, inputs are selected where the correct output is known. The fitness of the program is how closely the program output matches the correct outputs.
Crossover is applied by grafting pieces of the tree from one solution to another.
Mutation is applied by changing part of the tree.
Theoretically, the search space is all computer programs which are guaranteed to terminate. In reality, it works best to limit the complexity of the tree to keep things from drifting off into irrelevant parts of the solution space where the gradient is very flat.
A special structure, the Automatically Defined Function (ADF). Such functions encapsulate more complex operations and can be grafted into the tree as part of mutation or crossing.
No comments:
Post a Comment