# Genetic Algorithm - solving a matrix with hard and soft constraints

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.

• This would be better posted in Computational Science or Cross Validated (Statistics). Jan 21, 2013 at 21:19
• Could you provide more detail/specificity regarding the nature of "hard" and "soft" constraints? Sep 3, 2013 at 14:28
• What are the row constraints? Oct 21, 2013 at 13:09

## 1 Answer

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.