Branch and bound took us to the optimum of Rutalia's TSP by expanding a thousand nodes instead of a million — but we closed that lesson admitting that the combinatorial explosion was only delayed: with the 60-120 stops of a real van, no exact method finishes in time. This lesson crosses the frontier deliberately: genetic algorithms (GA) give up the guarantee of optimality and, in exchange, produce very good solutions in controlled time, for almost any problem you know how to evaluate. We will cover the full evolutionary scheme — encoding, population, fitness, selection, crossover, mutation, elitism — and implement it end to end in Python on the same 10-point instance from 02-02/02-03, so we can compare against the known optimum of 35.22 km. We'll finish with a hyperparameter guide and a brief look at the "cousin" metaheuristics (simulated annealing, tabu search).

1. Exact vs heuristic: what we sacrifice and what we gain
2. The evolutionary metaphor
3. Representation: binary chromosomes and permutations
4. The fitness function
5. Selection: tournament and roulette
6. Crossover: one-point and order crossover (OX)
7. Mutation, elitism, and stopping criteria
8. Complete implementation: a GA for Rutalia's TSP
9. Hyperparameters: what to tune and what to expect
10. The neighborhood cousins: simulated annealing and tabu search

The key word is certificate. A GA can hand you the optimal route — in fact, on our small instance it will — but it cannot tell you so: it produces no bounds proving that nothing better exists. For Rutalia the deal usually pays off: between "the optimal route in three weeks" and "a route 2% worse in one minute", operations picks the latter every single day. Professional discipline consists of knowing when you are making that deal and measuring quality against bounds or instances with a known optimum — exactly what we will do here.

A GA maintains a population of candidate solutions and evolves it by imitating natural selection:

The intuition for why it works: selection concentrates the population in good areas of the solution space (exploitation), crossover combines good fragments from different parents — perhaps one parent solves the north of the city well and the other the south —, and mutation injects variety to avoid getting stuck (exploration). None of this guarantees the optimum; what it produces is a sustained statistical pressure toward better solutions.

Vocabulary we will use: individual/chromosome (an encoded solution), gene (one position of the chromosome), fitness (the individual's quality), generation (one iteration of the loop).

The first design decision — and the most important — is how to encode a solution:

• Binary encoding: a list of 0/1. Natural for subset problems, like the knapsack from 02-02: [0, 1, 0, 1, 0] means "load E2 and E4". The classic operators (one-point crossover, bit-by-bit mutation) work directly.
• Permutation encoding: an ordering of elements. Natural for sequence problems like the TSP: [3, 1, 5, ...] is the visiting order of the stops. Careful: the classic binary operators break the solution here — crossing two permutations at one point usually duplicates some stops and omits others, i.e. it produces children that aren't even routes. Permutations demand specialized operators (OX, which we'll see shortly).

Fitness translates "quality" into a number that selection can compare. For the TSP, shorter distance = better individual. Two common options: use the route length directly (and select the smallest), or convert to "bigger is better" with fitness = 1 / length. We'll use the former for clarity, with one engineering precaution: fitness evaluation is 90% of the cost of a typical GA (it runs population × generations times), so it must be cheap — and with our matrix D precomputed in 02-02, it is.

For constrained problems (an overweight knapsack), the fitness must additionally decide what to do with infeasible individuals: penalize (subtract a lot of value per kilo of excess) or repair (unload items until it fits). Badly calibrated penalties are a classic source of GAs that "work" while full of unusable solutions.

Selection chooses which individuals reproduce. It must favor the good ones without wiping out diversity (if only the best one reproduces, within three generations the population is clones and the GA degenerates into an expensive greedy).

• Tournament (k participants): pick k individuals at random and the best one wins. Simple, robust, and with adjustable pressure: k = 2 is gentle, k = 7 is aggressive. It's the default choice in practice.
• Roulette: each individual gets a probability proportional to its fitness (a "roulette wheel" with unequal sectors). Elegant in theory, delicate in practice: it requires positive, "bigger = better" fitness, and if one individual dominates heavily, it monopolizes the wheel (premature convergence); if all are similar, selection becomes almost random.

