Constraint handling

Author:: Antonio J. Nebro
Version:: 1.1
Date:: 2022-3-28

Constraint handling in jMetal involves solutions, problems, and comparators. Currently, two constraint handling mechanisms are provided:

Number of violated constraints
Overall constraint violation degree, which is based on the scheme used in NSGA-II (described in [DPA02]).

If we take a look to the Solution interface:

package org.uma.jmetal.solution;

public interface Solution<T> extends Serializable {
  List<T> variables() ;
  double[] objectives() ;
  double[] constraints() ;
  Map<Object,Object> attributes() ;

  Solution<T> copy() ;
}

the method constraints() returns an array of double values, where each element represents some kind of potential violation degree. These values are usually assigned when a solution is evaluated by a constrained problem; if the problem has no constraints, that method will return an empty array.

An example of constrained problem is Srinivas, defined in [DPA02]:

public class Srinivas extends AbstractDoubleProblem {

  /** Constructor */
  public Srinivas()  {
    int numberOfVariables = 2 ;
    numberOfObjectives(2);
    numberOfConstraints(2);
    name("Srinivas");

    List<Double> lowerLimit = new ArrayList<>(numberOfVariables);
    List<Double> upperLimit = new ArrayList<>(numberOfVariables);

    for (int i = 0; i < numberOfVariables; i++) {
      lowerLimit.add(-20.0);
      upperLimit.add(20.0);
    }

    variableBounds(lowerLimit, upperLimit);
  }

  /** Evaluate() method */
  @Override
  public void evaluate(DoubleSolution solution)  {
    double[] f = new double[solution.getNumberOfVariables()];

    double x1 = solution.getVariable(0);
    double x2 = solution.getVariable(1);
    f[0] = 2.0 + (x1 - 2.0) * (x1 - 2.0) + (x2 - 1.0) * (x2 - 1.0);
    f[1] = 9.0 * x1 - (x2 - 1.0) * (x2 - 1.0);

    solution.setObjective(0, f[0]);
    solution.setObjective(1, f[1]);

    evaluateConstraints(solution);
  }

  /** EvaluateConstraints() method  */
  public void evaluateConstraints(DoubleSolution solution)  {
    double[] constraint = new double[this.getNumberOfConstraints()];

    double x1 = solution.getVariable(0) ;
    double x2 = solution.getVariable(1) ;

    constraint[0] = 1.0 - (x1 * x1 + x2 * x2) / 225.0;
    constraint[1] = (3.0 * x2 - x1) / 10.0 - 1.0;

    IntStream.range(0, getNumberOfConstraints())
        .forEach(i -> solution.constraints()[i] = constraint[i]);
    }
  }
}

We can observe that the problem formulation includes two constraints, which are defined in the evaluateConstraints() method that is called after a solution is evaluated. According to the NSGA-II constraint handling scheme, the requirement to work with constraints is that every constraint must be expressed as an inequality of type expression >=0.0. This way, when expression < 0.0 then it is considered as a constraint violation, and the overall constraint violation degree will the sum of the values of the constraints array. If that value is negative, then the solution is infeasible.

To facilitate the use of constraints, jMetal provides the utility ConstraintHandling class, which provides the following static methods:

isFeasible(Solution solution): returns true if the solution has no constraints or the number of violated constraints is zero.
numberOfViolatedConstraints(Solution solution): returns the number of violated constraints.
overallConstraintViolationDegree(Solution solution): returns the overall constraint violation degree of a solution.
feasibilityRatio(List<Solution> solutions): computes the ratio of feasible solutions in a solution list.
numberOfViolatedConstraints(Solution solution, int number): sets the number of violated constraints of a solution.
overallConstraintViolationDegree(Solution solution, double value): sets the overall constraint violation degree of a solution.

The last two methods are included to allow the adoption of adhoc mechanisms to compute both the number of violated constraints and the overall constraint violation degree. To cope with this possibility, the ConstraintHandling class includes the following enum type:

public enum PRECOMPUTED {
  OVERALL_CONSTRAINT_VIOLATION,
  NUMBER_OF_VIOLATED_CONSTRAINTS
}

It is assumed that a solution may have an attribute whose key value is OVERALL_CONSTRAINT_VIOLATION or NUMBER_OF_VIOLATED_CONSTRAINTS. If so, the associated values are returned when querying the constraint properties of the solution; otherwise, the constraints are computed using the default scheme. This is illustrated in the numberOfViolatedConstraints(Solution solution) and overallConstraintViolationDegree(Solution solution) methods:

public static <S extends Solution<?>> int numberOfViolatedConstraints(S solution) {
  return (int) solution.attributes().getOrDefault(
      PRECOMPUTED.NUMBER_OF_VIOLATED_CONSTRAINTS,
      (int) IntStream.range(0, solution.constraints().length)
          .filter(i -> solution.constraints()[i] < 0)
          .count());
}

public static <S extends Solution<?>> double overallConstraintViolationDegree(S solution) {
  double overallConstraintViolation =
      (double) solution.attributes().getOrDefault(
          PRECOMPUTED.OVERALL_CONSTRAINT_VIOLATION,
          0.0);
  if (overallConstraintViolation == 0.0) {
    overallConstraintViolation = IntStream.range(0, solution.constraints().length)
        .filter(i -> solution.constraints()[i] < 0.0).mapToDouble(i -> solution.constraints()[i])
        .sum();
  }
  return overallConstraintViolation;
}

Given two, solutions, the OverallConstraintViolationComparator and NumberOfViolatedConstraintsComparator classes can be used to compare then according the constraints. The implementation of the OverallConstraintViolationComparator class is included next:

public class OverallConstraintViolationComparator<S extends Solution<?>>
  implements ConstraintViolationComparator<S> {
  /**
   * Compares two solutions. If the solutions has no constraints the method return 0
   *
   * @param solution1 Object representing the first <code>Solution</code>.
   * @param solution2 Object representing the second <code>Solution</code>.
   * @return -1, or 0, or 1 if o1 is less than, equal, or greater than o2,
   * respectively.
   */
  public int compare(S solution1, S solution2) {
    double violationDegreeSolution1 ;
    double violationDegreeSolution2;

    violationDegreeSolution1 = ConstraintHandling.overallConstraintViolationDegree(solution1);
    violationDegreeSolution2 = ConstraintHandling.overallConstraintViolationDegree(solution2);

    if ((violationDegreeSolution1 < 0) && (violationDegreeSolution2 < 0)) {
      if (violationDegreeSolution1 > violationDegreeSolution2) {
        return -1;
      } else if (violationDegreeSolution2 > violationDegreeSolution1) {
        return 1;
      } else {
        return 0;
      }
    } else if ((violationDegreeSolution1 == 0) && (violationDegreeSolution2 < 0)) {
      return -1;
    } else if ((violationDegreeSolution1 < 0) && (violationDegreeSolution2 == 0)) {
      return 1;
    } else {
      return 0;
    }
  }
}

Note that the violation degree of solution is a negative number.