6
$\begingroup$

I have a two-objective assignment problem that appears to converge really slowly to a solution.

Even if we just have 1 objective that minimizes costs, it appears to be very slow for a worker-task matrix has a size of $500 \times 500$ and using NSGA-2 with a population size of $500$. The usual constraints of 1 worker to 1 task is being used here. It takes about 1 minutes to process 1 generations of 500 evaluations.

For the $500 \times 500$ cost matrix, I used a made-up one with a small number $9$ in the diagonals, and a large number $123$ in the non-diagonals

import numpy as np

c = np.full((500,500), 123)
np.fill_diagonal(c, 9)

The objective function to be minimized is the sum of the cost of all assignments, given by

$$ min\sum_{w \in W} \sum_{t \in T} C_{w,t} X_{w,t} $$

where $X$ is a $500 \times 500$ matrix containing either $0$ or $1$, $C$ is the cost matrix containing small numbers in the diagonal.

n_rows, n_cols = c.shape

def func_obj(x):
    assignments = x.reshape((n_rows, n_cols))
    return sum(np.multiply(c, assignments).reshape(-1))

and contraints are

$$ \sum_{w=1}^W X_{w,t} = 1 \quad \forall t \in \{ 1, ..., T \} $$

$$ \sum_{t=1}^T X_{w,t} = 1 \quad \forall w \in \{ 1, ..., W \} $$

$$ X_{w,t} \in \{0, 1\} \quad \forall w, t $$

When defining the problem, an equality constraint penalty was also set

ConstraintsAsPenalty(problem, penalty=1e10)

Is GA the wrong approach to use for solving two-objective assignment problems, and even for single objective ones like described in the example above? Or is it more likely I've described the problem incorrectly using code, or used poor hyperparameters?


Progress of the minimization process for 50 generations:

=======================================================
n_gen |  n_eval |  n_nds  |     eps      |  indicator  
=======================================================
    1 |     500 |       1 |            - |            -
    2 |    1000 |       1 |  1.88000E+12 |        ideal
    3 |    1500 |       1 |  4.90000E+12 |        ideal
    4 |    2000 |       1 |  3.14000E+12 |        ideal
    5 |    2500 |       1 |  3.86000E+12 |        ideal
    6 |    3000 |       1 |  9.80000E+11 |        ideal
    7 |    3500 |       1 |  3.98000E+12 |        ideal
    8 |    4000 |       1 |  2.08000E+12 |        ideal
    9 |    4500 |       1 |  6.08000E+12 |        ideal
   10 |    5000 |       1 |  2.10000E+12 |        ideal
   11 |    5500 |       1 |  2.10000E+12 |        ideal
   12 |    6000 |       1 |  2.40000E+12 |        ideal
   13 |    6500 |       1 |  4.66000E+12 |        ideal
   14 |    7000 |       1 |  1.84000E+12 |        ideal
   15 |    7500 |       1 |  6.74000E+12 |        ideal
   16 |    8000 |       1 |  1.46000E+12 |        ideal
   17 |    8500 |       1 |  4.44000E+12 |        ideal
   18 |    9000 |       1 |  1.76000E+12 |        ideal
   19 |    9500 |       1 |  1.48000E+12 |        ideal
   20 |   10000 |       1 |  4.04000E+12 |        ideal
   21 |   10500 |       1 |  3.38000E+12 |        ideal
   22 |   11000 |       1 |  1.98000E+12 |        ideal
   23 |   11500 |       1 |  5.10000E+12 |        ideal
   24 |   12000 |       1 |  5.00000E+11 |        ideal
   25 |   12500 |       1 |  5.86000E+12 |        ideal
   26 |   13000 |       1 |  0.00000E+00 |            f
   27 |   13500 |       1 |  7.28000E+12 |        ideal
   28 |   14000 |       1 |  1.08000E+12 |        ideal
   29 |   14500 |       1 |  8.80000E+11 |        ideal
   30 |   15000 |       1 |  3.22000E+12 |        ideal
   31 |   15500 |       1 |  2.96000E+12 |        ideal
   32 |   16000 |       1 |  2.44000E+12 |        ideal
   33 |   16500 |       1 |  6.16000E+12 |        ideal
   34 |   17000 |       1 |  3.40000E+11 |        ideal
   35 |   17500 |       1 |  4.22000E+12 |        ideal
   36 |   18000 |       1 |  2.24000E+12 |        ideal
   37 |   18500 |       1 |  9.46000E+12 |        ideal
   38 |   19000 |       1 |  0.00000E+00 |            f
   39 |   19500 |       1 |  2.38000E+12 |        ideal
   40 |   20000 |       1 |  2.30000E+12 |        ideal
   41 |   20500 |       1 |  0.00000E+00 |            f
   42 |   21000 |       1 |  5.10000E+12 |        ideal
   43 |   21500 |       1 |  6.80000E+11 |        ideal
   44 |   22000 |       1 |  5.64000E+12 |        ideal
   45 |   22500 |       1 |  1.94000E+12 |        ideal
   46 |   23000 |       1 |  3.64000E+12 |        ideal
   47 |   23500 |       1 |  2.66000E+12 |        ideal
   48 |   24000 |       1 |  4.46000E+12 |        ideal
   49 |   24500 |       1 |  8.00000E+11 |        ideal
   50 |   25000 |       1 |  3.18000E+12 |        ideal

giving the following matrix in the results, clearly showing that the constraints of 1 task per worker is not being enforced.

[[ True False  True ...  True  True False]
 [False False False ... False  True False]
 [ True  True  True ... False  True  True]
 ...
 [False False False ...  True  True  True]
 [False False False ...  True False  True]
 [ True  True False ...  True  True  True]]
$\endgroup$
1
  • 5
    $\begingroup$ Yes, GA is certainly not the best way to solve a single-objective assignment problem. There are specialized algorithms for that, but even an LP solver will handle your $500 \times 500$ instance in less than one second. $\endgroup$
    – RobPratt
    Apr 2 at 16:08

1 Answer 1

5
$\begingroup$

I agree with @RobPratt that a GA is not the ideal way to solve an assignment problem. The Wikipedia entry for assignment problems lists a few alternatives, and as Rob points out an LP solver should have no problem with it.

If you really want to use a GA, I would recommend using a permutation of the task indices as the chromosome rather than using a penalty function for constraint violations. I ran a permutation GA in R, using your 500 x 500 cost matrix (values 123 off diagonal, 9 on diagonal), with a population size of 500 (which I think is too high for this type of problem). It took about 0.85 seconds per generation. I should add that improvement in the objective was very slow.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.