MATLAB Answers

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

2 views (last 30 days)
Doug Rank
Doug Rank on 10 Oct 2019
Answered: Alberto Chavez on 21 Mar 2020
(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.
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?

Answers (1)

Alberto Chavez
Alberto Chavez on 21 Mar 2020
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?

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!