Genetic Algorithm — 0.001 Mutation Rate Cost 15% Route

Genetic algorithms (GA) are a class of evolutionary computation algorithms inspired by natural selection. They excel at combinatorial optimisation problems where exact methods are infeasible: travelling salesman, job shop scheduling, neural network architecture search, game-playing strategy design.

GAs do not guarantee finding the global optimum (they are metaheuristics), but they find good solutions to NP-hard problems where exact algorithms would take astronomical time. The travelling salesman problem with 100 cities has 100!/2 ≈ 10^157 possible routes — exhaustive search is impossible, but GAs routinely find solutions within 1-2% of optimal.

Why Genetic Algorithms Work Despite Randomness

A genetic algorithm (GA) is a search heuristic that mimics natural selection: a population of candidate solutions evolves over generations through selection, crossover, and mutation. The core mechanic is that fitter individuals have higher probability of reproducing, gradually improving the population's average fitness. Unlike gradient-based methods, GAs require no derivative information — they explore the solution space through stochastic variation and selection pressure.

In practice, a GA maintains a population of N individuals (typically 50–500), each encoded as a chromosome (e.g., a bit string or permutation). Selection picks parents proportional to fitness (roulette wheel or tournament). Crossover recombines two parents to produce offspring, and mutation randomly flips a small fraction of genes — typically 0.1%–1% per generation. The algorithm converges when the population's diversity collapses or a fitness plateau is reached. Key hyperparameters: population size, crossover rate (0.7–0.9), mutation rate (0.001–0.01), and selection pressure.

Use GAs when the search space is large, non-convex, or discrete — e.g., TSP, scheduling, hyperparameter tuning, or circuit design. They shine where gradient information is unavailable or expensive. The trade-off: GAs are sample-inefficient (require many fitness evaluations) and offer no optimality guarantees. In production, they are often hybridized with local search (memetic algorithms) to accelerate convergence.

Core Components

Every genetic algorithm has five components: representation (how solutions are encoded), fitness function (how good is each solution), selection (which solutions reproduce), crossover (how two parents combine), and mutation (random perturbation to maintain diversity).

Getting any one wrong can break the search. Representation is the most subtle — a poor encoding makes crossover produce invalid offspring, wasting generations.

import random

