Genetic Algorithms

In the preceding chapter we compared nearest-neighbour construction, best-improvement hill climbing with restarts, and simulated annealing on a small vehicle-routing instance. Those searches maintain one current candidate at a time. The hill climber can stop improving in its current neighbourhood, while annealing can accept a worse move under its temperature rule; neither finite-budget run guarantees that it visits every promising region.

A genetic algorithm attacks the same problem from a different angle. Instead of one candidate solution, it maintains a population of them. Instead of perturbing and accepting, it selects promising parents, builds new candidates by combining parts of two parents (crossover) and by perturbing the result (mutation), and then lets the better candidates survive (selection with elitism). The hope is that recombination assembles partial solutions that neither parent contains, so the population can improve faster than a single trajectory.

For that hope to pay off, the encoding has to cooperate. Our decision variable is the visiting order of eight customers, so a candidate is a permutation and every child of crossover or mutation must remain a permutation: no duplicated customers, no missing ones. The order-preserving crossover we build below guarantees this by construction, and the decoder turns any permutation into two feasible depot tours, so no repair step is needed for this instance.

Our aim in this chapter is to build the mechanism from primitives, count every objective evaluation, and compare it with NN-seeded random search, best-improvement segment-reversal hill climbing, and simulated annealing under the same 300-evaluation budget on exactly the same routing instance. Nearest-neighbour construction supplies the common starting permutation and is also reported separately as a one-evaluation baseline. Because the instance has only eight customers, we can enumerate all $8! = 40320$ permutations and report gaps to that reference. The worked parents are chosen to illustrate crossover; the repeated-run comparison will tell us how the actual search performs under its budget.

The evolutionary search here needs no derivatives. It scores complete candidates, making the framework applicable to a black-box objective when an encoding, valid variation operators, and a meaningful comparison rule are available. Candidates may be permutations as here, binary subsets, assignments, or real and integer vectors. Gradient Descent and Numerical Optimization used derivatives to construct local updates; our loop compares candidate costs directly. Noise still requires care because a low observed cost need not mean a low expected cost.

A population can retain candidates in several regions and offers several parents from which to build children. Recombination can combine structures from two candidates. In the deliberately selected worked example, parents of cost $38.2665$ and $39.1233$ produce a child of cost $37.3560$, shorter than either parent and equal to the enumerated minimum to the reported precision. This demonstrates one possible update; it does not estimate the probability of finding that child in a run or establish an advantage over local search.

The framework admits different encodings and operators. Constraints may be enforced by a feasible decoder, checked after variation, repaired, or included in a penalized comparison. Each approach needs validation. For a fixed deterministic objective, the elitist survival rule used here preserves the best retained cost, and an archive can return the best scored candidate when the allowed budget is exhausted.

Population initialization spends evaluations before any offspring are produced. With a population of 20 and a budget of 300, initialization costs 20 and leaves 280 offspring evaluations, or 14 complete generations. Full enumeration uses 40320 evaluations and is feasible for this teaching instance, but it has a different budget. We compare the heuristics at 300 evaluations and account separately for the exhaustive reference and other diagnostic work.

A finite run does not certify a global optimum. Outcomes can depend on the starting population, tournament size, variation probabilities, survivor rule, and stopping budget. Testing settings also performs evaluations: report that tuning separately or include it in the application budget. A successful hand-picked crossover is not evidence that a particular parameter setting will be effective across instances.

Selection can reduce diversity. When parents are identical permutations, the order crossover below returns that same permutation, so mutation is needed for a different child. A mutated child can still be rejected by elitist survival. Different permutations can also encode the same unordered pair of tours; this distinction matters when interpreting diversity. Finally, crossover can break useful route adjacencies or change vehicle assignments, even when it always produces a valid permutation.

The intuition behind a genetic algorithm is easy to state: keep several candidates alive, let good ones reproduce, and trust variation plus selection to improve the population. The formulas below make that intuition precise. They answer four questions in order: how a candidate is encoded and scored, how parents are chosen, how children are built without breaking the encoding, and how the next generation is chosen. Each piece exists for a reason, and the reasons are what make the algorithm more than a random search with extra steps.

We begin with the object being searched over. Because the decision is the order in which eight customers are visited, the natural genotype is a permutation. Let $n = 8$, let $\mathcal{C} = \{1,\dots,8\}$ index the customers, and let node $0$ be the depot. A genotype is a permutation

$$p = (p_1, p_2, \dots, p_8), \qquad \{p_1,\dots,p_8\} = \mathcal{C},$$

