Genetic Algorithms: How Evolution Solves Hard Problems

Evolution as Optimization

In 1975, computer scientist John Holland published Adaptation in Natural and Artificial Systems, laying the theoretical foundation for genetic algorithms. His central insight was elegant: natural selection is a search algorithm. Evolution doesn't follow a plan or gradient — it maintains a population of candidate solutions, tests each against an environment, and lets the best reproduce while the rest die off. Over generations, this blind process finds extraordinarily sophisticated solutions to extraordinarily complex problems.

The parallel to computer optimization is direct. Define a fitness function — a measure of how good any given solution is. Start with a random population of candidate solutions. Repeatedly select the fitter individuals to reproduce, combine their "genetic material," introduce occasional random changes, and evaluate the new generation. Iterate until a solution good enough emerges.

No derivative is required. No smooth landscape is assumed. No prior knowledge of the solution structure is needed. The algorithm searches by trying things, keeping what works, and discarding what doesn't — the same way four billion years of biological evolution produced the diversity of life on Earth.

Encoding Solutions as Chromosomes

Before evolution can work on a problem, the problem must be translated into a form evolution can act on. In biological evolution, the chromosome is a sequence of nucleotides encoding instructions for building an organism. In genetic algorithms, a chromosome is a string of bits, numbers, or symbols encoding a candidate solution.

The encoding choice is not trivial — it dramatically shapes what the algorithm can find and how fast it finds it. Consider the Travelling Salesman Problem: given a list of cities, find the shortest route that visits each exactly once and returns to the start. A natural encoding is a permutation of city indices — for five cities, a chromosome might be [3, 1, 4, 2, 5], meaning "visit city 3, then 1, then 4, then 2, then 5." The fitness function is simply the inverse of total route length: shorter routes have higher fitness.

Other encoding styles suit other problems. Continuous optimization problems often use real-valued chromosomes. Neural network architectures can be encoded as strings specifying layer sizes and connection patterns. Scheduling problems encode chromosomes as ordered lists of tasks. In each case, the encoding must allow meaningful recombination — mixing two good solutions should have a reasonable chance of producing another good solution, not random noise.

The Genetic Operators

Three operations drive the evolutionary search:

• Selection determines which individuals get to reproduce. The key is to give higher-fitness individuals more reproductive opportunities without eliminating low-fitness ones entirely — maintaining diversity. Tournament selection randomly samples a small group and picks the best; roulette-wheel selection assigns each individual a probability proportional to its fitness. Both approaches balance exploitation of good solutions with exploration of new regions.
• Crossover (recombination) combines two parent chromosomes to produce offspring. In single-point crossover, a random position splits each parent's chromosome, and the offspring receive one segment from each parent. Two-point crossover uses two split points, swapping the middle segment. Uniform crossover independently picks each gene from either parent with equal probability. Crossover is the primary mechanism for combining beneficial traits discovered in different individuals.
• Mutation randomly alters individual genes — flipping a bit, nudging a real value, swapping two elements in a permutation. Mutation rates are kept low (typically 0.1–1% per gene per generation) to avoid destroying good solutions, but high enough to maintain diversity and allow the population to escape local optima that crossover alone cannot escape.

Together, these three operators implement a parallel search: the entire population explores the solution space simultaneously, with information about good regions shared through crossover each generation.

Convergence and Diversity

The central tension in any genetic algorithm is exploration vs. exploitation. A population that converges too quickly — all individuals becoming nearly identical — gets stuck in whatever local optimum it found first, unable to discover better solutions elsewhere in the search space. This is called premature convergence, and it is the most common failure mode of genetic algorithms.

Several techniques help maintain diversity. Fitness sharing penalizes individuals that are too similar to others in the population, spreading the search across multiple peaks in the fitness landscape. Island models run several sub-populations in parallel with occasional migration between them — each island can converge independently, but migrants prevent complete isolation. Niching explicitly reserves space in the population for solutions in different regions of the search space.

The right balance depends on the problem. For problems with a single global optimum in a relatively smooth landscape, aggressive selection and low mutation work well. For highly multimodal problems with many local optima of similar fitness, maintaining diversity is critical — the goal is to map the landscape, not just climb the nearest hill.

Real-World Applications

Genetic algorithms have produced solutions to engineering problems that human designers could not easily find — and in some cases, could not have imagined:

• NASA's evolved antenna: For the Space Technology 5 mission, engineers needed a compact antenna with specific gain and impedance properties across multiple frequency bands. A genetic algorithm evolved an antenna that looks like a randomly bent wire — it has no obvious symmetry or intuitive structure, yet it outperforms conventional designs on every target metric. Human engineers, constrained by intuitions about what antennas "should" look like, would never have found it.
• Drug discovery: Molecular structures can be encoded as chromosomes and evolved toward desired binding properties, toxicity profiles, and bioavailability. GAs are used to explore the vast chemical space of potential drug candidates far more efficiently than brute-force screening.
• Airline crew scheduling: Assigning thousands of crew members to flights while respecting union rules, rest requirements, and qualifications is an NP-hard optimization problem. Genetic algorithms routinely find near-optimal schedules that save airlines millions of dollars annually.
• Neural architecture search: Modern AI systems use evolutionary methods to automatically discover neural network architectures — the structure and connectivity of deep learning models — that outperform hand-designed alternatives.

Genetic Algorithms vs. Other Optimization Methods

Genetic algorithms are not always the right tool. Gradient descent — the workhorse of machine learning — is far faster when the fitness landscape is smooth and differentiable, because it can follow the gradient directly to a local optimum. GAs require many fitness evaluations and are slow by comparison on problems where calculus applies.

But GAs shine in situations where gradient methods fail:

• The fitness function is not differentiable — it involves discrete choices, combinatorial structure, or simulation.
• The landscape is rugged — full of local optima that gradient methods would get trapped in.
• The solution space is mixed continuous/discrete, making standard calculus-based approaches awkward.
• The problem is so high-dimensional that analytical methods are intractable.

Simulated annealing solves some of the same problems as GAs — it can escape local optima by occasionally accepting worse solutions, with the probability of doing so decreasing over time like a cooling metal. But it operates on a single solution rather than a population, losing the parallel search advantage. Particle swarm optimization uses a population like GAs but updates solutions using velocity vectors rather than genetic operators, excelling on continuous optimization problems.

The lasting lesson of genetic algorithms is not that they always win — it's that evolution, as an algorithm, is far more general and powerful than it looks. Given only a fitness function and enough generations, it can climb mountains of complexity that no engineer could climb alone.