Genetic Algorithm - solving a matrix with hard and soft constraints

Question

I'm writing a Genetic Program that I need some advice on for crossover operations. The GP is attempting to find the best solution for a matrix that has hard row constraints and softer column constraints.

For a given solution in the population, the rows contain a random combination of object type ids from a fixed set. The GP is trying to find a solution where, after the rows are laid out, if you tally the id's in each column, the number of each type must fall within a recommended range for that id. I wrote a fitness function that allows me to grade the solution on how close it comes to the columns constraints - 100% being all the columns fall within specs.

Since fitness is tied to columns it seems logical that the crossover operation should grab columns of two parents to create a candidate offspring. Should a multipoint crossover be a better way to go? My concern is a crossover operation, almost certainly, will break the row contraints.

Thanks for any advice.

Answer 1

Hmmm... When I took a class on GA's and EA's, multipoint crossover was not necessarily better than single point crossover or even mutation and no crossover. In this case it seems that multipoint cross over may generate invalid rows and I'm assuming that means your evaluation function can't calculate a meaningful statistic. Given that, your idea to cross two matrixes by swapping whole rows seems like a good idea. Your algorithm might be more exploratory if you can mutate rows safely.