Day 343: Genetic Algorithms - Evolution in Silico

The core idea: a genetic algorithm searches by evolving a population of candidate solutions, keeping the ones that score well, recombining their useful parts, and mutating them so the search does not freeze around the first decent answer.

Today's "Aha!" Moment

In the previous lesson, cooperation evolved because successful strategies spread through Harbor City's cleanup fleet. A genetic algorithm uses the same evolutionary logic, but the thing evolving is not a skipper's behavior in the harbor. It is a proposed solution to an engineering problem. Harbor City now has a different challenge: every night it must decide where to place absorbent boom, which skiffs cover which sectors, and what route each skiff should follow before the morning tide pushes diesel residue into protected marsh channels.

That planning problem is awkward for classical optimization. Part of it is combinatorial because routes are ordered lists. Part of it is discrete because each skiff must be assigned to exactly one launch marina. Part of it is continuous because boom lengths and launch times can vary. Worst of all, the city scores a plan by running a spill-response simulator that mixes weather forecasts, tide models, radio delays, and shoreline sensitivity rules. There is no neat derivative to follow and no tiny checklist of cases to enumerate exhaustively.

The useful shift is this: a genetic algorithm does not need the search space to be smooth or elegant. It only needs a way to represent a candidate plan and a way to score it. Once those exist, the algorithm can keep a population of plans, favor the better ones, and generate new plans by mixing good fragments from different parents. The population acts like memory. Mutation acts like controlled surprise. The result is not magic evolution; it is a structured search procedure for messy objective functions.

Why This Matters

Production teams run into this shape of problem constantly. Delivery schedules, warehouse slotting, network layout, hyperparameter tuning, pricing bundles, game AI parameters, and robot motion plans often combine hard constraints with objectives that are evaluated by simulation or by a slow black-box system. In those cases, "just use gradient descent" is not helpful because the model is not differentiable, and "just solve it exactly" may be impossible because the search space explodes too quickly.

For Harbor City, a weak nightly plan has direct operational cost. Skiffs overlap the same shoreline, booms arrive after the tide turn, and marsh entrances stay exposed even though the fleet worked hard. A planner can improve the situation manually for small incidents, but once the harbor response must balance fuel, travel time, containment rate, crew limits, and environmental penalties across dozens of interacting decisions, intuition stops being reliable.

Genetic algorithms matter because they offer a practical middle ground. They are not guaranteed to find the global optimum, but they can discover strong solutions in large irregular spaces where brute force is infeasible and gradients are unavailable. That makes them valuable in real systems, provided you understand their mechanism and their limits. A bad encoding, a noisy fitness signal, or overly aggressive selection can make them converge confidently on mediocrity.

Learning Objectives

By the end of this session, you will be able to:

1. Explain when a genetic algorithm is an appropriate search tool - Identify problems that are simulator-scored, mixed-type, or too irregular for exact or gradient-based optimization.
2. Describe the genetic algorithm loop precisely - Trace how representation, fitness evaluation, selection, crossover, mutation, and elitism interact.
3. Evaluate the main engineering trade-offs - Judge solution quality, compute cost, diversity loss, and constraint handling in a production optimization workflow.

Core Concepts Explained

Concept 1: A genetic algorithm starts by turning the real problem into a genome

Harbor City's nightly plan has to answer three coupled questions: where should containment boom be anchored, which skiff should cover each harbor sector, and in what order should each skiff visit its assigned waypoints? A genetic algorithm cannot operate on those decisions until they are encoded into a candidate solution, usually called a genome or chromosome.

One workable encoding is to store the plan in blocks:

[boom anchors] [boom lengths] [sector assignments] [route order per skiff]

For example, the first block may be a bit string that says which candidate anchor points are active. The second block may contain normalized boom lengths. The third may assign each skiff to a launch marina or response sector. The route block may be a permutation so each skiff visits waypoints without duplication. That encoded object is the genotype. When the simulator turns it into actual boom placement and route instructions, you get the phenotype: the plan that would be executed on the water.

This translation step is the first make-or-break design decision. If the genome ignores an operational constraint, crossover and mutation will generate large numbers of impossible children. If the genome is too rigid, the search cannot express useful alternatives. Harbor City might decide that every child plan must be repairable into a legal schedule: duplicate waypoints are removed, missing sectors are reassigned, and boom lengths are clipped to available inventory. That repair step is not a hack around the algorithm. It is part of the algorithm, because it defines what kinds of candidate solutions can survive.

The fitness function then turns the simulated plan into a scalar score. A simple version might be:

