10 - Evolutionary Computation Review

Question 1

Evolutionary Algorithms

Answer 1

A subset of evolutionary computation.

Question 2

In this module, assume that the difference between Evolutionary Algos and Evo Computation is..

Answer 2

the difference between algorithm and computation

Question 3

Main idea of evo algos (steps)

Answer 3

Start with random initial population
- test individuals
- assign fitness
- terminate?
- select
- reproduce and mutate, repeat.

Question 4

global function optimisation purpose

Answer 4

Find the global max or min of the function

Question 5

Selection via truncation

Answer 5

In N individuals, select K best

Question 6

Roulette Wheel Selection

Answer 6

Draw a random number and see whether that drops onto a particular individual

Normalise fitness

Question 7

Tournament Selection

Answer 7

Select K random individuals, see which performs best and select that

Question 8

Selection Pressure

Answer 8

Balance between exploitation and exploration. Chance of being selected as parent

Eg in a pop of 100.
- selecting 50 parents would be low selection pressure
- selecting 5 parents = high selection pressure

Question 9

High selection pressure good or bad?

Answer 9

Bad, get stuck in narrow solution which doesn’t generalise well.

Good balance needed for diversity.

Question 10

4 Termination Criteria

Answer 10

• Stop with max num of generations
• Stop with max computation time
• Stop with desired fitness value
• Stop when fitness does not improve any more

Not required

Question 11

Genetic Algorithms

Answer 11

Encode a solution (Evo Algo) into bits.

Eg genotype [010001100] can be used to encode a 3x3 matrix which is a representation of the phenotype (solution)
n 1 2 3
1 0 1 0
2 0 0 1
3 1 0 0

Question 12

Genotype vs Phenotype representation

Answer 12

Genotype as a matrix
Phenotype as a directed graph

Question 13

9bits encode the presence of a link. 36 bits represent the value of each link

For 010 001 100
This means trhe first part is 1 to, second is 2 to and third is 3 to.
Which bits are active?

Answer 13

(from left) 2nd, 6th and 7th

Question 14

9bits encode the presence of a link. 36 bits represent the value of each link

For 010 001 100
and 0000 1100 0000 1000 0000 0011 0100 0000 0000
What is the value on a graph between each part of the genotype? (1,2,3)

Answer 14

1 -> 2 = 12
2-> 3 = 3
3 -> 1 =

Question 15

Why do some mutations have a larger effect than others?

Answer 15

Take 0000 for example

If a mutation occurs to make 0001 then that is a change of 1
If a mutation occurs to make 1000 then that is a change of 8

Question 16

Evolution Strategy

Answer 16

(μ,λ)-ES or (μ + λ) - ES

μ size of parent pop
λ size of offspring population
, parent is not part of new gen
+ parent is part of new gen

Question 16

(20,100)-ES

Answer 16

20 parents gen 100 children. Parents are discarded/discharged.

Each gen the top 20 individuals are selected to be parents

Question 17

(1+100)-ES

Answer 17

Only one solution is the parent. Each gen, 100 children and the 1 parent is included (+).

Best of them becomes new parent

Question 18

In Evolution Strategy, why my + be better than ,

Answer 18

If you’ve already found the best solution + prevents discarding it

Question 19

Why is (1,1)-ES not very meaningful?

Answer 19

Only creates solutions randomly

Question 20

Steady State ES

What is it? What is the selection pressure? Serial or parallel?

Answer 20

(μ+1)-ES

No generation gap. One parent generates one offspring and one individual is removed.

Low selection pressure and suited to parallel computing

Question 21

Evolving the mutation rate is called

Answer 21

Self adaptive adaptation

Question 22

Mutation rate vector tells you

Answer 22

what is a good mutation

(xi,sigi) for all i in {1,..,mu}

x is parameters of solution and sigi is the standard deviations for Gaussian mutations (strategy parameters)

Question 23

Genetic Programming Aim

Answer 23

Automatic programming by creating a working program from a high-level statement of a problem

Represented by trees

Question 24

Genetic Programming Definition solution

Answer 24

Represented as a tree whose non-leaf nodes are operators and leaf nodes are terminals

A tree captures the syntax of a formal expression. (arithmetic etc)

Question 25

Operator Sets in GP

Answer 25

Arithmetic: + - / *
Math: sin, cos, exp
Bool: AND, OR NOT
Assignment: =
Conditional; IF THEN ELSE
Iterative: FOR, WHILE, REPEAT

Question 26

Terminal Set in GP

Answer 26

Constants
Variables
0-arity functions: rand, go-right

Question 27

; in GP

Answer 27

used to separate commands

Question 28

IF in GP

Answer 28

Has 3 children
IF this, then do this, else do this

Question 29

Mutation in Genetic Programming

Answer 29

Select a random node and replace it with a function or terminal

Question 30

Crossover in GP

Answer 30

Taking subtrees and adding them to others

Question 31

Symbolic Regression Goal

Answer 31

Predict by understanding how values are generated. Training weights w to approximate any function

Question 32

2 Symbolic Regression difficulties

Answer 32

• We only have limited data
• Noise

Question 33

Main characteristics of GP

Answer 33

• SOlution is naturally dynamic in size/complexity
• Solution can be a program itself (self improvement)
• Search space in a GP app could be considerably larger than in a fixed-length EA
• Could be used to design topology of a elec circuit