0

I made a genetic algorithm a couple of months ago, but I turned out to be very week in solving any kind of problem. My initial goal was to use the genetic algorithm in a game applications

Now I'm recreating the whole thing and trying to take a view from another perspective.

Now that I'm about to define the steps in which the next generation is set.

My last idea was:

  • Take the top rated genes from the current generation and duplicate them in the next (the amount is set by the elitism)

  • Take two random genes and crossover them (the chances to do be picked is correlated to the gene rank), I made several of the crossover methods(one-point,two-points,three-parents,average,uniform...)

  • Fill the new generation with genes using the above method

  • Apply some mutation to the genes ( the chance of being selected is set by mutation rate) and it will change just part of the DNA ( top rated genes are excluded )

This proved to be very inefficient(Which I don't know why) and also very computing demanding since the crossover process looped over all the genes several times.

Now I'm thinking in a new approach.

Basically I'm aiming to maintain the the genes and remove the 'bad' ones, and fill the Gene Pool with crossed genes.

In a Gene Pool with 1.000 individuals I would:

  • Discard the 500 lowest ranked.

  • Duplicate the top rated (in a 10% elitism it's 100)

  • Generate 400 new genes using crossover.

  • Apply the mutation

I was taking the concept of 'generations' too literally and making them all die(expect the top rated ones), now I'm will let them all live, expect the bad ones. And repopulate as needed.

Am I missing anything? Will this new method be any better?

f.rodrigues
  • 3,499
  • 6
  • 26
  • 62
  • Your conceptual algorithms from idea 1 and 2 look OK to me. If you're having problems with inefficiencies I would investigate the implementation of the ideas. Keep in mind that genetic algorithms are not a sure-fire solution. All the control parameters have to be tweaked since there are no magic numbers for the "best" genetic algorithm. Maybe increase the population size, maybe look at the stopping criteria (are you evolving for too many generations for very little gain?), maybe more mutation, maybe less. – Tansir1 Dec 17 '14 at 17:45
  • Maybe my implementation was the cause of the problem, But I'm not really sure, I rewrote the code several times. The problem with GA is that is hard to debug, because the only thing that change are the genes, and they are all 'random'. About tweaking, yeah I didn't try much experimentation on that, I followed some guidelines I found over the internet. – f.rodrigues Dec 17 '14 at 17:52
  • 1
    Discarding the worse half of the population is not the best idea. This can VERY quickly lead to premature convergence. I suggest to look at the selection algorighm. I have very good experience with tournament selection. It's super easy to implement and often works better then an ordinary fitness-proportionate selection. It also has the property that the worst individuals don't survive. – zegkljan Dec 18 '14 at 13:59
  • 1
    Another thing that can cause poor performance is the genotype-phenotype mapping. If the genetic encoding of your solutions is very indirect it may be hard for the GA to find the solution. If a small change in genotype leads to a big change in the phenotype (the actual solution), the crossover and mutation can't work very well. – zegkljan Dec 18 '14 at 14:00

1 Answers1

0

There is an alternative to vertical gene transfer (the traditional concept of generations), which is horizontal gene transfer (see this paper). With horizontal gene transfer, the population size remains constant throughout the simulation.

Also, when you breed genotypes (with whichever method you choose) you should definitely not keep only the fittest candidates throughout the generations. If you do so, the solution you find will most likely be a local optimum. Every genotype should have some chance of making it to the next generation, with the fittest having a better chance (see this answer about linear rank selection).

Community
  • 1
  • 1
trakmack
  • 93
  • 7