def genetic_algorithm(target: str, pop_size: int = 200,
                       mutation_rate: float = 0.01,
                       max_generations: int = 1000) -> str:
    """Classic: evolve a string to match the target."""
    chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz !'
    n = len(target)

    def fitness(s): return sum(a==b for a,b in zip(s, target))
    def random_individual(): return ''.join(random.choice(chars) for _ in range(n))
    def crossover(a, b):
        pt = random.randint(0, n)
        return a[:pt] + b[pt:]
    def mutate(s):
        return ''.join(c if random.random() > mutation_rate
                        else random.choice(chars) for c in s)

    population = [random_individual() for _ in range(pop_size)]
    for gen in range(max_generations):
        population.sort(key=fitness, reverse=True)
        if fitness(population[0]) == n:
            print(f'Solved in generation {gen}')
            return population[0]
        # Select top 50%, breed next generation
        survivors = population[:pop_size//2]
        children = [mutate(crossover(random.choice(survivors),
                                     random.choice(survivors)))
                    for _ in range(pop_size//2)]
        population = survivors + children
    return population[0]

result = genetic_algorithm('Hello World')
print(f'Result: {result}')

Selection Strategies

Tournament selection: Pick k random individuals, choose the best. Computationally efficient, tunable selection pressure via k.

Roulette wheel (fitness proportionate): Select with probability proportional to fitness. Works poorly if one individual has much higher fitness than others (it dominates).

Rank selection: Sort by fitness, assign probability by rank not absolute fitness. More robust to fitness scale differences.

Elitism: Always copy the best individual(s) to the next generation unchanged. Prevents losing the best solution found.

Selection pressure determines how quickly the population converges. Too much pressure → premature convergence. Too little → the GA wanders randomly.

Crossover and Mutation: The Diversity Trade-off

Crossover recombines genetic material from two parents. It exploits existing building blocks. Mutation introduces random changes to explore new areas. The balance between them is critical.

High crossover rate (0.8-0.9) means most offspring are created by recombination. High mutation rate (>0.1) turns the algorithm into random search. Low mutation rate (<0.001) leads to premature convergence.

For permutation problems (TSP), standard one-point crossover produces invalid tours (duplicate cities). Specialised operators like Order Crossover (OX) or Partially Mapped Crossover (PMX) preserve the permutation property.

Adaptive mutation: increase mutation rate when diversity drops, decrease it when diversity is high. Implementation: track the average hamming distance or fitness variance.

def adaptive_mutate(individual, base_rate, diversity, target_diversity=0.3):
    """Increase mutation when diversity is low."""
    rate = base_rate * (target_diversity / max(diversity, 0.01))
    rate = min(rate, 0.5)  # cap at 50%
    return mutate(individual, rate)

def population_diversity(population):
    """Mean pairwise Hamming distance / chromosome length."""
    n = len(population)
    if n < 2: return 0
    chrom_len = len(population[0])
    total = 0
    for i in range(n):
        for j in range(i+1, n):
            total += sum(a!=b for a,b in zip(population[i], population[j]))
    # Normalise
    return total / (n * (n-1) / 2) / chrom_len

Travelling Salesman Example

The TSP is the canonical GA benchmark. Chromosome = permutation of cities. Crossover must preserve the permutation property (no city visited twice). Fitness = total route distance.

Order Crossover (OX): pick a segment from parent 1, then fill remaining positions from parent 2 in order, skipping already-used cities. This preserves relative order and creates valid tours.

For real-world TSP instances with 1000+ cities, a GA with OX crossover, tournament selection, and adaptive mutation can find solutions within 2% of optimal in minutes.

import random, math

def tsp_fitness(route, cities):
    return 1 / sum(math.dist(cities[route[i]], cities[route[(i+1)%len(route)]])
                   for i in range(len(route)))

def order_crossover(p1, p2):
    """Order crossover (OX) — preserves relative order, no duplicates."""
    n = len(p1)
    a, b = sorted(random.sample(range(n), 2))
    child = [None] * n
    child[a:b] = p1[a:b]
    remaining = [x for x in p2 if x not in child]
    j = 0
    for i in range(n):
        if child[i] is None:
            child[i] = remaining[j]
            j += 1
    return child

def mutate_swap(route, rate=0.01):
    """Swap two cities with probability rate per position."""
    for i in range(len(route)):
        if random.random() < rate:
            j = random.randrange(len(route))
            route[i], route[j] = route[j], route[i]
    return route

# Demo with 10 cities
random.seed(42)
cities = {i: (random.uniform(0,100), random.uniform(0,100)) for i in range(10)}
pop_size = 100
# Initialise population with random routes
pop = [list(range(10)) for _ in range(pop_size)]
for p in pop:
    random.shuffle(p)

for gen in range(200):
    pop.sort(key=lambda r: 1/tsp_fitness(r, cities), reverse=False)
    best_dist = 1/tsp_fitness(pop[0], cities)
    # Elitism: keep top 2
    next_pop = pop[:2]
    while len(next_pop) < pop_size:
        p1 = random.choice(pop[:20])
        p2 = random.choice(pop[:20])
        child = order_crossover(p1, p2)
        child = mutate_swap(child, 0.02)
        next_pop.append(child)
    pop = next_pop
    if gen % 20 == 0:
        print(f'Gen {gen}: best distance = {best_dist:.2f}')
print(f'Final best distance = {1/tsp_fitness(pop[0], cities):.2f}')

Hyperparameter Tuning: What Actually Matters

GAs have 4-5 critical hyperparameters: population size, mutation rate, crossover rate, selection pressure (tournament size), and elitism count.

Population size: 50-500 is common. Too small = premature convergence, too large = slow generations. Rule: set to 10× chromosome length for binary, 5× for permutations.

Mutation rate: Start at 1/(chromosome length). For binary strings of length 100, 0.01 works. For permutations of 100 cities, 0.02 (swap mutation) is a good start.

Crossover rate: 0.7-0.9. Lower values reduce exploitation, higher values risk losing good building blocks.

Tournament size: k=3 is a safe default. k=5 increases selection pressure. k=2 is weak.

Elitism: Always keep at least the single best individual. Keeping 2-5% of the population unchanged is common.

Don't tune all parameters at once. Start with default values, then tune sensitivity: which parameter changes best fitness most? That's the one to optimise.

Performance Considerations and When to Avoid GAs

GAs are not the fastest optimisation method. Each generation evaluates pop_size individuals — that's pop_size × generations function evaluations. For problems where a single fitness evaluation takes seconds (e.g., training a neural network), GAs can be prohibitively slow.

When GAs work well: - Combinatorial problems with no gradient (TSP, scheduling, packing) - Multi-modal landscapes (many local optima) - Black-box objectives where you can't compute derivatives - Problems where you can parallelise fitness evaluations easily

When to avoid GAs: - Differentiable functions: use gradient descent - Small search space (< 10^6 possibilities): use exhaustive search or B&B - Need guaranteed optimality: use integer programming - Function evaluation is expensive (> 1 second): use Bayesian optimisation or random search instead

Parallelisation: Fitness evaluation is embarrassingly parallel. In production, evaluate all individuals in parallel using multiprocessing or a distributed executor (e.g., Dask, Spark). The rest of the GA (selection, crossover) is sequential but fast.

from multiprocessing import Pool

def evaluate_population_parallel(population, fitness_func, workers=4):
    with Pool(workers) as pool:
        return pool.map(fitness_func, population)

# Usage in GA loop:
# fitnesses = evaluate_population_parallel(population, fitness_func, workers=8)

Fitness Functions: The Objective That Makes or Breaks Your GA

The fitness function is the oracle your GA worships. It's the single function that scores every chromosome — and if it's wrong, your entire evolution optimises for garbage. Real-world GAs don't fail because crossover is buggy. They fail because the fitness function rewards the wrong thing.

You're not maximising fitness. You're minimising the gap between your function and reality. Every selection, crossover, and mutation step is just a search guided by this function. If your fitness landscape has plateaus — regions where every candidate scores identically — selection becomes random walks. If it has sharp spikes, you converge on local optima and never escape.

Practical rule: your fitness function should be differentiable in spirit if not in code. Small changes in gene values should produce small, meaningful changes in fitness. Flat regions kill gradients. Steep cliffs blind the search. Design your scoring to reward partial progress, not just perfection.

For combinatorial problems like TSP, that means penalising constraint violations with a severity that scales — not a binary dead-or-alive flag. For continuous optimisation, normalise gene contributions so no single variable dominates the score.

// io.thecodeforge — dsa tutorial

public class FitnessEvaluator {
    // Traveling Salesman: minimize total distance
    // Penalize missing cities, reward short paths
    public static double evaluate(int[] route, double[][] distanceMatrix, int cityCount) {
        Set<Integer> visited = new HashSet<>();
        double totalDistance = 0.0;
        
        for (int i = 0; i < route.length - 1; i++) {
            int from = route[i];
            int to = route[i + 1];
            if (from < 0 || from >= cityCount || to < 0 || to >= cityCount) {
                return Double.MAX_VALUE; // invalid gene = death
            }
            visited.add(from);
            totalDistance += distanceMatrix[from][to];
        }
        visited.add(route[route.length - 1]);
        
        // Penalize missing cities: 10x average edge cost per missing city
        double avgEdge = totalDistance / (route.length - 1);
        int missing = cityCount - visited.size();
        return totalDistance + missing * avgEdge * 10.0;
    }
}

Termination Criteria: How to Stop Before You Burn CPU Cycles on Nothing

A GA that runs forever isn't an algorithm — it's an infinite loop with delusions of progress. You need hard stop conditions that balance solution quality against compute budget. The three real-world triggers: stagnation threshold, budget exhaustion, and early exit on good enough.

Stagnation matters most. Track the best fitness over the last N generations. If it doesn't improve by at least epsilon (say 0.1%) for 50 generations, the population has converged. More mutation won't save it — the search space is explored. Kill it gracefully.

Budget exhaustion is your safety net. Set a hard cap on generations or wall-clock time. In production, I've seen teams let GAs run for 12 hours chasing a 0.01% gain. Stop at generation 5000 or 10 minutes, whichever hits first. Log the convergence curve so you can tune next time.

Good enough: if your fitness hits a threshold that solves the business problem — like delivery routes under a cost target — stop immediately. Don't optimise for perfection when 95% solves the Monday morning logistics nightmare.

Combine all three: stop on stagnation OR max generations OR target fitness reached. And always serialise the best solution before terminating.

// io.thecodeforge — dsa tutorial

public class TerminationController {
    private double bestFitness = Double.MAX_VALUE;
    private int generationsSinceImprovement = 0;
    private final int stagnationLimit = 50;
    private final int maxGenerations = 5000;
    private final double targetFitness = 250.0; // business requirement

    public boolean shouldStop(int currentGeneration, double currentBestFitness) {
        if (currentGeneration >= maxGenerations) {
            System.out.println("Stopping: max generations reached");
            return true;
        }
        if (currentBestFitness <= targetFitness) {
            System.out.println("Stopping: target fitness achieved");
            return true;
        }
        double improvement = (bestFitness - currentBestFitness) / bestFitness;
        if (improvement > 0.001) {
            bestFitness = currentBestFitness;
            generationsSinceImprovement = 0;
        } else {
            generationsSinceImprovement++;
        }
        if (generationsSinceImprovement >= stagnationLimit) {
            System.out.println("Stopping: stagnation detected");
            return true;
        }
        return false;
    }
}

Encoding Methods: How You Squeeze Your Problem Into Chromosomes

Encoding is the translation layer between your problem domain and the GA's chromosome string. Pick wrong, and your crossover operator will spawn dead babies — invalid solutions that fail before selection gets a chance. Three patterns dominate production code: binary, permutation, and real-valued.

Binary encoding is the classic — each gene is a bit. Works for feature selection (gene i = include feature i?), combinatorial knapsack, or any yes/no decision. Crossover is trivial: cut and swap bit strings. Mutation flips bits. But for continuous problems, binary encoding wastes precision — you need many bits per variable, and Hamming distance doesn't map cleanly to solution distance.

Permutation encoding is your go-to for ordering problems like TSP, scheduling, or routing. Each chromosome is a permutation of city or job indices. Standard crossover will break the permutation constraint (duplicates, missing elements). Use PMX (Partially Mapped Crossover) or ordered crossover. Mutation swaps two positions, never flips bits.

Real-valued encoding is for continuous optimisation — tune 20 parameters of a PID controller? Each gene is a double. Crossover does arithmetic blending (BLX-alpha), not cut-and-swap. Mutation adds Gaussian noise. No invalid solutions possible, but you lose the crispness of binary search. Always clamp genes to domain bounds after mutation.

Never default to binary "because it's simple." The encoding determines what "close to optimal" looks like in genospace. Align it with your problem's natural structure.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class EncodingExamples {
    // Binary encoding: feature selection (8 features)
    static class BinaryChromosome {
        boolean[] features = new boolean[8]; // true = include feature
        void mutate(int geneIndex) { features[geneIndex] = !features[geneIndex]; }
    }
    
    // Permutation encoding: TSP route
    static class PermutationChromosome {
        int[] route; // e.g., [1, 3, 0, 2] means visit city1, city3, city0, city2
        PermutationChromosome(int cityCount) {
            route = new int[cityCount];
            for (int i = 0; i < cityCount; i++) route[i] = i;
            Collections.shuffle(Arrays.asList(route));
        }
        void swapMutate(int i, int j) { int tmp = route[i]; route[i] = route[j]; route[j] = tmp; }
    }
    
    // Real-valued encoding: continuous parameters
    static class RealChromosome {
        double[] params; // each in [0.0, 1.0]
        void clamp() { for (int i = 0; i < params.length; i++) {
            if (params[i] < 0.0) params[i] = 0.0;
            if (params[i] > 1.0) params[i] = 1.0;
        }}
    }
}

Evaluating the Results: Metrics That Separate Real Progress From Noise

Most GA tutorials stop at showing you the best fitness value. In production, that tells you almost nothing. The question isn't "did the fitness go up" but "did the population actually converge on a valid solution or just memorize a local optimum?". You need three metrics: average population fitness (tells you if the whole gene pool is improving), diversity index (proportion of unique chromosomes), and stagnation count (generations since best fitness changed). Track these per generation. A rising average with dropping diversity means premature convergence — your crossover is too aggressive. A flat average with high diversity means mutation is drowning out selection. Plot all three. If best fitness plateaus while average keeps climbing, your selection pressure is too weak. If both plateau but diversity is still high, your encoding can't represent the true optimum — that's a fatal encoding problem, not a tuning issue.

// io.thecodeforge — dsa tutorial

public class GAMetrics {
    public static void evaluate(Population pop, int gen) {
        double sum = 0, best = 0;
        int uniqueChromosomes = 0;
        Set<String> seen = new HashSet<>();
        for (Individual ind : pop.individuals) {
            sum += ind.fitness;
            best = Math.max(best, ind.fitness);
            seen.add(ind.encode());
        }
        double avg = sum / pop.size();
        double diversity = (double) seen.size() / pop.size();
        System.out.printf("Gen %d | avg=%.2f best=%.2f div=%.2f\n",
            gen, avg, best, diversity);
        if (diversity < 0.1) System.err.println("WARNING: premature convergence");
    }
}

Making It All Run: Async Evaluation and Distributed Workers

GAs are embarrassingly parallel: each fitness evaluation is independent. But most tutorials show synchronous loops that evaluate one chromosome at a time. That wastes GPU clusters and multicore machines. The fix: pool your workers (threads or remote servers) and batch-send chromosomes as soon as they're generated. Use a completion callback per chromosome, not a global barrier. Your main loop should do three things: spawn evaluation tasks, collect results, and generate next population — all overlapping. In Java, use a ForkJoinPool with RecursiveAction per evaluation. Set pool size to number of cores minus one. For distributed workers, use a message queue (RabbitMQ, Redis) with backpressure: if queue size exceeds 10x population size, pause generation. Never block the main thread waiting for all evaluations — that sequentializes your GA. The generation clock starts when the last slow worker finishes; optimize your slowest chromosome, not the average.

// io.thecodeforge — dsa tutorial

import java.util.concurrent.*;

public class AsyncGA {
    private final ForkJoinPool pool = new ForkJoinPool(
        Runtime.getRuntime().availableProcessors() - 1);

    public void run(Population pop) {
        CompletableFuture<?>[] futures = pop.individuals.stream()
            .map(ind -> CompletableFuture.runAsync(
                () -> ind.fitness = evalFitness(ind), pool))
            .toArray(CompletableFuture[]::new);
        CompletableFuture.allOf(futures).join();
        evolve(pop);
    }

    private double evalFitness(Individual i) { /* your domain logic */ return 0.0; }
}