CODEWITHSUNDEEP
genetic-algorithm
Melo1991
Melo1991

Reputation: 375

Genetic Algorithm Problems

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

Upvotes: 2

Views: 764

Answers (3)

Anna
Anna

Reputation: 63

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.

Upvotes: 1

naran
naran

Reputation: 57

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

Upvotes: 0

PGB
PGB

Reputation: 68

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.

Upvotes: 0

Related Questions