The fitness function is not a detail of the implementation — it is the problem statement. Getting it wrong is the most common way a genetic algorithm fails.
Fitness Is the Objective
A genetic algorithm has no opinion about your problem. It cannot see the road network, the radio budget or the customer. All it sees is the single number your fitness function returns for each candidate solution, and selection then multiplies whatever earns a high number. That is the entire mechanism. It is also why the fitness function is not a detail of the implementation: it is your problem statement, written in the only language the search can read.
Holland (1975), Adaptation in Natural and Artificial Systems, set out the framework in which selection acts on a population of structures according to a measured payoff, and Goldberg (1989) is the standard textbook treatment that follows it. In both, fitness is the environment: change it and you change what the population becomes. Everything in this lesson follows from that one fact.
A genetic algorithm maximises the function you wrote, not the goal you had in mind. Every failure mode in this lesson is a gap between those two things. When a run produces a nonsense winner, suspect the fitness function before you suspect the operators.
Reward the Outcome, Not the Behaviour
The most common way to write a bad fitness function is to picture how you would solve the problem and then score candidates on how closely they imitate you. Suppose you are evolving the duty-cycle schedule of a battery-powered sensor and you want it to run as long as possible while still being useful. It is tempting to reward "keeps the radio switched off", because you know the radio dominates the power budget. Do that and the search will find exactly what you asked for: a schedule with the radio off, a battery that lasts, and no data delivered.
The fix is to measure the outcome you actually care about — useful readings delivered per battery charge — and let the search discover for itself that this implies keeping the radio off most of the time. A fitness function that encodes your assumed method can only ever rediscover your method. One that encodes the outcome is free to find something better.
When the outcome genuinely cannot be measured and you must use a proxy, treat the proxy as a hypothesis rather than as the objective: inspect the winning individual against the real goal by hand before you trust it. Module 14 meets the same hazard from the other direction, where it is called reward hacking — the agent optimises what you measured, not what you meant.
A Worked Example: Placing Sensors
Concretely: you have 40 candidate positions for environmental sensors over a site divided into 200 grid cells. Each position covers a known set of cells and has a known installation cost, and you have a fixed budget. Following Lesson 13.2, a candidate is a binary string of length 40 — bit i is 1 if position i is used.
The obvious first fitness function is "number of distinct cells covered". Run it and the population converges on strings of almost all ones: maximum coverage, and a bill several times the budget. Nothing in that fitness function mentions money, so the search has no reason to care about it. This single example carries the rest of the lesson — it has two objectives in tension, a hard constraint, and an evaluation step that costs real time.
Multi-Objective Problems
Coverage should go up and cost should come down. There is no single best answer to that, only a set of defensible compromises, and the question is which of them the algorithm is allowed to return.
Weighted Sums
The simplest approach collapses the objectives into one number with weights you choose in advance.
Two honest limitations. First, the weights are a decision you have made before seeing any of the trade-off, and one run returns one compromise. Second, a weighted sum can only ever return solutions that sit on the convex part of the trade-off surface; compromises tucked into a concave stretch of that surface are unreachable by any choice of weights.
Pareto Dominance and the Front
The alternative refuses to collapse the objectives at all. One solution dominates another if it is at least as good on every objective and strictly better on at least one.
A multi-objective genetic algorithm returns an approximation of that front rather than one point, and a human then picks from it with full sight of what each extra cell of coverage costs. That is usually the more useful deliverable, because the weights were never really known in advance.
NSGA-II in Outline
The standard elitist multi-objective genetic algorithm is NSGA-II, from Deb, Pratap, Agarwal and Meyarivan (2002). Three ideas, and it is worth knowing which is which:
- Fast non-dominated sorting — the population is partitioned into fronts. Front 1 is the non-dominated set; front 2 is what becomes non-dominated once front 1 is removed, and so on. A lower front rank is always preferred.
- Crowding distance — the tie-breaker within a front, since by definition no member of a front beats another. It estimates how empty the objective space is around each solution, and prefers the ones in sparse regions. This is what keeps the returned front spread out instead of clumped.
- Elitism by combination — parents and offspring are pooled, then sorted by front rank and, within a front, by crowding distance, and the pool is truncated back to the population size. A good solution cannot be lost by accident, which is the same argument for elitism made in Lesson 13.2.
| Approach | What you get back | When it fits | Limitation |
|---|---|---|---|
| Single objective + penalty | One solution | One real objective; the others are constraints | Needs penalty weights chosen well |
| Weighted sum | One compromise | The trade-off is genuinely known in advance | Cannot reach concave parts of the trade-off surface |
| Pareto front (NSGA-II) | A spread of compromises | A human will choose after seeing the options | More machinery; the front still has to be presented and read |
Constraint Handling
The budget in the sensor example is not an objective to be traded away — it is a wall. There are four standard ways to teach a genetic algorithm about a wall, and they differ in how much of the search space they leave usable.
Picking the penalty coefficients is the part that needs judgement. Too small and the winner is an infeasible solution that has simply bought coverage with money it does not have. Too large and the penalty behaves like rejection: the search cannot cross a slightly infeasible ridge to reach a better feasible region on the far side, which is often exactly the path it needs.
Always report whether the best individual is feasible as a fact of its own, not as something inferred from its fitness. A penalised score and a genuinely feasible score are the same kind of number, and confusing them is how an infeasible design gets presented as the answer.
Premature Convergence and Diversity Loss
A genetic algorithm's power comes from recombining different solutions. Once the population is made of near-copies of one individual, crossover between two of them produces that same individual again, and mutation is the only remaining source of novelty — which is a very slow random walk. This is premature convergence: the run has stopped improving long before it found anything good, and from the outside it looks exactly like a run that has finished.
How to Detect It
- Best minus mean fitness — plot both per generation. When the gap collapses toward zero early, the population has become uniform.
- Distinct genotypes — count unique individuals per generation. A steep, early fall is the clearest signal there is.
- Per-gene allele frequencies — for a binary encoding, the fraction of the population with a 1 at each position. Positions saturating at 0 or 1 are positions crossover can no longer explore.
- Average pairwise distance — Hamming distance for bit strings, Euclidean for real vectors. It is the direct measurement of the thing you are worried about.
How to Counter It
Diversity is lost when selection pressure is high relative to the variation the operators supply, so every countermeasure adjusts one side of that balance.
- Reduce selection pressure — a smaller tournament size, or rank-based rather than fitness-proportionate selection (Lesson 13.2). Often the cheapest fix and the first to try.
- Raise the mutation rate, or raise it adaptively when a diversity measure falls below a threshold.
- Fitness sharing — make similar individuals compete with each other for a shared share of the fitness, so a crowd is penalised for being a crowd. Niching methods of this kind are covered in Goldberg (1989).
- Crowding replacement — a new child replaces the individual it most resembles rather than the worst in the population, which keeps distinct regions occupied.
- Restarts — reinitialise the population but keep an archive of the best solutions found. Cheap, and often more effective than tuning.
- Island models — several sub-populations evolving separately with occasional migration, so convergence in one does not converge the others.
Cost Accounting
In almost every real application the fitness evaluation dominates the runtime. Selection, crossover and mutation are a few array operations; one evaluation might be a simulation, a compile-and-test cycle, or the training of a whole model. So the number that matters is not the generation count but the total number of evaluations.
Put arithmetic to it. A population of 100 over 200 generations is 100 × 200 = 20,000 evaluations. At two seconds per evaluation that is 40,000 seconds — a little over eleven hours on one core, or about twenty-one minutes spread across thirty-two workers. Nothing about that is a measurement of any particular problem; it is the multiplication you should do before you start a run rather than after.
Ways to spend the budget better:
- Cache by genotype. As the population converges the same individual is re-evaluated constantly. A dictionary from genotype to fitness is a few lines of code and can remove a large fraction of the work late in a run.
- Evaluate cheaply first. Score on a data subsample or a shortened simulation, then re-evaluate only the survivors at full cost. Be aware this makes the fitness noisy, which weakens selection.
- Use a surrogate. Fit a cheap model of the fitness landscape from the evaluations you already have, screen candidates with it, and pay full price only for the promising ones. This is the same surrogate idea Bayesian optimisation uses in Lesson 10.2.
- Abandon early. If a candidate cannot beat the current best partway through its evaluation, stop it.
- Parallelise. Every individual in a generation is evaluated independently, so a generational genetic algorithm scales almost linearly with workers. This is a genuine structural advantage over strictly sequential search methods.
Decide the evaluation budget first, then choose the population size and generation count to fit inside it. Both matter and they trade off: a large population explores more per generation but affords fewer generations for the same budget. Announcing "we ran 500 generations" says nothing until the reader knows P and the cost of one evaluation.
Fitness is the problem statement, so suspect it first when a run misbehaves. Reward the outcome rather than the behaviour you assume produces it. For several objectives, either weight them — after rescaling, and knowing a weighted sum cannot reach concave parts of the trade-off surface — or return a Pareto front, which is what NSGA-II (Deb et al., 2002) does with non-dominated sorting, crowding distance and elitist truncation. Handle constraints by penalty, rejection, repair or feasibility-preserving operators, and always report feasibility separately from fitness. Watch diversity with the best-minus-mean gap and the count of distinct genotypes, and counter its loss by lowering selection pressure, sharing fitness, crowding, restarting or splitting into islands. Finally, budget in evaluations, not generations: the fitness evaluation is where the time goes.