Genetic Algorithms

Why Genetic Algorithms Matters

Suppose a candidate solution is a six-bit configuration. The left three bits and right three bits control two interacting groups of settings. One candidate gets the left group right, another gets the right group right, and changing only one bit may make either candidate worse. A search that maintains several candidates can recombine useful parts, then use occasional mutations to explore configurations that the current population does not contain.

A genetic algorithm, or GA, is a family of population-based optimization heuristics. It repeatedly evaluates candidates, favors fitter candidates as parents, combines their representations, introduces variation, and forms a new population. Here higher fitness is better. The result is the best evaluated candidate, together with a reproducible record of the search.

The lesson builds a specific binary, generational GA with two-way tournament selection, one-point crossover, bit mutation, one copied elite, and an independent best-ever archive. You will trace every child and run matching Python, C++, and Java programs. A finite run can find a good solution without establishing that no better solution exists; iteration limits and apparent convergence are stopping rules, not optimality proofs.

Core Concepts and Terminology

A genotype is the stored encoding; a phenotype is the solution it represents. In this lesson they coincide: an unsigned $L$-bit string denotes an integer $x$ with $0\le x\lt2^L$. A deterministic table supplies its fitness $f(x)$. A population $P_g$ is an ordered list of $N$ genomes at generation $g$; duplicates are allowed and occupy separate slots.

We maximize fitness, so parent selection compares values directly. Negative scores are valid: $-1$ is fitter than $-3$. Tournament selection needs no division by fitness, no positivity assumption, and no normalization. For a minimization objective $E$, one option is $f=-E$ when its numeric range remains valid.

The worked objective is deliberately deceptive. For a three-bit block containing $u$ ones, define

$$t(u)=\begin{cases}3,&u=3,\\2-u,&0\le u\lt3.\end{cases}$$

For six bits, sum the two block scores:

$$f(x)=t(u_{\mathrm{left}})+t(u_{\mathrm{right}}).$$

For example, 000000 scores $2+2=4$, 111000 scores $3+2=5$, and 111111 scores $3+3=6$. A single-bit change from 000000 reduces the score to $3$, so it is a strict local maximum for single-bit hill climbing. The unique global optimum is 111111: each block contributes at most $3$, with equality only at 111.

The landscape diagram groups each block by its number of ones; its horizontal distance is not the integer distance between whole genomes. GA moves have no fixed step size: crossover can change several loci, mutation can change zero through $L$ bits, and each generation contains several trajectories. An unchanged best score can indicate a plateau or a stalled search without certifying local or global optimality.

How Genetic Algorithms Works, Step by Step

The inputs specify the bit length, deterministic fitness table, initial ordered population, seed, generation limit $G$, mutation threshold $m$, and evaluation budget $B$. Initialization is supplied explicitly so that comparisons do not hide the cost or randomness of creating the initial population.

1. Validate, then initialize. Copy the inputs. If fewer than $N$ evaluations remain, return EVAL_LIMIT with no evaluated solution and no random draws. Otherwise evaluate all initial slots, including duplicates. Select the earliest maximum as the initial archive, and record generation $0$.
2. Check stopping rules. The generation limit is checked first. If it has been met, return GEN_LIMIT. Otherwise require room for all $N-1$ new evaluations. If that room is absent, return EVAL_LIMIT before drawing randomness or creating a partial generation.
3. Copy one elite. Find the earliest maximum in the current population and put a value copy into next slot $0$, retaining its cached fitness. The objective is deterministic, so this unchanged elite needs no new evaluation.
4. Select two parents for each remaining slot. Draw four old-population indices, with replacement. The first pair forms tournament A and the second pair tournament B. Higher fitness wins; a tie keeps the first sampled index, not the smaller index. Parents may be identical. All tournaments read the frozen old population, including when earlier children are already available.
5. Crossover once. For $L\gt1$, choose a cut $c$ uniformly from $1,\ldots,L-1$ in the ideal random model. Keep the first $c$ displayed bits of parent A and the final $L-c$ bits of parent B. Produce one child per slot. For $L=1$, use $c=0$ without drawing a cut, so the unmutated child is parent B.
6. Mutate each locus. Visit bits from left to right. Draw one integer $v$ from $0,\ldots,999$ for every bit, including at rates $0$ and $1000$. Flip that bit precisely when $v\lt m$. With independent uniform draws this is independent bit mutation with probability $p=m/1000$ per locus.
7. Evaluate and archive. Evaluate the mutated child once, append its genome and score, and update the archive only for a strictly larger fitness. Log the tournaments, cut, pre-mutation child, mutation draws, mask, final child, score, and generator state.
8. Commit the next population. After all child slots are filled, replace the old population and its scores together, increment the generation, record a snapshot, and repeat.

For integer bit operations, a suffix mask $s=2^{L-c}-1$ selects the low bits. With the full mask $M=2^L-1$, crossover is

$$x_{\mathrm{cross}}=(a\mathbin{\&}(M\mathbin{\oplus}s))\mathbin{\vert}(b\mathbin{\&}s).$$

Mutation constructs a flip mask $h$ and computes $x_{\mathrm{child}}=x_{\mathrm{cross}}\mathbin{\oplus}h$. Here $\&$, $\vert$, and $\oplus$ mean bitwise AND, OR, and XOR. A bit may flip even when it was inherited correctly; the archive and elite protect discoveries from those later changes.

