Week 7: Genetic Algorithms #2

Question 1

Many problems have real-valued parameters. If they were mapped to a ______ space in order to use GA, then high precision solutions would require very long _______

Answer 1

binary

chromosomes

Question 2

In Real Valued Genetic Algorithm (GA), can we use the crossover operators to combine two individuals, as we did from Simple GA?
What are they?

Answer 2

Yes, we can use any of these two:

1. Discrete. Convert the real value to binary, and then apply binary crossover
2. Intermediate. Use arithmetic to apply crossover. Can be:
   - Single arithmetic crossover
   - Simple arithmetic crossover
   - Whole arithmetic crossover

Question 3

When applying crossover on Real Valued Genetic Algorithm, we often use “Single” Arithmetic Crossover.

How does it work?

Assume that the parents are a vector of genes:
[ gene1, gene2, gene3, …. ]

What about the other child?

Answer 3

• From the set of parents, we pick a gene “k” at random. Let “x” and “y” be the values of the parents at this gene
• The child will take on the value αy + (1-α)x at the gene “k”, where α is between 0 and 1
• All other genes for the child will be the same as the “x” parent
• The other child will be the opposite ( αx + (1-α)y at “k”, and takes “y”’s values otherwise)

Question 4

When applying crossover on Real Valued Genetic Algorithm, we often use “Simple” Arithmetic Crossover.

How does it work?

Assume that the parents are a vector of genes:
[ gene1, gene2, gene3, …. ]

What about the other child?

Answer 4

• From the set of parents, we pick a gene “k” at random
• Apply Simple arithmetic crossover to all the points after “k” in the vector of genes for the parents
• For each pair of genes “x”, “y” after “k”, the child will take the value αy + (1-α)x, where α is between 0 and 1
• All other genes for the child (before “k”) will be the same as the “x” parent
• The other child will be the opposite ( αx + (1-α)y after “k”, and takes “y”’s values otherwise)

Question 5

When applying crossover on Real Valued Genetic Algorithm, we often use “Whole” Arithmetic Crossover.

How does it work?

Assume that the parents are a vector of genes:
[ gene1, gene2, gene3, …. ]

What about the other child?

Answer 5

• For all genes x_i from parent 1 and y_i from parent 2, the child’s i gene will be αy_i+ + (1-α)x_i, where α is between 0 and 1
• The other child will be the opposite ( αx_i + (1-α)y_i for all i)

Question 6

In Real Valued Genetic Algorithm, there are two types of mutations, what are their names?

Answer 6

1. Uniform mutation

2. Random noise mutation

Question 7

How does “uniform” mutation work for Real Valued GAs?

Assume the individual takes the form:
[ gene1, gene2, gene3, …. ]

Answer 7

turns into
[ new1, new2, new3, … ]

These “new” values are uniformly randomly generated with an upper and lower bound

This is analogous to bit-flipping in binary GA

Question 8

How does “Random noise” mutation work for Real Valued GAs?

Assume the individual takes the form:
[ gene1, gene2, gene3, …. ]

Answer 8

turns into
[ new1, new2, new3, … ]

For each gene, we add a random amount of noise:

new_i = gene_i + N(0,σ)

Where N(0,σ) is a random gaussian number with mean zero and standard deviation σ

Question 9

Permutation GA is made for what type of problems?

What does a sample solution look like?

Answer 9

Problems that take the form of deciding on the order in which a sequence of events shall occur - for example TSP (traveling salesman problem)

Sample solution is an ordered set of “n” variables, with each variable occurring exactly once

Question 10

In permutation GAs, there are 3 types of crossovers.

What are they?

Answer 10

Adjacency Based:
- Partially Mapped Crossover (PMX)

Order Based:

• Order 1 crossover
• Cycle crossover

Question 11

In Permutation GAs, how does the adjacency based Partially Mapped Crossover (PMX) work?

Assume that individuals/chromosomes take the form of “n” ordered variables/genes, with each variable occurring exactly once:
[a1, a2, a3, a4, … ]

Answer 11

PMX (Partially Mapped Crossover) for parents P1 & P2:

1. Choose random segment (subarray) from P1, and copy it into the offspring
2. Starting from the index of the first point in the chosen subarray, look for elements in that segment of P2 that have not been copied
3. For each of these “i”, look in the offspring to see what element “j” has been copied in its place from P1
4. Place “i” into the position occupied by “j” in P2, since we know that we will not be putting “j” there (its already in the offspring)
5. If the slot occupied by “j” in P2 has already been filled in the offspring “k”, then put “i” in the position occupied by “k” in P2
6. Having dealt with elements from the crossover segment, the rest of the offspring can be filled from P2. Second child is created analogously

Question 12

In Permutation GAs, how does the order 1 crossover work?

Assume that individuals take the form of “n” ordered variables, with each variable occurring exactly once:
[a1, a2, a3, a4, … ]

Answer 12

