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