Wk 2-3 Evolutionary Algorithms

Question 1

What operations would be required to run a ready state, ranked roulette wheel selection, single gene mutation, single point cross over evolutionary algorithm?

Answer 1

• Replacement
• sorting population by fitness
• generarion of a population of random solutions

Question 2

Given permutation ADEJAVBFIH would it make sense to perform swap mutation?(TSP)

Answer 2

Yes, because it would mantain permutation validity but will change the order mutating the solution successfully

Question 3

Given permutation ADEJAVBFIH would it make sense to perform single gene mutation?

Answer 3

No, it would change one letter into another in the range meaning one letter would be missing ( you’d have a duplicate )

Question 4

What degree of selection pressure do you have with t = 0 and popsize = 10000?

Answer 4

Selection pressure is low 1/1000

Question 5

Tournament selection what happens if we increase t?

Answer 5

Increase pressure, the chances of including a top performing solution. T=1 random selection, T = popsize would be hill climbing

Question 6

Initialization of EA

Answer 6

Initial random population is generated.
Each individual (program) represents a potential solution.

Question 7

Evaluation

Answer 7

Each program is executed and it’s performance/fitness is evaluated through a fitness function quantifying how good a solution is.

Question 8

Selection

Answer 8

Programs with higher fitness score are more likely to be selected:
- tournament -> (potentially - elitist)
- roulette wheel
- rank based

Question 9

Variations

Answer 9

• crossover
• mutation

Question 10

Crossover

Answer 10

Combines genetic material from 2 parents to create an offspring.

Question 11

Mutations

Answer 11

Creates random changes to genetic material of individual programs.

• single gene mutations
• M gene ( multiple instance of single gene replacements 0
• swap mutation ( swap 2 random genes)
• vector mutation ( add a perturbation to the candidate solution ( vector ))

Question 12

Replacement

Answer 12

Offspring generated through variations along with some of the parents, replace the worst fitting individuals in the population.

Question 13

Replacement strategies (choose)

Answer 13

• worst individuals
• random individuals
• combination strategy ( a certain percentage of the worst ones are replaced )

Question 14

Replacement mechanisms (replace):

Answer 14

• full replacement: all selected individuals replaced at the same time. Complete change of the population.
• overlapping: offspring gradually replace the initial population over multiple iterations.

Question 15

Termination:

Answer 15

• maximum number of iterations or generations
• no improvements
• certain level of fitness

Question 16

K-ary encoding

Answer 16

Encoding scheme to represent individuals or solutions within the population.

Question 17

Initialization with k-ary encoding

Answer 17

Each individual in the generated population (candidate solutions L ) is represented using a string of symbols, where each symbol can take one of k possible values.

For example, in binary encoding (k=2), each symbol can be either 0 or 1. In decimal encoding (k=10), each symbol can be any digit from 0 to 9. ( then you evaluate fitness

Question 18

Common crossover operators

Answer 18

-One-Point Crossover
-Two-Point Crossover
-Uniform Crossover

Question 19

One-point crossover

Answer 19

In one-point crossover, a single crossover point is randomly selected along the length of the child.

The genetic material beyond that point is exchanged between the parents to create two offspring.

This means that the genetic material from one parent is combined with the genetic material from the other parent after the crossover point.

The result is two new individuals with a mixture of genetic material from the parents.

Question 20

Two-point crossover

Answer 20

The genetic material between the two crossover points is exchanged between the parents to create two offspring.

The genetic material outside of the selected points remains the same in the offspring.

This operator provides more mixing of genetic material compared to one-point crossover.

Question 21

Uniform crossover

Answer 21

A mask is used, where each bit in the mask determines which parent’s symbol is chosen for the corresponding position in the offspring.

For example, if the mask has a value of 1010101, the offspring will inherit the symbols from the first parent at positions 1, 3, 5, and 7, and from the second parent at positions 2, 4, and 6. T

Question 22

Comprison between cross overs:

Answer 22

One-point crossover is simpler and generally less disruptive to the genetic material, while two-point crossover and uniform crossover provide more extensive mixing.

Question 23

Direct Encoding

Answer 23

Known as Genotype-Phenotype mapping, directly represents the solution or individual in the search space.

Genotype = genetic representation of an individual ( encoding, example xy)
Phenotype = the actual individual

Genotype is directly translated into the phenotype without any intermediate steps

Question 24

Example Direct encoding

Answer 24

For example, in a genetic algorithm solving a numerical optimization problem, an individual’s genotype may be represented as a binary string, where each bit represents a value of a variable. The phenotype would be obtained by decoding the binary string into the corresponding real-valued variables.

Question 25

Pro Cons of direct encoding

Answer 25

Pro
- simple to implement and interpret

Con
- less efficient for complex problems with high-dimensional search spaces or intricate relationships between variables.

Question 26

Indirect Encoding

Answer 26

Developmental encoding, separates the genotype and phenotype, introducing an intermediate step that generates the phenotype from the genotype.

In indirect encoding, the genotype contains instructions or rules that determine how the phenotype develops or evolves.

Question 27

Advantages Indirect encoding:

Answer 27

• more flexible representations, capturing complex relationships and patterns
• cut down the size of the search space
• easier to exploit domain knowledge

It can be beneficial when the relationship between the genotype and phenotype is not straightforward or when a more compact representation is desired.