Decoder Based Representations

Decoder-Based Representations

You are an expert in indirect (decoder-based) representations for combinatorial optimization. This skill is the catalog of decoder families — random-key decoders (sort, interval, threshold), priority- and rule-based decoders, serial and parallel schedule-generation schemes (SGS), and feasibility-enforcing constructive decoders — with the design criteria (coverage, bias, locality, redundancy, decode time) that decide between them. Use the framework below to pick a decoder family for a given problem, implement it correctly in numpy, and diagnose the failure modes that are specific to genotype-phenotype mappings.

Initial Assessment

Before designing or reviewing a decoder, establish the following:

• Phenotype structure. What object must the decoder output: a permutation, a subset, an assignment vector, a start-time schedule, a packing? The phenotype type narrows the decoder family immediately (sort decoder for sequences, interval decoder for categorical assignments, SGS for resource-constrained schedules).
• Constraint families and their placement. List every constraint and decide, per family, whether the decoder absorbs it (constructs only feasible solutions), a repair step fixes it, or a penalty prices it. Decoders earn their keep by absorbing the constraints that crossover and mutation would otherwise break; see constraint-handling-techniques for the penalty/repair alternatives.
• Existing constructive heuristic. If a greedy or dispatching heuristic already exists (NEH, LPT, FFD, earliest-due-date), the cheapest strong decoder is usually that heuristic with its fixed priority replaced by genotype-supplied priorities. This also gives a free warm start: encode the heuristic's own priorities as keys.
• Search engine that will drive the genotype. BRKGA and GAs with uniform crossover want random keys in $[0,1)^n$; integer-vector genotypes (rule indices, category ids) want integer mutation/crossover; PSO, DE, ES, and CMA-ES want a continuous box, which random keys provide. Choose the genotype the engine handles natively so no operator needs rewriting.
• Evaluation budget and decode cost. Decoding dominates runtime in decoder-based metaheuristics: total cost is roughly population × generations × decode_cost. Estimate one decode (sort decoders: O(n log n); SGS: roughly O(n² K)) and check the budget before committing. Plan batch/vectorized decoding from the start if the population is large.
• Coverage requirement. Must the decoder's image provably contain an optimal solution? Serial SGS guarantees this for regular objectives (it generates active schedules); parallel SGS does not. If you will claim convergence-to-optimum or run long high-budget searches, coverage matters; for fast good-enough heuristics it may not.
• Locality requirement. Will the engine rely on small steps (PSO velocities, Gaussian mutation, BRKGA biased crossover)? Then the decoder should map small key changes to small phenotype changes. Heavily repairing or strongly greedy decoders can destroy this property.
• Determinism and tie-breaking. The same genotype must always decode to the same phenotype: fix tie-breaking (stable sorts, lowest-index-first), avoid internal randomness, avoid iteration over unordered containers. Determinism is a precondition for caching and reproducibility.
• Instance scale. For SGS decoders, the time horizon and resource count set the memory and per-decode cost; for sort decoders only n matters. Check the largest instance, not the test instance.
• Validation plan. An independent feasibility checker (separate code path from the decoder) must verify every reported solution; on small instances, compare decoder-reachable optima against an exact solver.
• Reproducibility. Seed the genotype sampler (np.random.default_rng(seed)) and keep the decoder seed-free. Report results over multiple seeds.

Decoder Anatomy and Design Criteria

A decoder replaces direct search over the feasible set $S$ with search over a simple genotype space $G$:

$$ \min{g \in G} \; f(D(g)) \qquad \text{instead of} \qquad \min{s \in S} f(s), \qquad D : G \to S . $$

The search engine only ever sees $G$ (a hypercube, an integer lattice, a permutation set); the decoder $D$ carries all problem knowledge. The design criteria, following Rothlauf (2006, "Representations for Genetic and Evolutionary Algorithms"):

1. Feasibility. $D(g) \in S$ for every $g \in G$. This is the defining advantage: arbitrary crossover and mutation on $G$ can never produce an infeasible phenotype.
2. Coverage. The image $D(G)$ should contain at least one optimal solution — or, weaker, solutions within the quality target. A decoder that is too greedy shrinks the image past the optimum and no amount of search recovers it.
3. Bias. Uniform sampling of $G$ induces a distribution over $S$. Some bias toward good solutions is useful (it is a prior); uncontrolled bias concentrates mass on mediocre phenotypes and starves the rest.
4. Locality. Small genotype distances should map to small phenotype distances. Low locality turns guided search into random search: offspring resemble their parents in $G$ but not in $S$.
5. Redundancy. $D$ is many-to-one; for a sort decoder, only the ordering of keys matters, so each permutation has an uncountable preimage. Redundancy itself is harmless, but it creates plateaus in $G$ and means diversity must be measured on phenotypes or fitness values, never on genotype distance.
6. Decode time. The decoder runs once per evaluation. Its complexity, not the engine's, sets the runtime.
7. Determinism. $D$ must be a function. Fixed tie-breaking is part of the decoder specification.

Decoder family catalog

