genetic-algorithm

name	genetic-algorithm
description	Genetic algorithms — encoding (binary/real), selection (tournament/roulette), crossover, mutation, fitness function, constraint handling, NSGA-II multi-objective, engineering design optimization applications.
metadata	{"priority":7,"promptSignals":{"phrases":["genetic algorithm","evolutionary algorithm","NSGA-II","multi-objective optimization","GA optimization","evolutionary optimization","Pareto front optimization"],"minScore":3}}

Genetic Algorithms — Complete Skill

Core Concepts

GA: population-based metaheuristic inspired by natural selection Chromosome: encoding of one solution (individual) Gene: one element of chromosome (one design variable) Population: set of N candidate solutions Fitness: measure of solution quality (objective function value) Generation: one iteration of selection, crossover, mutation

Algorithm Structure

Initialize population P_0 of N random chromosomes
Evaluate fitness f(x_i) for each x_i ∈ P_0
For g = 1, 2, ..., G_max (generations):
    1. Selection: select parents from P_{g-1}
    2. Crossover: recombine parents → offspring
    3. Mutation: randomly modify offspring
    4. Evaluation: compute f for all offspring
    5. Replacement: form new P_g from P_{g-1} and offspring
Return best solution found

Encoding

Binary Encoding

Each variable encoded as binary string of L bits Precision: ΔX = (X_max - X_min)/(2^L - 1) L = 10 → 1024 levels; L = 16 → 65536 levels Gray code: adjacent integers differ by 1 bit → smoother fitness landscape

Real-Valued Encoding (most common for engineering)

Chromosome = vector of real numbers [x₁, x₂, ..., x_d] Direct representation; no precision loss; natural for continuous variables

Integer/Discrete Encoding

Mixed-integer: some real, some integer genes Special operators needed for integer constraints

Selection Operators

Tournament Selection

Select k random individuals; choose best as parent k = 2 (binary tournament): simple; good balance exploration/exploitation k = 3–5: more selective (faster convergence; less diversity)

Roulette Wheel (Fitness Proportionate)

P(select x_i) = f(x_i) / Σ f(x_j) Problem: scale-sensitive; dominated by high-fitness individuals → premature convergence Fix: rank-based or windowing

Rank-Based Selection

Rank individuals 1–N by fitness; selection prob proportional to rank Less scale-sensitive; more uniform exploration

Stochastic Universal Sampling (SUS)

Evenly spaced pointers on roulette wheel → N parents in one spin → less sampling variance

Crossover Operators

Single-Point Crossover (Binary)

Split parent chromosomes at one point; swap tails Parents: [1 0 1 1 | 0 0 1 0], [0 1 0 0 | 1 1 0 1] Offspring: [1 0 1 1 1 1 0 1], [0 1 0 0 0 0 1 0]

Two-Point Crossover

Two cut points; middle segment swapped; preserves schema better at endpoints

Uniform Crossover

Each gene independently taken from parent 1 or parent 2 with p = 0.5 Maximum disruption; good for loosely epistatic problems

Simulated Binary Crossover (SBX — for real variables)

Mimics binary crossover semantics for real-valued genes η_c = distribution index (higher → offspring closer to parents) Offspring: x_{1,2}^child = 0.5[(1 ± β) x₁ + (1 ∓ β) x₂] β distribution from η_c parameter

Typical η_c = 10–20 for engineering optimization

Mutation Operators

Bit Flip (Binary)

Flip each bit with probability p_m = 1/L (expected 1 mutation per chromosome)

Polynomial Mutation (Real-Valued)

δ_q = mutation amount; sampled from polynomial distribution parameter η_m Perturbs gene within [x_min, x_max] bounds Typical η_m = 20 (small mutation most likely)

Gaussian Mutation

x_new = x + N(0, σ²); σ = mutation step size Self-adaptive: σ evolves with chromosome (ES-style)

