L4 - EA's in more detail

Question 1

Define Generational Algorithm type…

Answer 1

An algorithm in which the genetic operator is applied across all N solutions to generate a new generation of solutions.

Question 2

Define Generational Elitist Algorithm type…

Answer 2

Take the K best solutions of N, and apply genetic operator to remainder of N to create the new generation of K + M( N-K )

Question 3

Define a Steady State Algorithm Type…

Answer 3

An EA where we use a selection algorithm to select K solutions from N. We apply genetic operator to all solutions in K. We perform a replacement operation of mutated K back on N.

Replacement operation is either Replace Weakest or Replace First Weakest.

Question 4

In Steady State Algorithms, what are the 2 replacement procedures we can use?

Answer 4

Replace Weakest : With our mutated set K, we iterate K and replace solutions in N with solutions in K so long as the current solution in K is no worse than the solution in N.

Replace First Weakest : With our mutated set K, we iterate K and as soon as we encounter a solution in N that is worse than k, we replace n with k.

Question 5

Define what is meant by Selection Pressure?

Answer 5

Refers to the degree in which individuals in a population are favoured for selection. Can range between Low, Medium and High. For example, low pressure would be a random selection.

Question 6

Define what is meant by Selection Process…

Answer 6

The Selection Process is the strategy we employ to decide which areas of the search space we should focus our efforts on.

Question 7

What are the names of the 3 selection processes we are looking at?

Answer 7

Fitness Wheel Selection (Fitness Proportionate)
Rank-based Selection
Tournament Selection

Question 8

Explain the process of Fitness Proportionate Selection…What are the problems with it? What is the name of the Selection Process the solves these problems?

Answer 8

For each solution, we divide its fitness by the sum of fitness. This gives us a selection pool in which solutions with higher fitness are more likely to be selected for mutation.

Problems:
- Solutions with much larger fitness scores will be chosen disproportionately.
- Negative fitness values skew sum of fitness values and thus skew the selection pool.

Solution:
Rank-Based Selection

Question 9

Explain the Rank-Based Selection Process and how it solves the issues of Fitness Wheel Selection…Give an example of how it solves the issue using the fitness values {100, 0.4, 0.3, 0.2, 0.1}

Answer 9

N is most fit.

Rank-based selection assigns selection probabilities based on the relative ranks of individuals rather than their fitness values. This helps reduce the influence of extreme fitness values on selection.
This removes the selection discrepancy introduced by the Fitness Wheel Selection.

#1 is least fit

E.g
Fitness Wheel : S(100) is 100x more likely to be selected.

Rank-Based : S(100) is 5x more likely to be selected.

Question 10

In Rank-Based Selection, what is Bias? Why do we use it?

Answer 10

Bias is a measure we can introduce to change the probabilities of solutions being chosen. We do this through applying some exponent do all fitness values in the set.

For example:

Low Bias : n^0.5 reduces the selection discrepancy between fitter and less fit solutions.

High Bias : n^2 increases selection discrepancy.

Question 11

Explain Tournament Selection… What are its pros and cons…

Answer 11

Tournament Selection is a rank-based selection in which a set of size t is chosen from the solutions, and they are ranked based on their fitness scores. One or more of the fittest solutions are chosen to create the new generation.

Pros:
- Tunable : We can increase or decrease t, which in turn changes the selection pressure. For example, t = 10, p = 10000 would be very low pressure.
- Avoids issues of super-fit or super-poor solutions.
- Simple and efficient to implement

Cons:
- Requires extra parameter ( tournament size )

Question 12

What are Genetic Operators?

Answer 12

The operators we use to mutate solutions and create new generations.

Question 13

Define exploitation and exploration…

Answer 13

Exploitation : When we want to work with solutions we already know are good, thus a small change or combination between known good solutions are used to create the new generation of candidate solutions.

Exploration : The process of searching new areas within the search space.

Question 14

What does it mean when we refer to a Solutions representation or encoding?

Answer 14

This is referring to the type that makes up the solution. E.g Integer, Vector.

Question 15

What is meant by K-ary encoding? Give an example of when k = 20…

Answer 15

If we were to select candidate solutions from the population as an array of length L, this would mean that that each candidate solution would be an array of length L, where each element was between 1 and 20.

In other words, this is a 20-ary encoding of length L.

Question 16

What are the 3 ways we can mutate K-ary encodings?

Answer 16

Single Gene Mutation:
Choose a random gene in the solution, and replace it with some random gene such that 1 ≤ new gene ≤ K.

M Gene Mutation:
Multiple instances of Single Gene Mutation.

Swap Mutation
Choose 2 genes at random and swap them.

Question 17

What are the 2 ways of mutating Vector-Based encodings of length L?

Answer 17

Single Gene Mutation:
Choose a gene at random and add a small deviation to it.

Vector Mutation:
Generate a small random vector of the same length L, and add it to the candidate solution.

Question 18

Why can we use Single Gene or Swap mutations when working with permutations?

Answer 18

Because that would break the permutation which achieved us the high fitness value???

Question 19

Define what is meant by Recombination / Crossover

Answer 19

The combining of 2 optimal solutions.

Question 20

What are the 2 ways that we can perform recombination?

Answer 20

Point Crossover:
Choose 1 or more points, and swap solution A and B at the points.

Uniform Crossover:
We create a binary mask which we use as a template to perform gene swaps between solution A and B.

Question 21

Why is Encoding a big problem in Evolutionary Computation?

Answer 21

We need to find a way to encode the solutions, but there are so many ways to encode the solutions for the same problem, each of which effects the generated landscape.