0

In my problem I plan on solving using GA, chromosomes can be infeasible. Which means, some solutions simply aren't valid and the fitness function cannot be computed for them. My goal is to keep the feasibility status binary (feasible or infeasible) since a quantification of the infeasibility of a chromosome would be terribly complicated or even impossible.

How can this be accomplished and implemented into a genetic algortihm in order to find the best, feasible solution?

nkxandroid
  • 659
  • 1
  • 5
  • 14
  • 1
    what is the point of keeping individuals with infeasible genetic code in your genetic pool? in the worst, unlucky case, you might end up with a population made only of infeasible individuals and no knowledge of how to recover back to your 'good' state, loosing any progress you made towards the optimal solution. Simply ensure that the function creating new individuals returns only feasible individuals, even at the cost of making several attempts to create new ones, or return a random new feasible one with no relationship whatsoever with his parents. – Patrick Trentin Dec 09 '16 at 10:01
  • I agree, this approach seems to be the most effective one. For random generations, you could always retry until a feasible solution is found. If that however fails after a certain amount of retries or the generation function does not have any randomness, you basically have two options: Generate a completely new, random solution with no relationship to its parents OR just not execute that mutation/crossover and let the 'family go extinct', if you know what I mean. Which of these two options sounds better to you? – nkxandroid Dec 09 '16 at 10:23
  • 1
    Better idea. Keep two counters for each individual, increment one when it fails to reproduce and increment another when it reproduces successfully. If the ratio among the two is too bad, replace the individual with a new random one unless it is in the top % of your population. Each time reproduction fails, keep around the parents but not the infeasible children. This scheme assumes 2 parents result in 2 children. It should avoid getting stuck in a plateau too. – Patrick Trentin Dec 09 '16 at 10:48
  • Interesting approach, I will try this out. Thanks! – nkxandroid Dec 09 '16 at 11:15
  • 3
    Have a look at T. Vidal et al. (2012) - A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems. They literally say _"The metaheuristic literature indicates that allowing a con- trolled exploration of infeasible solutions may enhance the performance of the search"_, so it might help to allow for infeasible solutions. If I remember correctly, they impose a penalty for being infeasible which increases over time. – Michiel uit het Broek Dec 09 '16 at 12:45
  • @MichielUitHetBroek thank you, I'll read that too – Patrick Trentin Dec 09 '16 at 13:08

0 Answers0