Earl's Genetics

By Richard Faint · 25 July 2026 · 12 min read

TL;DR:

Genetic algorithms improve routes by maintaining a population of candidate solutions rather than repeatedly refining one plan. Selection, crossover and mutation combine useful route structures while preserving enough variation to explore alternatives.

Earl Discovers That Two Good Ideas Can Have Children

The title is a pun about breeding. The subject is genetic algorithms, which evolve a whole population of candidate routes rather than improving a single one.

As part of my MSc dissertation, I built a genetic algorithm in Java to solve the Travelling Salesman Problem. I used Design of Experiments to examine how factors such as population size, crossover rate and mutation rate affected the quality of the routes it produced. At the time, I explained the algorithm through chromosomes, fitness functions and permutation operators, which was technically correct but perhaps not the easiest way to make the underlying logic intuitive.

Years later, it occurs to me that I could have explained most of it using My Name Is Earl, that certainly would have made it far more interesting!

Earl begins the series with a list of everything he has done wrong and a belief that repairing those mistakes will improve his karma. The list gives him an objective, but it does not tell him which item to tackle first, which sequence will create the best outcome, or whether solving one problem will make another one worse. Earl therefore spends each episode testing a possible route through a complicated social system, usually discovering that the most obvious approach is not necessarily the best one.

That makes Earl a surprisingly good model for optimisation. It also makes genetic algorithms particularly appropriate, because a genetic algorithm does not ask one version of Earl to keep improving the same plan. It imagines a whole population of possible Earls, each working through the same list in a different order, and allows the more successful plans to influence what happens next.

The Shift from One Earl to Many

Most of the optimisation methods covered earlier in this series begin with one current solution.

• Two-Opt takes one route and improves it by reversing intermediate sections. In Earl’s world, this would mean keeping the same list but changing the order in which two groups of items are completed.

• Simulated Annealing follows one route but occasionally accepts a worse move, allowing Earl to make a decision that appears unhelpful in the short term because it may create a better opportunity later.

• Tabu Search also works with one current route, but maintains a memory of recent moves. Earl remembers that he has already tried a particular approach and prevents himself from immediately repeating the same mistake.

Although these techniques explore the search space differently, they all follow one version of events. There is one Earl, one list and one current plan.

A genetic algorithm changes the unit of search. Instead of following one Earl through a single chain of decisions, it creates a population of Earls, each carrying a differently ordered version of the same list. The important difference is not simply that several plans are being tested at once. Each plan may contain a useful fragment that does not appear in the best overall solution. One Earl may deal with Joy particularly effectively but make a mess of everything involving Kenny. Another may handle Kenny and Randy well but create an unnecessary argument with Joy. A genetic algorithm attempts to preserve those useful fragments and combine them into something stronger.

Encoding Earl’s List

Imagine that Earl has temporarily exchanged Camden County for a delivery depot in Leeds. His task is to visit Bradford, Halifax, Huddersfield, Wakefield, York and Harrogate before returning to the depot.

One version of the list might be:

Leeds Depot → Bradford → Halifax → Huddersfield → Wakefield → York → Harrogate → Leeds Depot

Another Earl might attempt:

Leeds Depot → York → Harrogate → Bradford → Halifax → Wakefield → Huddersfield → Leeds Depot

Both Earls visit the same locations, but they take very different routes through the system.

In genetic algorithm terminology, each individual location is a gene. Halifax is a gene, York is a gene and Wakefield is a gene.

The complete ordered list of locations is a chromosome. It represents one possible solution to the routing problem.

The collection of all the different Earls and their lists is the population.

The score used to judge how well each Earl performed is the fitness function.

For a simple Travelling Salesman Problem, the fitness function may be based entirely on distance, with shorter routes receiving higher scores. In a real transport operation, Earl’s karma score might also consider travel time, fuel cost, driver hours, lateness, vehicle utilisation and whether every customer has actually been served.

This is where the analogy becomes more important than it first appears. Earl often assumes that crossing an item off the list is the same as repairing the damage he caused, but the programme repeatedly shows that these are not necessarily the same thing. He can complete the apparent task while upsetting Joy, misleading Randy or creating an entirely new problem for someone else.

An optimiser can make exactly the same mistake.

If the fitness function rewards only reduced mileage, the genetic algorithm will evolve routes that reduce mileage. It does not automatically understand that a driver needs a break, that a customer has a delivery window or that a warehouse cannot load six vehicles at the same time. Those concerns must appear either as constraints or as part of the fitness calculation. The population evolves towards whatever definition of success it has been given. If Earl defines karma badly, he becomes very efficient at doing the wrong thing.

