Genetic Algorithm Problems

Question

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

• Bernhard Barker: 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).
• Melo1991: 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!
• user571138: 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.
• Benoît Guédas: How many objectives are there in your problem ? And how many constraints ?

Answer 1

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.

Answer 2

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.

Answer 3

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

• Benoît Guédas: No, for a multiobjective optimization problem, you should obtain several different solutions spread over the Pareto front (if not, it was not really a multiobjective optimization problem). The question is about NSGA-II: a GA to solve multiobjective optimization problems.
• naran: @Benoît I think that is what i explained earlier. If you read my answer twice, you can get what i meant.
• Benoît Guédas: I read your answer twice, and it looks like I still don't get what you meant :-) A single solution may not be the ultimate result to any problem especially for a multicriteria optimization problem, because there are many Pareto-optimal solutions (and it is not because of the evolutionary approach).
• naran: @Benoît Thank you for what you said. I made it straight forward. Now read it and tell me what you get
• Benoît Guédas: Thanks! It's clearer now. Unfortunately, it seems that we will never know what was wrong with this algorithm :-(