Generating the next generation of a Genetic Algorithm

Question

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?

Answer 1

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).