Heuristic — memetic evolutionary search

Memetic EAX

Alias eax, memetic, memetic_eax
Type Heuristic — memetic evolutionary search
Complexity O(epochs · pop · children · n²)
Warm start Consumes the previous pipeline stage’s tour as one population member
Benchmarks published results ↓

Description

Memetic EAX keeps a population of locally optimised tours and recombines two parents by Edge Assembly Crossover (EAX). The union of the two parent edge sets is decomposed into alternating A/B cycles: each city pairs its A-only edges with its B-only edges, which yields disjoint even cycles. Applying a selected E-set to parent A as a symmetric difference gives every city exactly one new neighbour, so degree two is preserved. Any subtour the exchange creates is patched back into a single cycle by greedily merging the smallest component with candidate-list edges. Offspring are polished with a candidate-restricted 2-opt pass seeded by the disturbed vertices, and a parent is replaced only by its own strictly cheaper child (family-based replacement), which keeps population niches instead of letting one global best take over.

The solver is symmetric-only: TYPE: ATSP is rejected by the TSPLIB parser, and every move here assumes an undirected edge.

procedure MemeticEAX(cities, epochs, pop_size, children_per_pair):
    candidates ← k-nearest-neighbour lists
    population ← polished randomised constructive starts (+ warm-start seed)
    best ← cheapest member
    for epoch in 1..epochs:
        for each distinct pair (A, B) in a shuffled ring:
            child ← ∅
            for _ in 1..children_per_pair:
                cycles ← AB-cycles(A, B)
                E      ← select(cycles, strategy)
                tour   ← patch(A ⊕ E, candidates)
                tour   ← dirty_2opt(tour, candidates)
                child  ← cheaper(child, tour)
            if child < A: replace A with child
        if best improved: reset stagnation else stagnate++
    return best

Options

Field CLI flag Default Range Description
epochs --epochs 500 ≥ 0 Maximum generations; 0 means no epoch cap
pop_size --pop-size 100 ≥ 2 Population size
children_per_pair --children-per-pair 15 ≥ 1 Offspring considered per parent
strategy --strategy hybrid single_ab, rand, hybrid E-set selection
stall_epochs --stall-epochs 50 ≥ 1 hybrid switches to single_ab after this many stagnant generations; the solver stops at twice this count
candidate_k --candidate-k 20 ≥ 1 Nearest-neighbour list size for patching and local search
seed --seed system entropy any u64 Fixed RNG seed for reproducible runs

--stall-epochs falls back to --stagnation_epochs and --candidate-k to --n_nearest when the EAX-specific flag is omitted. All fields are also reachable through the REST API’s configs.memetic_eax, a TOML [memetic_eax]/[stage.memetic_eax] table, or the WASM SolveOptions fields (eaxPopSize, eaxChildrenPerPair, eaxStrategy with 0 = single_ab, 1 = rand, 2 = hybrid, eaxStallEpochs, eaxCandidateK).

Usage

# Standalone
teeline solve eax -i data/tsplib/berlin52.tsp --seed 1

# Warm-started after a constructive stage
teeline pipeline --steps=nn,eax -i data/tsplib/berlin52.tsp --seed 1

# TOML pipeline stage
cat > eax.toml <<'EOF'
[[stage]]
solver = "nn"

[[stage]]
solver = "memetic_eax"

[stage.memetic_eax]
pop_size = 50
children_per_pair = 8
strategy = "hybrid"
seed = 1
EOF
teeline pipeline --config eax.toml -i data/tsplib/berlin52.tsp

Notes

EAX is heavier per epoch than Lin-Kernighan or 2-opt: each child runs a crossover, a patching pass, and a local 2-opt polish. On berlin52 and kroA100 the default budget reaches the published optimum; a280 and dsj1000 approach it. For a tighter wall-clock budget, lower pop_size and children_per_pair first — both scale the per-epoch cost linearly, while strategy = "single_ab" reduces the crossover work further.

The published scores for this algorithm are indexed under eax in bench/solvers.json; the TSPLIB optimum is the ground truth, never the solver’s own output.

Benchmarks

Loading published results…