where:

• $p$: the permutation (genotype), a length-8 ordering of the customers
• $p_j$: the customer visited at position $j$ of the permutation
• $\mathcal{C}$: the set of customer indices $\{1,\dots,8\}$
• $n$: the number of customers ($n=8$), hence the length of every permutation

so the search space is $X = S_8$ with $|X| = 8! = 40320$ elements. This is already a strong constraint: every point in the search space is a valid ordering, and every ordering contains each customer exactly once. The algorithm never has to reason about missing or duplicated customers.

The permutation alone is not yet a pair of routes. The phenotype is produced by a decoder that cuts the permutation into two blocks of four and closes each block into a depot tour:

$$D(p) = \big([0, p_1, p_2, p_3, p_4, 0],\; [0, p_5, p_6, p_7, p_8, 0]\big).$$

where:

• $D(p)$: the phenotype of permutation $p$, a pair of closed depot tours
• $p_1,\dots,p_4$: the customers assigned to the first vehicle, visited in that order
• $p_5,\dots,p_8$: the customers assigned to the second vehicle, visited in that order
• $0$: the depot that opens and closes each tour

The decoder is doing two jobs at once. It assigns the first four customers to one vehicle and the last four to the other, and it makes every permutation feasible with respect to capacity, because each vehicle receives exactly four customers with $q_i = 1$ and $Q = 4$. That is not an accident of this instance: every customer demand is $q_i = 1$, every vehicle capacity is $Q = 4$, and the total demand $\sum_{i \in \mathcal{C}} q_i = 8$ equals the total capacity $2Q = 8$. The decoder enforces the only capacity split that can work.

Writing $d(a,b)$ for the Euclidean distance between nodes $a$ and $b$, the objective is the total length of both tours: the sum of the two closed depot tours produced by the decoder, in which each route begins at the depot, visits its four assigned customers in permutation order, and returns to the depot. The sum has ten terms in total: two depot-to-first-customer arcs, six customer-to-customer arcs, and two last-customer-to-depot arcs.

$$f(p) \;=\; \sum_{r=1}^{2}\Bigg[\, d\!\left(0,\,p_{4r-3}\right) \;+\; \sum_{j=4r-3}^{4r-1} d\!\left(p_j,\,p_{j+1}\right) \;+\; d\!\left(p_{4r},\,0\right) \Bigg].$$

where:

• $p$: the permutation (genotype) being scored, a length-8 ordering of the customers
• $p_j$: the customer visited at position $j$ of the permutation
• $r$: the vehicle index, running over the two vehicles $r=1$ and $r=2$
• $4r-3$: the first position of vehicle $r$'s block ($1$ for vehicle 1, $5$ for vehicle 2)
• $4r$: the last position of vehicle $r$'s block ($4$ for vehicle 1, $8$ for vehicle 2)
• $d(a,b)$: the Euclidean distance between nodes $a$ and $b$
• $0$: the depot node
• $f(p)$: the summed length of both closed tours, the quantity minimised

Read the outer sum first: it runs over the two vehicles, $r=1$ and $r=2$. Inside each term there are three pieces:

• the arc from the depot to the first customer of the route,
• the three arcs that connect the four customers of the route in order,
• the arc back to the depot.

The index arithmetic $4r-3$ is just bookkeeping that starts vehicle 1 at position $1$ and vehicle 2 at position $5$: for $r=1$ we get $4r-3=1$ and the inner sum runs over $j=1,2,3$; for $r=2$ we get $4r-3=5$ and the inner sum runs over $j=5,6,7$. The inner sum connects consecutive customers within a block, and the two outer distance terms close the block to the depot at both ends, so each route has five arcs: three customer-to-customer arcs connecting the four customers, plus the depot-to-first-customer arc and the last-customer-to-depot arc. Across both routes that is ten arcs, which matches the ten distance terms in the formula. The objective is a pure routing length: no vehicle cost, no lateness term, no service-time term. Every one of the ten arcs that the decoder creates is charged exactly once, and no arc is charged twice.

We use unit travel speed, so travel time equals Euclidean distance. Feasibility is checked by simulating each route. With $s_i$ the service start at node $i$, $a_i$ the arrival, $e_i$ and $\ell_i$ the window bounds, and $\tau_i$ the service time, the recursion is

$$\begin{aligned} s_i &= \max(a_i,\, e_i), \\ a_{\text{next}} &= s_i + \tau_i + d(i,\text{next}), \end{aligned}$$

where:

