genetic algorithms Flashcards
general principles of evolution
heredity - take genes from parents
natural selection
variation - there has to be means of introducing variation/randomness
evolutionary computing
algorithms inspired by evolution
used in optimization problems
pros:
-few assumptions needed
-any types of variables
-insensitive to discontinuity and shape
-works with non-linearity
GA general algorithm
- choose encoding
- choose fitness function
- choose selection method (e.g. roulette wheel - pick uniformly from[0,1], check which slice it falls in)
- randomly select initial population
- compute fitness for initial population
- selection method on initial population based on fitness
- modification:
6a.crossover - with predefined probability p, crossover chromosomes
chosen at step 5
6b.mutation - with predefined probability p, mutate new chromosomes
by flipping bits - put new chromosomes in population, back to step 4
Holland’s schema theorem
The presence of short, low-order schema with above-average fitness increases in successive generations of GA
critiques:
does not imply it finds global minima
assumes infinite population
Solving multi-objective problems
-problem consisting of two or more conflicting objectives
-need to find a set of solutions that define the best possible tradeoffs between objectives
Performance measurement
Pareto optimal solution = there is no other solution which improves one objective without degrading the performance of another (these worse solutions are called Pareto dominated)
Pareto front can be discontinuous / weird shape and GA still works0
NSGA II
same as GA but choosing chromosomes is different
make table of chromosomes, count dominated / dominated by
divide into fronts based on nr of dominated by
need to choose chromosomes in order to keep variance (diversity preservation) => crowding distance => low crowing distance points eliminated (they do not affect variance as much)