flowchart TD
    A["Validate and copy inputs"] --> B{"Budget covers initialization?"}
    B -->|No| Z["Return no evaluated solution"]
    B -->|Yes| C["Evaluate initial population and archive best"]
    C --> D{"Generation limit reached?"}
    D -->|Yes| Y["Return archive and completed population"]
    D -->|No| E{"Budget covers a full generation?"}
    E -->|No| Y
    E -->|Yes| F["Copy one elite into next population"]
    F --> H["Select two parents from frozen population"]
    H --> I["Crossover then mutate every bit"]
    I --> J["Evaluate child and update archive"]
    J --> K{"More child slots?"}
    K -->|Yes| H
    K -->|No| M["Commit next population and record generation"]
    M --> D

Worked Example with a Full Trace

Use $L=6$, $N=4$, seed $113$, $G=3$, $m=100$, and $B=100$. The initial population is [000000,000111,111000,010101], with scores $[4,5,5,1]$. Its total fitness is $15$ and its mean is $15/4=3.75$. The first tied maximum is 000111, so that genome enters the archive.

Randomness comes from the integer recurrence

$$z_{k+1}=48271z_k\bmod2147483647,\qquad z_0=113.$$

Each raw draw is a state $z$ from $1,\ldots,2147483646$. To obtain an integer below a positive bound $b$, let $R=2147483646$, set $v=z-1$, and accept it only if

$$v\lt R-(R\bmod b).$$

Return $v\bmod b$ after acceptance; otherwise draw again. This rejection mapping gives equal-sized residue classes under a uniform raw-input model, unlike unrestricted modulo mapping when $b$ does not divide $R$. The generator itself is a deterministic teaching generator; its outputs are correlated and are not independent mathematical randomness.

For every child, the order of mapped draws is four tournament indices, one cut draw if $L\gt1$, then $L$ mutation draws. The stored cut adds $1$ to its mapped value. No rejection occurs in this sample, so each child consumes $4+1+6=11$ raw draws and each full generation consumes $33$. For example, the first raw state is $5454623$, giving first tournament index $(5454623-1)\bmod4=2$.

The following table records all nine children. Indices refer to the preceding generation, and A/B lists the tournament winners. The six mutation draws are in displayed left-to-right bit order. A 1 in the mask marks a flipped bit.

The child in generation $2$, slot $2$, combines 111000 and 000111 at cut $3$, obtaining 111111 without mutation. The next child in that same generation still selects from generation $1$; it cannot select this newly produced optimum. In generation $3$, slot $1$, draws $98$ and $30$ flip two bits of 100111, creating the poor genome 101011 with score $0$.

These are the completed populations and cumulative counters:

The final status is GEN_LIMIT, with archive 111111:6, $13$ evaluations, $9$ children, $3$ flipped bits, $99$ raw draws, no rejection retries, and final random state $501268393$. The mean drops from $4.5$ to $4$ in the final generation while best fitness remains $6$.

For complete generator accounting, the child-end states and cumulative draw counts are:

The run has found the global optimum because the independent block bound proves $f(x)\le6$ and its archive reaches $6$. GEN_LIMIT itself carries no such guarantee. The implementation deliberately keeps running after finding this value because it accepts arbitrary tables and has no built-in optimum target.

Implementation in Python, C++, and Java

Each panel is a complete program with the same supplied population and integer random source. Run Python $3.10+$, compile C++ as C++17, or save the Java panel as Main.java and use Java $11+$.

genetic_algorithm accepts $1\le L\le12$, a table of exactly $2^L$ integer scores in $[-10^9,10^9]$, and $2\le N\le32$ valid genome integers. The seed must be in $1,\ldots,2147483646$; the requested generations are $0$ through $500$; the mutation threshold is $0$ through $1000$; and the evaluation budget is $0$ through $10^6$. Python also rejects booleans and non-integer numeric parameters or elements. The inputs must be ordinary finite sequences; Java arrays must be non-null.

The result holds status, has_value, archive, final population and matching scores, completed generations, evaluation/child/bit-flip counts, generator state/draw/rejection counts, generation snapshots, and child events. If initialization cannot fit, has_value is false, the final population and histories are empty, best index is $-1$, and the zero fitness field is a dummy value. Invalid inputs raise an exception before searching.

An evaluation means one lookup in this teaching table. Duplicate genomes are evaluated again in child slots; only the unchanged elite's score is reused. A budget of $6$ initializes four members but leaves room for only two of the three required children, so the program stops at generation $0$ without drawing randomness. A zero-generation request still evaluates the initial population if its budget permits; after initialization, GEN_LIMIT takes precedence when both limits would stop the run.

All state arithmetic uses integers. C++ and Java use signed 64-bit values for the generator product, score values, and population totals, which can reach magnitude $32\times10^9$. Genomes and shifts remain safely bounded by the validated length. Crossover and mutation produce new scalar genomes, and population snapshots are copied so later generations cannot alter earlier history.

The sample includes the full trap run, an insufficient-generation budget, a zero budget, and a one-bit population with negative scores and mutation rate $1$. The last case shows that the elite remains unchanged even when every bit of every newly generated child flips.

