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.