mutation-and-perturbation-operators

Mutation and Perturbation Operators

You are an expert in variation-operator design for combinatorial and continuous metaheuristics. This skill is the reference catalog for unary operators: mutation inside evolutionary algorithms, kick moves inside iterated local search, proposal moves inside simulated annealing, and destroy-style perturbations inside ruin-and-recreate loops. Use the framework below to pick the operator that matches the encoding and the problem structure, implement it correctly in vectorized numpy, calibrate its strength, and adapt that strength during the run.

Initial Assessment

Establish these points before recommending or writing any operator:

• Encoding. Binary string, integer vector, real vector, permutation, or a structured object (routes, schedules)? The encoding fixes the admissible operator family. If the encoding itself is still open, settle it first (see solution-encodings).
• Role of the operator. Three distinct roles use the same mechanics with different strengths:
  • Variation in a population method (GA/ES): small, applied to every offspring, rate-controlled.
  • Kick in a trajectory method (ILS): medium, applied once per local-search round, must escape the local-search neighborhood.
  • Proposal in an acceptance-based method (SA): small, applied every iteration, evaluated via delta.
• What structure the objective rewards. Adjacency (TSP edges), absolute position (QAP assignments), relative order (scheduling precedence), or subset membership (knapsack)? Pick the operator that perturbs the rewarded structure least per unit of randomization, unless the explicit goal is diversification.
• Feasibility. Does the operator preserve constraints (permutation operators preserve permutation feasibility) or can it produce infeasible offspring (bit-flip under a capacity constraint)? If infeasible, decide repair vs penalty before coding.
• Evaluation cost. If the objective supports O(1) or O(n) delta evaluation for a move, the same move doubles as a local-search neighborhood; design the operator so the delta formula applies.
• Strength budget. What disruption level is wanted: expected Hamming distance, number of tour edges changed, sigma as a fraction of variable range? Every operator must expose exactly one strength knob.
• Adaptation requirements. Fixed strength, deterministic schedule, feedback-driven adaptation, or self-adaptation encoded in the genome? Match the choice to run length and tuning budget.
• Population vs single solution. Population methods justify fully vectorized operators over an (m, n) array; trajectory methods need fast single-solution variants.
• Reproducibility. One np.random.default_rng(seed) per run, passed into every operator; never module-level np.random.* calls.
• Time budget for tuning. A fixed rate of 1/n is the right default when there is no budget; adaptive schemes pay off on long runs and unknown instances.