Grammatical Evolution Flashcards
What is Grammatical Evolution an extension of?
A GP
Still searches in the program space
Each gene is called a codon (8 bit string)
Gram E ALG:
create initial pop of variable length binary strings
map vie a BNF grammar
eval fitness
while(termination cond not met){
select fitter individuals for reproduction
recombine selected indivs
mutate offspring
eval fitness of offspring
replace all indivs in the pop with offspring
end
return best indiv
How does a context free grammar look like?
G = <N, T, P, S>
G = Grammar
N = non-terminals denoted by <> (whatever is inside can be simplified by other attributes)
T = terminal final values
P = Production rules
S = Starting value
How is the initial population generated?
Random generate a population of variable length binary strings (indivs)
Lengths are determined randomly from a lower bound and upper bound range(8 - 20)
What does mapping involve?
converting binary strings to decimal and using them to select production rules to apply. (Derivation i.e genotype to phenotype)
Mapping equation:
Rule = (colon decimal value)%(no of production rules)
What is a phenotype?
A derivation tree that is evolved by iterating and mapping through the sequence of codons
How is the derivation process performed?
left->right starting with the left-most non-terminal
What is wrapping?
If the iteration process reaches the end of the sequence of codons before the derivation tree is evolved. the procedure continues by looping to the start of the codon sequence
How is the fitness of a phenotype evaluated?
By applying it to a problem
What are the 2 selection types in GE?
Tournament selection / Fitness proportionate
What are the genetic operators?
Crossover mutation Reproduction Elitism
What is the most common crossover and how does it work?
Single point crossover.
Crossover point is randomly selected from the shortest parent.
Other methods are possible but need to consider the lengths
Mutation for GE:
Similar to GA (bit mutation)
How is the population replaced in GE?
It is either replaced generationally or steady state (find out difference)