Selection: Which Earl Gets Another Episode?

Once every route has been evaluated, the genetic algorithm decides which Earls should become parents. The strongest candidates are normally given a greater probability of being selected, but weaker candidates are not always eliminated completely. This matters because a poor overall route may still contain one excellent section.

Suppose Earl A produces the shortest route in the current population. Earl B performs badly overall but discovers a particularly efficient sequence through:

Bradford → Halifax → Huddersfield

Earl C finds a useful connection between:

York → Harrogate → Wakefield

If the algorithm simply copied Earl A and discarded everyone else, those useful local structures might disappear. Selection therefore favours stronger solutions without making the process completely deterministic.

One common approach is tournament selection. A small group of Earls is chosen at random and the best performer within that group becomes a parent. Repeating the process creates pressure towards better routes while still allowing different parts of the population to compete.

Another method is roulette-wheel selection, where each Earl’s chance of becoming a parent is proportional to fitness. Better routes receive more opportunities to reproduce, but weaker routes retain a small chance of contributing something useful.

The balance matters. If selection pressure is too weak, Earl keeps giving unsuccessful plans another chance and improvement becomes slow. If it is too strong, the population quickly fills with near-identical copies of one successful Earl. Diversity disappears, and the search can become trapped around a solution that is good but not exceptional.

The algorithm must reward success without allowing one successful version of Earl to take over the entire programme.

Crossover: Two Good Lists Have Children

Crossover is the defining feature of a genetic algorithm. Two parent routes are selected and combined to produce a child route. The intention is that the child will inherit useful structures from both.

Suppose one Earl has discovered that the West Yorkshire section works particularly well in this order:

Bradford → Halifax → Huddersfield

Another Earl has discovered a good sequence involving:

York → Harrogate → Wakefield

Crossover attempts to create a new Earl whose list preserves both insights. In principle, this sounds simple. Earl takes the best section from one list, the best section from another and joins them together. Unfortunately, routing problems make this more difficult than it appears.

Imagine these two valid parent routes:

Parent Earl 1

Bradford → Halifax → Huddersfield | Wakefield → York → Harrogate

Parent Earl 2

Huddersfield → Harrogate → York | Bradford → Wakefield → Halifax

A naive crossover might take the first half of Parent 1 and attach the second half of Parent 2:

Bradford → Halifax → Huddersfield → Bradford → Wakefield → Halifax

The child has inherited plenty from both parents, but it is not a valid route. Bradford and Halifax appear twice, while York and Harrogate have disappeared. This would be rather like Earl combining two versions of his list and somehow ending up apologising to Kenny twice while forgetting that Joy exists. The list may have six entries, but it no longer represents the original problem.

With binary chromosomes, crossover is relatively straightforward because each position can independently contain a zero or a one. A route is different. Each delivery location normally needs to appear exactly once, which means the chromosome is an ordered permutation rather than an arbitrary sequence. This was one of the central lessons from my MSc work. A genetic algorithm is not a universal mechanism that can be dropped onto any problem unchanged. The chromosome representation and the genetic operators must reflect the structure of the domain.

Earl cannot simply tear two lists in half and staple them together.

Routing genetic algorithms therefore use specialised crossover techniques. One of the most common is Order Crossover, usually called OX1. It preserves a contiguous section from one parent and fills the remaining positions using the relative order of unused locations from the second parent.

Suppose the child inherits this section from Parent Earl 1:

Bradford → Halifax → Huddersfield

The algorithm then looks at Parent Earl 2 and adds locations that have not already appeared, preserving their relative order. One possible child might become:

Bradford → Halifax → Huddersfield → Harrogate → York → Wakefield

Every location appears once, and the child inherits information from both parents.

Another method is Partially-Mapped Crossover, or PMX. This creates mappings between the locations found inside two crossover sections and uses those mappings to resolve duplicates.

A third method is Edge Recombination Crossover, which focuses on preserving connections rather than positions. Instead of asking whether Halifax was third or fourth on Earl’s list, it asks which locations Halifax was next to.

This is especially relevant in routing. The fact that Halifax appears in position three is rarely valuable by itself. The useful information may be that Halifax sits between Bradford and Huddersfield in several good routes.

The genetic material is therefore not necessarily the town itself or its numerical position. It may be the relationship:

