When Evolution Wins — and When It Loses | ML-101

Where a genetic algorithm earns its keep, where a cheaper method already exists, and the cost argument that decides most of it.

The Honest Question

Lesson 13.1 framed evolution as a search strategy rather than a model class, and that framing decides this whole lesson. The question is never "is a genetic algorithm good?" — it is "does my problem have structure that a cheaper method could exploit, and am I ignoring it?" A genetic algorithm asks almost nothing of a problem: no derivatives, no convexity, no continuity, not even a numerical representation. That generality is exactly why it is slow. You pay for every assumption you decline to make.

So the useful way to read this lesson is as a set of tests. Each application below wins for a specific reason, and each of those reasons is also a way of failing the test when your problem is different.

If the Objective Is Differentiable, Use the Gradient

This is the single most important rule in the module, and it is a statement about information per unit of compute rather than about elegance. When a loss is differentiable in its parameters, backpropagation (Lesson 6.3) computes the exact partial derivative with respect to every parameter in one backward pass, at a cost of roughly the same order as one forward pass.

What One Backward Pass Returns

\nabla_{\boldsymbol{\theta}} L = \left[\frac{\partial L}{\partial \theta_1}, \; \frac{\partial L}{\partial \theta_2}, \; \ldots, \; \frac{\partial L}{\partial \theta_d}\right]

All d components at once, each telling you which way to move that parameter and how strongly. A population-based method paying for P evaluations receives P scalars in exchange, and has to infer a direction in d dimensions from them.

For a network with millions of parameters that difference is not a matter of degree. Evolving the weights of a large network by fitness values alone means discarding the derivative information the model was built to provide. If the objective is differentiable — and every loss in Modules 2, 6, 7, 8 and 9 is — the gradient is not merely the faster option, it is the option that uses what you know.

The Cost Argument in One Line

A genetic algorithm spends population x generations evaluations to make progress that a differentiable model makes with one forward and one backward pass per step. Reach for evolution when that trade is forced on you by the problem, not when it is chosen.

The Budget You Are Committing

N_{\text{eval}} = P \cdot G, \qquad T_{\text{wall}} \approx \frac{P \cdot G \cdot t_{\text{eval}}}{K}

The same accounting as Lesson 13.3. When one evaluation is itself a full model training run, P and G are multipliers on that cost — which is why the sections below care so much about how expensive a single fitness evaluation is.

Hyperparameter Search

Hyperparameters are not differentiable in any usable way, they mix continuous and discrete and conditional choices, and each evaluation is a training run. That is a genuine black box, so a genetic algorithm is at least admissible here — which is not the same as being the right tool. Lesson 10.2 already taught the alternatives; the point of this section is to place evolution honestly among them.

Method	How it chooses the next point	Parallelism	What it needs from you
Grid search	Enumerates a grid fixed before the first run	Fully parallel	A grid, and few enough dimensions that it is affordable
Random search	Samples from ranges you specify; ignores all results	Fully parallel	Sensible ranges and distributions
Bayesian optimisation	Fits a surrogate to every result so far, then optimises an acquisition function	Sequential by design; batching needs extra machinery	A search space the surrogate can model
Genetic algorithm	Recombines and mutates the better members of the current population	Fully parallel within a generation	An encoding, plus operators that respect it

Three mechanism-level observations, and deliberately no claim about which one wins:

Bayesian optimisation extracts more from each evaluation. It models the value of the objective and its uncertainty everywhere it has not looked. Tournament or rank selection in a genetic algorithm uses only the ordering of a generation, discarding magnitudes. Where evaluations are the scarce resource, using more of each one is the structurally sound choice.
A genetic algorithm uses parallel hardware more naturally. Every individual in a generation is independent, so P workers are busy without any extra theory. Bayesian optimisation is sequential in its basic form because each choice depends on the previous result.
Awkward search spaces favour evolution. Variable-length configurations, layer stacks, conditional parameters that only exist if another was chosen, permutations — you can encode all of these directly and write operators that keep them valid. Making a surrogate model handle the same objects requires a kernel defined over them.

And the honest first move, before any of this: for a handful of hyperparameters, random search over sensible ranges is a strong default. Bergstra and Bengio (2012) showed random search finds configurations as good as or better than grid search for the same budget, because most hyperparameter spaces have low effective dimensionality. Do not open with a population-based method for a problem that a hundred random trials will settle.

Feature Selection as Subset Search

Choosing which of d features to keep is a natural fit for the binary encoding of Lesson 13.2: one bit per feature, one string per candidate subset. The search space is every subset.

Subset Search Space and Fitness

|\mathcal{S}| = 2^{d}, \qquad F(S) = \mathrm{CV}(S) - \alpha \cdot \frac{|S|}{d}

With d = 50 features there are more than 10^15 subsets, so enumeration is out. Fitness is a cross-validated score with a penalty for keeping features, since a subset that scores the same with fewer columns is the better subset.

This is a wrapper method: fitness is the performance of the actual model, so it can find combinations of features that only help together — something a filter ranking each feature on its own cannot see. It also means each evaluation is a full cross-validation, which puts the cost accounting of Lesson 13.3 squarely in charge.

The Trap: Overfitting the Validation Score

You are about to select the maximum of tens of thousands of noisy cross-validation scores. The winning subset will look better than it is, because some of its apparent advantage is luck in those particular folds. Hold out a test set that the search never touches and report the final number there — the same discipline Lessons 1.4 and 10.2 insist on, and it matters more here because the search evaluates the validation score so many times.

