Introducing Penalty Functions

What are penalty functions?

We need a way to account for solutions that aren’t considered valid, meaning they don’t meet the constraints defined by the problem. For example, in the cargo problem, you need a way to penalize solutions that exceed the weight limit, so your algorithm doesn’t produce an invalid solution.

A penalty function is a function applied to constraint satisfaction problems for the purpose of reducing them into an unconstrained problem. Rather than putting constraints on possible solutions, penalty functions incur a cost on solutions that violate a constraint of the original problem. In layman’s terms, that means to take points away from solutions that aren’t valid, so they don’t get considered better than solutions that are valid.

To better understand penalty functions, consider this: the speed limit changes depending on each road. Law enforcement would love it if cars automatically detected the speed limit of a certain road and only allowed driving at or below that speed. Of course, implementing this would be impossible because there are too many roads, and speed limits change rapidly among them. Rather than putting constraints on cars, the law introduces a “penalty” for driving over the speed limit. The penalty is a speeding ticket. The cost of speeding outweighs the cost of driving within the speed limit. In this way, the law eliminates the need for explicit constraints and instead punishes drivers who don’t obey the rules.