• $s_i$: the service start time at node $i$, i.e. arrival held until the window opens
• $a_i$: the arrival time at node $i$ (the clock after traveling from the previous node)
• $e_i$: the opening of the time window at node $i$
• $\ell_i$: the closing of the time window at node $i$
• $\tau_i$: the service time at node $i$
• $d(i,\text{next})$: the Euclidean travel distance from node $i$ to the next node

The recursion is subject to $s_i \le \ell_i$ for every node including the return to the depot, and to $\sum_{i \in \text{route}} q_i \le Q$, where $q_i$ is the demand at node $i$ and $Q$ is the vehicle capacity. Here every customer demand is $q_i = 1$ and every vehicle capacity is $Q = 4$, and the total demand $\sum_{i \in \mathcal{C}} q_i = 8$ equals the total capacity $2Q = 8$, so each vehicle must carry exactly four customers: the decoder enforces that automatically. All windows are $[0, 80]$, and since every coordinate lies in $[0,8]\times[0,6]$ no arc exceeds $\sqrt{8^2+6^2}=10$. A route has five arcs and serves four customers, each with service time $\tau_i = 1$. Starting from the depot, the service start at the fourth customer is at most $4\cdot 10 + 3\cdot 1 = 43 < 80$, and the return to the depot takes one more arc of at most $10$ and one more service time of $1$, giving $4\cdot 10 + 4\cdot 1 + 10 = 54 < 80$. Every permutation is therefore feasible here. That is deliberate: the wide windows isolate search behaviour, and this instance does not test restrictive time-window handling.

Because we minimise, lower cost is better, and tournaments can compare costs without converting them into a separate fitness scale. For illustration, the positive transform $F(p)=1/(1+f(p))$ maps costs 38 and 40 to $1/39$ and $1/41$. The latter is $2/41\approx4.88$ percent smaller than the former. That transform compresses this particular cost difference; how concentrated proportional selection becomes depends on the full population. Our implementation instead selects the lowest raw cost in each sampled tournament.

On this symmetric-distance instance with deliberately wide windows, swapping the vehicles or reversing either tour preserves cost and feasibility. The decoded route sequences themselves change. We define a canonical signature $\sigma(p)$ by choosing the lexicographically smaller direction for each route and sorting the two resulting sequences. It identifies unordered pairs of undirected tours. Counting these signatures measures phenotype diversity; raw permutations and Hamming distance measure a different, genotype-level form of diversity that can also affect crossover.

Selection is the pressure that turns variation into progress. Tournament selection draws $k$ distinct individuals uniformly at random from the population and returns the one with the lowest cost. It is simple, it needs no fitness scaling, and its selection pressure has a clean closed form.

For this rank calculation, assume distinct costs, or a fixed total tie order applied consistently when selecting a winner. In a population of size $N$, rank $r=1$ is best and rank $r=N$ is worst. An individual of rank $r$ wins if it is drawn and no better individual (one of the $r-1$ individuals with smaller rank) is drawn with it. The number of $k$-subsets that contain it and otherwise contain only the $N-r$ worse individuals is $\binom{N-r}{k-1}$, out of $\binom{N}{k}$ equally likely subsets, so

$$P(\text{select individual of rank } r) \;=\; \frac{\binom{N-r}{\,k-1\,}}{\binom{N}{\,k\,}}.$$

where:

• $N$: the population size
• $k$: the tournament size (the number of individuals drawn without replacement)
• $r$: the rank of the individual, with $r=1$ the best and $r=N$ the worst
• $\binom{N-r}{k-1}$: the number of $k$-subsets containing the individual and only worse individuals
• $\binom{N}{k}$: the total number of equally likely $k$-subsets

Under that strict ranking, for $N=20$ and $k=3$ the unique best individual is selected with probability $\binom{19}{2}/\binom{20}{3} = 171/1140 = 0.15$, three times the uniform rate of $1/20 = 0.05$, while the worst individual with rank $r=20$, hence $N-r=0$, has probability $\binom{0}{2}/\binom{20}{3} = 0$. Raising $k$ sharpens the pressure; $k=2$ is mild and $k=N$ always picks the leader. Summing the expression over $r = 1,\dots,N$ returns $1$ by the hockey-stick identity, $\sum_{r=1}^{N}\binom{N-r}{k-1} = \sum_{m=0}^{N-1}\binom{m}{k-1} = \binom{N}{k}$, so it is a proper distribution. The formula describes selection under the stated ranking. Our code resolves a cost tie by the order in which contenders were sampled, so it does not assign a fixed strict rank to tied individuals. The rank formula alone does not predict a diversity-loss rate.

