Thanks to some great replies in a previous question, I think I now have a better understanding of GAs, but am still confused on a couple of points. I'll start with one here.I've been reading around about how a GA algorithm works, and have seen what appear to be conflicting opinions as to what you do at each generation:Some articles seem to say you pick the two best chromosomes and mate them, using the crossover and mutation rates to produce an offspring. You then replace the chromosome with the lowest fitness with the offspring. That only changes one chromosome per generation, which I would have thought makes for a very slow change overall, and so a slow approach to a solution. Why not do this for (say) the best 50% of the chromosomes, and replace the worst 50% at each generation? I've not seen this suggested.The other approach I've seen is to pick two chromosomes using some stochastic process, such as a roulette wheel, mate them to produce an offspring, then repeat until you have generated a whole new population. You then throw away the last generation entirely, and replace it with the new population. Whilst this will obvious produce more change per generation than the previous method, it has the (apparent) disadvantage of throwing away the best chromosomes from the previous generation. Granted, we hope that the offspring may be better, but they might not, and even if they are overall, you still throw away what could be even better chromosomes.Sorry if this is a dumb question, but I haven't seen a clear explanation of this part of the algorithm, and I'm not sure how it's supposed to be done. I wrote my very first GA code last night, which didn't do badly, but didn't perform as well as I'd hoped, and I'm wondering if I am doing this part wrongly.Thanks for any help you can give.Edit: Following some of the comments and replies, here is more information about the problem I'm trying to solve. Being really new at this, I've started with the simplest problem I could find, that of finding a string of all 1s. I fix the string length, say 20, and the fitness of any chromosome will be the number of 1s divided by 20.My first definition of performance was how close it got to the right solution. Given the easy nature of this problem, I know that the right solution is just a string of twenty 1s.I had a a further play, and found that by increasing the number of chromosomes helped for strings of length up to about 30, but once I got above that, it never really got past a fitness of about 0.8, ie sixteen 1s in the string.Don't know if that helps. From the comments, it sounds like I just have to keep playing (shame!).Edit2: Following all the excellent comments, but specifically Delioth's explanation, I tried keeping the 50% of the current population with the highest fitness, and replacing the poorer 50% with new chromosomes bred by roulette wheel selection from the current population. The results were pretty dramatic, with the GA finding the correct solution in around 200 generations, even when I increased the string length significantly. This compares with it not finding it after 10,000 generations before!I tried playing with the ratio of current chromosomes kept, but found that as long as I kept away from extremes either way, it didn't make a lot of difference.Thanks to everyone for the help. This has been a great learning experience. I have more questions, so will be back!
How do we produce the next generation?
genetic algorithms
Genetic algorithms are one of those pieces in CS where it's less science and more art, and very dependent on the requirements. You get to try some things, adjust it a bit and see how that turns out, and eventually come to your own consensus.As a rule, there are 4 things you can do in various combinations to create a new generation:Mating, which usually produces two children (xxxxx + yyyyy => xxyyy + yyxxx or various other possible splits)Mutation, changing one thing out of a chromosome and pushing it forward (xxxxx=>xxxyx)New blood, where we generate an entirely new chromosome in the new generationI don't recall the name, but forwarding a chromosome unchanged into the next generation is an option as well.In a typical genetic algorithm, you generally use all of these- but it's usually also entirely random. We like to use some sort of biased selection to get our generations improving, but if we take the top ones and decide to just keep those the algorithm will tend to stagnate- as an example, assume we have 10 copies of xxxyzz in a gene pool of 20. If we keep the top 50% as-is and mate and mutate to create 8 more, we have a whole pool of xxxyzz with two new bloods and aren't making any progress, since 90% of our chromosomes are the same (or one bit off of the same).As such, a typical genetic algorithm assumes each generation is entirely new, even though some of the members are the same as the previous generation. We try to keep the number of kept members to a minimum, since a few copies of a decent solution can very easily overwhelm a population if there are too many being kept, which leads to stagnation (and once you hit sufficient stagnation, every generation isn't helping you much since you're relying on either a lucky new blood or a good incremental improvement).In a case where there are several very different/distinct 'correct' solutions (final chromosomes), you may need to have a high rate of entirely new chromosomes. In a case where you know the general structure of the result, you may not want any new blood- you may just want incremental changes on the chromosomes you've got (since new blood could at that point give you an entirely nonfunctional answer)- but you may keep new blood in the algorithm and it might do better.