fitness(plan) =
    0.55 * contained_oil
  - 0.20 * fuel_cost
  - 0.15 * late_sector_penalty
  - 0.10 * marsh_exposure_penalty

The exact numbers are policy choices. They encode Harbor City's priorities. If marsh protection matters more than fuel burn, the weights must say so. This is why genetic algorithms are never "just an optimizer." They force the team to make the objective explicit, which often reveals disagreements that were hidden in casual planning conversations.

The trade-off is straightforward. Rich encodings and realistic fitness functions make the search more relevant, but they also make each evaluation slower and each bug more expensive. If the representation is sloppy, the algorithm spends generations evolving artifacts of the encoding instead of better response plans.

Concept 2: Selection, crossover, and mutation create biased search rather than blind randomness

Once Harbor City can score one plan, it can score many. A genetic algorithm begins with a population of candidate plans, often seeded partly at random and partly with heuristic baselines from experienced dispatchers. Each generation follows the same cycle: evaluate every candidate, keep some pressure toward the better ones, and create a new population from the survivors.

The core loop looks like this:

population = initialize_population()

for generation in range(max_generations):
    scores = [simulate_and_score(plan) for plan in population]
    elites = keep_best(population, scores, count=4)
    parents = tournament_select(population, scores)
    children = []

    while len(children) < len(population) - len(elites):
        parent_a, parent_b = sample_pair(parents)
        child_a, child_b = crossover(parent_a, parent_b)
        child_a = mutate(child_a, rate=0.03)
        child_b = mutate(child_b, rate=0.03)
        children.extend([repair(child_a), repair(child_b)])

    population = elites + children[: len(population) - len(elites)]

Selection is the biasing mechanism. Tournament selection, rank selection, or roulette-wheel selection all try to answer the same question: which plans deserve more descendants? Elitism preserves a few high-quality plans unchanged so the search does not forget its best discoveries. Crossover mixes fragments from two parents. In Harbor City, one parent may contribute a strong marsh-protection boom layout while another contributes an efficient route order for the western basin. Mutation then perturbs the child by flipping an anchor bit, swapping two route stops, or nudging a launch time.

In practice, those operators usually need to respect the structure of each genome block rather than treating the whole chromosome as a flat string. A one-point crossover might work for the anchor bit field, but route permutations often need an order-preserving operator so a child does not visit waypoint 17 twice and skip waypoint 23 entirely. Continuous parameters such as launch offsets or boom lengths may use arithmetic blending or bounded perturbations instead of bit flips. This is one reason production GA code tends to look more domain-specific than textbook diagrams suggest: the search operators are part of the model, not interchangeable decorations.

This is why the method is more disciplined than "try random plans until one works." A pure random search has no memory. A genetic algorithm retains and recombines useful partial structures, sometimes called building blocks. If a certain boom arrangement consistently protects the estuary mouth, that pattern can propagate across the population even while other parts of the plan continue changing.

The failure mode is premature convergence. If selection pressure is too strong, the population collapses around one early winner and stops exploring. If mutation is too weak, the search cannot escape that basin. If mutation is too strong, the algorithm destroys the very structures crossover was supposed to preserve. Tuning the operator mix is therefore not cosmetics. It changes whether the search behaves like careful adaptation or noisy thrashing.

Concept 3: The hard part in production is not running the loop but trusting what it optimizes

Suppose Harbor City runs the algorithm overnight and gets a plan with a score far better than the human baseline. The obvious temptation is to promote it directly into the morning dispatch sheet. That can be dangerous, because a genetic algorithm is only as trustworthy as the fitness landscape it sees.

If the simulator uses a single tide forecast, the algorithm may overfit that forecast and exploit quirks that will vanish under real wind shifts. If radio latency is modeled as fixed but the harbor network degrades under rain, routes that looked tightly coordinated in simulation may unravel in practice. If the scoring function penalizes fuel lightly, the optimizer may discover plans that achieve excellent containment numbers by exhausting crews and burning through reserve capacity. The algorithm did not make a mistake in those cases. It solved the problem it was given.

Production use therefore requires a validation layer around the optimizer. Harbor City might score each top candidate across multiple weather scenarios, reserve a fraction of the fleet for contingency response, and compare evolved plans against a rule-based fallback. If simulator randomness is substantial, the city may need repeated evaluations per candidate or common-random-number testing so one lucky weather draw does not crown a brittle plan as the winner. It may also promote the algorithm from advisory mode to partial automation only after several spill drills show that the candidate plans remain strong under perturbed assumptions.

