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.
-
1This would be better posted in Computational Science or Cross Validated (Statistics).Assad Ebrahim– Assad Ebrahim2013年01月21日 21:19:24 +00:00Commented Jan 21, 2013 at 21:19
-
2Could you provide more detail/specificity regarding the nature of "hard" and "soft" constraints?Mark Canlas– Mark Canlas2013年09月03日 14:28:56 +00:00Commented Sep 3, 2013 at 14:28
-
What are the row constraints?redcalx– redcalx2013年10月21日 13:09:12 +00:00Commented Oct 21, 2013 at 13:09
1 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.