Genetic Algorithms

Among population-based algorithms, genetic algorithms are conceptually simple and widely applicable. They are strongly inspired natural evolution, operating on a population using:

• Selection (survival of the fittest)
• Recombination (information mixing)
• Mutation (innovation)

Considering information in search algorithms, genetic algorithms inject structure through the representation (what patterns can exist), variation operator (what patterns are preserved or disrupted), and selection (what information is retained).

Genetic algorithms are not a good choice when the problem is convex, smooth, and well-conditioned, or when gradient/second order information is available. They’re also not good when the evaluation budget is extremely limited. In these cases, simpler methods like trajectory search may be better.

Representation

• See Representation in Binary Genetic Algorithms

Representation is the language of the search.

• Good encoding: Small genetic changes correspond to meaningful solution changes
• Bad encoding: Break structure such that neighbors in genotype are unrelated in phenotype

Crossover

• See Crossover

Crossover is a structured guess; essentially, we are saying that good partial solutions combined might result in a better solution.

This is most effective when the encoding preserves the building blocks. Poorly aligned crossover can destroy structure faster than it creates it.

Mutation

• See Mutation

Mutation provides fresh directions when the population becomes similar/homogeneous. It prevents the search from getting stuck in local traps. We can think of it as a small random nudge to open new pathways.

Selection

• See Selection in Genetic Algorithms

Selection is the mechanism that chooses parents (and sometimes survivors), and turns fitness differences into reproduction opportunities. We want the selection process to bias reproduction toward better solutions while still allowing chance.

Selection pressure is how strongly selection favors high-fitness individuals over others.

• Low selection pressure: Slower convergence, better exploration/diversity, more robust to local optima
• High selection pressure: Fast convergence, diversity collapses quickly, higher risk of premature convergence

Selection without variation collapses diversity. Variation without selection is random search.

Common selection schemes:

• Fitness-proportionate: $p_i\propto f_i$
• Tournament selection: best-of-$k$
• Rank-based selection: probability of survival depends on rank (not raw fitness)

Example