Standard genetic algorithms (GAs) are designed for independent, bit-string representations where each position on a chromosome represents an isolated trait. In these traditional domains, a standard one-point or two-point crossover operator cuts two parent chromosomes at a random boundary and swaps the segments. If the traits are relatively independent, this successfully recombines good building blocks.
However, many real-world problems require optimizing sequences or permutations. Examples include the Traveling Salesman Problem (TSP), job shop scheduling, and task mapping in parallel computing. In these domains, a chromosome is an ordered list of unique elements. If you apply a standard crossover operator to two valid permutations—say, [1, 2, 3, 4, 5] and [5, 4, 3, 2, 1]—and cut them in the middle, the resulting offspring might be [1, 2, 3, 2, 1]. This offspring is completely invalid: elements 2 and 1 are duplicated, while 4 and 5 are missing entirely.
As Wang et al. note, generic genetic operators frequently generate invalid sequences that violate mandatory constraints, leading to a severe loss of solution diversity or requiring computationally expensive post-hoc repair steps. To make evolutionary computation viable for combinatorial sequences, we need operators that are structurally closed within the space of valid permutations and valid precedence graphs.
Preserving Permutations and Eliminating Positional Bias
The first layer of sequence preservation ensures that every element appears exactly once. When optimizing permutations, the absolute position of an item is often less important than its relative ordering or its adjacency to other items.
To prevent standard crossover from breaking permutations, researchers developed specialized operators like Partially Matched Crossover (PMX) and uniform order crossover. For instance, Wang utilizes partially matched crossover to maintain valid permutations when optimizing discrete mining sequences, ensuring that no step is duplicated or omitted. Similarly, Gagné et al. and Gagné et al. employ uniform partially matched crossover and swap mutations to optimize the permutations used in low-discrepancy sequences, allowing the algorithm to explore digit scramblings without violating structural constraints.
Another challenge is "defining length bias"—the phenomenon where elements that happen to be physically close together on the chromosome are less likely to be separated by crossover than elements far apart. To eliminate this artificial bias, Caruana et al. introduced Shuffle Crossover. This technique shuffles the positions of elements randomly before applying a standard recombination operator, and then reverses the shuffle afterward. By decoupling the physical representation from the genetic operator, the probability of separating any two elements becomes entirely independent of their original distance on the chromosome.
In routing and logistics, maintaining valid paths is equally vital. Armstrong-Crews et al. designed a specialized crossover operator for helicopter routing that synchronizes the order of elements between two parents. By copying a specific sequence from one parent and reordering the second parent's elements to match, the operator avoids redundant visits while preserving inherited path segments. In a similar vein, Wen et al. utilize an exchange heuristic crossover operator to combine parent sequences for material handling systems, allowing the algorithm to inherit and recombine efficient sub-sequences from high-performing candidates without generating invalid permutations.
Preserving Precedence in Epistatic Domains
In many advanced scheduling and structural learning problems, the challenge goes beyond maintaining a simple permutation; the sequence must also obey strict chronological or causal dependencies. This is known as epistasis, where the validity or fitness of one parameter depends heavily on others. As Davis early on recognized, specialized mutation and crossover operators are required to manipulate ordered lists while maintaining the relative sequence of elements, allowing the evolutionary process to explore the permutation space without violating structural constraints.
Consider the problem of scheduling tasks on heterogeneous or multicore computing environments. Tasks often form a Directed Acyclic Graph (DAG), where certain tasks must finish before others can begin. Wang et al. addressed this by employing specialized crossover and mutation operators that modify execution sequences while ensuring the resulting scheduling string remains a valid topological sort of the task dependency graph.
To achieve this without expensive repair steps, researchers use precedence-preserving crossover (PPX). As demonstrated by Wang et al. and Wang et al. in the context of flexible job shop scheduling, a precedence-preserving crossover operator selects operations one by one from the parents while strictly maintaining their relative order. This ensures that offspring remain feasible according to task dependency constraints throughout the entire evolutionary cycle.
When dependencies are highly restrictive, mutations must also be constrained. Meng et al. designed mutation operators constrained by the dependencies of the underlying DAG. By restricting a task's movement strictly to the interval between its immediate predecessors and successors, the algorithm guarantees that every generated offspring represents a valid execution sequence.
This principle of structural closure extends to other domains as well:
- Bayesian Network Structure Learning: Lee et al. developed a Dual Genetic Algorithm that evolves variable ordering and connectivity simultaneously. Their genetic operators are designed to be closed within the space of valid DAGs, ensuring that every crossover or mutation produces a valid acyclic model.
- Multiple Sequence Alignment: In biological sequence alignment, Taheri introduced specialized evolutionary operators that dynamically shift coordinates to correct chronological sequence violations, ensuring that candidate solutions always represent feasible alignments.
Mutation in Sequence Space: Shifts vs. Swaps
Just as standard crossover fails on sequences, standard mutation operators like random swaps can be highly destructive. If a sequence depends on relative ordering (e.g., job $A$ must precede job $B$, which must precede job $C$), swapping two distant elements can inadvertently destroy the beneficial relative ordering of many intervening elements. As Ishibuchi et al. point out, simple mutation operators in permutation-based problems can disrupt high-performing schedule segments, hindering the search process.
To solve this, Ishibuchi et al. and Ishibuchi et al. advocate for positional shift mutation over simple swaps. Instead of swapping two elements, a positional shift mutation relocates a single element to a new position and shifts the intervening elements to accommodate the move.
Original Sequence: [ A , B , C , D , E ]
Swap (B and E): [ A , E , C , D , B ] <-- Breaks relative order of (B,C) and (B,D)
Shift (B to end): [ A , C , D , E , B ] <-- Preserves relative order of (C,D,E)
By shifting rather than swapping, the relative ordering of the majority of elements is preserved. This strategy maintains the structural integrity of high-quality sub-sequences while introducing the necessary variation to escape local optima, making it a cornerstone of successful sequence-based evolutionary optimization.
Key Foundational Work
Applying Adaptive Algorithms to Epistatic Domains (1985) — contributed 1 concept elements to this direction.
Representation and Hidden Bias II: Eliminating Defining Length Bias in Genetic Search via Shuffle Crossover (1989) — contributed 1 concept elements to this direction.