Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 36 ยท Constraints and Multi-objective

Handling Constraints with Penalty Functions

Learn how to keep a genetic algorithm inside the rules. Build static, dynamic and adaptive penalty functions and see how penalty strength changes the search.

Real problems come with rules. A backpack has a weight limit, a schedule cannot put one nurse in two wards at once, and a bridge design must carry a minimum load. A genetic algorithm (GA) knows nothing about those rules: it only sees a fitness number. If you let it, it will happily evolve a "perfect" solution that breaks every rule.

The simplest way to teach the GA about rules is to punish violations. You turn a constrained problem into an unconstrained one by subtracting a penalty from the fitness of every individual that breaks a constraint. This lesson shows how to design that penalty and why its strength matters so much.

Constrained problems in one formula

A constrained maximization problem looks like this:

  • maximize f(x)
  • subject to g_i(x) <= 0 for inequality constraints
  • and h_j(x) = 0 for equality constraints

A solution that satisfies all constraints is feasible. Everything else is infeasible. For each constraint we can measure the violation: max(0, g_i(x)) for an inequality, and abs(h_j(x)) for an equality (usually with a small tolerance such as 1e-4, because exact equality is almost impossible with real numbers).

A violation is 0 when the constraint holds and grows as the solution gets further from feasibility. A good penalty uses the size of the violation, not just a yes/no flag.

The basic penalty

The penalized fitness is:

TEXT
penalized(x) = f(x) - penalty(x)
penalty(x)   = R * sum(violation_i(x) ** 2)

R is the penalty coefficient. Squaring the violation makes small violations cheap and large ones expensive, and it keeps the function smooth near the boundary. Now look at what happens when R is chosen badly:

  • R too small: the best penalized solution is infeasible, because breaking the rule pays more than it costs.
  • R too large: every infeasible individual looks terrible, the population collapses onto whatever feasible solution it first finds, and the search cannot walk along the boundary where the optimum often lives.

The optimum of a constrained problem very often sits on the boundary (a full backpack, a fully used budget). So a good penalty lets the GA approach the boundary from both sides.

flowchart LR
    A["Candidate x"] --> B["Compute f(x)"]
    A --> C["Measure violations"]
    C --> D["penalty = R * sum(v^2)"]
    B --> E["fitness = f(x) - penalty"]
    D --> E
    E --> F["Selection uses fitness"]

The GA never sees the constraints: only the combined fitness.

Example: a constrained function

We will maximize f(x, y) = x + y on the disk x^2 + y^2 <= 1. The true answer is x = y = 1/sqrt(2), with f = sqrt(2) = 1.4142. The GA below uses real-valued genes in [-2, 2]. Change R and watch whether the final answer is feasible.

Python Penalty strength on a circle constraint

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.

With a small R the answer typically lands outside the disk (positive violation and an f larger than 1.4142). With a very large R the answer is feasible but may sit a little inside the boundary. Somewhere in between is the sweet spot.

Static, dynamic and adaptive penalties

You have three families to choose from.

Static penalty

R is a constant for the whole run, as above. It is simple and predictable, but you must tune it for every problem.

Dynamic penalty

R grows with the generation number t. Early on, the GA explores freely, including infeasible regions that may connect good feasible areas. Later, it is forced inwards:

TEXT
R(t) = (C * t) ** alpha        # for example C = 0.3, alpha = 2

Adaptive penalty

R reacts to what the population is doing. A common rule: look at the best individual of each of the last k generations. If they were all feasible, the penalty is too strong, so decrease R. If they were all infeasible, increase it. If mixed, leave it. The population ends up hovering around the boundary, exactly where you want it.

Python Compare static, dynamic and adaptive penalties

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.

Equality constraints and tolerance

Suppose a constraint says x + y = 1. The chance that a random real pair satisfies it exactly is zero. Two standard fixes:

  1. Treat abs(h(x)) <= epsilon as satisfied (for example epsilon = 1e-4), and penalize only the excess.
  2. Remove the constraint by substitution: evolve only x and compute y = 1 - x. This is a form of repair, covered in Repair and Decoders.

Normalize before you add

If one constraint is measured in kilograms and another in dollars, a single R is unfair to one of them. Divide each violation by a typical scale (the constraint's limit, or the largest violation seen in the current population) before summing. This one step removes a lot of tuning pain.

Common mistakes

  • Penalizing with a flat constant. Every infeasible individual gets the same bad score, so the GA gets no hint of which one is closer to feasible.
  • Letting infeasible beat feasible. Check that the penalty is large enough that no infeasible point has a better fitness than a good feasible one in the final population.
  • Forgetting to report feasibility. Always print the violation next to the fitness. A beautiful fitness with violation > 0 is a failed run.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a penalty function do in a genetic algorithm?

    A penalty is subtracted from fitness, so infeasible individuals are less likely to be selected, without being deleted.
  2. 2. What usually goes wrong when the penalty coefficient R is far too small?

    If breaking a rule costs less than it earns, the best-scoring individual will break the rule.
  3. 3. Why does an adaptive penalty decrease R when the recent best individuals were all feasible?

    Optima often lie on the constraint boundary; a too-strong penalty keeps the search from approaching it.
  4. 4. How are equality constraints usually handled in a penalty approach?

    Real numbers rarely satisfy equality exactly, so a small tolerance is used.

Summary

  • A penalty turns a constrained problem into an unconstrained one: fitness = f - R * violation^2.
  • Measure violation by size, not by yes/no, so the GA can tell what is closer to feasible.
  • Too small an R yields infeasible answers; too large an R blocks movement along the boundary.
  • Static, dynamic (growing) and adaptive (feedback) penalties trade simplicity for robustness.
  • Normalize violations and use a tolerance for equalities. Always report feasibility.

Next: Repair and Decoders