Defining new problems

To include a problem in jMetalPy, it must implement the Problem interface from the jmetal.core.problem module.

Use case: Subset Sum

The goal is to find a subset S of W (list of non-negative integers) whose elements sum is closest to (without exceeding) C. For example, for the input \(W=\{3, 34, 4, 12, 5, 2\}\) and \(C=9\), one output could be \(S=\{4, 5\}\) (as it is a subset with sum 9).

In jMetalPy, this problem can be encoded as a binary problem with one objective (to be maximized) and one variable (a binary array representing whethever the ith element of W is selected or not):

class SubsetSum(BinaryProblem):

   def __init__(self, C: int, W: list):
      super(SubsetSum, self).__init__(reference_front=None)
      self.C = C
      self.W = W

      self.number_of_bits = len(self.W)
      self.number_of_objectives = 1
      self.number_of_variables = 1
      self.number_of_constraints = 0

      self.obj_directions = [self.MAXIMIZE]
      self.obj_labels = ['Sum']

   def evaluate(self, solution: BinarySolution) -> BinarySolution:
      pass

   def create_solution(self) -> BinarySolution:
      pass

   def get_name(self) -> str:
      return 'Subset Sum'

Now we have to define the abstract methods evaluate and create_solution from the jmetal.core.problem.Problem class.

Note that each solution consists of one objective function to be maximized to be as close as possible to \(C\):

\[\max{\sum_{i \in S}{s_i}}\]

Taking this into account, one solution could be created and evaluated as follows:

Note

jMetalPy assumes minimization by default. Therefore, we will have to multiply the solution objective by \(-1.0\).

def evaluate(self, solution: BinarySolution) -> BinarySolution:
    total_sum = 0.0

    for index, bits in enumerate(solution.variables[0]):
        if bits:
            total_sum += self.W[index]

    if total_sum > self.C:
        total_sum = self.C - total_sum * 0.1

        if total_sum < 0.0:
            total_sum = 0.0

    solution.objectives[0] = -1.0 * total_sum

    return solution

def create_solution(self) -> BinarySolution:
    new_solution = BinarySolution(number_of_variables=self.number_of_variables,
                                  number_of_objectives=self.number_of_objectives)
    new_solution.variables[0] = \
        [True if random.randint(0, 1) == 0 else False for _ in range(self.number_of_bits)]

    return new_solution

Use case: Multi-objective Subset Sum

The former problem can be formulated as a multi-objective binary problem whose objectives are as follows:

1. Maximize the sum of subsets to be as close as possible to \(C\) and

2. Minimize the number of elements selected from \(W\).

This can be done by incorporating the objective function and increasing the number of objectives in consecuence:

class SubsetSum(BinaryProblem):

   def __init__(self, C: int, W: list):
      super(SubsetSum, self).__init__(reference_front=None)
      self.C = C
      self.W = W

      self.number_of_bits = len(self.W)
+     self.number_of_objectives = 2
      self.number_of_variables = 1
      self.number_of_constraints = 0

+     self.obj_directions = [self.MAXIMIZE, self.MINIMIZE]
+     self.obj_labels = ['Sum', 'No. of Objects']

   def evaluate(self, solution: BinarySolution) -> BinarySolution:
      total_sum = 0.0
+     number_of_objects = 0

+     for index, bits in enumerate(solution.variables[0]):
+        if bits:
+           total_sum += self.W[index]
+              number_of_objects += 1

      if total_sum > self.C:
         total_sum = self.C - total_sum * 0.1

         if total_sum < 0.0:
             total_sum = 0.0

      solution.objectives[0] = -1.0 * total_sum
+     solution.objectives[1] = number_of_objects

      return solution

API

class jmetal.core.problem.BinaryProblem

Bases: Problem[BinarySolution], ABC

Class representing binary problems.

number_of_bits_per_variable_list()

total_number_of_bits()

class jmetal.core.problem.DynamicProblem

Bases: Problem[S], Observer, ABC

abstract clear_changed() → None

abstract the_problem_has_changed() → bool

class jmetal.core.problem.FloatProblem

Bases: Problem[FloatSolution], ABC

Class representing float problems.

create_solution() → FloatSolution

Creates a random_search solution to the problem.

Returns:

Solution.

number_of_variables() → int

class jmetal.core.problem.IntegerProblem

Bases: Problem[IntegerSolution], ABC

Class representing integer problems.

create_solution() → IntegerSolution

Creates a random_search solution to the problem.

Returns:

Solution.

number_of_variables() → int

class jmetal.core.problem.OnTheFlyFloatProblem

Bases: FloatProblem

Class for defining float problems on the fly.

Example:

>>> # Defining problem Srinivas on the fly
>>> def f1(x: [float]):
>>>     return 2.0 + (x[0] - 2.0) * (x[0] - 2.0) + (x[1] - 1.0) * (x[1] - 1.0)
>>>
>>> def f2(x: [float]):
>>>     return 9.0 * x[0] - (x[1] - 1.0) * (x[1] - 1.0)
>>>
>>> def c1(x: [float]):
>>>     return 1.0 - (x[0] * x[0] + x[1] * x[1]) / 225.0
>>>
>>> def c2(x: [float]):
>>>     return (3.0 * x[1] - x[0]) / 10.0 - 1.0
>>>
>>> problem = OnTheFlyFloatProblem()            .set_name("Srinivas")            .add_variable(-20.0, 20.0)            .add_variable(-20.0, 20.0)            .add_function(f1)            .add_function(f2)            .add_constraint(c1)            .add_constraint(c2)

add_constraint(constraint) → OnTheFlyFloatProblem

add_function(function) → OnTheFlyFloatProblem

add_variable(lower_bound, upper_bound) → OnTheFlyFloatProblem

evaluate(solution: FloatSolution) → None

Evaluate a solution. For any new problem inheriting from Problem, this method should be replaced. Note that this framework ASSUMES minimization, thus solutions must be evaluated in consequence.

Returns:

Evaluated solution.

name() → str

number_of_constraints() → int

number_of_objectives() → int

set_name(name) → OnTheFlyFloatProblem

class jmetal.core.problem.PermutationProblem

Bases: Problem[PermutationSolution], ABC

Class representing permutation problems.

class jmetal.core.problem.Problem

Bases: Generic[S], ABC

Class representing problems.

MAXIMIZE = 1

MINIMIZE = -1

abstract create_solution() → S

Creates a random_search solution to the problem.

Returns:

Solution.

abstract evaluate(solution: S) → S

Evaluate a solution. For any new problem inheriting from Problem, this method should be replaced. Note that this framework ASSUMES minimization, thus solutions must be evaluated in consequence.

Returns:

Evaluated solution.

abstract name() → str

abstract number_of_constraints() → int

abstract number_of_objectives() → int

abstract number_of_variables() → int