Teaching adapter versus a real objective: this program receives the complete fitness table. If that table is already known, a linear scan over its $2^L$ entries finds the exact optimum directly, and there is no reason to use a GA to solve that small problem. The table makes objective behavior transparent and independently checkable. A practical GA normally calls an expensive evaluator without precomputing the search space; account for those actual evaluations and initialization costs when adapting it.

from dataclasses import dataclass, field


MOD = 2147483647
RANGE = MOD - 1


class RandomSource:
    def __init__(self, seed):
        self.state = seed
        self.draws = 0
        self.rejections = 0

    def below(self, bound):
        limit = RANGE - RANGE % bound
        while True:
            self.state = (48271 * self.state) % MOD
            self.draws += 1
            value = self.state - 1
            if value < limit:
                return value % bound
            self.rejections += 1


@dataclass
class Event:
    generation: int
    slot: int
    picks: list
    parents: list
    cut: int
    before: int
    mutation_draws: list
    flip_mask: int
    child: int
    fitness: int
    rng_state: int
    rng_draws: int


@dataclass
class Snapshot:
    generation: int
    population: list
    fitness: list
    best: int
    best_fitness: int
    total: int
    evaluations: int
    rng_draws: int


@dataclass
class Result:
    status: str
    has_value: bool = False
    best: int = -1
    best_fitness: int = 0
    population: list = field(default_factory=list)
    fitness: list = field(default_factory=list)
    generations: int = 0
    evaluations: int = 0
    children: int = 0
    bit_flips: int = 0
    rng_state: int = 0
    rng_draws: int = 0
    rng_rejections: int = 0
    history: list = field(default_factory=list)
    events: list = field(default_factory=list)


def genetic_algorithm(length, scores, initial, seed, generations,
                      mutation_per_mille, evaluation_budget):
    scalars = [length, seed, generations, mutation_per_mille,
               evaluation_budget]
    if any(type(x) is not int for x in scalars):
        raise ValueError("integer parameters required")
    if not (1 <= length <= 12 and 1 <= seed < MOD and
            0 <= generations <= 500 and 0 <= mutation_per_mille <= 1000 and
            0 <= evaluation_budget <= 1000000):
        raise ValueError("parameter out of range")
    if len(scores) != 1 << length or not 2 <= len(initial) <= 32:
        raise ValueError("invalid table or population size")
    if any(type(x) is not int or not -1000000000 <= x <= 1000000000
           for x in scores):
        raise ValueError("invalid fitness")
    if any(type(x) is not int or not 0 <= x < 1 << length for x in initial):
        raise ValueError("invalid genome")
    table, population = list(scores), list(initial)
    rng = RandomSource(seed)
    result = Result("EVAL_LIMIT", rng_state=seed)
    size = len(population)
    if evaluation_budget < size:
        return result
    fitness = [table[x] for x in population]
    result.has_value = True
    result.evaluations = size
    elite = max(range(size), key=lambda i: fitness[i])
    result.best, result.best_fitness = population[elite], fitness[elite]

    def record():
        result.history.append(Snapshot(
            result.generations, list(population), list(fitness), result.best,
            result.best_fitness, sum(fitness), result.evaluations, rng.draws))

    record()
    while True:
        if result.generations == generations:
            result.status = "GEN_LIMIT"
            break
        if evaluation_budget - result.evaluations < size - 1:
            result.status = "EVAL_LIMIT"
            break
        elite = max(range(size), key=lambda i: fitness[i])
        next_population = [population[elite]]
        next_fitness = [fitness[elite]]
        for slot in range(1, size):
            picks = [rng.below(size) for _ in range(4)]
            a = picks[0] if fitness[picks[0]] >= fitness[picks[1]] else picks[1]
            b = picks[2] if fitness[picks[2]] >= fitness[picks[3]] else picks[3]
            cut = 1 + rng.below(length - 1) if length > 1 else 0
            suffix = (1 << (length - cut)) - 1
            before = (population[a] & (((1 << length) - 1) ^ suffix)) | (
                population[b] & suffix)
            mutation_draws = [rng.below(1000) for _ in range(length)]
            flip_mask = 0
            for j, draw in enumerate(mutation_draws):
                if draw < mutation_per_mille:
                    flip_mask |= 1 << (length - 1 - j)
                    result.bit_flips += 1
            child = before ^ flip_mask
            value = table[child]
            result.evaluations += 1
            result.children += 1
            if value > result.best_fitness:
                result.best, result.best_fitness = child, value
            next_population.append(child)
            next_fitness.append(value)
            result.events.append(Event(
                result.generations + 1, slot, picks, [a, b], cut, before,
                mutation_draws, flip_mask, child, value, rng.state, rng.draws))
        population, fitness = next_population, next_fitness
        result.generations += 1
        record()
    result.population, result.fitness = list(population), list(fitness)
    result.rng_state, result.rng_draws = rng.state, rng.draws
    result.rng_rejections = rng.rejections
    return result


def trap_table():
    scores = []
    for genome in range(64):
        value = 0
        for shift in (0, 3):
            ones = sum((genome >> (shift + j)) & 1 for j in range(3))
            value += 3 if ones == 3 else 2 - ones
        scores.append(value)
    return scores


