Algorithm
- Generate a population of individuals
- Evaluate the fitness of each individual
- While termination criteria not met:
- Select parents
- Create offspring using cross-over and mutation
- Update population
- Evaluate fitness of all individuals
Techniques
- Representation. “Individuals” are the solutions. Chromosomes
representations:
- binary representation (array of 0s and 1s)
- floating-point representation (array of numbers)
- Initialization
- random
- large population has more diversity
- Fitness function
- better fitness would mean better solution
- constraints can be added through penalties
- Selection
- random: randomly select two parents
- tournament: choose best individual from randomly selected
groups
- elitism: choose best individuals from overall population
- Cross-over
- uniform random: each gene is randomly selected from one of the
parents (toss a coin per gene)
- one point crossover: the first P genes will be from one parent, the
rest from the other parent (P is chosen randomly)
- Mutation
- uniform
- for binary representation
- each bit/gene is flipped with some probability p
- gaussian/normal:
- for floating-point representation
- each gene is updated with some probability p by adding a random normal amount
- Stopping conditions
- max generations
- fitness threshold
- convergence: when fitness stops improving sufficiently quickly