One-point crossover (binary encoding): cut both parents at the same random position and swap the halves. For the knapsack: [1,0|0,1,1] × [0,1|1,0,0] → children [1,0,1,0,0] and [0,1,0,1,1]. Cheap and effective when contiguous genes form meaningful "blocks".

Order crossover (OX) (permutations): the star operator for routes. It copies a segment from parent 1 verbatim, and fills the gaps with the remaining stops in the order they appear in parent 2. The child inherits a literal sub-route from one parent and the relative ordering of the other — and it is always a valid permutation:

• Mutation: with small probability, alter the individual. Binary: flip a bit. Permutations: swap two positions or reverse a segment. Without mutation, the population only recombines its initial genetic material: if no initial permutation puts H at the end, crossover will never invent it; mutation will.
• Elitism: copy the 1-2 best individuals intact into the next generation. It guarantees the best result never gets worse between generations (a monotonicity that stochastic selection alone does not provide). With too much elite, the population homogenizes.
• Stopping criteria: a fixed number of generations (predictable, our default), stagnation (X generations without improvement — the most used in production), a time budget, or reaching a known bound.

All together, on the instance from 02-02 (requires NAMES, D, and route_length from that lesson). The depot (index 0) stays out of the chromosome: it is always the start and the end, so the individual is a permutation of [1..9]:

Points that deserve a magnifying glass:

• Total evaluations: 100 individuals × 200 generations = 20,000 route evaluations — the same order of useful work as B&B's ~1,200 nodes multiplied by their bound cost, and far below brute force's 362,880 routes. In our run, the GA reaches the known optimum of 35.22 km (the same route as B&B), usually within the first few dozen generations. That this almost always happens on a 10-node instance is to be expected: the space is small for the method's power. The difference appears at scale: with 100 stops, B&B doesn't finish and the GA keeps delivering good routes with the same code.
• The elite is copied (ind[:]), not referenced: if mutation touched a shared reference, it would silently corrupt the best individual. Bugs like that are the nightmare of debugging GAs, because the algorithm keeps working, just worse.
• The history is your diagnostic instrument: a curve that drops fast and flattens early suggests convergence (premature?); one that keeps stumbling downward until the end is asking for more generations.
• The seed pins the random sequence. In production you run several seeds and report the mean and best case — a single run of a stochastic algorithm is an anecdote, not a measurement.

GAs aren't programmed once: they are tuned. A guide to the effects:

The underlying tension is always the same: exploitation (refining the good: more selection pressure, more elite) versus exploration (seeking the new: more mutation, larger population). There is no universal configuration; there is the habit of measuring with the history and adjusting one parameter at a time.

GAs are not the only way to search without guarantees. Two families worth knowing by name — they work with a single individual that moves through its neighborhood (solutions one small change away), instead of with a population:

• Simulated annealing: sometimes accepts moves that make things worse, with a probability that decays over time (the "temperature" cools). Early on it explores freely; at the end it only refines. Inspiration: the slow cooling of metals.
• Tabu search: local search that keeps a tabu list of recently made, now-forbidden moves, so as not to undo its steps or cycle around a local optimum.

In practice they compete head-to-head with GAs (and are often hybridized: a GA whose best individual is refined with local search). We won't develop them further: it's enough to know they exist and what sets them apart, because the next lesson presents a metaheuristic of a very different spirit — based on cooperation through shared trails — and we'll close by comparing the module's three approaches on the same TSP.