def show(label, result, length):
    print(label)
    for row in result.history:
        members = ",".join(format(x, f"0{length}b") for x in row.population)
        values = ",".join(map(str, row.fitness))
        print(f"g={row.generation} pop={members} fitness={values} "
              f"best={row.best:0{length}b}:{row.best_fitness} "
              f"sum={row.total} eval={row.evaluations} draws={row.rng_draws}")
    best = f"{result.best:0{length}b}:{result.best_fitness}" if result.has_value else "NONE"
    print(f"status={result.status} best={best} generations={result.generations} "
          f"eval={result.evaluations} children={result.children} "
          f"flips={result.bit_flips} draws={result.rng_draws} "
          f"rejections={result.rng_rejections} rng={result.rng_state}")


def main():
    table, initial = trap_table(), [0, 7, 56, 21]
    show("trap", genetic_algorithm(6, table, initial, 113, 3, 100, 100), 6)
    show("budget", genetic_algorithm(6, table, initial, 113, 3, 100, 6), 6)
    show("zero-budget", genetic_algorithm(6, table, initial, 113, 3, 100, 0), 6)
    show("one-bit", genetic_algorithm(1, [-3, -1], [0, 0], 7, 2, 1000, 10), 1)


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include <utility>
using namespace std;

using I64 = int64_t;
constexpr I64 MOD = 2147483647, RANGE = MOD - 1;

struct RandomSource {
    I64 state;
    int draws = 0, rejections = 0;
    explicit RandomSource(I64 seed) : state(seed) {}
    int below(int bound) {
        I64 limit = RANGE - RANGE % bound;
        while (true) {
            state = (48271 * state) % MOD;
            ++draws;
            I64 value = state - 1;
            if (value < limit) return int(value % bound);
            ++rejections;
        }
    }
};
struct Event {
    int generation, slot;
    vector<int> picks, parents;
    int cut, before;
    vector<int> mutation_draws;
    int flip_mask, child;
    I64 fitness, rng_state;
    int rng_draws;
};
struct Snapshot {
    int generation;
    vector<int> population;
    vector<I64> fitness;
    int best;
    I64 best_fitness, total;
    int evaluations, rng_draws;
};
struct Result {
    string status = "EVAL_LIMIT";
    bool has_value = false;
    int best = -1;
    I64 best_fitness = 0;
    vector<int> population;
    vector<I64> fitness;
    int generations = 0, evaluations = 0, children = 0, bit_flips = 0;
    I64 rng_state = 0;
    int rng_draws = 0, rng_rejections = 0;
    vector<Snapshot> history;
    vector<Event> events;
};

Result genetic_algorithm(int length, const vector<I64>& scores,
                         const vector<int>& initial, I64 seed, int generations,
                         int mutation_per_mille, int evaluation_budget) {
    if (length < 1 || length > 12 || seed < 1 || seed >= MOD ||
        generations < 0 || generations > 500 || mutation_per_mille < 0 ||
        mutation_per_mille > 1000 || evaluation_budget < 0 ||
        evaluation_budget > 1000000)
        throw invalid_argument("parameter out of range");
    if (scores.size() != size_t(1 << length) || initial.size() < 2 || initial.size() > 32)
        throw invalid_argument("invalid table or population size");
    for (I64 x : scores)
        if (x < -1000000000 || x > 1000000000) throw invalid_argument("invalid fitness");
    for (int x : initial)
        if (x < 0 || x >= (1 << length)) throw invalid_argument("invalid genome");
    vector<I64> table = scores;
    vector<int> population = initial;
    RandomSource rng(seed);
    Result result;
    result.rng_state = seed;
    int size = int(population.size());
    if (evaluation_budget < size) return result;
    vector<I64> fitness;
    for (int x : population) fitness.push_back(table[x]);
    result.has_value = true;
    result.evaluations = size;
    auto elite_index = [&]() {
        int best = 0;
        for (int i = 1; i < size; ++i) if (fitness[i] > fitness[best]) best = i;
        return best;
    };
    int elite = elite_index();
    result.best = population[elite]; result.best_fitness = fitness[elite];
    auto record = [&]() {
        I64 total = 0;
        for (I64 value : fitness) total += value;
        result.history.push_back(Snapshot{result.generations, population, fitness,
            result.best, result.best_fitness, total, result.evaluations, rng.draws});
    };
    record();
    while (true) {
        if (result.generations == generations) {
            result.status = "GEN_LIMIT"; break;
        }
        if (evaluation_budget - result.evaluations < size - 1) {
            result.status = "EVAL_LIMIT"; break;
        }
        elite = elite_index();
        vector<int> next_population{population[elite]};
        vector<I64> next_fitness{fitness[elite]};
        for (int slot = 1; slot < size; ++slot) {
            vector<int> picks;
            for (int j = 0; j < 4; ++j) picks.push_back(rng.below(size));
            int a = fitness[picks[0]] >= fitness[picks[1]] ? picks[0] : picks[1];
            int b = fitness[picks[2]] >= fitness[picks[3]] ? picks[2] : picks[3];
            int cut = length > 1 ? 1 + rng.below(length - 1) : 0;
            int suffix = (1 << (length - cut)) - 1;
            int before = (population[a] & (((1 << length) - 1) ^ suffix)) |
                         (population[b] & suffix);
            vector<int> mutation_draws;
            int flip_mask = 0;
            for (int j = 0; j < length; ++j) {
                int draw = rng.below(1000); mutation_draws.push_back(draw);
                if (draw < mutation_per_mille) {
                    flip_mask |= 1 << (length - 1 - j); ++result.bit_flips;
                }
            }
            int child = before ^ flip_mask;
            I64 value = table[child];
            ++result.evaluations; ++result.children;
            if (value > result.best_fitness) {
                result.best = child; result.best_fitness = value;
            }
            next_population.push_back(child); next_fitness.push_back(value);
            result.events.push_back(Event{result.generations + 1, slot, picks,
                vector<int>{a, b}, cut, before, mutation_draws, flip_mask,
                child, value, rng.state, rng.draws});
        }
        population = move(next_population); fitness = move(next_fitness);
        ++result.generations; record();
    }
    result.population = population; result.fitness = fitness;
    result.rng_state = rng.state; result.rng_draws = rng.draws;
    result.rng_rejections = rng.rejections;
    return result;
}