Cheaper alternatives you should rule out first: L1 regularisation drives coefficients to exactly zero as a side effect of fitting one model (Lesson 2.3); tree-based feature importance comes almost free from a model you already trained (Lesson 3.2); and greedy forward or backward selection costs on the order of d-squared evaluations rather than a full population search. A genetic algorithm earns the extra cost when features interact strongly enough that a greedy path gets stuck.

Neuroevolution

Neuroevolution means evolving neural networks, and it splits into two quite different jobs.

Evolving Weights

Encode the weights as a real-valued vector and select on performance. Given the gradient argument above, this is the wrong choice whenever a differentiable loss exists — which is most supervised learning. It becomes reasonable exactly when no such loss does: when the only feedback is the outcome of a simulation or a game, when the reward arrives long after the actions that earned it, or when the network's output passes through something non-differentiable before the score appears. Note that Module 14 attacks the same class of problem with reinforcement learning, which does construct a gradient estimate from reward, so evolution is one option there rather than the only one.

Evolving Architecture

Topology is discrete: how many layers, how wide, which connections exist. No gradient is available with respect to those choices, so search is the honest approach and evolution is a natural fit. NEAT — Stanley and Miikkulainen (2002), Evolving Neural Networks through Augmenting Topologies — evolves connection weights and topology together, and its three well-known ideas each solve a specific problem that arises once structure can change:

Start minimal and complexify. Begin with the simplest networks and add nodes and connections over the run, so the search does not begin in a needlessly large space.
Historical markings. Each new structural element gets an identifier when it first appears, which lets crossover line up the genes two networks inherited from a common ancestor instead of pairing unrelated parts.
Speciation. Individuals compete mainly within their own species, protecting a newly added structure long enough to have its weights optimised. Without it, a fresh innovation is usually worse on arrival and is selected away before it can be made to work.

Symbolic Regression and Genetic Programming

In genetic programming the individual is a program rather than a vector. Koza (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, represents programs as expression trees over a chosen set of functions and terminals; crossover swaps subtrees between two parents, and mutation replaces a subtree with a new one. Because the operators work on trees, the candidate stays a valid program — the feasibility-preserving idea from Lesson 13.3, applied to code.

Applied to data fitting this is symbolic regression: search over expressions for one that both fits and can be read. The output is not a set of weights but something like a formula you could put in a report and reason about, which is a different deliverable from every other model in this course. Where it pays is exactly there — when you want the relationship, not only the prediction.

Parsimony Pressure

F(p) = -\,\mathrm{error}(p) \; - \; \beta \cdot \mathrm{size}(p)

Trees tend to grow over a run without fitting any better — known as bloat — and a huge expression defeats the purpose of using this method at all. Charging for size is the standard countermeasure; beta sets how much accuracy you will trade for readability.

When Not to Reach for a Genetic Algorithm

The objective is differentiable. Use the gradient. This covers most of this course.
The problem is convex, linear or a standard integer program. A dedicated solver returns an answer with a bound on how far from optimal it is. A genetic algorithm returns a good solution and no bound at all.
The problem has known combinatorial structure. Shortest paths, matchings, scheduling problems with an exact algorithm — an exact method that exploits the structure beats a general search that ignores it.
The search space is small. A few thousand candidates? Enumerate them. You get the true optimum and simpler code.
The fitness is very noisy. Selection needs to be able to tell two candidates apart. If the noise exceeds the differences, the population drifts and the run only looks like it is working.
You cannot write a fitness function you trust. Then the problem is Lesson 13.3, not the algorithm, and no amount of tuning will rescue it.
Your evaluation budget is tiny. A handful of expensive evaluations suits a method that models the objective; a population of 100 has not even finished being born.

A Decision Checklist

Can I differentiate the objective? If yes, stop here and use the gradient.
Does the problem match a solved class? Convex, linear, integer program, graph problem — use the dedicated method and get a guarantee.
Is the space small enough to enumerate, or to settle with random search? Try the cheap thing first, and keep it as the baseline the search must beat.
How expensive is one evaluation, and how many can I afford? Very few and very expensive points toward a surrogate-model method; many, cheap and parallel points toward a population.
Is my representation awkward — variable length, conditional, permutations, trees? This is where evolution is genuinely comfortable and other methods need extra scaffolding.
Do I trust the fitness function? Re-read Lesson 13.3 before spending the budget.
Have I fixed the honest baseline? Random search under the same evaluation budget. Report both, or the comparison means nothing.

Key Takeaways

A genetic algorithm assumes almost nothing about the problem, and pays for that generality in evaluations. If the objective is differentiable, use the gradient: one backward pass gives the exact derivative for every parameter, while P evaluations give P scalars. Evolution is admissible for hyperparameter search, but compare it honestly with grid, random and Bayesian search (Lesson 10.2) — Bayesian optimisation extracts more per evaluation, a genetic algorithm parallelises more naturally, awkward search spaces favour evolution, and random search (Bergstra and Bengio, 2012) is the baseline all of them must beat. Feature selection as subset search works and overfits the validation score if you let it. Evolving architecture is more defensible than evolving weights, and NEAT (Stanley and Miikkulainen, 2002) shows why: minimal starts, historical markings, speciation. Genetic programming (Koza, 1992) is the case where the deliverable is a readable expression, with bloat as the standing hazard. And when a cheaper method fits the problem, use it.