The selection pressure implied by this formula can be read directly. The following computation evaluates the rank probabilities for several tournament sizes.

Define the diversity of a generation as the number of distinct canonical signatures in the population, $D_t = |\{\sigma(p) : p \in P_t\}|$, with $D_t \le \mu$, where:

• $D_t$: the number of distinct canonical signatures in generation $t$
• $\sigma(p)$: the canonical signature of permutation $p$ (vehicle-symmetric, reversal-invariant)
• $P_t$: the population of parents at generation $t$
• $\mu$: the number of parents (population size)

For populations with $\mu>1$, genotype-level diversity can also be measured with the mean pairwise Hamming distance $\frac{1}{\mu(\mu-1)}\sum_{i \ne j} |\{t : p^{(i)}_t \ne p^{(j)}_t\}|$, where:

• $p^{(i)}$: the $i$-th individual permutation in the population
• $t$: a position index, $t = 1,\dots,n$
• $\mu$: the number of parents (population size)

The sum runs over ordered pairs $i \ne j$, so each unordered pair is counted twice, matching the $\mu(\mu-1)$ denominator. This measures genotype difference: swapping the two halves changes Hamming distance while preserving the unordered tour pair. The signature count instead measures distinct phenotypes under the stated symmetry; neither measure fully characterizes what crossover can produce.

Diversity is what makes crossover useful, and this can be shown rather than asserted. Order crossover applied to identical parents returns the parent: the block matches, and the filtered list from $q=p$ (the values of $p$ not copied into the block, in the cyclic order in which they appear in $p$) is placed into the empty positions in cyclic order; the two cyclic orderings agree, so each value is placed back where it started. So if the population collapses to copies of one permutation, $\text{OX}(p,p) = p$ for every selected pair, and the only source of novelty is mutation. A population in that state is a single point with random kicks, which is precisely the trajectory we were trying to escape.

This loss of useful variation is one form of premature convergence. Selection can remove variants; mutation proposes new variants but does not guarantee their survival. A low mutation rate may leave identical parents reproducing copies. A high rate may perturb useful structures. The appropriate balance depends on the encoding, objective, survivor rule, and evaluation budget.

The balance is problem specific, and with a budget of only $G = \lfloor (300-20)/20 \rfloor = 14$ generations there is little room to recover from a bad setting mid-run. We illustrate the trade-off with actual runs in the visualisation section rather than claiming a rule of thumb.

Repair is one alternative when feasibility is not enforced by construction. A repair operator $R$ maps an infeasible genotype back into the feasible set, and a penalty method folds violations into the objective:

$$f_{\text{pen}}(p) = f(p) + \lambda \cdot v(p)$$

where:

• $R$: the repair operator, which takes any genotype and returns a feasible one
• $f(p)$: the routing length of permutation $p$, as defined above
• $v(p)$: a nonnegative violation measure, larger when capacity or windows are exceeded
• $\lambda \ge 0$: the penalty weight that trades violation against routing length

The penalty objective compares violation and route cost on a chosen scale. A finite penalty need not make its minimizer feasible: a low route cost can outweigh the violation penalty. A validated repair may require computation or additional scoring, and many-to-one repair can reduce variation. Increasing $\lambda$ amplifies violation differences rather than generally flattening the objective. Our decoder needs no repair on this wide-window instance. With restrictive windows, feasibility would need a suitable decoder, feasible moves, rejection, repair, penalties with explicit validation, or another constraint-handling rule.

The formulas are only convincing if they reproduce on a single generation. We therefore work through one generation by hand on the shared instance, with a population of four so the arithmetic stays visible. The costs below are computed from the distance matrix; the implementation re-derives them from code, which lets us check that the hand calculation and the program agree.

Take the population

Distances and totals below are rounded independently from full-precision values, so summing the displayed arc lengths can differ in the final decimal place. The first individual is the nearest-neighbour construction, which is where every method in this chapter starts. Its cost is the sum of the arcs $d(0,1)=3.1623$, $d(1,7)=2.8284$, $d(7,8)=2.8284$, $d(8,3)=2.2361$, $d(3,0)=6.4031$ for the first vehicle, giving $17.4583$, and $d(0,6)=6.0828$, $d(6,5)=2.8284$, $d(5,4)=3.1623$, $d(4,2)=5.0000$, $d(2,0)=6.3246$ for the second, giving $23.3980$. In total $40.8563$. The other rows are decoded the same way: split the permutation after position four, close each half with the depot, and sum the five arcs in each route.

