Week 11: Genetic Programming Flashcards
What is genetic programming?
Genetic programming is a model of programming which uses the ideas of biological evolution to handle a complex problem.
Genetic programming is an extension of GA (Genetic Algorithm) - a model for testing and selecting the best choice among a set of results
What is the data structure used to represent a solution in Genetic Programming?
Solutions are represented as Tree Structures
What is the general mechanism used for recombining solutions in Genetic Programming?
Crossover is done by exchanging of subtrees
What is the general mechanism used for mutation in Genetic Programming?
Mutation is a random change in trees
What is the general mechanism used for parent selection in Genetic Programming?
Parent selection is fitness proportional (just like GA)
What is the general mechanism used for survivor selection in Genetic Programming?
Same as GA, the fittest will survive and replace the less fit
In GA (Genetic Algorithm):
- Chromosomes are linear structures (bit strings, integer string, real-valued vectors, permutations)
- The size of chromosomes is fixed.
How are these different in GP (Genetic Programming)? Tree Structures are used in GP to represent solutions
In GP:
- Trees may vary in depth and width
- The size of Chromosomes is fixed
- Trees may vary in depth and width
Give an outline of the step-by-step process for 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 steps 2 & 3, until either an acceptable solution is found, or until the algorithm has iterated through a given number of cycles/generations
What does the Genetic Programming flowchart look like?
The Tree-based representation of a solution in Genetic Programming is composed of two parts.
Describe them
- Terminals, T. These are leaf nodes in the tree. Every member of T is a correct expression, “e”.
- Function set, F. These are operators that can be applied onto terminals: f(e1,e2, …) to produce an expression “e”.
How is mutation performed in Genetic Programming for the tree structures?
Take a random subtree in the structure and replace it by a randomly generated tree (randomly generated terms and functions)
In Genetic Programming, mutation has two parameters. What are they?
Can the size of the child in mutation be different to the size of the parent in mutation?
- Probability Pm to choose mutation vs recombination (crossover), with typical value very small (0.05) or 0
- Probability to chose an internal point as the root of the subtree which is to be mutated
- The size of the child can exceed the size of the parent
In Genetic Programming, a state can undergo ______ or ______, but not both in one ______
mutation
recombination/crossover
generation
How is Recombination performed in Genetic Programming for two tree structures (parents)?
Pick a subtree in parent 1, and another subtree in parent 2.
Exchange these two subtrees between the two parents (swap the subtrees) and you’ll have the two children
In Genetic Programming, the Recombination operator has two parameters. What are they?
- Probability Pc to choose recombination vs mutation
- Probability to chose an internal point as the root of the subtree which is to be used in crossover
- The size of the trees in the children can exceed that of the parents
