Genetic Algorithms › Formula

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.