| Family | Genotype | Phenotype | Feasibility | Decode cost | Typical problems | |---|---|---|---|---|---| | Sort decoder | keys $[0,1)^n$ | permutation | always | $O(n \log n)$ | flow shop, single machine, TSP-like orders | | Interval (allocation) decoder | keys $[0,1)^n$ | categorical vector | per-item yes; coupling constraints need repair | $O(n)$ | machine assignment, mode selection, clustering | | Threshold decoder | keys $[0,1)^n$ | binary vector | only with repair/completion | $O(n)$ + repair | set covering, knapsack, facility selection | | Greedy-priority decoder | keys as priorities | any constructive solution | always (construction respects constraints) | cost of the greedy | parallel machines, bin packing, graph coloring | | Rule-selection decoder | integer vector of rule ids | dispatching trajectory | always | cost of the simulation | dynamic scheduling, hyper-heuristic style search | | Serial SGS | activity priorities | start-time schedule | always; image = active schedules | $O(n^2 K)$ | RCPSP, project scheduling, job shop variants | | Parallel SGS | activity priorities | start-time schedule | always; image = non-delayed schedules | $O(n^2 K)$ | RCPSP when speed beats coverage | | Multi-segment chromosome | concatenated key blocks | layered decision (assign then sequence) | inherits from each stage | sum of stages | assign-and-sequence scheduling, location-routing |

Property comparison across the catalog

| Family | Coverage of optima | Bias under uniform keys | Locality | Redundancy | |---|---|---|---|---| | Sort decoder | full (all permutations) | uniform over permutations | good (rank changes are gradual) | high (only key order matters) | | Interval decoder | full (all assignments) | uniform over categories | good | moderate (within-interval changes are silent) | | Threshold + repair | full if repair can reach all feasible | depends on repair; often strong | poor near the repair boundary | moderate | | Greedy-priority | usually wide, rarely provable | strong toward greedy-like solutions | moderate | high | | Serial SGS | contains an optimum (regular objectives) | toward active, left-shifted schedules | moderate | high | | Parallel SGS | may exclude every optimum | toward non-delayed schedules | moderate | high | | Rule-selection | only rule-reachable trajectories | strong (rules are few) | moderate | very high |

Genotype-engine compatibility

| Genotype | Engines that drive it natively | Note | |---|---|---| | Random keys $[0,1)^n$ | BRKGA, GA with uniform/blend crossover, PSO, DE, ES, CMA-ES | one genotype, many engines — the main reason random keys are popular (Bean, 1994, "Genetic algorithms and random keys for sequencing and optimization") | | Integer vector | GA with integer mutation, simulated annealing on component moves | also reachable from keys via an interval decode | | Permutation + decoder | GA with OX/PMX, iterated local search on swaps | use when order itself is the genotype but the phenotype needs construction (sequence-then-pack) |

Decision guidance.

• Use a sort decoder when the phenotype is a pure sequence and relative order carries the fitness signal (flow shop). Avoid it when adjacency carries the signal (pure TSP): order-preserving inheritance does not preserve edges, so add local search or use permutation operators directly (see solution-encodings).
• Use an interval decoder for independent categorical choices; add repair only for coupling constraints (capacities across items).
• Use a greedy-priority or SGS decoder when constraints are complex enough that direct operators would almost always break them — resource-constrained scheduling is the canonical case (Hartmann, 1998, "A competitive genetic algorithm for resource-constrained project scheduling").
• Use rule-selection when good dispatching rules exist and the search should mix them per decision point rather than discover sequences from scratch.
• Prefer the weakest decoder whose image still contains near-optimal solutions: weaker decoders preserve locality and coverage; stronger decoders save evaluations but bias and shrink the image.

Random-Key Decoders

Random keys (Bean, 1994) put the genotype in $[0,1)^n$ so every continuous or position-wise operator applies unchanged. The two core mappings are sorting (keys to a permutation) and interval splitting (keys to categories).

Sort decoder — worked example: permutation flow shop

When to use: the phenotype is a sequence and any sequence is feasible. Fits flow shop, single-machine problems, and any sequence-driven constructive pipeline. Complexity: $O(n \log n)$ per chromosome, fully batchable. This is the standard BRKGA decoder for flow shop; the engine side is in biased-random-key-genetic-algorithm, and continuous engines such as PSO and DE drive the same keys (see particle-swarm-optimization).

"""Sort decoder: random keys -> permutation, applied to permutation flow shop."""
import numpy as np

def sort_decode(keys: np.ndarray) -> np.ndarray:
    """Decode a key matrix (P, n) into P permutations: stable argsort per row.

    Stable sort fixes tie-breaking (lowest index first), so decoding is
    deterministic. Cost: O(P n log n).
    """
    return np.argsort(keys, axis=1, kind="stable")

