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\):
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