Genetic Algorithm Basics

Study Notes

Genetic Algorithm (GA) Basics

A variant of stochastic beam search that generates successor states by combining two parent states rather than modifying a single state.
Analogous to natural selection, but with sexual rather than asexual reproduction.
Each state (or individual) is represented as a string over a finite alphabet, commonly a string of 0s and 1s.

Representation of States

An 8-queens state requires 24 bits (8 × log2 8) or 8 digits, each in the range from 1 to 8.
Different encodings (e.g., binary vs. decimal) can behave differently.

Fitness Function

Rates each state by the objective function, which should return higher values for better states.
In the 8-queens problem, the fitness function can be the number of nonattacking pairs of queens, with a maximum value of 28 for a solution.

Producing the Next Generation

Probability of being chosen for reproduction is directly proportional to the fitness score.
Two pairs are selected at random for reproduction, with crossover points chosen randomly.
Offspring are created by crossing over the parent strings at the crossover point.

Crossover Operation

Can produce a state that is a long way from either parent state, especially when parents are quite different.
Frequently takes large steps in the state space early on and smaller steps later on when individuals are similar.

Mutation

Each location is subject to random mutation with a small independent probability.
In the 8-queens problem, this corresponds to choosing a queen at random and moving it to a random square in its column.

Genetic Algorithm Advantages

Combines an uphill tendency with random exploration and exchange of information among parallel search threads.
Primary advantage comes from the crossover operation, which can combine large blocks of letters that have evolved independently to perform useful functions.

Description

Learn the fundamentals of Genetic Algorithm, a search heuristic that mimics the process of natural selection, and understand how it generates successor states through sexual reproduction. Explore the concept of population and individual representation in GA.