L6 - Genetic Programming Flashcards
Define Genetic Programming…
Genetic Programming is the process of leveraging the natural process of evolution to generate a computer program that optimally solves a problem.
A type of evolutionary algorithm focussed on evolving candidate programs in a quest to configure the most optimal program that solves the problem.
What are Candidate Programs?
The programs to assess the fitness of and apply mutations on in order to create new generations. The Candidate Programs are usually stored in a Tree structure.
What structure are the Candidate Programs usually stored in?
Tree Structure
What are the processes Genetic Programming conducts to generate new candidate programs?
Selection
Mutation
Recombination
What unit do we use to measure the quality of a Candidate Program?
Fitness
What are the 4 general steps included in a Genetic Programming Algorithm?
- Generate initial parent programs as the root solutions.
- Evaluate fitness of programs using training data.
- Perform mutation on candidate programs such as cross over or single point.
- Assess whether sufficient program has been found. I.e Fitness is around some threshold.
Give some creative ways that GP could be used to advance technology…
Used to find optimal OS’s, processors, or customer facing software where the fitness value is determined by customer feedback.
How do we perform a fitness evaluation for Genetic Programming?
- Run the program for fitness evaluation.
- Program behaviour has to be assessed over a range of inputs.
What is an issue with evaluating program fitness in Genetic Programming?
Computationally Expensive.
Explain the 5 step process to generating an initial population in Genetic Programming?
- Define the program in Tree Structure.
- Randomly generate N programs based on the Program Tree.
- Evaluate fitness of programs and select next generation based on selection criteria.
- Mutate solutions via recombination.
- Back to step 3 and repeat.
What are the 5 preparatory steps for Genetic Programming?
- Define set of terminals.
- Define set of functions.
- Define the fitness measure.
- Define the parameters to run.
- Define the termination criteria.
In the program Tree, what do nodes and leaves represent?
Nodes -> Functions or conditionals.
Leaves -> Constants or variables.
In the program tree, can we have a function as a leaf ?
No, only terminals can be a leaf e.g variables, or values.
How do we evaluate the program tree?
Recursively evaluate the tree nodes, starting at the root node.
What does the structure of the tree represent?
The order of operations in the program, from top to bottom and left to right.