Deb's Polynomial Mutation, Explained Properly
Every GA library ships several mutation operators and the documentation usually stops at listing them. ParGA has four: polynomial, gaussian, uniform and boundary. Polynomial is the default in most of the field, it is the least obvious of the four, and the reason it wins is worth understanding.
The operator
Deb’s polynomial mutation takes a gene x in [lo, hi] and perturbs it by an amount drawn so that small moves are much more likely than large ones, with the distribution shaped by a parameter eta.
Start with the two normalized distances from the gene to each of its bounds:
delta1 = (x - lo) / (hi - lo) how far up from the lower bound
delta2 = (hi - x) / (hi - lo) how far down from the upper bound
Draw u uniformly on [0, 1]. If u < 0.5 the gene moves down, otherwise it moves up, and the size of the step is computed from the distance to the bound it is moving toward:
u < 0.5: delta = [2u + (1 - 2u)(1 - delta1)^(eta+1)]^(1/(eta+1)) - 1
u >= 0.5: delta = 1 - [2(1-u) + (2u - 1)(1 - delta2)^(eta+1)]^(1/(eta+1))
and the new gene is x + delta * (hi - lo).
The important structural detail is that the downward branch uses delta1 and the upward branch uses delta2. Each branch is scaled by how much room the gene has in the direction it is actually going. That is what gives the operator its two defining properties:
It cannot leave the bounds. Not by clamping afterwards, which would pile probability mass onto the boundary itself, but by construction: the step is derived from the remaining distance, so it shrinks to nothing as the gene approaches a bound.
It is unbiased in the middle. At x exactly halfway between the bounds, delta1 = delta2, the two branches are mirror images, and up and down are equally likely and equally sized.
Both properties break if a branch uses the wrong distance, and the failure is quiet: the operator still produces valid genes in range, it just drifts. Which is why the two tests worth writing are statistical rather than exact.
The two tests worth writing
For any stochastic operator, these are cheap and they catch the things that matter:
Unbiased at the midpoint. Mutate a mid-range gene many times and check that roughly half the results land on each side. Sampling ParGA’s operator on [0, 1]:
3,600 samples: mean 0.5000, 50.7% below the midpoint, 49.3% above
bounds respected: True, min 0.0000, max 1.0000
Moves off a boundary. Put a gene exactly on a bound and confirm it can leave over N samples. A gene at lo has delta1 = 0, which is the case where an off-by-one in the branch gives you a step of exactly zero forever, and a population that welds itself to the edge of the search space.
Neither test needs an exact expected value, which is the point. Comparing floats out of a stochastic operator is a losing game; comparing a proportion over a few thousand samples is not.
What choosing it is worth
The operator determines what precision you can reach, and where. Eight dimensions, optimum at every gene equal to a target, median squared error over 24 seeds:
| mutation | optimum at 0.5 (interior) | at 0.02 (near a bound) | at 0.0 (on the bound) |
|---|---|---|---|
| polynomial | 3.83e-07 | 2.00e-07 | 9.71e-17 |
| gaussian | 1.94e-06 | 2.29e-06 | 0.00 |
| uniform | 2.72e-05 | 3.35e-05 | 7.84e-05 |
| boundary | 0.0156 | 0.0025 | 0.00 |
Three things fall out of that table.
Polynomial is the best general-purpose choice, about five times more precise than gaussian in the interior and an order of magnitude better than uniform. It is the default for a reason.
Boundary optima are the easy case, not the hard one. That surprised me. Every operator except uniform nails an optimum sitting exactly on a bound, several to machine precision, because bound-clamping pushes a gene onto the answer for free. The hard case is an optimum near a bound but not on it, where clamping overshoots and the operator has to actually resolve the position.
Uniform is the only operator that is worse on the bound than in the interior, and the reason says what it is: uniform mutation replaces a gene with a fresh uniform draw, so its step size never shrinks. It cannot fine-tune anywhere, which makes it a diversity tool rather than a convergence one.
Boundary mutation is a specialist, exactly as named. Perfect on bounds, four orders of magnitude worse than polynomial in the interior. Use it when you know the answer is on an edge, which is a real situation in constrained design problems and nowhere else.
Choosing
Polynomial unless you have a reason. Gaussian if your problem is genuinely unbounded, where polynomial’s bound-derived step size has nothing to work with. Uniform as a diversity injection alongside something else, not as your only mutation. Boundary when the optimum is on a constraint and you know it.
from parga import minimize, MutationMethod
result = minimize(f, genome_length=10, bounds=(0.0, 1.0),
mutation_method=MutationMethod.polynomial())
pip install parga.
Stay in the loop
Get notified when I publish new posts. No spam, unsubscribe anytime.