The idea is to preserve relative order that elements occur

1. Choose an arbitrary subarray from the first parent
2. Copy this part to the child
3. Copy the numbers that are not yet in the child:
   - Start from the element which is to the right of the right most element in the copied part (wrap around)
   - Use the relative order of the un-added elements of the second parent
   - Wrap around the end
4. Repeat for second child but swapping the roles of parent 1 and parent 2

Question 13

In Permutation GAs, how does the cycle crossover?

Assume that individuals take the form of “n” ordered variables (genes), with each variable occurring exactly once:
[a1, a2, a3, a4, … ]

Answer 13

1. Identify cycles in the number orders between parent 1 and parent 2 by using the a parent’s gene’s value as an index lookup for the other parent
2. Create a group for each cycle found - the groups should have equal number of elements in parent 1 and parent 2
3. Take the second of these groups (ordered by starting index), and swap the values at these elements between parent 1 and parent 2

Question 14

In Permutation GAs, there are four types of mutation operators. What are they?

Answer 14

• insert mutation
• swap mutation
• inversion mutation
• scramble mutation

Question 15

In Permutation GAs, how does insert mutation work?

Assume that individuals take the form of “n” ordered variables (genes), with each variable occurring exactly once:
[a1, a2, a3, a4, … ]

Answer 15

Insert mutation:
1. Pick two gene values at random

2. Move the second to follow the first, shifting the rest up by 1 to accommodate
3. Preserves most of the order and the adjacency information

Question 16

In Permutation GAs, how does swap mutation work?

Assume that individuals take the form of “n” ordered variables (genes), with each variable occurring exactly once:
[a1, a2, a3, a4, … ]

Answer 16

Swap mutation:

pick two genes at random, and swap their positions

Question 17

In Permutation GAs, how does scramble mutation work?

Assume that individuals take the form of “n” ordered variables (genes), with each variable occurring exactly once:
[a1, a2, a3, a4, … ]

Answer 17

Scramble mutation:
- Pick two gene values at random

• Randomly rearrange the genes in those positions

Question 18

One main disadvantage of GAs is the problem of “parameter tuning”

What does parameter tuning mean?

Answer 18

Parameter tuning refers to the problem of finding suitable values for the different algorithm parameters before the algorithm is run

Question 19

What are some disadvantages of parameter tuning?

Answer 19

• Time consuming process
• Parameters are tuned one-by-one, which may lead to sub-optimal choices because the parameters are not independent
• Simultaneous tuning of parameters may lead to an enormous amount of experiments
• The best parameters settings are problem specific
• Different values may be optimal at different stages of the search process

Question 20

Adaptive techniques have been proposed in GAs to set the values of the different algorithm parameters on-the-fly,

What is the advantage of this?

What is the difference between Parameter tuning and Parameter control?

What are the 3 types of parameter control in adaptive GA?

Answer 20

• These algorithms are more efficient and perform better on a wider range of problems.
• Parameter tuning is done before the run, whereas parameter control is done during the run
• The 3 types of parameter control are Deterministic, Adaptive, and Self-Adaptive

Question 21

In GAs, what does it mean for parameter control to be “Deterministic”?

Note that this is part of parameter control during the run of the algorithm

Answer 21

Deterministic parameter control is characterized by replacing any parameter p with a function p(t), where t is the generation number

This approach does not take the progress of the search process into account (or the
current state of the search).

Question 22

In GAs, what does it mean for parameter control to be “Adaptive”?

Note that this is part of parameter control during the run of the algorithm

Answer 22

Adaptive parameter control takes feedback from the current state of the search and heuristically control the parameter values

Question 23

In GAs, what does it mean for parameter control to be “self-adaptive”?

Note that this is part of parameter control during the run of the algorithm

Answer 23

Self-adaptive approaches incorporate the parameter values into the chromosomes.

In this case the parameter control process will be driven through selection, crossover and mutation.

Question 24

In Real-valued GAs, we use the Gaussian mutation to apply mutation on all genes of an individual:

new_i = gene_i + N(0,σ)

How can you deterministically set the value of σ during the run?

What does this help with?

Answer 24

σ can be changed according to some rule:

σ(t) = 1 - 0.9 * t/T

Where “t” is the generation number ranging from 0 to T (which is the maximum generation number)

This way, σ is changed from 1 at the beginning to 0.1 at the end.

This helps with enhancing the fine tuning ability of the search towards the end

Question 25

Adaptive GAs incorporates feedback from the search process. One way of doing this is adapting to the “1/5 success rule”.

What is this rule?

How can this be applied to GAs, in the controlling of σ, to make it adaptive?

Note that σ is the std-deviation of mutation when applying random noise mutation

Answer 25

• 1/5 success rule states that at least 1 out of 5 mutations should be a mutation that produces a better individual.
• The value for σ at a given iteration can be selected based on the ratio of successful to unsuccessful mutations
• If the ratio is greater than 1/5, then the mutation step size should be increased. If the ratio is less than 1/5, then the step size should be decreased

