Evolution as a Search Strategy

When There Is No Gradient to Follow

Every method in this course so far has asked the objective the same question: which way is downhill? Gradient descent in Module 2 answers it with a derivative. Backpropagation in Module 6 answers it by pushing that derivative back through a stack of layers. Both are extraordinarily efficient, and both depend on one thing being true — that the quantity you want to improve is a smooth function of the numbers you are allowed to change.

A great many real objectives are not. Four kinds show up constantly:

Discrete choices. Which of your 40 candidate features should the model see? There is no derivative with respect to “include feature 7 or not” — it is a yes-or-no switch, not a dial. Combinatorial structure. In what order should a maintenance crew visit 20 cell sites? The answer is a permutation, and nudging a permutation by an infinitesimal amount is meaningless. Simulation-based objectives. If the score comes out of a network simulator, a queueing model or a physical measurement, there is no formula to differentiate — only a procedure to run. Black boxes. If the thing you are scoring is a vendor binary or a piece of hardware, you get outputs for inputs and nothing else.

Take the feature-selection case concretely. With 8 candidate features there are 2⁸ = 256 possible subsets, and you could simply try them all. With 40 candidates there are 2⁴⁰ = 1,099,511,627,776 subsets. If a single evaluation means training and scoring a model in one second, exhaustive search finishes in about thirty-four thousand years. The space is finite, fully specified, and hopeless to enumerate.

What you can still do is evaluate and compare. You may not know the shape of the objective, but you can hand it a candidate and read back a number. That is the only interface a genetic algorithm ever needs.

One Point Downhill, or a Population Spread Out

Gradient descent maintains exactly one candidate solution and moves it. Each step reads the local slope and takes a step against it.

A population method maintains many candidates at once and gets its information from comparisons among them. Nobody ever asks which direction is better; the algorithm only ever asks which candidate is better. That difference buys three things:

Several regions at once. A single hill climber commits to the neighbourhood it started in. A population of 50 can be sitting in several basins simultaneously, and the ones in poor basins are cheap to abandon. Parts, not just points. Two mediocre candidates can each hold a useful fragment — one has the right set of features, the other the right regularisation strength. Recombination is what lets a method assemble a child from both, and it is the ingredient no single-point method has. No smoothness requirement. Comparison works on anything you can order: integers, permutations, program trees, categorical choices.

The Four Ingredients

John Holland set out this scheme in Adaptation in Natural and Artificial Systems (1975), and David Goldberg’s Genetic Algorithms in Search, Optimization, and Machine Learning (1989) is the textbook that carried it into engineering practice. Strip away the biological vocabulary and any genetic algorithm is four decisions:

1. Representation. How is one candidate solution written down? A bit string, a vector of real numbers, a permutation, a tree. This choice constrains everything after it, because the variation operators have to act on whatever you chose. 2. Fitness. The single number that says how good a candidate is. This is the objective, and Lesson 13.3 is devoted entirely to getting it right. 3. Selection. Which candidates get to be parents. This is where the search direction comes from. 4. Variation. How children differ from parents — recombination of two parents (crossover) and small random change (mutation).

Selection Pressure, and the Classic Failure

Selection pressure is how strongly better-than-average candidates are favoured when parents are chosen. It is the single most consequential setting in the whole method, and getting it wrong is the classic way a genetic algorithm fails while appearing to work.

The oldest scheme, fitness-proportionate selection, gives each individual a share of the parent slots in proportion to its fitness:

Too much pressure is the failure mode to fear. If the best individual takes most of the parent slots, its copies fill the population within a few generations. Diversity is then gone, and with it crossover: recombining two nearly identical parents reproduces the parent. All that remains is mutation, so the method quietly degenerates into a slow random walk around one point — and it is quiet, because average fitness stops falling and the run looks converged. This is premature convergence, and Lesson 13.3 covers how to detect and counter it.

Too little pressure fails less dramatically and just as completely. If parents are chosen almost uniformly, good structure is not preserved long enough to be built on, and the population drifts. You have paid for a population and bought random search.

Where the Genetic Algorithm Sits

Genetic algorithms are one option among several for a derivative-free objective, and it helps to see the family in order of how much memory each method keeps.

Random search samples candidates independently. It has no memory at all, so it never gets better at guessing — but it is trivially parallel and it is a serious baseline, not a straw man. Grid search enumerates a lattice. It is systematic and reproducible, and the number of points it needs multiplies with every dimension you add, which is why Lesson 10.2 warns you off it for high-dimensional hyperparameter tuning. Hill climbing keeps one candidate and accepts only improving moves. It exploits well and gets stuck in the first local optimum it meets; random restarts are the usual patch. Simulated annealing also keeps one candidate but sometimes accepts a worse move, with a probability that shrinks as a temperature parameter is lowered — exploration early, exploitation late, one point throughout. Genetic algorithms keep a population and add recombination: the ability to build a child out of parts of two different parents. That operator is what distinguishes them from everything above, and Goldberg (1989) is explicit that traditional search methods — calculus-based, enumerative and purely random — each fail on a different class of problem, which is the argument for having this family available at all.

Evolution Is a Search Strategy, Not a Model Class

This is the framing to hold on to, and it is the one most often garbled. A genetic algorithm is not a competitor to a random forest or a neural network. It does not learn from labelled data, and it produces no model. It is a way to choose — which features, which hyperparameters, which architecture, which schedule, which rule set — and the model class is whatever your fitness function trains and scores inside the loop.

Two consequences follow immediately. First, a genetic algorithm is only as good as the fitness function you gave it; there is no equivalent of “more data will fix it”. Second, if your objective is differentiable, use the derivative. A gradient tells you a direction in one evaluation; a population has to infer a direction from many. Reaching for evolution when calculus is available is the most common way to spend a hundred times the compute for a worse answer — a point Lesson 13.4 makes with the cost arithmetic laid out.

Nor is any of this guaranteed to find the best solution. A genetic algorithm is a heuristic: it trades the guarantee for the ability to work on problems where no guarantee is on offer at any price. What you control is the budget — population size times generations — and what you get is the best candidate seen inside it.