Genetic Algorithms Flashcards
Alteration (Crossover)
the random exchange of 2 parents’ chromosomes during reproduction, resulting in offspring that have some traits of each parent
Alteration requires
genetic diversity to ensure sufficiently varied offspring
Mutation
occurence of errors during the process of copying chromosome, can be harmful, beneficial, or neither
Natural Selection
the fittest survive in a competitive environment resulting in better organisms; better traits survive longer, better chance to reproduce; species improves as whole as better traits outnumber
representation of individuals for genetic algorithms
solutions represented as a vector of values
genetic algorithm
create initial population; evaluate fitness of each individual, check if termination criteria met; select parents according to fitness; recombine parents to generate offspring; mutate offspring; replace pop with new offspring
Initialization of population issues
size and diversity of initial population
A lack of diversity for initial population leads to what?
Premature convergence to a non-optimal solution
How is a diverse initial population generated?
uniformly random; grid initialization; non-clustering; local optimization
uniformly random
generate individuals randomly from a solution space with uniform distribution
grid initialization
choose individuals at regular “intervals” from the solution space
non-clustering
require individuals to be a predefined “distance” away from those already in the population
local optimization
find an initial population of local optima; does’t enforce diversity but guarantees solution to be no worse
evaluation ranks the individuals by what?
fitness measure
fitness measure
corresponds with the quality of the individual solutions
what happens if selection is too dependent on evalution/fitness function?
like greedy search, non-optimal solution may be found
what happens if selection is not dependent enough on evaluation/fitness function?
may not converge to a solution at all
2 types of proportional fitness selection techniques?
rank selection; proportional selection
rank selection
individual selected with a probability proportional to its rank in population, sorted by fitness
proportional selection
individual selected with a probability (given fitness values, sum fitnesses, determine probabilities)
tournament selection
randomly select two individuals and the one with the highest rank goes on and reproduces; only care about one with higher rank, puts upper and lower bound on the chances that any individual has to reproduce for the next generation
crowding
problem with selection - when individuals that are most fit quickly reproduce so that very large percentage of population looks similar; reduces diversity; may hinder long-run progress of the algorithm
crossover
pick pairs of individuals as parents and randomly swap their segments (parameters: crossover rate, number of crossover points, positions of the crossover points)
1-point crossover
pick a dividing point in the parents’ vectors and swap the segments
N-point crossover
pick n dividing points in the parents’ vectors and splice together alternating segments
Uniform crossover
the value of each element of the vector is randomly chosen from the values in the corresponding elements of the two parents
Mutation
randomly change an individual; parameters = mutation rate, size of mutation
Genetic algorithm
have an inition population; let p[i] be fitness probabilities, randomly pick 2 parents with probabilites, randomly select 1 crossover point, swap strings of parents 1 and 2 to generate children, randomly mutate each posision in child with small prob; new generation replaces old
Problem of Local Maxima
individuals get stuck at pretty good but not optimal solutions
