Genetic Algorithms › Example

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.