Constraint Handling

Penalty Function

Convert constrained to unconstrained: f_penalty(x) = f(x) + Σ r_i × max(0, g_i(x))² r_i = penalty coefficient; large r → feasibility enforced; too large → optimization loss Dynamic penalty: r increases with generation → strict at end; loose at start

Repair Methods

If infeasible, project or repair to nearest feasible solution Example: if x_1 + x_2 > X_max → normalize both by factor

Tournament Feasibility (Deb's rule)

Any feasible solution beats any infeasible one in tournament Among feasibles: better fitness wins; among infeasibles: smaller violation wins Simple; effective; no tuning required

Multi-Objective GA (NSGA-II)

Pareto Dominance

x₁ dominates x₂ if: x₁ is no worse in all objectives AND strictly better in at least one Pareto front: set of non-dominated solutions; represents optimal trade-offs

NSGA-II Algorithm (Deb 2002)

1. Non-dominated sorting: rank solutions into fronts (Front 1, 2, ...)
2. Crowding distance: within each front, space solutions evenly
3. Selection: prefer lower front rank; tie → larger crowding distance
4. Tournament, crossover, mutation, evaluation, combine parents+offspring, truncate to N

Reference point based (NSGA-III): for k > 3 objectives; better spread on reference point surface Hypervolume (MOEA/D): decompose into scalar subproblems; better diversity

Pareto Front Post-Processing

Select final solution from Pareto front by:

• Decision maker preference (e.g., weight cost twice as much as weight)
• Normalized Pareto distance from utopia point
• Multi-criteria decision making (TOPSIS, AHP)

Hyperparameters and Tuning

Parameter	Typical Range	Effect
Population size N	50–500	Larger → better exploration; slower per generation
Crossover prob P_c	0.6–0.9	Higher → more recombination
Mutation prob P_m	0.001–0.1	Higher → more exploration; too high → random
Generations G	100–2000	Trade computation vs. quality
η_c (SBX)	5–20	Higher → offspring closer to parents
η_m (poly mutation)	5–50	Higher → smaller mutations

Engineering Applications

Structural optimization: truss topology, plate thickness distribution, MEMS topology Airfoil/blade shape: chord/thickness/twist optimization for Cl/Cd → aerodynamic Material selection: multi-objective (cost + strength + weight + corrosion resistance) Manufacturing process: welding parameters, heat treat schedule, machining speeds System design: engine cycle optimization, energy system configuration PID tuning: minimize ISE + control effort simultaneously

Comparison to Other Optimizers

Method	Best for	Avoid when
GA/NSGA-II	Multi-objective; discrete/mixed; noisy	Smooth unimodal (gradient methods better)
Bayesian Opt	Expensive evaluations (<1000)	Large populations; cheap functions
PSO	Continuous; fast convergence	Discrete variables; constraints
CMA-ES	Continuous; ill-conditioned	Large d (d > 50)
Gradient (SQP)	Smooth, differentiable	Non-smooth; multi-modal

Implementation (Python)

DEAP (Distributed Evolutionary Algorithms in Python): Flexible framework; any encoding; NSGA-II built in

toolbox.register("mate", tools.cxSimulatedBinaryBounded, ...)
toolbox.register("mutate", tools.mutPolynomialBounded, ...)
toolbox.register("select", tools.selNSGA2)

Pymoo: dedicated NSGA-II/NSGA-III/MOEA/D; NumPy-based; fast jMetalPy: multi-objective; Java-equivalent API in Python MATLAB ga / gamultiobj: built-in; easy to use; limited customization

Output

Provide: encoding type (real/binary), population size N, number of generations G, crossover/mutation probabilities, fitness function f(x) formulation (with units), constraint handling method, convergence criterion, Pareto front for multi-objective, sensitivity of solution to hyperparameters (run multiple seeds), final solution x* with objective values f(x*), and comparison to gradient-based result if applicable.