Genetic Algorithm Problems

2
votes

I'm implementing the NSGA II genetic algorithm to develop a set of timetables for my college. I am having problems with variation of solutions.

My algorithm works fine as in initialization, mutation and crossover but after the final generation when reviewing my solutions they are all the same e.g I have 200 in a generation, maybe 64 of them will be the same as each other, 54 the same as each other etc.

My question is what may be causing this? And what is the best form of crossover and mutation?

Also is there norm for generation size, amount of generations, mutation rate and cross over rate?

At the moment it runs like so:

  1. Randomly generate 300 solutions
  2. Calculate fitness and ranking
  3. Pick 200 of the best solutions
  4. Mutate 5% of these and produce 80 children
  5. Calculate and Rank again
  6. Pick the best 300 to move on to next generation
  7. Repeat
3
genetic-algorithm
It's difficult to say anything beyond "there is probably a bug somewhere" with the information you provided. It shouldn't be too difficult to reduce your algorithm to a few lines of pseudo-code (at least the selection and generation of each generation) (which you can then add to the question). Looking at the population at initialization and intermediate steps of the algorithm might also provide some insight. Also, this question is probably outside the scope of SO (maybe better for CSTheory, CS or Programmers). - Bernhard Barker
At the minute it runs like so 1. Randomly generate 300 solutions 2. Calculate fitness and ranking 3. Pick 200 of the best solutions 4. Mutate 5% of these and produce 80 children 5. Calculate and Rank again 6. Pick the best 300 to move on to next generation Repeat above I don't think it is a bug as I have worked through it and everything seems to be ok. Though I would be more than happy to be proved wrong! - Melo1991
Not much info here, but my gut tells me you are having a problem with your weighting of solutions and therefore your selection (3) is being hyper-selective, leading to an overly homogenous population. Try unit testing & measuring their outputs outside of the GA to verify their correctness. - NWS
How many objectives are there in your problem ? And how many constraints ? - Benoît Guédas

3 Answers

1
votes

I believe there may be no error in your algo. This is a well known problem for GA. If you want to have a variety of solutions, you should implement some Niching method. Its idea is in punishing similar individuals in your population. You can figure out some heuristic for individuals similarity and exclude similar individuals from your population or eliminate individual's fitness. This will keep your population more diverse and will not allow your variation operators choose and evolve same individuals. It'll be useful to look through "Niching Methods for Genetic Algorithms" of Samir W. Mahfoud.

0
votes

This outcome is not necessarily bad. It may just be converging on a couple of solutions which do not have any other viable solutions "nearby". Are the solutions you are converging on bad?

One thing I notice is that although you mention crossover you do not list it as one of your 7 steps. If in fact you are only doing mutation, that would make it more difficult for the GA to climb out of local optima.

0
votes

G.A's works like Converging to a point choosing a minimal set of alleles(solutions) as best. In some rare cases, after a long run like some thousands of generations, it may bring a single optimal solution.

But in some cases, it may bring converging solutions in minimal number of runs, say 100. But it has the possibility of getting stuck in the local optima, failing to reach the global optima.

I am not sure upto which generation, you have tried. I suggest you to go for 1000 generations and compare the results. Also the plot may change after some generations like you can see entirely new set of solutions

There are different crossover and mutation for different representations. May be you could tell the representation you are using and the results are directly proportional with number of generations