.. _nb_subset_selection:

## Subset Selection Problem

A genetic algorithm can be used to approach subset selection problems by defining custom operators. In general, a metaheuristic algorithm might not be the ultimate goal to implement in a real-world scenario; however, it might be useful to investigate patterns or characteristics of possible well-performing subsets. 
Let us consider a simple toy problem where we have to select numbers from a list. For every solution, exactly ten numbers have to be selected that their sum is minimized.
For the subset selection problem, a binary encoding can be used where **one** indicates a number is picked. In our problem formulation, the list of numbers is represented by $L$ and the binary encoded variable by $x$.


\begin{align}
\begin{split}
\min f(x) & = & \sum_{k=1}^{n} L_k \cdot x_k\\[2mm]
\text{s.t.} \quad g(x)  & = & (\sum_{k=1}^{n} x_k - 10)^2\\[2mm]
\end{split}
\end{align}


As shown above, the equality constraint is handled by ensuring $g(x)$ can only be zero if exactly ten numbers are chosen.
The problem can be implemented as follows:


```python
import numpy as np
from pymoo.core.problem import ElementwiseProblem

class SubsetProblem(ElementwiseProblem):
    def __init__(self,
                 L,
                 n_max
                 ):
        super().__init__(n_var=len(L), n_obj=1, n_constr=1)
        self.L = L
        self.n_max = n_max

    def _evaluate(self, x, out, *args, **kwargs):
        out["F"] = np.sum(self.L[x])
        out["G"] = (self.n_max - np.sum(x)) ** 2
    
    
# create the actual problem to be solved
np.random.seed(1)
L = np.array([np.random.randint(100) for _ in range(100)])
n_max = 10
problem = SubsetProblem(L, n_max)

```

The customization requires writing custom operators in order to solve this problem efficiently. We recommend considering the feasibility directly in the evolutionary operators because otherwise, most of the time, infeasible solutions will be processed.
The sampling creates a random solution where the subset constraint will always be satisfied. 
The mutation randomly removes a number and chooses another one. The crossover takes the values of both parents and then randomly picks either the one from the first or from the second parent until enough numbers are picked.


```python
from pymoo.core.crossover import Crossover
from pymoo.core.mutation import Mutation
from pymoo.core.sampling import Sampling


class MySampling(Sampling):

    def _do(self, problem, n_samples, **kwargs):
        X = np.full((n_samples, problem.n_var), False, dtype=bool)

        for k in range(n_samples):
            I = np.random.permutation(problem.n_var)[:problem.n_max]
            X[k, I] = True

        return X


class BinaryCrossover(Crossover):
    def __init__(self):
        super().__init__(2, 1)

    def _do(self, problem, X, **kwargs):
        n_parents, n_matings, n_var = X.shape

        _X = np.full((self.n_offsprings, n_matings, problem.n_var), False)

        for k in range(n_matings):
            p1, p2 = X[0, k], X[1, k]

            both_are_true = np.logical_and(p1, p2)
            _X[0, k, both_are_true] = True

            n_remaining = problem.n_max - np.sum(both_are_true)

            I = np.where(np.logical_xor(p1, p2))[0]

            S = I[np.random.permutation(len(I))][:n_remaining]
            _X[0, k, S] = True

        return _X


class MyMutation(Mutation):
    def _do(self, problem, X, **kwargs):
        for i in range(X.shape[0]):
            X[i, :] = X[i, :]
            is_false = np.where(np.logical_not(X[i, :]))[0]
            is_true = np.where(X[i, :])[0]
            X[i, np.random.choice(is_false)] = True
            X[i, np.random.choice(is_true)] = False

        return X
```

After having defined the operators a genetic algorithm can be initialized.


