Symmetry-Aligned Crossover for Searching Cyclic and Double-Circulant Codes

Genetic algorithms build good solutions by recombining pieces of two parents. Recombination only helps if the pieces survive the cut. In many problems, many different encodings describe the same solution. A tour can start at any city, and cluster labels can be renamed. When two parents describe similar solutions in different "orientations," crossover splices mismatched halves, and the offspring is damaged. Two existing operators show that fixing this pays off by rotating one parent to match the other before cutting. CSRX does this for traveling-salesperson tours. HG-means does it for cluster labels. Both are hand-built for a single symmetry.

This proposal carries the same move into a setting where the symmetries are known exactly and where computer search still produces records: the search for error-correcting codes with large minimum distance. A cyclic code is specified by choosing a set of "cyclotomic cosets," fixed blocks of exponents that together define the code. A double-circulant code is specified by a single polynomial. In both cases a known group of coordinate relabelings maps one specification to another that defines an equivalent code with identical minimum distance. The idea is to first move one parent by the group element that makes it agree most with the other parent, and only then apply ordinary crossover. We test whether this turns code search from mostly destructive recombination into constructive recombination.

Core Claim

Fitness-preserving symmetries create redundant encodings. In code search these come from the multiplier group $x \mapsto x^a$ with $\gcd(a,n)=1$, together with cyclic shifts in the double-circulant case. Because of them, blind crossover between two good codes mostly produces bad codes. This is the "negative average fitness delta" that On the Effectiveness of Genetic Operations in Symbolic Regression measured for tree crossover. Write $p_1$ and $p_2$ for the parent encodings, $G$ for the known group that preserves the code's parameters, and $\operatorname{dist}$ for Hamming distance between encodings. Pairwise alignment applies crossover to $p_1$ and $g^\star p_2$, where

$$g^\star = \arg\min_{g \in G} \operatorname{dist}(p_1, g\,p_2).$$

The claim is that this alignment raises the fraction of offspring that keep their parents' minimum distance. It also shortens the time needed to reach best-known codes.

The groups involved are small enough to search exhaustively. For binary cyclic codes of length 255, the multipliers act on cosets with only 16 distinct effects. For double-circulant codes of length $2p$, the group of shifts and multipliers has about $p^2$ elements. Comparing $p^2$ bit-strings costs far less than one minimum-distance evaluation. This sidesteps the quadratic alignment overhead that the research file flags as a limitation of sequence-alignment crossovers.

The new element is the group itself. CSRX hard-codes rotations and reversals of a polygon. HG-means solves a Euclidean matching over cluster labels. The longest-common-subsequence operators of Sadeghiram et al. (Cluster-Guided Genetic Algorithm for Distributed Data-intensive Web Service Composition, A memetic algorithm with distance-guided crossover) protect shared blocks only when those blocks appear in the same linear order. None of these operators handles an arbitrary permutation group acting on a finite field. Cyclic and Negacyclic Codes with Optimal and Best Known Minimum Distances frames the open problem. It matched or beat 145 table entries with algebraic coset unions, but it notes that this approach becomes intractable for distances of 10 and above. It also notes that many table entries come from unguided searches that yield unstructured codes. Our operator searches only inside the space of cyclic and double-circulant codes, so every code it finds keeps that structure.

Research Program

The operator is generic. It takes a group, given by generators acting on the encoding, and it enumerates that group or a sampled subset of it. It returns $g^\star$ and passes the aligned pair to any base crossover: one-point, uniform, or the donor step of Gene-pool Optimal Mixing. The operator is first validated on traveling-salesperson tours with the rotation-and-reversal group. There it should reproduce the CSRX behavior, which shows that the generic version loses nothing compared with the hand-built one.

It is then applied to two code families. The first is binary cyclic codes of odd length, with lengths 63 to 255 for exact checks and up to 511 for record attempts. The encoding is a bit-vector over cyclotomic cosets. Fixing the code dimension $k$ means the selected cosets must cover exactly $n-k$ exponents. A repair step restores this after crossover by adding or removing cosets of matching size.

The second family is binary double-circulant codes of length $2p$, with the shift and multiplier group. The research file suggests the record tables contain many such searched codes but gives no figures; Cyclic and Negacyclic Codes with Optimal and Best Known Minimum Distances notes that many entries come from heuristic computer searches.

Fitness is a proxy during search: the number of codewords below a target weight, estimated by partial enumeration. The exact minimum distance is computed only for final candidates.

