L6 - Genetic Programming

Question 1

Define Genetic Programming…

Answer 1

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.

Question 2

What are Candidate Programs?

Answer 2

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.

Question 3

What structure are the Candidate Programs usually stored in?

Answer 3

Tree Structure

Question 4

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

Answer 4

Selection
Mutation
Recombination

Question 5

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

Answer 5

Fitness

Question 6

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

Answer 6

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.

Question 7

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

Answer 7

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

Question 8

How do we perform a fitness evaluation for Genetic Programming?

Answer 8

• Run the program for fitness evaluation.
• Program behaviour has to be assessed over a range of inputs.

Question 9

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

Answer 9

Computationally Expensive.

Question 10

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

Answer 10

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.

Question 11

What are the 5 preparatory steps for Genetic Programming?

Answer 11

• Define set of terminals.
• Define set of functions.
• Define the fitness measure.
• Define the parameters to run.
• Define the termination criteria.

Question 12

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

Answer 12

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

Question 13

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

Answer 13

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

Question 14

How do we evaluate the program tree?

Answer 14

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

Question 15

What does the structure of the tree represent?

Answer 15

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

Question 16

What are the 2 main mutation techniques in GP?

Answer 16

Standard Mutation
Crossover

Question 17

In GP, how do we perform a Standard Mutation?

Answer 17

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.

Question 18

In GP, how do we perform a Crossover?

Answer 18

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

Question 19

What are 2 issues with Standard Mutation in GP?

Answer 19

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