GitHub Newsletter Discord

Version: 0.6.1.3

Repair

The repair operator is mostly problem-dependent. Most commonly, it is used to make sure the algorithm is only searching in the feasible space. It is applied after the offsprings have been reproduced. In the following, we are using the knapsack problem to demonstrate the repair operator in pymoo.

In the well-known Knapsack Problem. In this problem, a knapsack has to be filled with items without violating the maximum weight constraint. Each item \(j\) has a value \(b_j \geq 0\) and a weight \(w_j \geq 0\) where \(j \in \{1, .., m\}\). The binary decision vector \(z = (z_1, .., z_m)\) defines, if an item is picked or not. The aim is to maximize the profit \(g(z)\):

\begin{eqnarray} max & & g(z) \\[2mm] \notag \text{s.t.} & & \sum_{j=1}^m z_j \, w_j \leq Q \\[1mm] \notag & & z = (z_1, .., z_m) \in \mathbb{B}^m \\[1mm] \notag g(z) & = & \sum_{j=1}^{m} z_j \, b_j \\[2mm] \notag \end{eqnarray}

A simple GA will have some infeasible evaluations in the beginning and then concentrate on the infeasible space.

from pymoo.operators.crossover.hux import HUX
from pymoo.operators.mutation.bitflip import BitflipMutation
from pymoo.operators.sampling.rnd import BinaryRandomSampling
from pymoo.optimize import minimize
from pymoo.algorithms.soo.nonconvex.ga import GA
from pymoo.problems.single.knapsack import create_random_knapsack_problem

problem = create_random_knapsack_problem(30)


algorithm = GA(pop_size=200,
               sampling=BinaryRandomSampling(),
               crossover=HUX(),
               mutation=BitflipMutation(),
               eliminate_duplicates=True)


res = minimize(problem,
               algorithm,
               termination=('n_gen', 10),
               verbose=True)

=================================================================================
n_gen  |  n_eval  |     cv_min    |     cv_avg    |     f_avg     |     f_min
=================================================================================
     1 |      200 |  1.300000E+02 |  4.971950E+02 |             - |             -
     2 |      400 |  5.700000E+01 |  3.461950E+02 |             - |             -
     3 |      600 |  5.700000E+01 |  2.462000E+02 |             - |             -
     4 |      800 |  0.000000E+00 |  1.654450E+02 | -3.538000E+02 | -4.370000E+02
     5 |     1000 |  0.000000E+00 |  9.591000E+01 | -3.341667E+02 | -4.370000E+02
     6 |     1200 |  0.000000E+00 |  4.528000E+01 | -3.032000E+02 | -4.530000E+02
     7 |     1400 |  0.000000E+00 |  1.091500E+01 | -2.972818E+02 | -5.490000E+02
     8 |     1600 |  0.000000E+00 |  0.000000E+00 | -3.028700E+02 | -5.490000E+02
     9 |     1800 |  0.000000E+00 |  0.000000E+00 | -3.685000E+02 | -5.890000E+02
    10 |     2000 |  0.000000E+00 |  0.000000E+00 | -4.137900E+02 | -6.770000E+02

Because the constraint \(\sum_{j=1}^m z_j \, w_j \leq Q\) is fairly easy to satisfy. Therefore, we can make sure that this constraint is not violated by repairing the individual before evaluating the objective function. A repair class has to be defined, and the population is given as input. The repaired population has to be returned.

import numpy as np
from pymoo.core.repair import Repair


class ConsiderMaximumWeightRepair(Repair):

    def _do(self, problem, Z, **kwargs):

        # maximum capacity for the problem
        Q = problem.C

        # the corresponding weight of each individual
        weights = (Z * problem.W).sum(axis=1)

        # now repair each indvidiual i
        for i in range(len(Z)):

            # the packing plan for i
            z = Z[i]

            # while the maximum capacity violation holds
            while weights[i] > Q:

                # randomly select an item currently picked
                item_to_remove = np.random.choice(np.where(z)[0])

                # and remove it
                z[item_to_remove] = False

                # adjust the weight
                weights[i] -= problem.W[item_to_remove]

        return Z

algorithm = GA(pop_size=200,
               sampling=BinaryRandomSampling(),
               crossover=HUX(),
               mutation=BitflipMutation(),
               repair=ConsiderMaximumWeightRepair(),
               eliminate_duplicates=True)


res = minimize(problem,
               algorithm,
               termination=('n_gen', 10),
               verbose=True)

=================================================================================
n_gen  |  n_eval  |     cv_min    |     cv_avg    |     f_avg     |     f_min
=================================================================================
     1 |      176 |  0.000000E+00 |  0.000000E+00 | -1.453920E+02 | -4.250000E+02
     2 |      376 |  0.000000E+00 |  0.000000E+00 | -2.294250E+02 | -4.270000E+02
     3 |      576 |  0.000000E+00 |  0.000000E+00 | -2.993900E+02 | -5.540000E+02
     4 |      776 |  0.000000E+00 |  0.000000E+00 | -3.578850E+02 | -5.870000E+02
     5 |      976 |  0.000000E+00 |  0.000000E+00 | -4.061650E+02 | -6.320000E+02
     6 |     1176 |  0.000000E+00 |  0.000000E+00 | -4.537500E+02 | -6.320000E+02
     7 |     1376 |  0.000000E+00 |  0.000000E+00 | -4.890000E+02 | -6.320000E+02
     8 |     1576 |  0.000000E+00 |  0.000000E+00 | -5.216750E+02 | -6.640000E+02
     9 |     1776 |  0.000000E+00 |  0.000000E+00 | -5.445500E+02 | -6.770000E+02
    10 |     1976 |  0.000000E+00 |  0.000000E+00 | -5.590650E+02 | -6.770000E+02

As demonstrated, the repair operator makes sure no infeasible solution is evaluated. Even though this example seems to be quite easy, the repair operator makes especially sense for more complex constraints where domain-specific knowledge is known.

<< Mutation

Visualization >>