Wk 2-3 Evolutionary Algorithms Flashcards
What operations would be required to run a ready state, ranked roulette wheel selection, single gene mutation, single point cross over evolutionary algorithm?
- Replacement
- sorting population by fitness
- generarion of a population of random solutions
Given permutation ADEJAVBFIH would it make sense to perform swap mutation?(TSP)
Yes, because it would mantain permutation validity but will change the order mutating the solution successfully
Given permutation ADEJAVBFIH would it make sense to perform single gene mutation?
No, it would change one letter into another in the range meaning one letter would be missing ( you’d have a duplicate )
What degree of selection pressure do you have with t = 0 and popsize = 10000?
Selection pressure is low 1/1000
Tournament selection what happens if we increase t?
Increase pressure, the chances of including a top performing solution. T=1 random selection, T = popsize would be hill climbing
Initialization of EA
Initial random population is generated.
Each individual (program) represents a potential solution.
Evaluation
Each program is executed and it’s performance/fitness is evaluated through a fitness function quantifying how good a solution is.
Selection
Programs with higher fitness score are more likely to be selected:
- tournament -> (potentially - elitist)
- roulette wheel
- rank based
Variations
- crossover
- mutation
Crossover
Combines genetic material from 2 parents to create an offspring.
Mutations
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 ))
Replacement
Offspring generated through variations along with some of the parents, replace the worst fitting individuals in the population.
Replacement strategies (choose)
- worst individuals
- random individuals
- combination strategy ( a certain percentage of the worst ones are replaced )
Replacement mechanisms (replace):
- 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.
Termination:
- maximum number of iterations or generations
- no improvements
- certain level of fitness
K-ary encoding
Encoding scheme to represent individuals or solutions within the population.
Initialization with k-ary encoding
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
Common crossover operators
-One-Point Crossover
-Two-Point Crossover
-Uniform Crossover
One-point crossover
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.
Two-point crossover
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.
Uniform crossover
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
Comprison between cross overs:
One-point crossover is simpler and generally less disruptive to the genetic material, while two-point crossover and uniform crossover provide more extensive mixing.
Direct Encoding
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
Example Direct encoding
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.
Pro Cons of direct encoding
Pro
- simple to implement and interpret
Con
- less efficient for complex problems with high-dimensional search spaces or intricate relationships between variables.
Indirect Encoding
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.
Advantages Indirect encoding:
- 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.