Note that “step size” is the amount at which we change σ

Question 26

In Adaptive GAs, when using the 1/5 success rule to modify the value of σ as the algorithm progresses, what is the motivation behind:

• Increasing step size for σ whenever successful mutation ratio is greater than 1/5
• Decreasing step size of σ whenever successful mutation ratio is less than 1/5

Note that σ is the std-deviation of mutation when applying random noise mutation

Answer 26

• If the moves are not very successful, then we should proceed in smaller steps
• If the moves are very successful, then we should try larger steps in order to improve the efficiency of the search

Question 27

Describe the Self-Adaptive approach to GAs

How is the σ parameter changed over time?

Note that σ is the std-deviation of mutation when applying random noise mutation

Answer 27

• The self-adaptive approach adds the mutation step-size to the individual
• The value of σ is evolved with the individual
• Each individual will have a different mutation step size
• Mutating the individual is usually on the the form:

σ_new = σ * e^N(0, τ)
gene_i = gene + N(0, σ_i)

Where τ is a parameter of the method referred to as the learning rate

Question 28

In Adaptive GAs, the crossover operator can also be adapted as the algorithm progresses in 3 different ways.

What are they?

Answer 28

1. Top level: adapting the crossover operator itself
2. Medium level: adapting the probability of crossover. Instead of a constant crossover probability, it can be adjusted
3. Bottom level: adapting the crossing position or the swapping probability

Question 29

Parallelism can be integrated into GAs by running numerous algorithms in parallel. This is known as Parallel GAs

What are the different approaches of Parallel GAs?

Answer 29

• Master-slave approach
• Fine-grained GAs
• Coarse-grained GAs

Question 30

How does Master-slave parallelism GA work?

Note: this is also known as global parallel GAs

Answer 30

• There is 1 master processor, and numerous worker processors
• Selection and mating are handled by the master processor and applied on the entire population
• The fitness evaluation process is distributed among different slave processors

Question 31

How does fine-grained parallel GA work?

Answer 31

• There are parallel processes working on the same population, but with different individuals
• Selection and mating is restricted to local neighbourhoods (they may overlap amongst individuals)
• Suitable for massively parallel computers
• The ideal case is to have one individual per processor

Question 32

How does Coarse-grained prallel GA work?

Answer 32

• Multiple populations evolving in parallel with different processors
• Selection and mating are restricted within a population
• The populations exchange individuals every now and then (migration)

Question 33

What are some issues that need to be considered in coarse-grained (multiple-deme) GAs?

Answer 33

• Number of sizes of populations
• Different topologies between populations
• Different migration policies - how migrating individuals are selected
• Different migration frequencies
• Different migration rates

Question 34

What are the four different types of neighbourhood topologies for regular GAs or for coarse-grained (multiple-deme) prallel GAs?

Answer 34

1. Star Topology - All populations/individuals are connected to each other
2. Grid topology - populations/individuals are connected to 4 adjacent populations/individuals
3. Hyper-cube topology - populations/individuals are connected to 3 adjacent populations/individuals
4. Ring topology - populations/individuals are connected to 4 adjacent populations/individuals

Question 35

What effect do the different neighbourhood topologies have on the GA algorithm (for parallel and regular)

Note that Dense vs Sparse topologies is sometimes referred to as Dynamic vs static topologies

Answer 35

• In dense topologies (star topology), good solutions spread faster and quickly take over the population or set of populations
• In sparse topologies, solutions spread slower, different solutions appear. These solutions may come together towards the end and recombine to produce even better individuals

Question 36

In parallel GA with the multiple-deme approach (coarse-grained), the migration frequency controls when the communication is being carried out.

What are the two types of communications that can happen between populations?

What happens if communication between populations happens too early in the progression of the algorithm?

Answer 36

1. Synchronous communication in which migration happens every predetermined number of generations
2. Asynchronous communication in which migration happens when a certain event occurs (eg. convergence)
   - Communication in the early stages may lead the populations to sub-optimal solutions & causes high communication costs

Question 37

In parallel GA with the multiple-deme approach (coarse-grained), the migration rate is the number of individuals that are being migrated from one population to another at every communication step.

What effect does low migration rates or high migration rates have?

Answer 37

• Low migration rates may cause the populations to behave independently, and the migrants won’t have a significant effect on the algorithm
• High migration rates may cause a fast convergence to and lead to sub-optimal solutions

Question 38

One form of parallelization in GAs is Cooperative GAs.

How does Cooperative GA work? whats the idea behind it?

Answer 38

• The idea is to have different populations optimizing different variables of the problem (different dimensions of the solution)
• The fitness of any individual is determined by its value and the value of the best individuals in all the other populations
• Performs best if the problem variables are independent
• The best individuals from all the populations come together to build the overall solution