Genetic Algorithms › Practical Implications

A genetic algorithm is a candidate when an encoding and objective are available and the budget can support a population. Independent offspring can be evaluated concurrently, and recombination may combine useful structures. Those mechanisms do not establish superiority for routing, scheduling, feature selection, or another application. On this eight-customer instance, enumeration is computationally feasible; the 300-evaluation comparison serves to inspect the heuristics under a deliberately limited budget.

If evaluations are expensive and serial, initialization can consume a substantial part of the budget. Our population of 20 leaves 14 full generations after initialization at budget 300. A single-current-state method allocates its budget differently. Select a baseline and compare under the application's constraints rather than inferring a preferred optimizer from that accounting alone.

A practical decision should also account for constraint structure. If a decoder can map every genotype to a feasible solution, as the two-tour split does here, the search never wastes evaluations on infeasible candidates. If feasibility is difficult to encode, a constraint-handling rule is needed; feasible moves, rejection, repair and penalties have different costs and guarantees. Any scoring or tuning they perform must be disclosed. That choice affects validity and the work available for exploring new candidates.

Comparing heuristics requires a common budget and an explicit accounting convention. Here the unit is one complete-route objective evaluation: both tours are decoded and scored. Initialisation, duplicate children, rejected proposals, restart candidates, and any complete scoring calls performed during repair are charged; memoisation is disabled so that repeated candidates cost full price. Nearest-neighbour construction also scans arcs that are not complete-route evaluations, and those scans are disclosed separately rather than folded into the count. Equal evaluation counts therefore do not imply equal runtime, and the median_seconds column should be read as machine-dependent.

Repeated seeds expose run-to-run variation on this fixed instance. The same seed integer initializes a separate default_rng for each method, but the algorithms consume random numbers differently and use them for different operations. Matching seed labels does not remove random advantage or automatically reduce comparison variance. We report the 20 observed outcomes, reference hits within the stated numerical tolerance, and gaps; uncertainty about other seeds or other instances remains.

The reference must be independent of the search. Calling the best observed heuristic value "the optimum" does not establish a lower bound; gaps to that value can understate the unknown gap to the true minimum. Here all 40320 permutations are scored by the stated objective, and a separate coordinate-based reproduction checks the reference and decoder, so each heuristic result becomes a measured gap. When full enumeration becomes impractical, a result needs another independent optimality certificate to be called optimal. Without one, report "best found under budget".

A genetic algorithm does not require a training set or labels; it needs a candidate representation and a comparable objective or comparison rule, with decoding and constraint handling chosen for the problem. For this chapter the genotype is a permutation of eight customers, the decoder splits it into two four-customer depot tours, and the objective sums Euclidean arc lengths. The distance matrix used by the objective should be the same matrix used by the feasibility check; if two distance conventions are mixed, a route can be scored with one length and validated with another.

With noisy evaluations, a low observed cost can be lucky. Elitist survival then compares stored observations rather than expected costs. Re-evaluation and additional simulation replicates need a stated budget and comparison rule; increasing population size alone does not validate the incumbent. Record both candidate-evaluation effort and runtime when either matters to the application.

Preprocessing is mostly about encoding and feasibility rather than scaling. Features must be mapped into a representation that variation operators can preserve: permutations for ordering problems, binary vectors for subsets, integer or real vectors for mixed parameters. With restrictive constraints, validate the decoder and choose an explicit constraint-handling rule. Count any objective evaluations performed during repair, rejection or comparison. In this instance every customer has demand 1, each vehicle has capacity 4, and all windows are $[0,80]$, so every permutation is feasible; the wide windows isolate search behaviour and do not test restrictive window handling.

At budget 300, populations 10,20 and 50 permit 29,14 and 5 complete generations after initialization, respectively. These are budget calculations, not recommendations for every combinatorial problem. Tournament width likewise defines a selection rule: with distinct costs, $k=3$ samples a unique best member with probability 0.15 in a population of 20. Choose a small, explicitly budgeted setting comparison if the application needs tuning, and monitor both cost and diversity.

This comparison uses crossover probability 0.9 and per-child swap probability 0.5; the diagnostic also tries 0.1. These choices illustrate the operators and are not validated defaults. Elitist survival preserves the best retained deterministic cost, while an explicit archive could preserve a best observation under another survival rule. Count duplicate children and inspect genotype and phenotype diversity alongside cost.

Use explicit seed indices, report the outcome distribution over a stated number of runs, and independently validate reported routes. The 20 seeds here are a disclosed experimental choice, not a universal minimum. Parallel evaluations can change runtime without changing the candidate count. Population size, variation and selection settings still require assessment on the actual encoding and objective.

The characteristic failure is premature convergence. Selection favours the current leaders, so the population can become a set of near-copies; once two parents are identical, order crossover returns the same permutation, and only mutation creates novelty. If the whole population collapses to copies of one permutation, crossover adds no variation; mutation supplies the random kicks. Monitoring the number of distinct canonical signatures and the mean pairwise Hamming distance can reveal the collapse early. Increasing mutation, reducing tournament size, or injecting immigrants are standard responses, but each consumes budget or perturbs good structure.

A second pitfall is misusing a generic crossover. Permutation search needs variation that preserves validity or an explicit correction rule. OX is one validity-preserving crossover; swapping values position by position or using one-point crossover on a permutation can create duplicates and omissions, which then require repair. Repair is not free, and a repair operator that maps many children to the same feasible point can bias the search. A validated feasibility-preserving encoding can avoid repair work when its construction cost and restrictions on the search are acceptable. Penalty methods have another failure mode: a finite weight may still prefer an infeasible point, and a large weight can make violation differences dominate route-length differences. Validate feasibility rather than inferring it from a penalized score.

A third pitfall is treating the genotype as the solution. A permutation is not a pair of routes until it is decoded, checked against capacity and time windows, and scored by the same objective used in the search. Reporting a permutation without that validation can hide infeasible offspring, a mismatched decoder, or a distance convention that differs from the one used for scoring. The final answer should be the validated phenotype and its objective, not the raw genotype alone.

Each complete generation scores $N$ children in addition to initialization. For expensive objectives, scoring may dominate and independent evaluations may be parallelized. For the cheap objective here, operator and diagnostic overhead can matter. OX uses lists and membership checks; survivor sorting processes up to $2N$ individuals, and pairwise Hamming diagnostics form an $N\times N\times n$ comparison. Equal candidate counts do not make these costs equal across methods.

The population stores $N$ permutations of length $n$ plus costs. The current Hamming diagnostic also creates an $N\times N\times n$ boolean array, and retained traces/history consume additional memory. Exact enumeration stores $n!$ permutations and their costs, feasible at $n=8$ but growing factorially. For larger instances, distinguish a lower bound, a relaxation, or a best-known feasible reference from a proven minimum.

In deployment, the genetic algorithm is naturally an anytime method: for this deterministic objective, elitism preserves the best retained cost. After valid initialization, the function can spend a partial final generation and return its incumbent at the stated budget. Monitor the best cost, the population diversity, and the evaluation count; if diversity falls or the incumbent stalls, investigate with a separately budgeted experiment rather than treating either diagnostic as a convergence certificate. Revalidate the decoded routes before use, version the objective, decoder and search implementation together. Record the instance, runtime, operator settings and initial seed to reproduce a run; store the final candidate and its validation report to check the reported result. On small instances where a local search is cheaper and more reliable, the genetic algorithm should be treated as one option among several rather than the default.