Intro

Question 1

what is a constructive solver?

>>> what is the search trajectory?

Answer 1

constructive solver?

works by extending an empty solution

>>> search trajectory is correct but incomplete solutions

Question 2

what is an iterative improvement method?

>>> what is the search trajectory?

Answer 2

iterative improvement method:

works by improving solution

>>> complete but incorrect solutions

Question 3

what are 4 classes of NP problems?

Answer 3

NP-problems:

1. P - solvable in polynomial time
2. NP - solvable and any solution can be verified in polynomial time
3. NP-complete: belongs to class NP and any other problem in NP can be reduced to this problem in polynomial time
4. NP-hard: problem is at least as hard as any other problem in NP-complete but solution cannot necessarliy be verified in polynomial time

Question 4

what is lamarckism? how does it relate to EC?

Answer 4

lamarckism: acquired features can be inherited from parents to offspring

>>> turns out not to be true in biological evolution

>>> but we can use it in EC

Question 5

what are the two competing forces in evolution?

Answer 5

competing forces in evolution

1. increasing population diversity by variation

> mutation and recombination

>>> push towards novelty

2. decreasing population diversity by selection

> selection of parents/ survivors

>>> push towards quality

Question 6

selection operators act on …?

variation operators act on….?

Answer 6

selection operators operate on population level

variation operators act on individual level

Question 7

what are 4 possible termination conditions?

Answer 7

1. reaching some fitness level
2. reaching maximum amount of generations

3 reaching minimum level of diversity

4. reaching some specific number of generations without fitness improvement

Question 8

why are selection operators independent of representation?

Answer 8

they only use the fitness value

Question 9

is it worth expending effort on smart initialization?

Answer 9

depends:

> can be good if solution/ methods exist

> may not be necessary, EA will catch up quickly

Question 10

global optima: deterministic vs heuristic approaches

Answer 10

deterministic:

> guarantee to find global optimum

> may have bounds on runtime, usually polynomial

heuristic:

> generate and test approach

> no guarantee that solution is global optimum

> no bounds on runtime