Wk 3-4 Genetic Programming Flashcards
Genetic algorithms :
They are a specific type of evolutionary algorithm that that mimics the process of natural selection to solve optimization and search problems.
They employ genetic inspired operators (crossover, mutation) to evolve a population of individuals toward an optimal or near-optimal solution.
Focus representation and manipulation of genetic material (often in binary or chromosome format)
Genetic algorithm outline ( same as EA) :
- Generate random “programs”
- Evaluate programs using training data
- Selectively modify population of programs using crossover and mutation etc.
- If a good program is found, finish, else go to
How is the fitness evaluation different from standard EAs in genetic programs?
The chromosome is a program. To evaluate it, we have to run it, and test its behaviour over a range of potential inputs. Therefore its more complex.
EA Fitenss –> We just evaluate it and give it a score.
Genetic Programming Mutation:
Standard approach is to choose a subtree at random, remove it, and then generate a new subtree in its place.
This is usually biased towards nodes with high depth.
Five Major Preparatory Steps for GP
- Determining the set of terminals
- Determining the set of functions
- Determining the fitness measure
- Determining the parameters for the run
- Determining the criterion for terminating a run
In genetic programming how are functions represented ?
By parse trees
Fitness parity problem
Input: A binary string of a fixed length.
Output: Determine if the binary string has an equal number of 0s and 1s.
(3-parity problem) odd-parity problem
That takes three input variables (X1, X2, X3) and returns 1 if an odd number of the input variables are 1. Otherwise, the function should return 0. ( toghether they make Y the function output I wish to achieve)
Serves as a common benchmark problem to evaluate the performance and effectiveness of GP algorithms.
You compare the program output with Y to see if the answer is correct.
Hamming distance
It calculates the minimum number of substitutions required to change one string into another by replacing individual characters. ( distance in changes between two strings of equal len )
Lower Hamming distance
may be more likely to be chosen as parents for crossover, as they are more similar and can potentially generate offspring with desirable characteristics.
Higher Hamming
distance may be preferred for mutation to introduce diversity into the population.
Hamming distance crossover example
DIstance between parents is 3 .
Distance between cross over child and parent is 2 then the distance with the other parent will be 1.
H(PARENTA, CHILD) + H(PARENTB, CHILD) = H(A,B)
SEMANTICS
Meaning of the problem, output fo the tree.
The semantics of a program is all input-output pairs defining the computed function
SYNTAX
structure of the problem
Traditional genetic programming
does blind syntactic manipulation of parent parse trees, regardless of their semantics