A second integration targets linkage learning. Methods such as Conditional Direct Empirical Linkage Discovery and Linkage Kernels in GOMEA measure which positions in the encoding vary together. If the population holds the same good code in many orientations, these statistics blur, which is Gap 1 in the research file. We align each donor to the receiver before the mixing step. We also align the population to a running reference before estimating linkage. We then measure whether the learned linkage groups sharpen, using the mutual information of the top linkage groups.

Shortest Edit Path Crossover is the methodological precedent for treating redundant encodings by alignment rather than by restricting the representation. It was developed for neural architecture graphs. We reuse its stance, not its graph matching.

Baselines

The naive reference is a standard genetic algorithm on the same encodings. It uses uniform and one-point crossover, bit-flip mutation, elitism and the same repair step, with no alignment.

The strongest existing method for this structured search is the algebraic route of Cyclic and Negacyclic Codes with Optimal and Best Known Minimum Distances. That paper reports 145 codes matching or exceeding best-known entries. It gives no per-instance search-time figures, and the research file contains no reported result for any evolutionary search over cyclotomic cosets. For double-circulant codes, we report the best minimum distances in the code tables as the target. The file does not list those values, so the targets will be read from codetables.de directly.

The strongest evolutionary competitor is linkage-learning GOMEA with linkage kernels (Solving Multi-Structured Problems by Introducing Linkage Kernels into GOMEA), run unaligned on the same encoding. A tabu-search hill climber over single-coset or single-bit flips is also included. All methods get the same budget of proxy-fitness evaluations. All get the same number of tuning trials, chosen by random search over their hyperparameters. All are run for 30 seeds per instance.

Two ablations isolate the key ingredient. The first applies a random group element instead of $g^\star$. If this matches the full method, any gain came from added diversity, not from alignment. The second, canonicalization, maps every individual to the lexicographically smallest member of its group orbit before crossover.

On tours, the reference number is from CSRX: on st70, after 1000 generations, CSRX reached 4.88% relative error against 21.19% for Best Order Crossover. The generic operator should land within seed noise of that figure.

On codes, aligned search beats the baselines if it does two things. It must reach the target minimum distance in strictly fewer evaluations than unaligned GOMEA and tabu search, at a significant median difference across seeds. It must also match the algebraically known optimal codes on lengths where they exist.

Why not just…?

Why not just canonicalize every individual instead of aligning pairs? This is the most serious threat. It is cheaper because the work is done once per individual, not once per pair. Its weakness is that the smallest orbit member is a discontinuous choice: two codes one bit apart can have canonical forms that are far apart, so canonicalization can still misalign near-identical parents. Pairwise alignment picks the orientation closest to the specific partner. On the small cyclic-code groups the two methods may tie. We expect the difference to show on double-circulant codes, where the group has about $p^2$ elements. The canonicalization ablation settles this directly. If it ties on both families, we will report canonicalization as the recommended method and drop the pairwise claim.

Why not just derive the codes algebraically? Algebraic recipes cover only certain parameter conditions. The Galois-ring construction of Quasi-cyclic perfect codes in Doob graphs needs $\Delta$ odd. The coset-union families of Cyclic and Negacyclic Codes stall at larger distances. Our search runs exactly where those recipes give no guarantee, and its outputs remain cyclic or double-circulant codes.

Why not just use linkage learning or a strong local search? Linkage learners estimate dependencies at fixed positions in the encoding, and redundant orientations wash those statistics out. HG-means found that alignment-based crossover lifted the Adjusted Rand Index, a measure of agreement with the true clustering, from 0.65 for repeated K-means to 0.99. Its local search alone kept falling into shallow optima. Code search may behave differently from clustering, so we run GOMEA and tabu search under equal budgets and also test GOMEA with alignment added. Aligned GOMEA beating plain GOMEA would directly confirm the linkage-blurring mechanism.

Proposed Experiments

The first experiment is a disruption measurement. For pairs of good parents, we record the distribution of the offspring's change in minimum distance under aligned, randomly moved, canonicalized and blind crossover. We use binary cyclic codes at lengths 63, 127 and 255, where exact distances are affordable. The prediction is that only aligned crossover moves the mean change toward zero.

The second experiment measures time to target. We take cyclic and double-circulant parameter sets with known best distances and record evaluations-to-target and success rate over 30 seeds against every baseline. The tour check on att48, eil51 and st70 confirms that the generic operator recovers CSRX.

The decisive check is the gap between pairwise alignment and canonicalization as the double-circulant group grows from $p=31$ to $p=127$. A widening gap supports the claim. No gap means the simpler method wins and the note's recommendation changes accordingly.

A stretch goal is record attempts at lengths 511 and above. The orbit-aware search for decoding sets left open in On McEliece-Type Cryptosystems Using Self-Dual Codes With Large Minimum Weight is noted as a follow-up and is not part of this study.