breeding parents for multiple children in genetic algorithm

Question

I'm building my first Genetic Algorithm in javascript, using a collection of tutorials.

I'm building a somewhat simpler structure to this scheduling tutorial http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx#Chromosome8, but I've run into a problem with breeding.

I get a population of 60 individuals, and now I'm picking the top two individuals to breed, and then selecting a few random other individuals to breed with the top two, am I not going to end up with a fairly small amount of parents rather quickly?

I figure I'm not going to be making much progress in the solution if I breed the top two results with each of the next 20.

Is that correct? Is there a generally accepted method for doing this?

Answer 1

I have a sample of genetic algorithms in Javascript here.

One problem with your approach is that you are killing diversity in the population by mating always the top 2 individuals. That will never work very well because it's too greedy, and you'll actually be defeating the purpose of having a genetic algorithm in the first place.

This is how I am implementing mating with elitism (which means I am retaining a percentage of unaltered best fit individuals and randomly mating all the rest), and I'll let the code do the talking:

// save best guys as elite population and shove into temp array for the new generation
for(var e = 0; e < ELITE; e++) {
   tempGenerationHolder.push(fitnessScores[e].chromosome); 
}

// randomly select a mate (including elite) for all of the remaining ones
// using double-point crossover should suffice for this silly problem
// note: this should create INITIAL_POP_SIZE - ELITE new individualz
for(var s = 0; s < INITIAL_POP_SIZE - ELITE; s++) {
   // generate random number between 0 and INITIAL_POP_SIZE - ELITE - 1
   var randInd = Math.floor(Math.random()*(INITIAL_POP_SIZE - ELITE));

   // mate the individual at index s with indivudal at random index
   var child = mate(fitnessScores[s].chromosome, fitnessScores[randInd].chromosome);

   // push the result in the new generation holder
   tempGenerationHolder.push(child);
}

It is fairly well commented but if you need any further pointers just ask (and here's the github repo, or you can just do a view source on the url above). I used this approach (elitism) a number of times, and for basic scenarios it usually works well.

Hope this helps.