Does encoding method matter in Genetic Algorithm with linear+integer constraints, with respect to crossover?

(Preface: There are a few details here that may raise yellow/red flags to a reader. Rest assured that the choice of algorithm and the population size relative to the solution size are necessary for this application.)

I am using the built-in Genetic Algorithm to optimize problems with a large solution space. The solution is constrained to be a binary vector (integer constraint) with ~1500 elements and there are a large number of linear constraints (about 500 or so).

If I initialize the GA with a random feasible population of about 500, the entire population (aside from the elites) becomes infeasible by the second generation. As the generations progress, members of the population become feasible so that after 30 or so generations all or almost all of them are feasible.

You might think this is contrary to the documentation, and you are right. But it is how the algorithm works.

As far as I know, the crossover function becomes a black box once you have integer constraints, since you cannot change it in the options in this scenario. Linear constraints are also no longer strictly enforced in this scenario.

Now I am wondering if my specific choice for encoding the solution as a vector would matter with respect to crossover. The solution makes most sense when viewed as a matrix, like:

A11 A12 A13

A21 A22 A23

A31 A32 A33

A41 A42 A43

A51 A52 A53

and so on.

If we just use that small example, two key constraints are that the column sums must be <= 2 and the row sums must be >= 1.

Another constraint may be that the first two row sums must == 1 and the column sum of the first two rows must == 0 or 2. In other words, for the first two rows:

1 0 0

1 0 0

or

0 1 0

0 1 0

or

0 0 1

0 0 1

are all good. But:

0 1 0

1 0 0

or

1 1 0

1 0 0

for example, are bad.

I encode the matrix as a solution vector for the algorithm as:

A11 A12 A13 A21 A22 A23 A31 A32 A33 A41 A42 A43 A51 A52 A53

But given the constraints that are present, would it be better to encode it as:

A11 A21 A31 A41 A51 A12 A22 A32 ... (and so on)

so that crossover has a better chance of producing feasible offspring?

Answer 1

[Alberto Chavez]

I believe it matters, because it copies hole sections of the chromosomes, it also depends in the locations for the crossovers and how many they are. But as I still have the ga in the Optimization tool I will place this information obtained from it here:

"Crossover combines two individuals, or parents, to form a new individual, or child, for the next generation. Ignored with integer constraints."

So if the solver does exactly the same thing as the one in the Optimization tool, then your crossover is being ignored because you have integer constraints.

Or perhaps I'm missinterpreting the information and how you can setup the solver?