```python
from pymoo.algorithms.soo.nonconvex.ga import GA
from pymoo.optimize import minimize

algorithm = GA(
    pop_size=100,
    sampling=MySampling(),
    crossover=BinaryCrossover(),
    mutation=MyMutation(),
    eliminate_duplicates=True)

res = minimize(problem,
               algorithm,
               ('n_gen', 60),
               seed=1,
               verbose=True)

print("Function value: %s" % res.F[0])
print("Subset:", np.where(res.X)[0])

```

    
    Compiled modules for significant speedup can not be used!
    https://pymoo.org/installation.html#installation
    
    To disable this warning:
    from pymoo.config import Config
    Config.show_compile_hint = False
    
    ===========================================================================
    n_gen |  n_eval |   cv (min)   |   cv (avg)   |     fopt     |     favg    
    ===========================================================================
        1 |     100 |  0.00000E+00 |  0.00000E+00 |  2.58000E+02 |  4.43940E+02
        2 |     200 |  0.00000E+00 |  0.00000E+00 |  1.85000E+02 |  3.49800E+02
        3 |     300 |  0.00000E+00 |  0.00000E+00 |  1.59000E+02 |  3.01110E+02
        4 |     400 |  0.00000E+00 |  0.00000E+00 |  1.49000E+02 |  2.60290E+02
        5 |     500 |  0.00000E+00 |  0.00000E+00 |  1.45000E+02 |  2.25590E+02
        6 |     600 |  0.00000E+00 |  0.00000E+00 |  1.28000E+02 |  1.97060E+02
        7 |     700 |  0.00000E+00 |  0.00000E+00 |  1.00000E+02 |  1.75580E+02
        8 |     800 |  0.00000E+00 |  0.00000E+00 |  1.00000E+02 |  1.57490E+02
        9 |     900 |  0.00000E+00 |  0.00000E+00 |  9.80000E+01 |  1.41920E+02
       10 |    1000 |  0.00000E+00 |  0.00000E+00 |  6.10000E+01 |  1.28920E+02
       11 |    1100 |  0.00000E+00 |  0.00000E+00 |  6.10000E+01 |  1.17730E+02
       12 |    1200 |  0.00000E+00 |  0.00000E+00 |  6.10000E+01 |  1.09730E+02
       13 |    1300 |  0.00000E+00 |  0.00000E+00 |  6.10000E+01 |  1.03210E+02
       14 |    1400 |  0.00000E+00 |  0.00000E+00 |  6.10000E+01 |  9.73500E+01
       15 |    1500 |  0.00000E+00 |  0.00000E+00 |  6.10000E+01 |  9.37400E+01
       16 |    1600 |  0.00000E+00 |  0.00000E+00 |  6.10000E+01 |  9.04500E+01
       17 |    1700 |  0.00000E+00 |  0.00000E+00 |  6.10000E+01 |  8.60100E+01
       18 |    1800 |  0.00000E+00 |  0.00000E+00 |  5.70000E+01 |  8.21100E+01
       19 |    1900 |  0.00000E+00 |  0.00000E+00 |  5.50000E+01 |  7.90200E+01
       20 |    2000 |  0.00000E+00 |  0.00000E+00 |  5.50000E+01 |  7.72200E+01
       21 |    2100 |  0.00000E+00 |  0.00000E+00 |  5.30000E+01 |  7.44300E+01
       22 |    2200 |  0.00000E+00 |  0.00000E+00 |  5.30000E+01 |  7.25200E+01
       23 |    2300 |  0.00000E+00 |  0.00000E+00 |  4.90000E+01 |  7.06400E+01
       24 |    2400 |  0.00000E+00 |  0.00000E+00 |  4.60000E+01 |  6.82500E+01
       25 |    2500 |  0.00000E+00 |  0.00000E+00 |  4.60000E+01 |  6.49500E+01
       26 |    2600 |  0.00000E+00 |  0.00000E+00 |  4.60000E+01 |  6.21700E+01
       27 |    2700 |  0.00000E+00 |  0.00000E+00 |  4.40000E+01 |  5.90200E+01
       28 |    2800 |  0.00000E+00 |  0.00000E+00 |  4.40000E+01 |  5.76400E+01
       29 |    2900 |  0.00000E+00 |  0.00000E+00 |  4.40000E+01 |  5.61500E+01
       30 |    3000 |  0.00000E+00 |  0.00000E+00 |  4.40000E+01 |  5.44400E+01
       31 |    3100 |  0.00000E+00 |  0.00000E+00 |  4.10000E+01 |  5.31800E+01
       32 |    3200 |  0.00000E+00 |  0.00000E+00 |  4.10000E+01 |  5.27300E+01
       33 |    3300 |  0.00000E+00 |  0.00000E+00 |  4.10000E+01 |  5.21800E+01
       34 |    3400 |  0.00000E+00 |  0.00000E+00 |  4.10000E+01 |  5.17700E+01
       35 |    3500 |  0.00000E+00 |  0.00000E+00 |  4.10000E+01 |  5.12400E+01
       36 |    3600 |  0.00000E+00 |  0.00000E+00 |  4.10000E+01 |  5.06200E+01
       37 |    3700 |  0.00000E+00 |  0.00000E+00 |  4.10000E+01 |  5.02900E+01
       38 |    3800 |  0.00000E+00 |  0.00000E+00 |  4.10000E+01 |  5.00100E+01
       39 |    3900 |  0.00000E+00 |  0.00000E+00 |  4.10000E+01 |  4.95300E+01
       40 |    4000 |  0.00000E+00 |  0.00000E+00 |  3.90000E+01 |  4.88000E+01
       41 |    4100 |  0.00000E+00 |  0.00000E+00 |  3.90000E+01 |  4.85000E+01
       42 |    4200 |  0.00000E+00 |  0.00000E+00 |  3.90000E+01 |  4.82400E+01
       43 |    4300 |  0.00000E+00 |  0.00000E+00 |  3.90000E+01 |  4.81500E+01
       44 |    4400 |  0.00000E+00 |  0.00000E+00 |  3.90000E+01 |  4.77300E+01
       45 |    4500 |  0.00000E+00 |  0.00000E+00 |  3.90000E+01 |  4.75700E+01
       46 |    4600 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.68200E+01
       47 |    4700 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.64700E+01
       48 |    4800 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.62800E+01
       49 |    4900 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.59900E+01
       50 |    5000 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.58000E+01
       51 |    5100 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.55800E+01
       52 |    5200 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.54500E+01
       53 |    5300 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.53900E+01
       54 |    5400 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.51800E+01
       55 |    5500 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.50300E+01
       56 |    5600 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.48000E+01
       57 |    5700 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.47100E+01
       58 |    5800 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.45800E+01
       59 |    5900 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.44300E+01
       60 |    6000 |  0.00000E+00 |  0.00000E+00 |  3.70000E+01 |  4.43300E+01
    Function value: 37.0
    Subset: [ 5  9 12 36 37 40 47 52 68 99]


Finally, we can compare the found subset with the optimum known simply through sorting:


```python
opt = np.sort(np.argsort(L)[:n_max])
print("Optimal Subset:", opt)
print("Optimal Function Value: %s" % L[opt].sum())
```

    Optimal Subset: [ 5  9 12 31 36 37 47 52 68 99]
    Optimal Function Value: 36


af0247b43347e987c0d94a79bc15c8d3173a75c1
ipynb
Jupyter Notebook
source/customization/subset.ipynb
SunTzunami/pymoo-doc
f82d8908fe60792d49a7684c4bfba4a6c1339daf
Apache-2.0
2021-09-11T06:43:49.000Z
2021-11-10T13:36:09.000Z
source/customization/subset.ipynb
SunTzunami/pymoo-doc
f82d8908fe60792d49a7684c4bfba4a6c1339daf
Apache-2.0
2021-09-21T14:04:47.000Z
2022-03-07T13:46:09.000Z
source/customization/subset.ipynb
SunTzunami/pymoo-doc
f82d8908fe60792d49a7684c4bfba4a6c1339daf
Apache-2.0
2021-10-09T02:47:26.000Z
2022-02-10T07:02:37.000Z
Qwen/Qwen-72B
1. YES
2. YES