vector<I64> trap_table() {
    vector<I64> scores;
    for (int genome = 0; genome < 64; ++genome) {
        I64 value = 0;
        for (int shift : vector<int>{0, 3}) {
            int ones = 0;
            for (int j = 0; j < 3; ++j) ones += (genome >> (shift + j)) & 1;
            value += ones == 3 ? 3 : 2 - ones;
        }
        scores.push_back(value);
    }
    return scores;
}
string bits(int x, int length) {
    string out;
    for (int j = length - 1; j >= 0; --j) out += char('0' + ((x >> j) & 1));
    return out;
}
void show(const string& label, const Result& result, int length) {
    cout << label << '\n';
    for (const auto& row : result.history) {
        cout << "g=" << row.generation << " pop=";
        for (size_t i = 0; i < row.population.size(); ++i) {
            if (i) cout << ',';
            cout << bits(row.population[i], length);
        }
        cout << " fitness=";
        for (size_t i = 0; i < row.fitness.size(); ++i) {
            if (i) cout << ',';
            cout << row.fitness[i];
        }
        cout << " best=" << bits(row.best, length) << ':' << row.best_fitness
             << " sum=" << row.total << " eval=" << row.evaluations
             << " draws=" << row.rng_draws << '\n';
    }
    cout << "status=" << result.status << " best=";
    if (result.has_value) cout << bits(result.best, length) << ':' << result.best_fitness;
    else cout << "NONE";
    cout << " generations=" << result.generations << " eval=" << result.evaluations
         << " children=" << result.children << " flips=" << result.bit_flips
         << " draws=" << result.rng_draws << " rejections=" << result.rng_rejections
         << " rng=" << result.rng_state << '\n';
}
int main() {
    auto table = trap_table(); vector<int> initial{0, 7, 56, 21};
    show("trap", genetic_algorithm(6, table, initial, 113, 3, 100, 100), 6);
    show("budget", genetic_algorithm(6, table, initial, 113, 3, 100, 6), 6);
    show("zero-budget", genetic_algorithm(6, table, initial, 113, 3, 100, 0), 6);
    show("one-bit", genetic_algorithm(1, vector<I64>{-3, -1}, vector<int>{0, 0},
         7, 2, 1000, 10), 1);
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    static final long MOD = 2147483647L, RANGE = MOD - 1;
    static class RandomSource {
        long state;
        int draws, rejections;
        RandomSource(long seed) { state = seed; }
        int below(int bound) {
            long limit = RANGE - RANGE % bound;
            while (true) {
                state = (48271 * state) % MOD;
                ++draws;
                long value = state - 1;
                if (value < limit) return (int)(value % bound);
                ++rejections;
            }
        }
    }
    static class Event {
        int generation, slot;
        int[] picks, parents;
        int cut, before;
        int[] mutation_draws;
        int flip_mask, child;
        long fitness, rng_state;
        int rng_draws;
        Event(int g, int s, int[] p, int[] par, int c, int b, int[] md,
              int mask, int ch, long f, long rs, int rd) {
            generation=g; slot=s; picks=p; parents=par; cut=c; before=b;
            mutation_draws=md; flip_mask=mask; child=ch; fitness=f;
            rng_state=rs; rng_draws=rd;
        }
    }
    static class Snapshot {
        int generation;
        int[] population;
        long[] fitness;
        int best;
        long best_fitness, total;
        int evaluations, rng_draws;
        Snapshot(int g, int[] p, long[] f, int b, long bf, int ev, int rd) {
            generation=g; population=p.clone(); fitness=f.clone(); best=b;
            best_fitness=bf; evaluations=ev; rng_draws=rd;
            for (long x : f) total += x;
        }
    }
    static class Result {
        String status="EVAL_LIMIT";
        boolean has_value;
        int best=-1;
        long best_fitness;
        int[] population=new int[0];
        long[] fitness=new long[0];
        int generations, evaluations, children, bit_flips;
        long rng_state;
        int rng_draws, rng_rejections;
        List<Snapshot> history=new ArrayList<>();
        List<Event> events=new ArrayList<>();
    }
    static int eliteIndex(long[] fitness) {
        int best=0;
        for (int i=1; i<fitness.length; ++i)
            if (fitness[i]>fitness[best]) best=i;
        return best;
    }
    static Result genetic_algorithm(int length, long[] scores, int[] initial,
                                    long seed, int generations,
                                    int mutation_per_mille, int evaluation_budget) {
        if (length<1 || length>12 || seed<1 || seed>=MOD || generations<0 ||
            generations>500 || mutation_per_mille<0 || mutation_per_mille>1000 ||
            evaluation_budget<0 || evaluation_budget>1000000)
            throw new IllegalArgumentException("parameter out of range");
        if (scores.length!=(1<<length) || initial.length<2 || initial.length>32)
            throw new IllegalArgumentException("invalid table or population size");
        for (long x : scores)
            if (x < -1000000000L || x > 1000000000L)
                throw new IllegalArgumentException("invalid fitness");
        for (int x : initial)
            if (x<0 || x>=(1<<length)) throw new IllegalArgumentException("invalid genome");
        long[] table=scores.clone(); int[] population=initial.clone();
        RandomSource rng=new RandomSource(seed); Result result=new Result();
        result.rng_state=seed;
        int size=population.length;
        if (evaluation_budget<size) return result;
        long[] fitness=new long[size];
        for (int i=0; i<size; ++i) fitness[i]=table[population[i]];
        result.has_value=true; result.evaluations=size;
        int elite=eliteIndex(fitness);
        result.best=population[elite]; result.best_fitness=fitness[elite];
        result.history.add(new Snapshot(0, population, fitness, result.best,
            result.best_fitness, result.evaluations, rng.draws));
        while (true) {
            if (result.generations==generations) {
                result.status="GEN_LIMIT"; break;
            }
            if (evaluation_budget-result.evaluations<size-1) {
                result.status="EVAL_LIMIT"; break;
            }
            elite=eliteIndex(fitness);
            int[] next_population=new int[size]; long[] next_fitness=new long[size];
            next_population[0]=population[elite]; next_fitness[0]=fitness[elite];
            for (int slot=1; slot<size; ++slot) {
                int[] picks=new int[4];
                for (int j=0; j<4; ++j) picks[j]=rng.below(size);
                int a=fitness[picks[0]]>=fitness[picks[1]] ? picks[0] : picks[1];
                int b=fitness[picks[2]]>=fitness[picks[3]] ? picks[2] : picks[3];
                int cut=length>1 ? 1+rng.below(length-1) : 0;
                int suffix=(1<<(length-cut))-1;
                int before=(population[a]&(((1<<length)-1)^suffix)) |
                           (population[b]&suffix);
                int[] mutation_draws=new int[length]; int flip_mask=0;
                for (int j=0; j<length; ++j) {
                    int draw=rng.below(1000); mutation_draws[j]=draw;
                    if (draw<mutation_per_mille) {
                        flip_mask |= 1<<(length-1-j); ++result.bit_flips;
                    }
                }
                int child=before^flip_mask; long value=table[child];
                ++result.evaluations; ++result.children;
                if (value>result.best_fitness) {
                    result.best=child; result.best_fitness=value;
                }
                next_population[slot]=child; next_fitness[slot]=value;
                result.events.add(new Event(result.generations+1, slot, picks,
                    new int[]{a, b}, cut, before, mutation_draws, flip_mask,
                    child, value, rng.state, rng.draws));
            }
            population=next_population; fitness=next_fitness; ++result.generations;
            result.history.add(new Snapshot(result.generations, population, fitness,
                result.best, result.best_fitness, result.evaluations, rng.draws));
        }
        result.population=population.clone(); result.fitness=fitness.clone();
        result.rng_state=rng.state; result.rng_draws=rng.draws;
        result.rng_rejections=rng.rejections;
        return result;
    }
    static long[] trap_table() {
        long[] scores=new long[64];
        for (int genome=0; genome<64; ++genome) {
            for (int shift : new int[]{0, 3}) {
                int ones=0;
                for (int j=0; j<3; ++j) ones += (genome>>(shift+j))&1;
                scores[genome] += ones==3 ? 3 : 2-ones;
            }
        }
        return scores;
    }
    static String bits(int x, int length) {
        String s=Integer.toBinaryString(x);
        return "0".repeat(length-s.length())+s;
    }
    static void show(String label, Result result, int length) {
        System.out.println(label);
        for (Snapshot row : result.history) {
            StringBuilder members=new StringBuilder(), values=new StringBuilder();
            for (int i=0; i<row.population.length; ++i) {
                if (i>0) { members.append(','); values.append(','); }
                members.append(bits(row.population[i], length)); values.append(row.fitness[i]);
            }
            System.out.println("g="+row.generation+" pop="+members+" fitness="+values+
                " best="+bits(row.best, length)+":"+row.best_fitness+" sum="+row.total+
                " eval="+row.evaluations+" draws="+row.rng_draws);
        }
        String best=result.has_value ? bits(result.best, length)+":"+result.best_fitness : "NONE";
        System.out.println("status="+result.status+" best="+best+" generations="+
            result.generations+" eval="+result.evaluations+" children="+result.children+
            " flips="+result.bit_flips+" draws="+result.rng_draws+" rejections="+
            result.rng_rejections+" rng="+result.rng_state);
    }
    public static void main(String[] args) {
        long[] table=trap_table(); int[] initial={0, 7, 56, 21};
        show("trap", genetic_algorithm(6, table, initial, 113, 3, 100, 100), 6);
        show("budget", genetic_algorithm(6, table, initial, 113, 3, 100, 6), 6);
        show("zero-budget", genetic_algorithm(6, table, initial, 113, 3, 100, 0), 6);
        show("one-bit", genetic_algorithm(1, new long[]{-3, -1}, new int[]{0, 0},
            7, 2, 1000, 10), 1);
    }
}

