15-03-2012, 01:16 PM
Genetic Programming
[attachment=18364]
What is Genetic Programming
Genetic programming is a model of programming which uses the ideas (and some of the terminology) of biological evolution to handle a complex problem. … 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, each represented by a string.
Outline of the Genetic Algorithm
Randomly generate a set of possible solutions to a problem, representing each as a fixed length character string
Test each possible solution against the problem using a fitness function to evaluate each solution
Keep the best solutions, and use them to generate new possible solutions
Repeat the previous two steps until either an acceptable solution is found, or until the algorithm has iterated through a given number of cycles (generations)
Why Genetic Programming?
“It is difficult, unnatural, and overly restrictive to attempt to represent hierarchies of dynamically varying size and shape with fixed length character strings.” “For many problems in machine learning and artificial intelligence, the most natural representation for a solution is a computer program.” [Koza, 1994]
A parse tree is a good representation of a computer program for Genetic Programming
Genetic Operations
Random Generation of the initial population of possible solutions
Mutation of promising solutions to create new possible solutions
Genetic Crossover of two promising solutions to create new possible solutions
What About Just Randomly Generating Programs?
Is Genetic Programming really better than just randomly creating new functions?
Yes!
Pete Angeline compared the result of evolving a tic-tac-toe algorithm for 200 generations, with a population size of 1000 per generation, against 200,000 randomly generated algorithms
The best evolved program was found to be significantly superior to the best randomly generated program [Genetic Programming FAQ, 2002]
The key lies in using a fitness measure to determine which functions survive to reproduce in each generation
[attachment=18364]
What is Genetic Programming
Genetic programming is a model of programming which uses the ideas (and some of the terminology) of biological evolution to handle a complex problem. … 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, each represented by a string.
Outline of the Genetic Algorithm
Randomly generate a set of possible solutions to a problem, representing each as a fixed length character string
Test each possible solution against the problem using a fitness function to evaluate each solution
Keep the best solutions, and use them to generate new possible solutions
Repeat the previous two steps until either an acceptable solution is found, or until the algorithm has iterated through a given number of cycles (generations)
Why Genetic Programming?
“It is difficult, unnatural, and overly restrictive to attempt to represent hierarchies of dynamically varying size and shape with fixed length character strings.” “For many problems in machine learning and artificial intelligence, the most natural representation for a solution is a computer program.” [Koza, 1994]
A parse tree is a good representation of a computer program for Genetic Programming
Genetic Operations
Random Generation of the initial population of possible solutions
Mutation of promising solutions to create new possible solutions
Genetic Crossover of two promising solutions to create new possible solutions
What About Just Randomly Generating Programs?
Is Genetic Programming really better than just randomly creating new functions?
Yes!
Pete Angeline compared the result of evolving a tic-tac-toe algorithm for 200 generations, with a population size of 1000 per generation, against 200,000 randomly generated algorithms
The best evolved program was found to be significantly superior to the best randomly generated program [Genetic Programming FAQ, 2002]
The key lies in using a fitness measure to determine which functions survive to reproduce in each generation
