Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
1  
This would be better posted in Computational Science or Cross Validated (Statistics). –  Assad Ebrahim Jan 21 '13 at 21:19
2  
Could you provide more detail/specificity regarding the nature of "hard" and "soft" constraints? –  Mark Canlas Sep 3 '13 at 14:28
    
What are the row constraints? –  locster Oct 21 '13 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.