5

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 you measure its performance? Perhaps it might have performed better with more generations? ;) That's the fun about genetic algorithms! ;) – FrustratedWithFormsDesigner Dec 21 '16 at 14:59
  • @FrustratedWithFormsDesigner I updated the question to give more details. Don't know if you have any further comments. Thanks. – Avrohom Yisroel Dec 21 '16 at 16:51
  • I think you are taking the 'genetic' analogy a little too literally. There is no requirement for there to be 'chromosomes' or 'mating'. The key here is that you have a some kind of process to introduce new combinations and some sort of selection process to cull solutions that moves you towards an optimal solution. – JimmyJames Dec 21 '16 at 17:07
  • 1
    If want to preserve the top chromosomes, you may try elitism. In summary, you determine the percent of top best current population to be preserve to the next generation. You have to experiment on what is the best percent for your scenario. – OnesimusUnbound Dec 21 '16 at 17:25
2

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 generation

  • I 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.

  • I already do the first two of your bullet points. When breeding two chromosomes, I take the first part of one and the second part of the other (defined by the crossover), and then mutate individual bits depending o the mutation rate. Never thought of the third option, but the fourth basically comes down to what I was asking, do we generate a completely new set of chromosomes, or just replace the poorest n% and keep the best. I updated the question to give more details. Don't know if you have anything further to add. Thanks – Avrohom Yisroel Dec 21 '16 at 16:53
  • 1
    @AvrohomYisroel I added a couple paragraphs to the middle to explain why we don't typically try to keep much (if you keep too much an "okay" solution can out-populate the rest and you won't improve your solutions much). – Delioth Dec 21 '16 at 17:04
  • I like that you discuss getting stuck in a low local optimum in your last paragraph. That's generally a problem with these kind of "slowly walking uphill" algorithms. Sometimes you have to walk down the hill into the valley to get to the big mountain. – Jörg W Mittag Dec 21 '16 at 17:09
  • @Delioth That's a brilliant reply, and really helps a lot. As it happens, since reading the first set of comments, I tried keeping the best 50% of my current generation, and replacing the poorer 50% with new ones, bred by crossover and mutation. Please see my updated question (2nd edit) for more details. I don't know why someone downvoted your reply, it helped me a lot! – Avrohom Yisroel Dec 21 '16 at 17:36
3

There is no correct answer to this - each variation has its own merits and also disadvantages... For example in some problems that are heavily constrained you will not want to change the whole population, as none of the new ones may be at all fit while slight variations on the originals would have been. In contrast some problems with a very large search space could benefit from having many changes.

In summary you would need to think about the problem you have and experiment to find the optimal strategy for each specific problem. A good way to think about this is by examining real evolution - if only the very best were favored each time genetic diversity would be lowered and one specific problem could cause all the population to fail. With this in mind it is 'usually' better to have a fair amount of diversity at each generation which helps avoiding being stuck in local maxima/minima and have a better chance to find optimal solutions

  • 1
    Good idea to point out that the mutation rate of a GA can be "too high" or "too low" depending on the problem domain. – Ivan Dec 21 '16 at 14:41
  • @Milney I updated the question to give more details. Don't know if you have any further comments. Thanks. – Avrohom Yisroel Dec 21 '16 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.