Evolutionary algorithms are usually unconstrained optimization procedures. In this tutorial, we present several ways of adding different types of constraints to your evolutions. This tutorial is based on the paper by Coello Coello [CoelloCoello2002].
Penalty functions are the most basic way of handling constrains for individuals that cannot be evaluated or are forbidden for problem specific reasons, when falling in a given region. The penalty function gives a fitness disadvantage to these individuals based on the amount of constraint violation in the solution. For example, instead of evaluating an individual violating a constraint, one can assign a desired value to its fitness. The assigned value can be constant or increasing (decreasing for maximization) as the distance to a valid solution increases. The following figure shows the fitness function (in green) and the penalty function (in red) of a one attribute individual, subject to the constraint . The continuous line represent the fitness that is actually assigned to the individual .
The figure on the left uses a constant offset when a constraint is not respected. The center plot uses the euclidean distance in addition to the offset to create a bowl like fitness function . Finally, the right plot uses a quadratic distance function to increase the attraction of the bowl , where is the approximate center of the valid zone.
from math import sin from deap import base from deap import tools def evalFct(individual): """Evaluation function for the individual.""" x = individual return (x - 5)**2 * sin(x) * (x/3), def feasible(individual): """Feasibility function for the individual. Returns True if feasible False otherwise.""" if 3 < individual < 7: return True return False def distance(individual): """A distance function to the feasibility region.""" return (individual - 5.0)**2 toolbox = base.Toolbox() toolbox.register("evaluate", evalFct) toolbox.decorate("evaluate", tools.DeltaPenalty(feasible, 7.0, distance))
The penalty decorator takes 2 mandatory arguments and an optional one. The first argument is a function returning the validity of an individual according to user defined constraints. The second argument is a constant value () returned when an individual is not valid. The optional argument is a distance function between an invalid individual and the valid region. This last argument takes on the default value of 0. The last example shows how the right plot of the top image was obtained.