For this illustrative update, two size-$k=2$ tournaments select the intended parents. The first pits $P_2$ against $P_4$ and returns $P_2$, since $38.2665<60.0227$. The second pits $P_3$ against $P_1$ and returns $P_3$, since $39.1233<40.8563$. Thus $p=P_2=(1,2,3,8,6,5,4,7)$ and $q=P_3=(1,2,3,7,4,5,6,8)$.

Each tournament returns its cheaper contender. The two sampled pairs are supplied for the hand calculation, rather than a claim about which individuals a random run will select. The example uses four scored parents and one illustrated offspring before survival.

The block is copied first. Note that positions $4$, $5$, $6$ of $p$ hold the values $6, 5, 4$, so $U = \{4,5,6\}$.

Next, list $q$ cyclically starting at position $b+1 = 7$: the values are $q_7=8$, then $q_0=1$, $q_1=2$, $q_2=3$, $q_3=7$, and then $q_4=4$, $q_5=5$, $q_6=6$ which are all in $U$ and are skipped. The filtered list is therefore $8, 1, 2, 3, 7$. The empty positions in cyclic order from $7$ are $7, 0, 1, 2, 3$, so we assign

$$c_7 \leftarrow 8,\quad c_0 \leftarrow 1,\quad c_1 \leftarrow 2,\quad c_2 \leftarrow 3,\quad c_3 \leftarrow 7,$$

giving the child $c = (1,2,3,7,6,5,4,8)$.

The important point is that the child is a permutation without any repair. The copied block supplies $6,5,4$; the filtered list supplies the remaining values in the order $q$ had them, after removing the copied ones. Nothing is duplicated and nothing is lost.

The child decodes to the tours $0 \to 1 \to 2 \to 3 \to 7 \to 0$ and $0 \to 6 \to 5 \to 4 \to 8 \to 0$. Vehicle 1 costs $d(0,1) + d(1,2) + d(2,3) + d(3,7) + d(7,0) \approx 3.1623 + 3.1623 + 2.2361 + 4.1231 + 3.1623 \approx 15.8460$, and vehicle 2 costs $d(0,6) + d(6,5) + d(5,4) + d(4,8) + d(8,0) \approx 6.0828 + 2.8284 + 3.1623 + 3.6056 + 5.8310 \approx 21.5100$. The total is $15.8460 + 21.5100 = 37.3560$, which is shorter than either parent ($38.2665$ and $39.1233$).

That is recombination doing real work. The child keeps the left block $1,2,3$ in $q$'s order and appends the value $7$ that $q$ had right after it, and it keeps $p$'s descending block $6,5,4$ and closes it with $8$ from $q$. Neither parent contained both blocks in that arrangement. The example is small, but it shows the mechanism the population is supposed to exploit: crossover can assemble a combination that neither parent had.

The loop applies swap mutation to a child with probability $p_m$ (the per-child mutation rate, here 0.5) before scoring it, so only one of the two versions, the mutated one or the unmutated one, is charged to the budget. For illustration, swapping positions $5$ and $6$ of the child gives $(1,2,3,7,6,4,5,8)$ with cost $39.0210$, which is worse than the unmutated child; mutation is a perturbation, not an improvement operator. This one swap is worse; it does not establish how often all swaps lose.

Survivor selection is $(\mu+\lambda)$ with $\mu=4$. The pool is the four parents plus the child, and the four cheapest are kept: the child at $37.3560$, then $P_2$ at $38.2665$, $P_3$ at $39.1233$, and $P_1$ at $40.8563$. $P_4$ at $60.0227$ is discarded. The population mean falls from

$$\frac{40.8563+38.2665+39.1233+60.0227}{4} = 44.5672 \quad\text{to}\quad \frac{37.3560+38.2665+39.1233+40.8563}{4} = 38.9005 .$$

Whether this child is optimal is a question for enumeration, which we run in the implementation; on this instance enumeration confirms that the child is optimal, with minimum cost approximately $37.3560$ (rounded to four decimal places). The enumeration is an independent computation excluded from every search budget; the optimization figures and the summary table report that measured result. Scoring the four parents and both displayed child variants costs six illustrative evaluations, separate from every search budget. In the actual loop only the final, possibly mutated version of each child is scored. The hand example has shown the mechanics; the next section turns those mechanics into code and holds the result to the same budget as the other methods.

