Genetic Algorithms

Variant of local beam search in which a successor state is generated by combining two parent states Start population – k randomly generated states A state is represented by a chromosome – a string over a finite alphabet (often a string of 0s and 1s), e.g. positions of queens in 8-queens Evaluation function (fitness function): higher values for better states, e.g. number of non-attacking pairs of queens Produce the next generation of states by crossover (recombination) and mutation