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 and one variable:

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'

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}}\]

In the former example, 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=1, number_of_objectives=1)
    new_solution.variables[0] = \
        [True if random.randint(0, 1) == 0 else False for _ in range(self.number_of_bits)]

    return new_solution