Expected standard output, identical in all three languages:

• trap
• g=0 pop=000000,000111,111000,010101 fitness=4,5,5,1 best=000111:5 sum=15 eval=4 draws=0
• g=1 pop=000111,111000,000000,100011 fitness=5,5,4,1 best=000111:5 sum=15 eval=7 draws=33
• g=2 pop=000111,100111,111111,110111 fitness=5,4,6,3 best=111111:6 sum=18 eval=10 draws=66
• g=3 pop=111111,101011,100111,111111 fitness=6,0,4,6 best=111111:6 sum=16 eval=13 draws=99
• status=GEN_LIMIT best=111111:6 generations=3 eval=13 children=9 flips=3 draws=99 rejections=0 rng=501268393
• budget
• g=0 pop=000000,000111,111000,010101 fitness=4,5,5,1 best=000111:5 sum=15 eval=4 draws=0
• status=EVAL_LIMIT best=000111:5 generations=0 eval=4 children=0 flips=0 draws=0 rejections=0 rng=113
• zero-budget
• status=EVAL_LIMIT best=NONE generations=0 eval=0 children=0 flips=0 draws=0 rejections=0 rng=113
• one-bit
• g=0 pop=0,0 fitness=-3,-3 best=0:-3 sum=-6 eval=2 draws=0
• g=1 pop=0,1 fitness=-3,-1 best=1:-1 sum=-4 eval=3 draws=5
• g=2 pop=1,0 fitness=-1,-3 best=1:-1 sum=-4 eval=4 draws=10
• status=GEN_LIMIT best=1:-1 generations=2 eval=4 children=2 flips=2 draws=10 rejections=0 rng=439347582