• Classic crossover on permutations. One-point crossover applied to routes produces children with duplicated and omitted stops — they aren't even solutions. With permutations, use OX (or its relatives PMX/CX). It's the number-one mistake when adapting knapsack code to the TSP.
• Forgetting to copy the elite. new_gen = population[:2] stores references; a later mutation corrupts the best individuals. Copy with ind[:] or list(ind).
• Expensive fitness. If evaluating an individual costs 10 ms, 100 × 200 evaluations is 3.3 minutes of fitness alone. Precompute (our matrix D), cache, vectorize. The cost analysis of 01-02 applies inside the metaheuristic.
• Undiagnosed premature convergence. If by generation 20 all individuals are nearly identical, the rest of the budget is thrown away. Monitor diversity (e.g. distinct lengths in the population) in addition to the best fitness.
• Concluding from a single run. Stochastic means seed 42 might be lucky. Run 10-30 seeds and look at the distribution, not the anecdote.
• Using a GA where a viable exact method exists. For the 5-shipment knapsack or the 10-point TSP, DP and B&B deliver the certified optimum in less time than it takes to tune hyperparameters. Metaheuristics are the frontier tool, not the first option.
• Tip: always keep the global best individual of the run (not just the last generation's) and, if one exists, compare it against a bound or a known optimum. Without a reference, "the GA improved" means nothing.

1. OX by hand. With parents P1 = [2, 5, 1, 4, 3, 6] and P2 = [4, 1, 6, 2, 5, 3] and a segment at positions 1–3 (0-indexed, both inclusive), compute the ox_crossover child step by step. Verify that it is a valid permutation.

2. A GA for the knapsack. Adapt the full scheme to the 0/1 knapsack from 02-02 (capacity 15, weights [12, 7, 11, 8, 9], values [40, 24, 35, 26, 30]): binary encoding, one-point crossover, bit-flip mutation, and fitness with a penalty for excess weight (value − 10 × excess). Does it reach the €50 optimum? What happens if the penalty is 1 per unit of excess instead of 10?

3. Mutation study. Run genetic_algorithm with mutation_prob in {0.0, 0.05, 0.2, 0.8} and 10 seeds each (leave the other parameters at their defaults). For each value, record how many seeds reach 35.22 km and the mean of the best result. Interpret the extremes.

Exercise 1. Segment of P1, positions 1–3: 5, 1, 4 → partial child [_, 5, 1, 4, _, _]. Remaining from P2 in its order, skipping 5, 1, 4: P2 = [4, 1, 6, 2, 5, 3] → 6, 2, 3 remain. Gaps: positions 0, 4, 5 → child = [6, 5, 1, 4, 2, 3]. It contains each gene 1..6 exactly once: a valid permutation. Note the inheritance: the block 5-1-4 comes verbatim from P1; the relative order 6 → 2 → 3 comes from P2.

Exercise 2. Skeleton of the changes:

With penalty 10, excess weight is exorbitantly expensive and the population converges to feasible individuals; the optimum [0,1,0,1,0] (€50) shows up within a few generations — the space has only 2⁵ = 32 points, so it's less a challenge than a test bench. With penalty 1, the GA discovers an unwanted "trick": [1,1,1,1,1] weighs 47 (excess 32) and scores 155 − 32 = 123 > 50 — the best individual is infeasible and the GA enthusiastically optimizes the wrong problem. That's the important lesson of the exercise: the penalty must ensure that no infeasible individual beats a feasible one, or the fitness lies.

Exercise 3. Typical results (yours will vary — that's what the exercise is about): with 0.0, several seeds get stuck above the optimum — without mutation, the population exhausts its initial genetic material and cannot manufacture new orderings; with 0.05 and 0.2, the vast majority of seeds reach 35.22 km, with 0.2 somewhat more robust on this instance; with 0.8, children are destroyed almost as soon as they're born and the mean worsens — the search approaches random sampling with an elite. The quality-vs-mutation curve is an inverted U: the sweet spot is where there's enough variety without destroying inheritance.

We have made the heuristic deal with our eyes open: in exchange for the certificate of optimality that DP and B&B provided, genetic algorithms give us scale and generality — all they ask for is a sensible encoding (binary for subsets, permutations with OX for routes), a fitness that is cheap and honest about constraints, and the eternal balance between selection pressure and mutation. On Rutalia's TSP, our GA of 100 individuals and 200 generations reached the same 35.22 km that B&B certified in 02-03 — unable to certify them, but with code that would keep working just the same with 100 stops, where B&B is no longer in the game. In the next lesson we'll meet a metaheuristic with a different biological inspiration: instead of inheritance and selection, indirect cooperation — ants leaving chemical signals on the good routes. We will implement ant colony optimization on this same instance and close the module with the experimental comparison of the three approaches: exact, evolutionary, and stigmergic.