This is also where the trade-off against other optimization methods becomes concrete. If the problem is small and highly structured, a mixed-integer solver may produce better guarantees. If the objective is differentiable, gradient-based methods are usually more sample-efficient. Genetic algorithms earn their keep when representation is awkward, the objective is black-box or discontinuous, and good enough solutions found quickly are more valuable than exact proofs of optimality.

That handoff matters for the next lesson. A genetic algorithm can evolve route policies, role allocations, or controller parameters offline. Multi-agent coordination is the runtime question that follows: once many agents execute those policies together, what organization emerges, and what new coupling effects appear?

Troubleshooting

Issue: The population converges in a few generations, but the best plan is only slightly better than the initial heuristic.

Why it happens / is confusing: Selection pressure is likely too strong or the population lacks diversity, so early winners dominate before the search explores alternative structures.

Clarification / Fix: Increase population diversity, reduce elitism, or raise mutation selectively on the stagnant genome blocks. In Harbor City terms, that may mean forcing more variation in route permutations even when boom layouts have already stabilized.

Issue: Many offspring are invalid schedules with duplicate waypoints or impossible boom allocations.

Why it happens / is confusing: The encoding and crossover operators are not aligned with the constraint structure of the problem.

Clarification / Fix: Use representation-aware operators such as permutation-preserving crossover for routes, or add a repair stage that restores feasibility before scoring. If invalid children dominate, the algorithm is spending most of its compute budget generating garbage.

Issue: The "best" plan changes wildly from run to run even when the setup looks identical.

Why it happens / is confusing: The fitness function is noisy because the simulator includes randomness from tide timing, weather shifts, or communication delays, so a single evaluation does not give a stable ranking.

Clarification / Fix: Re-score strong candidates multiple times, average or risk-adjust the result, and compare finalists under matched random seeds when you want a fair A/B test. Otherwise, the algorithm may be selecting for lucky draws rather than genuinely robust plans.

Issue: The algorithm finds plans that look excellent in simulation and disappoint in field drills.

Why it happens / is confusing: The fitness function or simulator omitted an operational variable, so the search learned to exploit a model gap rather than to improve the real system.

Clarification / Fix: Re-evaluate top candidates under multiple scenarios, add penalties for fragile plans, and keep a human-readable audit of which terms drove the final score. The goal is not only to evolve a strong plan, but to understand what kind of plan the objective is rewarding.

Advanced Connections

Connection 1: Genetic algorithms <-> evolutionary dynamics in multi-agent systems

The previous lesson treated evolution as a population-level update rule over strategies: cooperative behaviors spread when their payoffs held up under repeated interaction. Genetic algorithms use the same selection logic deliberately. The difference is that the population now consists of candidate solutions to an optimization problem rather than agents competing directly in the harbor. That shared structure is why ideas such as fitness, mutation, diversity, and selection pressure transfer naturally between evolutionary game theory and evolutionary optimization.

Connection 2: Genetic algorithms <-> multi-agent coordination

A genetic algorithm often optimizes the policy space before deployment, but coordination problems do not disappear after optimization. Harbor City may evolve patrol routes that look individually efficient and still discover congestion when many skiffs try to pass the same channel marker at once. The next lesson picks up there: how local agent interactions produce organized or disorganized collective behavior at runtime, even when the initial policies were optimized offline.

Resources

Optional Deepening Resources

• [BOOK] Adaptation in Natural and Artificial Systems - John H. Holland
  • Link: https://press.umich.edu/Books/A/Adaptation-in-Natural-and-Artificial-Systems2
  • Focus: The original framing of selection, recombination, and adaptation that shaped later genetic algorithm work.
• [BOOK] Genetic Algorithms in Search, Optimization, and Machine Learning - David E. Goldberg
  • Link: https://www.oreilly.com/library/view/genetic-algorithms-in/0201157675/
  • Focus: Representation choices, building blocks, and practical operator design for real optimization problems.
• [DOC] DEAP Documentation
  • Link: https://deap.readthedocs.io/en/master/
  • Focus: Concrete implementations of selection, crossover, mutation, and constraint-handling patterns in Python.
• [DOC] pymoo: Genetic Algorithm
  • Link: https://pymoo.org/algorithms/soo/ga.html
  • Focus: Modern single-objective GA configuration, especially population management and mixed-variable optimization.

Key Insights

1. A genetic algorithm is only as good as its representation - If the genome and repair logic do not reflect the real constraint structure, the search wastes effort on invalid or misleading candidates.
2. The search works because it is biased, not because it is random - Selection preserves useful partial solutions, crossover recombines them, and mutation prevents the population from freezing too early.
3. Fitness design is a production decision - The algorithm will optimize whatever the score rewards, including simulator loopholes and omitted costs if you leave them in the objective.