Evolutionary algorithms are usually unconstrained optimization procedures. In this tutorial, we present several ways of adding different types of constraint to your evolutions. This tutorial is based on the paper by Coello Coello [CoelloCoello2002].
Penality function are the most basic way of handling constrains for individuals that cannot be evaluated or are forbiden for problem specific reasons, when falling in a given region. The penality function gives a fitness disavantage to theses individuals based on the amount of constraint violation in the solution. For example, instead of evaluating an individual violating a constraint one can assings 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 penality 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 use a constant offset when a constraint is not respected. The center plot use the euclidean distance in addition to the offset to create a bowl like fitness function . Finally, the left plot use a quadratic distance funtion 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): """Feasability function for the individual. Returns True if feasible False otherwise.""" if 3 < individual < 5: return True return False def distance(individual): """A distance function to the feasability region.""" return (individual - 5.0)**2 toolbox = base.Toolbox() toolbox.register("evaluate", evalFct) toolbox.decorate("evaluate", tools.DeltaPenality(feasible, 7.0, distance))
The penality 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.