Genetic Algorithm

Unlike single-point search methods such as Simulated Annealing, a genetic algorithm maintains a population of candidate solutions that evolve simultaneously. This parallel exploration of the search space provides inherent resistance to premature convergence on local optima.

• Each individual in the population represents a potential solution encoded as a chromosome (often a bit string or array)
• The population size balances exploration breadth against computational cost
• Diversity across the population is critical for avoiding stagnation

Selection is the mechanism that drives the population toward higher fitness by preferentially choosing stronger individuals as parents for the next generation. The selection pressure determines the balance between exploration and exploitation.

• Fitness-proportionate (roulette wheel) selection: Probability of selection is proportional to fitness relative to the population
• Tournament selection: A random subset competes, and the fittest wins—providing tunable selection pressure via tournament size
• Rank-based selection: Mitigates premature dominance by super-fit individuals in early generations

Crossover is the primary exploitation operator that combines genetic material from two parent chromosomes to produce offspring. It preserves and propagates building blocks—short, low-order schemata associated with high fitness.

• Single-point crossover: A single cut point is chosen; segments beyond that point are swapped
• Two-point and uniform crossover: Multiple exchange points increase mixing of genetic material
• Order crossover (OX): Specialized for permutation encodings, such as route sequences in the Vehicle Routing Problem, preserving relative order while preventing duplicate genes

Mutation introduces random perturbations to individual chromosomes, serving as the primary exploration mechanism that prevents the irreversible loss of genetic diversity. It ensures the algorithm can theoretically reach any point in the search space.

• Mutation rate is typically low (e.g., 0.1%–1% per gene) to avoid destroying good solutions
• Bit-flip mutation for binary encodings; swap mutation for permutation encodings
• Adaptive mutation strategies increase the rate when population diversity drops below a threshold, helping escape local optima

Elitism is a preservation strategy that guarantees the best-performing individuals survive unchanged into the next generation. This ensures the maximum fitness discovered so far is monotonically non-decreasing across generations.

• Typically, the top 1–5% of individuals are copied directly to the next generation
• Elitism accelerates convergence but must be balanced against maintaining diversity
• The algorithm terminates when the population converges—when the fitness variance drops below a threshold or a maximum number of generations is reached

A genetic algorithm navigates the fitness landscape—a hyperdimensional surface where each point represents a solution and its elevation represents fitness. The algorithm's operators are designed to efficiently traverse this landscape without gradient information.

• Deceptive landscapes: Problems where following local gradients leads away from the global optimum; GAs can bypass these via population diversity
• Epistasis: Gene interactions where the contribution of one gene depends on others; crossover can recombine co-adapted gene groups
• Niching and speciation: Techniques like fitness sharing maintain subpopulations on separate peaks, enabling the discovery of multiple optima in multi-modal optimization problems

The mechanism that chooses parent solutions from the current population to breed the next generation, favoring fitter individuals.

• Fitness-Proportionate (Roulette Wheel): Selection probability is directly proportional to an individual's fitness score.
• Tournament Selection: A random subset of individuals is chosen, and the fittest among them wins, providing a tunable selection pressure.
• Rank-Based Selection: Individuals are sorted by fitness, and selection probability is based on rank rather than absolute fitness value, preventing premature convergence by highly fit outliers.

A genetic operator that combines the genetic information of two parent solutions to generate one or more offspring, enabling the exploration of new regions in the search space.

• Single-Point Crossover: A single crossover point on the parent chromosomes is selected, and the data beyond that point is swapped.
• Uniform Crossover: Each gene in the offspring is randomly chosen from one of the corresponding parents with equal probability.
• Order Crossover (OX): Designed for permutation-based problems like the Traveling Salesman Problem, it preserves the relative order of genes from one parent while inheriting sequence information from the other.

A unary operator that introduces random, small-scale perturbations to an individual's chromosome to maintain genetic diversity and prevent the population from stagnating at a local optimum.

• Bit-Flip Mutation: For binary encodings, a bit is randomly flipped from 0 to 1 or vice versa.
• Swap Mutation: For permutation encodings, two randomly selected positions in the sequence are exchanged.
• Gaussian Mutation: For real-valued encodings, a small Gaussian-distributed random value is added to a gene, enabling fine-tuning of continuous parameters.

A conceptual representation of the search space where the height of each point corresponds to the fitness value of a candidate solution, and the spatial coordinates represent the solution's genotype or phenotype.

• Local Optima: Peaks or valleys in the landscape where a solution is better than all its immediate neighbors but not necessarily the global best.
• Ruggedness: A measure of the landscape's irregularity; highly rugged landscapes with many local optima are difficult for simple hill-climbing algorithms to navigate.
• Genetic algorithms use a population-based approach to sample multiple peaks simultaneously, making them robust on deceptive or rugged landscapes.

A related evolutionary algorithm that primarily relies on mutation as the main search operator and typically operates on real-valued vectors, making it highly effective for continuous optimization.

• Covariance Matrix Adaptation (CMA-ES): A state-of-the-art ES variant that learns a full covariance matrix to model the distribution of successful mutation steps, enabling it to efficiently navigate ill-conditioned and non-separable fitness landscapes.
• Unlike standard genetic algorithms, ES often encodes the mutation step size directly within the individual's chromosome, allowing the search strategy itself to evolve.

An extension of genetic algorithms where the individuals in the population are executable computer programs, typically represented as syntax trees, rather than fixed-length strings.

• Tree-Based Crossover: Subtrees are randomly selected and swapped between two parent programs to create offspring.
• GP is used for symbolic regression to automatically discover mathematical expressions that fit data, and for evolving control policies or decision logic.
• The solution is an interpretable model, unlike the weight matrices of a neural network.