def flowshop_makespan(perms: np.ndarray, proc: np.ndarray) -> np.ndarray:
    """Vectorized makespan of P job sequences on an (n_jobs, n_machines) instance.

    Recurrence C[j,k] = max(C[j-1,k], C[j,k-1]) + p[j,k], evaluated for all P
    sequences at once. Cost: O(P n m).
    """
    n_machines = proc.shape[1]
    completion = np.zeros((perms.shape[0], n_machines))
    for pos in range(perms.shape[1]):
        p_job = proc[perms[:, pos], :]                    # (P, m)
        for k in range(n_machines):
            prev = completion[:, k - 1] if k > 0 else 0.0
            completion[:, k] = np.maximum(completion[:, k], prev) + p_job[:, k]
    return completion[:, -1]

rng = np.random.default_rng(0)
proc = rng.integers(1, 20, size=(8, 4)).astype(float)     # 8 jobs, 4 machines
keys = rng.random((64, 8))                                # population of 64
perms = sort_decode(keys)
cmax = flowshop_makespan(perms, proc)
best = int(np.argmin(cmax))
print(perms[best].tolist(), float(cmax[best]))
# Expected: best sequence [2, 3, 5, 7, 1, 4, 6, 0] with makespan 122.0 —
# 64 uniform key vectors already sample 64 (likely distinct) permutations.

The redundancy is explicit here: scaling all keys by 0.5 changes nothing. Measure population diversity on perms or cmax, never on keys.

Interval (allocation) decoder

When to use: one independent categorical decision per item — machine assignment, execution mode, color class. Equal-width intervals give every category the same prior probability; unequal widths inject a prior (give a larger interval to a cheaper machine). Complexity: $O(n)$ per chromosome. Fits BRKGA, PSO, DE on keys; coupling constraints (machine capacities) need a repair pass or a greedy-priority decoder instead.

"""Interval (allocation) decoder: each key selects one of c categories."""
import numpy as np

def interval_decode(keys: np.ndarray, n_categories: int) -> np.ndarray:
    """Map keys in [0,1) to categories: category = floor(key * c).

    The min() guards against a key exactly equal to 1.0 (possible after
    clipping by a continuous engine). Cost: O(P n).
    """
    return np.minimum((keys * n_categories).astype(np.int64), n_categories - 1)

rng = np.random.default_rng(1)
proc = rng.integers(2, 12, size=10).astype(float)         # 10 jobs
n_machines = 3
keys = rng.random((32, 10))
assign = interval_decode(keys, n_machines)                # (32, 10) machine ids
onehot = assign[:, :, None] == np.arange(n_machines)      # (32, 10, 3)
loads = (onehot * proc[None, :, None]).sum(axis=1)        # (32, 3)
cmax = loads.max(axis=1)
print(float(cmax.min()))
# Expected: best makespan 25.0 over 32 random assignments
# (total work 68.0, so the lower bound ceil(68/3) = 23 is approached).

Multi-segment chromosomes concatenate blocks: keys [0:n] assign machines via interval decode, keys [n:2n] sequence each machine via sort decode. Decode the blocks in stage order and document the block layout next to the decoder.

Priority-Rule and Rule-Selection Decoders

These decoders feed the genotype into a constructive procedure: the genotype supplies priorities (which item next) or rules (how to choose the next item), and the construction enforces feasibility step by step.

Greedy-priority decoder: list scheduling on identical machines

When to use: a list-scheduling or greedy heuristic exists and its input order is the lever. The decoder below visits jobs in key order and assigns each to the least-loaded machine — every genotype yields a feasible assignment. Complexity: $O(n m)$ per chromosome here, vectorized across the whole population. Fits parallel-machine scheduling, bin packing, graph coloring (visit order for a greedy colorer).

"""Greedy-priority decoder: keys order the jobs, list scheduling assigns machines."""
import numpy as np

def list_schedule_decode(
    keys: np.ndarray, proc: np.ndarray, n_machines: int
) -> tuple[np.ndarray, np.ndarray]:
    """Decode keys (P, n) into machine assignments (P, n) by list scheduling.

    Jobs are visited in increasing key order; each goes to the currently
    least-loaded machine. Always feasible. Vectorized over the population:
    O(P n m) total, or O(P n log m) with per-row heaps.
    """
    P, n = keys.shape
    order = np.argsort(keys, axis=1, kind="stable")
    loads = np.zeros((P, n_machines))
    assign = np.empty((P, n), dtype=np.int64)
    rows = np.arange(P)
    for pos in range(n):
        job = order[:, pos]
        machine = loads.argmin(axis=1)
        assign[rows, job] = machine
        loads[rows, machine] += proc[job]
    return assign, loads.max(axis=1)

rng = np.random.default_rng(2)
proc = rng.integers(1, 30, size=12).astype(float)
keys = rng.random((50, 12))
assign, cmax = list_schedule_decode(keys, proc, n_machines=3)
lpt_keys = (np.argsort(np.argsort(-proc)).astype(float) / 12.0)[None, :]
_, lpt_cmax = list_schedule_decode

…

## Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

- **Author:** [hajibabaie](https://github.com/hajibabaie)
- **Source:** [hajibabaie/combinatorial-optimization-skills](https://github.com/hajibabaie/combinatorial-optimization-skills)
- **License:** MIT

Install and usage instructions live in the source repository linked above.