Week 7: Genetic Algorithms #2 Flashcards
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 _______
binary
chromosomes
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?
Yes, we can use any of these two:
- Discrete. Convert the real value to binary, and then apply binary crossover
- Intermediate. Use arithmetic to apply crossover. Can be:
- Single arithmetic crossover
- Simple arithmetic crossover
- Whole arithmetic crossover
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?
- 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)
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?
- 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)
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?
- 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)
In Real Valued Genetic Algorithm, there are two types of mutations, what are their names?
- Uniform mutation
2. Random noise mutation
How does “uniform” mutation work for Real Valued GAs?
Assume the individual takes the form:
[ gene1, gene2, gene3, …. ]
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
How does “Random noise” mutation work for Real Valued GAs?
Assume the individual takes the form:
[ gene1, gene2, gene3, …. ]
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 σ
Permutation GA is made for what type of problems?
What does a sample solution look like?
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
In permutation GAs, there are 3 types of crossovers.
What are they?
Adjacency Based:
- Partially Mapped Crossover (PMX)
Order Based:
- Order 1 crossover
- Cycle crossover
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, … ]
PMX (Partially Mapped Crossover) for parents P1 & P2:
- Choose random segment (subarray) from P1, and copy it into the offspring
- 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
- For each of these “i”, look in the offspring to see what element “j” has been copied in its place from P1
- 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)
- 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
- Having dealt with elements from the crossover segment, the rest of the offspring can be filled from P2. Second child is created analogously
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, … ]
The idea is to preserve relative order that elements occur
- Choose an arbitrary subarray from the first parent
- Copy this part to the child
- 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 - Repeat for second child but swapping the roles of parent 1 and parent 2
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, … ]
- 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
- Create a group for each cycle found - the groups should have equal number of elements in parent 1 and parent 2
- Take the second of these groups (ordered by starting index), and swap the values at these elements between parent 1 and parent 2
In Permutation GAs, there are four types of mutation operators. What are they?
- insert mutation
- swap mutation
- inversion mutation
- scramble mutation
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, … ]
Insert mutation:
1. Pick two gene values at random
- Move the second to follow the first, shifting the rest up by 1 to accommodate
- Preserves most of the order and the adjacency information
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, … ]
Swap mutation:
pick two genes at random, and swap their positions
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, … ]
Scramble mutation:
- Pick two gene values at random
- Randomly rearrange the genes in those positions
One main disadvantage of GAs is the problem of “parameter tuning”
What does parameter tuning mean?
Parameter tuning refers to the problem of finding suitable values for the different algorithm parameters before the algorithm is run
What are some disadvantages of parameter tuning?
- 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
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?
- 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
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
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).
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
Adaptive parameter control takes feedback from the current state of the search and heuristically control the parameter values
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
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.
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?
σ 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
