What is a genetic algorithm and how does it mimic evolution?
A genetic algorithm (GA) is a population-based search method that evolves a set of candidate solutions toward better answers by repeatedly applying selection and variation, much like natural selection. It solves hard optimization and search problems where the objective is non-differentiable, discrete, or has many local optima, such as routing, scheduling, and hyperparameter tuning. Its main trade-off is flexibility versus efficiency: GAs explore rugged search spaces well but converge slowly and provide no guarantee of finding the global optimum.
Read full answerHide full answer
Applies tomachine learning concepts (examples in Python 3.12)
The Evolutionary Loop
-
Population (chromosomes): A generation holds many candidate solutions encoded as chromosomes (for example, bit strings or real vectors).
-
Fitness function: Scores how well each chromosome solves the problem; higher (or lower) fitness guides evolution.
-
Selection: Fitter individuals are more likely to reproduce. Common methods: tournament (best of a random subset wins), roulette wheel (probability proportional to fitness), and rank (probability based on sorted rank, reducing dominance by very fit individuals).
-
Crossover (recombination): Combines parts of two parents to form offspring, e.g. one-point (swap segments after a cut) or uniform (choose each gene from either parent).
-
Mutation: Randomly alters genes (bit flips or small numeric perturbations) to introduce new variation.
-
Elitism and replacement: Elitism copies the best individuals unchanged into the next generation; replacement defines how offspring and parents form the new population. The loop repeats for a fixed number of generations or until fitness stops improving.
Encoding, Parameters, and Convergence
-
Encoding choices (they define what crossover/mutation mean):
-
Binary strings: Natural for on/off decisions; use bit-flip mutation and one-/uniform crossover.
-
Real vectors: Natural for continuous parameters; use Gaussian mutation and blend/arithmetic crossover.
-
Permutations: Required for routing/order problems (e.g., traveling salesperson) so every city appears once; use order crossover (OX) and swap mutation to preserve valid tours.
-
Key parameters: Population size controls diversity; crossover rate controls how much offspring inherit mixed traits; mutation rate controls random exploration.
-
Exploration vs. exploitation: High mutation and large populations explore widely; strong selection and elitism exploit known good solutions. Too much exploitation causes premature convergence (the population loses diversity and stalls at a local optimum). Preserve diversity with higher mutation, tournament selection with moderate pressure, or niching/crowding.
Comparison and ML Uses
| Method | How it works | Strengths | Weaknesses | When to use | Typical scale/complexity |
|---|---|---|---|---|---|
| Genetic algorithm | Evolves a population via selection, crossover, mutation | Handles discrete, non-differentiable, multimodal objectives | Slow; many evaluations; no optimality guarantee | Combinatorial or black-box search | Cost ~ generations × population × fitness cost |
| Gradient descent | Follows gradient of a differentiable loss | Fast, precise for smooth problems | Needs gradients; can stick in local minima | Training differentiable models | Cost dominated by gradient evaluations |
| Simulated annealing | Single-solution local search that accepts worse moves with cooling probability | Simple; can escape local optima | Sensitive to cooling schedule; single trajectory | Continuous or discrete local refinement | Cost ~ iterations × neighbor/fitness cost |
| Particle swarm | Particles move using personal/global best positions | Few hyperparameters; good on continuous spaces | Can converge prematurely; weaker on discrete encodings | Continuous black-box optimization | Cost ~ iterations × swarm size × fitness cost |
| Random search | Samples candidates independently | Trivial baseline; strong for some hyperparameters | No learning from past samples | Cheap baselines, hyperparameter search | Cost ~ number of samples × fitness cost |
-
ML uses: hyperparameter search, feature selection (binary masks), neural architecture search, and multi-objective optimization such as NSGA-II (balancing accuracy and model size/latency).
Interview Tips
-
Common pitfalls: choosing an encoding that breaks problem constraints, setting mutation too low (premature convergence) or too high (random walk), using a fitness function that does not match the real objective, and comparing runs without fixed seeds.
-
Follow-ups interviewers ask: How do tournament and roulette-wheel selection differ? Why does elitism help? How would you encode a permutation problem? When would you prefer a GA over gradient-based optimization or Bayesian hyperparameter search?