Complexity, Correctness, and Invariants

Let $g$ be the number of completed generations and $C=g(N-1)$ the number of evaluated children. For an initialized run, the exact evaluation count is

$$E=N+g(N-1),\qquad g=\min\left(G,\left\lfloor\frac{B-N}{N-1}\right\rfloor\right).$$

When $B\lt N$, no evaluation occurs. Fitness values do not affect how many generations this implementation completes: it has no early optimum or stagnation exit. With sufficient budget, best, average, and worst objective landscapes all require exactly $N+G(N-1)$ evaluations. Random draw counts can still differ because the integer mapper sometimes rejects a raw value.

Write $D$ for the number of raw generator draws and $J$ for rejection retries. The exact relation is

$$D=C\bigl(4+\mathbf{1}_{L\gt1}+L\bigr)+J.$$

For the actual table-based implementation, including input validation/copies and retained traces, running time is

$$\Theta\bigl(2^L+N+gN+CL+D\bigr).$$

For the particular generator and allowed bounds, each mapped draw takes at most two raw draws. A rejected state is $z=2147483647-k$ for some $1\le k\le999$; its successor is $2147483647-48271k$, which lies below every rejection interval used here. Thus $J$ is at most the number of requested mapped draws, and this bounded implementation has best-, average-, and worst-case time $\Theta(2^L+N+gNL)$ for fixed input sizes and completed generation count. Displaying all genomes adds $O((g+1)NL)$ output work.

If the raw generator were replaced by an independent uniform random source, rejection sampling would instead have expected constant cost, with no fixed worst-case retry bound. The explicit $D$ expression remains valid in either model; the two-draw bound relies on this generator, multiplier, and small validated bounds.

With an external fitness evaluator costing $C_f$ per child and ordinary $L$-gene variation, the usual expected search cost is $O(NC_f+gN(L+C_f))$, plus representation construction and validation. There is no general polynomial bound on generations needed to discover an optimum. A GA's quality and runtime depend on the encoding, operators, objective, and stopping policy.

Two live populations need $O(NL)$ space for explicit gene arrays, or $O(N)$ machine words for this packed bounded encoding. This program keeps full history: its auxiliary storage is $\Theta(2^L+(g+1)N+C(L+1))$ words, including the copied fitness table, generation snapshots, and every child's mutation draws. Removing history and using an external evaluator leaves the population storage plus the archive and evaluator state.

The proof of the useful guarantees is an induction over generations. Initialization pairs each genome with its exact deterministic score and sets the archive to their maximum. During a generation, all parents and comparisons refer to that unchanged pair of old arrays. Crossover masks and mutation masks contain only the lowest $L$ bits, so every child is a valid genome; evaluating it restores the exact genome/fitness pairing. Strict archive updates preserve the maximum over every evaluated initial member and child. Copying the current elite retains the previous maximum, so after committing a complete generation,

