Genetic Algorithm Basics

What is the primary difference between a genetic algorithm and stochastic beam search?

What is the purpose of the fitness function in a genetic algorithm?

How are states typically represented in a genetic algorithm?

What is the value of the fitness function for a solution to the 8-queens problem?

What is the role of natural selection in a genetic algorithm?

What is the benefit of using a binary string representation of states in a genetic algorithm?

What is the primary factor in determining the selection of individuals for reproduction in this genetic algorithm?

How is the crossover point determined in this genetic algorithm?

What is the result of crossover operation when two parent states are quite different?

What is the purpose of the mutation operation in this genetic algorithm?

What is the advantage of crossover operation in genetic algorithms?

What is the consequence of permuting the positions of the genetic code initially in a random order?

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.

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.