Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 36 ยท Constraints and Multi-objective

Repair Operators and Decoders

Keep every individual feasible by construction. Learn repair functions, random-key decoders and greedy decoders with runnable knapsack and scheduling examples.

Penalty functions let infeasible individuals live and punish them. There is a second school of thought: never let a broken solution reach the fitness function. Either you repair an infeasible individual after crossover or mutation, or you design the chromosome so that every chromosome decodes into a valid solution. The second idea is called a decoder.

Both techniques move knowledge about the problem from the fitness function into the encoding. They remove tuning parameters such as R, and they often make the GA dramatically faster, but they also bias the search, so you need to understand what you are trading.

Repair: fix it after it breaks

A repair operator takes an infeasible chromosome and changes it, minimally, until it is feasible. Take the 0/1 knapsack: a bit string says which items go in the bag, and the total weight must not exceed the capacity. After crossover the bag may be too heavy. A simple repair removes items until the weight fits.

Which items should be removed? Three common choices:

  • Random: remove a random packed item. Unbiased but wasteful.
  • Worst ratio first: remove the packed item with the lowest value-to-weight ratio. Greedy and effective.
  • Then fill up: after removing, try to add the best unpacked items that still fit. This keeps the bag full.

Repair has a choice: write the repaired chromosome back into the population (Lamarckian) or use it only to compute fitness (Baldwinian). Writing back converges faster but can reduce diversity.

Python Knapsack GA with a greedy repair operator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Decoders: make every chromosome valid

A decoder is a function from a chromosome (the genotype) to a solution (the phenotype). If the decoder always outputs a valid solution, the GA can use ordinary crossover and mutation and never wonders about feasibility.

Random keys for permutations

Permutation problems (tour order, job order) break ordinary crossover: swapping halves of two permutations makes duplicates. The random-key encoding fixes this. Each gene is a real number in [0, 1). To decode, sort the genes and read off the indices:

TEXT
genes   = [0.62, 0.05, 0.91, 0.33]
argsort = [1, 3, 0, 2]      # this is the permutation

Any real vector is a valid permutation, so you can use blend crossover and Gaussian mutation, the standard real-valued operators.

Greedy decoders for scheduling

A greedy decoder takes a priority list from the chromosome and builds a schedule step by step, always assigning the next job to the earliest free machine. The chromosome never says when things happen; the decoder works that out, and constraints such as "one machine, one job at a time" hold automatically.

Python Random keys plus a greedy scheduling decoder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every random vector decodes to a schedule where no machine runs two jobs at once. There was no penalty and no repair, yet the GA is always inside the rules.

Which technique should you use?

Technique Strengths Weaknesses
Penalty Easy; needs no problem knowledge Needs tuning; wastes evaluations on infeasible points
Repair Always feasible; fast Biases the search; repair code can be slow
Decoder Elegant; reuses standard operators Many genotypes map to one solution (redundancy); can hide good regions
Reject (throw away) Trivial Fails when feasible space is tiny

A good habit: start with a penalty to get a baseline, then add a repair or decoder if feasibility is the bottleneck.

Common mistakes

  • Repair that always makes the same fix. If every repaired knapsack drops the same item, diversity dies. Add some randomness.
  • Decoders with huge redundancy. If a million genotypes decode to one solution, mutation often changes nothing.
  • Forgetting to re-evaluate. If you repair after fitness was computed, the fitness belongs to a different solution than the one you store.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a decoder in a genetic algorithm?

    The decoder turns the genotype into the phenotype; a good decoder always outputs a feasible solution.
  2. 2. With random keys, how do you turn the genes [0.9, 0.1, 0.5] into a permutation?

    argsort of the keys gives the order. Index 1 has the smallest key, then 2, then 0.
  3. 3. What is the difference between Lamarckian and Baldwinian repair?

    Writing back changes the stored genes; Baldwinian leaves them alone and only borrows the repaired fitness.
  4. 4. Which is a typical weakness of repair operators?

    If the repair always does the same fix, many individuals end up looking alike.

Summary

  • Repair fixes an infeasible individual after variation; a decoder prevents infeasibility by construction.
  • Greedy repair (drop the worst ratio, then fill up) works very well for knapsack-like problems.
  • Random keys let you use real-valued operators for permutation problems.
  • Greedy decoders turn priority lists into valid schedules.
  • Balance feasibility against bias and diversity, and compare against a penalty baseline.

Next: Multi-objective Optimization and Pareto Dominance