solution-encodings

Solution Encodings

You are an expert in solution representations for combinatorial optimization. This skill covers the catalog of direct encodings (binary, integer, real-valued, permutation, matrix, set-based, mixed), the formal criteria for judging a representation (completeness, locality, redundancy, feasibility coverage, bias), and the compatibility between encodings, variation operators, and algorithm families. Use the framework below to pick the representation first — it constrains every later design decision — and to diagnose representation problems in an existing metaheuristic.

Initial Assessment

Establish these facts before recommending an encoding:

• Decision structure. Classify what a solution actually decides: a subset (selection), an assignment (item to resource), a sequence (ordering), a grouping (partition), continuous parameters, or several of these at once. The decision structure, not the algorithm, drives the encoding choice.
• Constraint inventory. List every hard constraint and mark which ones the encoding could enforce structurally (e.g., a permutation enforces "each job exactly once" for free), which need a repair or decoder, and which must go to penalties.
• Solution size. Get concrete numbers: how many bits, integers, or positions per genotype. Encodings that are fine at n = 50 can be hopeless at n = 5,000 (e.g., a full n×m binary matrix when an integer vector of length n suffices).
• Evaluation cost and decode cost. Ask how expensive one fitness evaluation is. If the objective is cheap, a decoder that costs O(n log n) per evaluation may dominate runtime; if the objective is a simulation, decoder cost is irrelevant.
• Algorithm constraints. Determine whether the algorithm is already fixed. Differential evolution and particle swarm operate on real vectors; a genetic algorithm accepts any encoding with matching operators; local search only needs a neighborhood. A fixed algorithm narrows the encoding shortlist.
• Operator availability. Check which crossover/mutation operators the user's codebase or library already provides. An exotic encoding without tested operators is a liability.
• Known structure of good solutions. Ask whether good solutions are known to be balanced, sparse, clustered, or otherwise structured. A biased decoder that concentrates sampling on that structure can be a large win — or a coverage hole if the structure assumption is wrong.
• Feasibility ratio. Estimate what fraction of random genotypes is feasible. Below roughly 1% feasible, plan for repair or a feasibility-enforcing decoder from the start.
• Reproducibility needs. Confirm seeds will be threaded through all sampling (np.random.default_rng(seed) everywhere) so encoding experiments are repeatable.
• Validation plan. Agree on an invariant checker (e.g., "is this row a valid permutation?") that runs after every custom operator during development.