Lecture 3 Flashcards

1
Q

why do we do encoding and decoding in EA?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

how do you solve a problem defined over real values?

A
  • subdivide a solution into n segments of equal length
  • decode
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what is exploration in EA?

A

discovering promising areas in the search space, gaining information on the problem (crossover)

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

what is exploitation in EA?

A

optimizing a promising area, using information (mutation)

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

how does a genetic algorithm work?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

what is a schema?

A

a partial instantiation of a string
H /in {0, 1, }
eg. 100
00**10

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

what is the order of a schema?

A

the number of instantiated elements in it:
o(H) = |{i|h_i /in {0,1}}|

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

what is the defining length of a schema?

A

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}}

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

what is the probability that crossover does not occur within the defining length?

A

1 - (p_c * d(H) / (l - 1))

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

what is the probability that the schema is not mutated?

A

(1 - p_m)^o(H)

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

what is m(H,t)?

A

the expected number of instantiations of schema H in generation t

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

what is the expected number of instantiations of H selected for crossover?

A

m(H,t) * f(H)/f_mean

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

what were seen as explanations for the power of GAs?

A

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

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

what is the expected number of instances of a schema H in generation t+1?

A

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

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