Lecture 3 Flashcards
why do we do encoding and decoding in EA?
we need to map the problem-specific representation (phenotype space) to bitstrings (genotype space) and back
=> the variation operators act on genotypes, the phenotypes are evaluated
how do you solve a problem defined over real values?
- subdivide a solution into n segments of equal length
- decode
what is exploration in EA?
discovering promising areas in the search space, gaining information on the problem (crossover)
what is exploitation in EA?
optimizing a promising area, using information (mutation)
how does a genetic algorithm work?
- initialize the population
- evaluate the population
WHILE criteria not met: - select parents to mate
- crossover with probability p_c => children
- mutation on children with probability p_m
- evaluate the children
- children form the new population
what is a schema?
a partial instantiation of a string
H /in {0, 1, }
eg. 10000**10
what is the order of a schema?
the number of instantiated elements in it:
o(H) = |{i|h_i /in {0,1}}|
what is the defining length of a schema?
the length of the substring starting at the first and ending at the last instantiated element of the schema minus one
d(H) = max{i|h_i /in {0,1}} - min{i|h_i /in {0,1}}
what is the probability that crossover does not occur within the defining length?
1 - (p_c * d(H) / (l - 1))
what is the probability that the schema is not mutated?
(1 - p_m)^o(H)
what is m(H,t)?
the expected number of instantiations of schema H in generation t
what is the expected number of instantiations of H selected for crossover?
m(H,t) * f(H)/f_mean
what were seen as explanations for the power of GAs?
implicit parallelism: a lot of different schemas are effectively processed in parallel by a GA
Building Blocks Hypothesis: GAs are able to detect short, low order and highly fit schemata and combine these into highly fit individuals
what is the expected number of instances of a schema H in generation t+1?
m(H,t+1) = the expected number of instances of H selected for crossover * the probability that H is not destroyed by crossover * the probability that H is not destroyed by mutation