We use NumPy arrays to expose the population, variation, and selection operations directly. The implementation has four parts: the instance and its independent validator, the evaluation account, the operators, and the comparison harness that runs every method under the same 300-evaluation budget.

Coordinates, demands, capacities, windows, and service times are the shared instance from the preceding chapter. The distance matrix is the same matrix used for both the objective and the schedule, so there is no second notion of "cost". Keeping one matrix for both purposes is important: if the objective and the feasibility check used different distance conventions, a route could be scored with one length and validated with another.

The decoder is a slice; the objective is a simulation of two tours. The validator is deliberately written a second time from raw coordinates with np.hypot, so that a reported route is checked by code that does not share the objective's distance matrix. That redundancy is intentional: it catches mistakes in the objective rather than merely repeating them.

Every scoring call for a complete permutation passes through one counter. The counter also stores the running best, which is what lets us plot evaluation-indexed incumbent traces instead of wall-clock curves. There is no memoisation anywhere: if a child duplicates an existing individual it is scored again and charged again. This is the implementation of the budget identity from the formula section.

Nearest-neighbour construction scans 36 candidate arcs to build the permutation: it considers 8+7+6+5+4+3+2+1 remaining customers, resetting to the depot after the first four. These arc lookups are extra construction work, not complete-route evaluations. The diagnostic NN cost below is one separate score. Each search run scores the NN permutation again through its own counter as evaluation 1, then spends its remaining budget. No cached NN objective value is inserted into a run.

The three baselines follow the shared comparison contract. Each performs one actual nearest-neighbour scoring call per run and then spends the remaining 299 evaluations. The SA schedule is $T_m=2(0.01/2)^{m/299}$ before proposal $m$, for $m=1,\ldots,299$. It skips an acceptance draw for a strict improvement; ties consume a draw and are accepted. The objective also accumulates all ten arcs in the same sequential order as the preceding chapter. Even mathematically equivalent summation can change a floating-point tie and therefore the later random-call order; matching these details makes the baseline reproducible across the two chapters. The random baseline is explicitly NN-seeded random search, not 300 uniform draws.

Before scoring, the implementation rejects a represented t_end / t_start ratio below the smallest positive normal value of its floating-point dtype. This catches zero and subnormal quotients, which can erase or distort the cooling schedule. A constant positive subnormal temperature remains allowed because its ratio is one. The temperatures still approximate the geometric schedule in floating-point arithmetic; this guard does not guarantee exact endpoints or a bound on relative error.

The operators are short enough to read line by line. order_crossover implements the rule derived in the formula section, using cyclic position indices so that a block ending at the last position wraps around correctly. swap_mutation is the permutation-space mutation, and tournament and elitist_survivors implement the selection and survival rules.

The following settings define this comparison; their effects need to be measured under the chosen budget.

• pop_size ($\mu$, here 20): the number of retained candidates. Complete generations number $\lfloor(B-N)/N\rfloor$ after initialization. A larger population leaves no more complete generations at a fixed budget, and often fewer, but does not guarantee greater useful diversity.
• tournament_size ($k$, here 3): the tournament width. A unique best individual is sampled with probability $3/20=0.15$ under distinct costs, compared with $1/20$ for uniform parent choice. Ties and downstream diversity need separate interpretation.
• crossover_rate (here 0.9): the chance of applying OX to two selected parents rather than copying the first. The implementation draws $a$ uniformly from 0 through 6, then $b$ uniformly from $a+1$ through 7; these cut pairs are not uniformly distributed.
• mutation_rate (here 0.5): the probability that a child receives one swap. This is the only operator that can create novelty once the population copies itself.
• Budget handling: the NN permutation is scored once inside each run, then 19 random permutations complete the initial population. Every child is scored, including duplicates. A budget below the requested initial population is rejected before scoring.

The population budget and number of generations are coupled. Parent pressure and variation also interact through the candidates that survive. The explicit settings make those choices reproducible; they do not establish that more mutation, more population members, or larger tournaments improve performance.

The functions map onto the components of the algorithm. decode and schedule define the genotype-to-phenotype map and the feasibility check; objective is the complete-route cost that the counter charges for; validate_solution re-derives the same quantities independently from the raw coordinates and is used only on reported answers. On the search side, tournament implements selection, order_crossover and swap_mutation implement variation, elitist_survivors implements $(\mu+\lambda)$ survival with elitism, and population_stats records the diagnostics (number of distinct canonical solutions and mean pairwise Hamming distance), while canonical_signature computes the vehicle-symmetric tour signature used for those diagnostics, that we use to discuss diversity.