Bradford → Halifax

or:

Halifax → Huddersfield

A good crossover operator preserves the structures that matter operationally rather than merely rearranging names.

Mutation: Randy Changes the List

Crossover can only recombine information already present in the population. Mutation introduces something new.

In My Name Is Earl, Randy is mutation.

Earl may have constructed a careful plan, only for Randy to misunderstand an instruction, move something to the wrong place or involve someone who was never supposed to be involved. Most of these interventions make the situation worse. Occasionally, however, Randy’s mistake reveals an option Earl would never have considered deliberately.

A routing mutation might swap Bradford and Wakefield, move York to a different position or reverse the section between Halifax and Harrogate.

For example:

Before mutation

Bradford → Halifax → Huddersfield → Wakefield → York → Harrogate

After Randy interferes

Bradford → Halifax → York → Wakefield → Huddersfield → Harrogate

The new route may be worse, but it introduces a structure that was not previously available through crossover.

Mutation is essential because a population can gradually become too similar. Once all the Earls carry nearly identical lists, combining them produces little that is genuinely new. The search becomes predictable and may settle prematurely around a mediocre solution. Too little mutation means Randy never interferes, the population loses diversity and Earl becomes trapped in familiar patterns. Too much mutation means Randy rewrites the entire list every few minutes, destroying useful structures before the algorithm has time to exploit them.

The objective is controlled disruption. Randy must create enough uncertainty to keep the search alive, but not so much that every generation forgets what the previous one learned.

Darnell Preserves the Best Route

Genetic algorithms often use a mechanism called elitism, where one or more of the best solutions are copied directly into the next generation. In Earl’s world, Darnell keeps a clean copy of the best list somewhere safe before Earl and Randy begin experimenting again.

Without elitism, an excellent route could disappear because of an unlucky crossover or mutation. The population might discover a highly efficient route in one generation and then lose it entirely in the next. Elitism prevents that regression. The strongest Earl survives unchanged while the rest of the population continues experimenting.

However, elitism also needs limits. If too many elite routes are preserved, the population becomes dominated by the existing winners and diversity falls. Once again, the algorithm must balance exploitation of what already works with exploration of what might work better.

Why My Dissertation Focused on the Settings

When I built my genetic algorithm, the code for selection, crossover and mutation was only part of the problem. The behaviour of the algorithm also depended heavily on its settings.

• The population size determined how many different Earls were exploring the problem at once. A larger population provided more diversity but required more routes to be evaluated in every generation.

• The crossover rate controlled how frequently two parent lists were combined. Too little crossover limited the algorithm’s ability to combine useful structures. Too much could repeatedly break apart strong routes before they had time to spread through the population.

• The mutation rate controlled how often Randy became involved. Too little mutation encouraged premature convergence. Too much reduced the process to random disruption.

• The number of elite solutions, selection method and stopping criteria also affected performance.

These variables do not operate independently. A mutation rate that works well with a population of twenty routes may behave differently with a population of two hundred. Strong selection pressure may require more mutation to preserve diversity. A particular crossover operator may work well for one problem size but poorly for another.

That was why I used Design of Experiments rather than changing one variable at a time. The objective was not simply to discover one combination of settings that happened to perform well. It was to understand which factors mattered, how they interacted and whether the results were robust.

The Evolutionary Loop

The complete process repeats across generations over time, efficient route sections become more common. Weak structures gradually disappear. Useful connections through Bradford, Halifax and Huddersfield spread through the population, while poor sequences are less likely to survive.

There is no guarantee that the final route is the global optimum. A genetic algorithm is a metaheuristic, and its result can vary between runs. Its value lies in its ability to explore a very large and complicated search space without requiring every possible route to be tested. For an operational optimiser, this is often enough. The organisation may not need mathematical proof that no better route exists. It needs a strong, feasible plan before the vehicles are due to leave.

Earl’s Population of Possible Lives

The original idea behind My Name Is Earl is that Earl has one list but many possible ways of working through it. Every choice affects what becomes possible next, and an apparently sensible action can create consequences that were not visible when the decision was made.

A genetic algorithm makes that idea explicit. It creates multiple versions of the list, allows them to compete, combines the most useful sections and occasionally permits Randy to interfere.

Its power does not come from any single candidate route. It comes from the population’s ability to preserve and exchange partial knowledge.

Try it interactively. Open the genetic algorithm simulator on its own page → — full-width, with a walkthrough of what each control does.

Back to Articles