Genetic Algorithm - solving a matrix with hard row and soft column contraints

0
votes

I'm writing a GP that I need some advice on for crossover and mutation 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.

Where I need a little advice is on my crossover. Parents are chosen from solutions with higher fitness scores. I have a one-point crossover where I slice some rows from the top of the father and the complimentary bottom rows from the mother to generate the offspring. I can't slice by column because that would almost always make the solution infeasible.

Does this approach seem reasonable for crossover? I'm worried that not enough good genetic 'material' passes from generation to generation to ultimately make this feasible. For mutation, I just plan on re-randomizing a row or two and checking the new fitness score for the solution.

Thanks for any advice as I plod along.

1
algorithmmatrixgenetic-algorithm
This question might be better on programmers.stackexchange.com. - Some programmer dude
How so? A search for 'genetic algorithm' on this site found several pages of hits, all having to do with problems along the same line as my own. - cardinalPilot
Your question seems more conceptual and less specific. SO is more for specific problems about code while Programmers is more for conceptual questions about coding in general. - Some programmer dude
You could relax your hard constraint to a certain extent when generating new solutions. That will allow more diversity. You can add a penalty where a solution which violates a constraint is penalized, with the degree of penalty a function of the extent of violation. You can also increase that penalty as the violating solution ages. This allows for greater diversity, and will aid in hill climbing especially during the initial generations. - VSOverFlow

1 Answers

0
votes

In any genetic algorithm, the crossover method should be chosen to appropriate to the encoding of the solution. If crossing over in a particular way would make many of the offspring non-viable, then you shouldn't cross them like that. However, it does sound like crossing over rows would prevent you from exploring the search space thoroughly.

There are several approaches that you could use to address this:

  1. Use a "course" fitness function initially, which does not penalise invalid solutions as harshly initially, as suggested by VSOverflow. Such approaches are not absent from the literature either - see Punch (1996) for example.
  2. Split your population into several initial subpopulations, and don't permit them to interact except occasionally. This will slow the convergence of rows so that promising rows are less likely to be killed off by random chance.
  3. If a more fine-grained selection would be possible to swap even individual cells (in a controlled fashion, so that the results are still valid afterwards) that's probably a good idea.