Constraint Handling

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

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.

In DEAP, a penality function can be added to any evaluation function using the DeltaPenality decorator provided in the tools module.

from math import sin
from deap import base
from deap import tools

def evalFct(individual):
    """Evaluation function for the individual."""
    x = individual[0]
    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[0] < 5:
        return True
    return False

def distance(individual):
    """A distance function to the feasability region."""
    return (individual[0] - 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.

Examples

References

[CoelloCoello2002]

Coelle Coello, C. A. Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Computer Methods in Applied Mechanics and Engineering 191, 1245–1287, 2002.