L6 - Genetic Programming Flashcards

1
Q

Define Genetic Programming…

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are Candidate Programs?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What structure are the Candidate Programs usually stored in?

A

Tree Structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the processes Genetic Programming conducts to generate new candidate programs?

A

Selection
Mutation
Recombination

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What unit do we use to measure the quality of a Candidate Program?

A

Fitness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the 4 general steps included in a Genetic Programming Algorithm?

A
  1. Generate initial parent programs as the root solutions.
  2. Evaluate fitness of programs using training data.
  3. Perform mutation on candidate programs such as cross over or single point.
  4. Assess whether sufficient program has been found. I.e Fitness is around some threshold.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Give some creative ways that GP could be used to advance technology…

A

Used to find optimal OS’s, processors, or customer facing software where the fitness value is determined by customer feedback.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How do we perform a fitness evaluation for Genetic Programming?

A
  • Run the program for fitness evaluation.
  • Program behaviour has to be assessed over a range of inputs.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is an issue with evaluating program fitness in Genetic Programming?

A

Computationally Expensive.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Explain the 5 step process to generating an initial population in Genetic Programming?

A
  1. Define the program in Tree Structure.
  2. Randomly generate N programs based on the Program Tree.
  3. Evaluate fitness of programs and select next generation based on selection criteria.
  4. Mutate solutions via recombination.
  5. Back to step 3 and repeat.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are the 5 preparatory steps for Genetic Programming?

A
  • Define set of terminals.
  • Define set of functions.
  • Define the fitness measure.
  • Define the parameters to run.
  • Define the termination criteria.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

In the program Tree, what do nodes and leaves represent?

A

Nodes -> Functions or conditionals.
Leaves -> Constants or variables.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

In the program tree, can we have a function as a leaf ?

A

No, only terminals can be a leaf e.g variables, or values.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How do we evaluate the program tree?

A

Recursively evaluate the tree nodes, starting at the root node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does the structure of the tree represent?

A

The order of operations in the program, from top to bottom and left to right.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the 2 main mutation techniques in GP?

A

Standard Mutation
Crossover

17
Q

In GP, how do we perform a Standard Mutation?

A

Remove a random subtree of the solution, and replace it with another subtree.

The new subtree can either be a terminal or another subtree, or anything in between.

18
Q

In GP, how do we perform a Crossover?

A

Swap 2 subtrees of the parents to generate 2 new solutions.

19
Q

What are 2 issues with Standard Mutation in GP?

A
  • Bias towards nodes of greater depth, which overemphasises complex solutions.
  • Risk of structural disruption, which can lead to an invalid program tree.