Genetic Algorithm

Unlike single-point search methods like simulated annealing, a genetic algorithm maintains a population of candidate solutions that evolve in parallel. This inherent parallelism allows the algorithm to explore multiple regions of the search space simultaneously, reducing the risk of getting trapped in a local optimum. Each individual in the population represents a potential solution encoded as a chromosome, typically a binary string or an array of real numbers.

The selection operator drives the population toward higher fitness by preferentially choosing the strongest individuals to reproduce. Common methods include:

• Roulette Wheel Selection: Probability of selection is proportional to an individual's fitness relative to the population.
• Tournament Selection: A random subset of individuals is chosen, and the fittest among them wins the right to reproduce.
• Rank Selection: Selection probability is based on relative rank, not absolute fitness, preventing a single super-individual from dominating prematurely.

Crossover is the exploitation engine of a genetic algorithm, combining the genetic material of two parent solutions to produce offspring that inherit traits from both. The most common type is single-point crossover, where a random cut point is selected and the tails of two parents are swapped. Other variants include two-point crossover and uniform crossover, where each gene has an independent probability of being swapped. This operator assumes that combining good building blocks from different solutions can yield a superior solution.

Mutation is the exploration engine that injects genetic diversity back into the population, preventing premature convergence on a local optimum. For a binary-encoded chromosome, mutation flips a random bit with a small probability. For real-valued encodings, Gaussian mutation adds a small random number drawn from a normal distribution. The mutation rate is critical: too high turns the search into a random walk, while too low stifles exploration. It ensures that the algorithm can theoretically reach any point in the search space.

The fitness function is the objective function that defines the environment. It quantifies the quality of every candidate solution, assigning a scalar score that the algorithm seeks to maximize or minimize. The shape of this landscape dictates algorithm performance. A rugged landscape with many local optima requires high diversity and exploration, while a smooth, unimodal landscape favors exploitation. A well-designed fitness function must penalize infeasible solutions through penalty functions or repair algorithms to guide the search back into valid regions.

Elitism is a practical enhancement that guarantees the best solution found so far is never lost. A small number of the fittest individuals are copied directly into the next generation without undergoing crossover or mutation. This ensures that the maximum fitness is monotonically non-decreasing. Convergence occurs when the population's genetic diversity drops below a threshold, often measured by the Hamming distance between chromosomes. At this point, the algorithm has likely settled on a global or strong local optimum.

A probabilistic optimization technique that mimics the physical process of heating and controlled cooling of a material. Unlike genetic algorithms that maintain a population of solutions, simulated annealing works on a single candidate, probabilistically accepting worse solutions to escape local optima. The 'temperature' parameter controls the exploration-exploitation trade-off, gradually reducing randomness as the search converges.

The set of all non-dominated solutions in a multi-objective optimization problem where improving one objective requires degrading another. Genetic algorithms excel at approximating the Pareto frontier through multi-objective evolutionary algorithms like NSGA-II, which use crowding distance and non-dominated sorting to maintain a diverse set of trade-off solutions across conflicting objectives.

The fundamental dilemma in sequential decision-making where an agent must balance trying new actions (exploration) against choosing the best-known action (exploitation). In genetic algorithms, this is managed through selection pressure and mutation rates: high mutation favors exploration of the search space, while elitist selection favors exploitation of known high-fitness regions.

A mathematical problem defined by variables and constraints restricting allowed value combinations. While CSP solvers use backtracking and constraint propagation for exact solutions, genetic algorithms can be adapted through penalty functions or repair mechanisms to handle constraints heuristically, making them suitable for over-constrained problems where finding any feasible solution is challenging.

A sequential design strategy for optimizing expensive-to-evaluate black-box functions using a probabilistic surrogate model (typically a Gaussian process) and an acquisition function. Unlike genetic algorithms, which require many function evaluations across generations, Bayesian optimization is designed for sample efficiency when each evaluation is costly, such as hyperparameter tuning of deep learning models.

A family of optimization methods that incorporate randomness in the search process or handle objective functions subject to statistical noise. Genetic algorithms are inherently stochastic through random initialization, probabilistic selection, crossover, and mutation. This randomness provides robustness against noisy fitness landscapes and helps avoid premature convergence to local optima in deceptive search spaces.