$$\max_{x\in P_{g+1}}f(x)\ge\max_{x\in P_g}f(x).$$

In this implementation that maximum equals the archive's score at every recorded generation. The mean and minimum fitness need not improve. Reserving the whole generation's evaluations before creating children ensures the returned population and history always end at a completed generation.

One theoretical distinction matters. Under fresh independent bit mutation with $0\lt p\lt1$, any pre-mutation genome reaches any particular target at Hamming distance $h$ with probability $p^h(1-p)^{L-h}$. This is at least $\varepsilon=\min(p,1-p)^L\gt0$. Therefore after $C$ offspring the probability of never sampling a fixed optimum is at most $(1-\varepsilon)^C$, even when the parental genomes adapt to previous outcomes. An unlimited ideal run samples that optimum with probability $1$, but this loose bound may be astronomically unhelpful. It does not establish a finite-run certificate, does not apply at $p=0$ or $p=1$, and does not turn this finite deterministic PRNG into an independent random source.

Variants, Pitfalls, and Optimizations

Choose operators for the representation. Bit-flip mutation and one-point crossover preserve binary strings. They do not preserve permutations, precedence constraints, route feasibility, or fixed-cardinality subsets. For a tour, use permutation-aware crossover and swap or inversion mutation; for constraints, define a feasible decoder, repair rule, or explicit constraint-handling policy. A repaired offspring must be evaluated in its final form.

Keep selection and fitness direction consistent. This code maximizes. A tournament handles zero and negative values correctly; ordinary roulette-wheel probabilities proportional to raw fitness fail when weights are negative or their total is zero. For a single objective, a strictly increasing fitness transformation preserves tournament winners, although fitness totals and stopping thresholds may change. Penalized objectives require deliberate tradeoffs, not arbitrary constants.

Separate the archive from breeding elitism. An archive can remember a lost candidate without keeping it available for reproduction. Elitism actively inserts that candidate into the next population. Excessive elitism and strong tournaments may remove diversity; too little selection pressure can spend evaluations almost randomly. Equal best scores or many duplicate genomes do not prove that the whole feasible space has been explored.

Preserve parent and score integrity. With mutable chromosomes, selecting an individual twice may create aliases. Clone before changing its genes, preserve the old generation until replacement, and invalidate any cached score after variation. The integer encoding here avoids chromosome aliasing, but snapshots still require independent list/array copies. DEAP's operator documentation documents the same ownership issue for its in-place variation operators.

Interpret mutation probabilities precisely. This implementation mutates every child and makes a separate decision per bit. Under the ideal model, the expected number of flips is $Lp$, and the probability of at least one flip is $1-(1-p)^L$. For $L=6$ and $p=0.1$, those are $0.6$ flips and probability $0.468559$; it is incorrect to call this a $10\%$ probability of mutating the whole child. A rate near $1/L$ is a useful experiment on some binary benchmarks, not a universal best setting. Mutation rate $1$ complements every child; it does not sample uniformly. Rate $0.5$ produces a uniform random bit string conditional on any pre-mutation child under independent bit draws, largely erasing parental information.

Do not equate crossover with improvement. In the trace, joining 111000 with 000111 at cut $3$ produces 111111, while reversing those parent roles at the same cut produces 000000. Useful recombination depends on which loci interact and how the encoding groups them; a cut can break a good block. Uniform, two-point, and problem-specific crossovers explore different combinations.

Measure quality against evaluations. Compare independent seeds, initialization schemes, and exact small-instance optima; report success rate and best-score distributions at the same evaluation budget. Include random search and simpler local methods as baselines. A fixed seed supports reproducibility, while many seeds assess variability. Parallel offspring evaluation can help when objectives are expensive; preserve deterministic slot order, per-child random streams, and tie rules if you need reproducible results.

Cache and stop carefully. Caching deterministic duplicate genomes can reduce costly objective calls, but changes what an evaluation-budget counter means; the shown code intentionally evaluates each child. For noisy or time-changing fitness, elite score reuse and monotonic best-value claims require reevaluation or an explicit statistical policy. A stagnation exit saves work but is still heuristic. Restarts, random immigrants, islands, and fitness sharing can encourage diversity; memetic algorithms combine evolutionary variation with local improvement. Real-valued evolutionary strategies and multiobjective methods such as NSGA-II solve different representation or selection problems; their settings and guarantees must be assessed separately.

Practice Problems and Real-World Use

Start with a target-bit or OneMax objective whose optimum is known, then move to a small deceptive landscape like this lesson's. Replace the table with an evaluator only after the small cases have exact reference answers. DEAP's OneMax example is a primary worked example of the selection/variation/evaluation loop; its operator reference is useful for checking representation-specific choices. Those examples use their own GA policies, so do not expect their traces to match the particular policy defined here.

For a practical optimization study, record the encoding and decoder, objective and constraints, initial population, seed policy, operators and their probabilities, tie rules, budget accounting, and independent validation of the final candidate. In engineering design or scheduling, evaluator cost and feasibility often matter more than the arithmetic of the genetic operators. A benchmark score is meaningful only when compared with an appropriate exact bound or baseline.