3

I'm programming Genetic Algorithm in C++ and after searching all kind of ways of doing GA'a operators (selection, crossover, mutation) I came up with a doubt.

Let's say I have an initial population of 500. My selection will consist in getting the top 20% of 500(based on best fitness). So I get 100 individuals to mate. When I do the crossover I'll get 2 children where both together have 50% of surviving. So far so good. I start the mutation, and everything's ok.. Now when I start choosing the Next generation, I see that I have a big number of children (in this case, 4950 if you wanna know). Now the thing is, every time I run GA, if I send all the children to the next generation, the number of individuals per generation will increase exponentially.

So there must be a way of choosing the children to fulfill a new generation without getting out of this range of the initial population.

What I'm asking here is if there is anyway of choosing the children to fill the new generations OR should I choose somehow (and maybe reduce) the parents to mate so I don't get so many children in the end.

Improve this question
6
  • 2
    You haven't mentioned dying yet. You need ways for individuals to die if they don't meet your fitness algorithm. Every normal biological system is constrained by things like disease, overpopulation, etc. Were that not the case, the bacterium you have on your finger would multiply exponentially and cover the entire earth to a depth of one foot within a month or two.
    – Robert Harvey
    Jun 12, 2014 at 16:35
  • 3
    So you're saying that I should send all the children, run the fitness algorithm, and then create a new generation with only the ones who fit. Reducing the "number" to the initial size
    – RubenC
    Jun 12, 2014 at 16:52
  • That would work. There might be a small amount of growth, just like there is in normal biological systems.
    – Robert Harvey
    Jun 12, 2014 at 16:54
  • 1
    @RobertHarvey GA selects from a population of fit candidates. Hence, the remainder that are not fit simply don't mate and the process of death is not accounted for. Also, the population shrinks by selection and not by death. There is also no growth in the population either. This is GA not biological reproduction.
    – Mushy
    Jun 12, 2014 at 17:11
  • 1
    Usually you just pick a population size, and each new generation is exactly that size. Instead of iterating the existing population, select pairs randomly. Don't bother generating every possible cross. (If you want to do an exhaustive search, just set it up as a tree search with some sort of breadth-first or depth-first traversal... but that's not the point of GA.)
    – sea-rob
    Jun 12, 2014 at 17:18

3 Answers 3

Reset to default
3

After that you have generated your initial population (the pool should be quite large) and you apply your fitness function to it, you select your parents for the next generation.

Once that you have your parents, you discard the other individuals so that you can replace them with the new generation. This replacing will keep your population size in control, after all, if individual I did not fit the fitness criteria to contribute to the next generation, why do you need to keep it?

Note however, that in your study, there is a high chance that your algorithm will converge to a local maxima/minima very quickly. This is because you only keep the top 20% of your population for mating. This is usually a bad idea since it will get your GA stuck in a local maxima/minima. To fix this, you would also include some of worse solutions as well, say for instance, the top 20% and the worse 5-10%.

EDIT: Alternatively, you could also go for something akin to what @ Jeff Langemeier proposes and instead of selecting the worse 10% of the population, you randomly select a given amount from the non best (in this case, the remaining 80%) individual.

Improve this answer
5
  • I'm not going to add it as an answer, since it's an addendum to yours. A more "realistic" route would be to select 10% randomly from the lower 80%, since the likelihood that a non-maximally fit critter passes on their genetics becomes more and more up to chance the further from the maximal point. A Poisson, exponential, or hill function for distribution selection may be the most effective at getting a proper parent group.
    – Jeff Langemeier
    Jun 13, 2014 at 15:02
  • @Jeff Langemeier I don't think your suggestion or npinti's would actually deal with the exponentially increasing population that was asked.
    – InformedA
    Jun 13, 2014 at 15:18
  • @randomA The exponential increase is due to hanging on to successive parent generations, so why wouldn't keeping a balanced birth and death rate from parent to child generations fix it? My suggestion was just a modification on npinti's final paragraph.
    – Jeff Langemeier
    Jun 13, 2014 at 15:37
  • @Jeff Langemeier npinti was only talking about annealing so that you exclude some of those at the top to give places to a few in the rest (this is simulated annealing in principle). And I wonder why did he separate each generation when applying fitting function??
    – InformedA
    Jun 13, 2014 at 15:54
  • Ok, I got the problem now, the asker applies fitness function on each generation separately and asks for how to specially applying the fitness function to the children generation. He didn't apply the fitness function to the whole population as normal. Sorry I assume that's what he did, I was wrong.
    – InformedA
    Jun 13, 2014 at 15:58
3

Choosing the children that are fit for the next generation of mating is the same fitness calculation that made their parents fit. Also, at the end of the current generation, you should not have more children than the initial population. Remember, this is not a free-for-all but survival of the fittest.

You are picking a highly selected group that are fit to mate from; essentially discarding up to 75 - 80% or more of your initial population (search space) or however much you need to ensure only the fittest mate.

A genetic algorithm should be run until you have exhausted the search space or, in other words, until there are no more mating pairs and, hopefully, that last offspring or very small group of offspring yield the answer you want.

This will require you to tune the fitness, crossover, and mutation factors. I recall when I wrote a GA to solve how the arithmetic operators (*, /, +. -) and the numeric values (0-9) are combined to form a randomly generated value such as 45. I represented my chromosomes as x-bit binary values that contained every operator and the number 0-9. They were heavily randomized through a heuristic to ensure as much variation as possible.

I had to tweak selection, crossover, and mutation just to solve the problem but it could be solved. If you see populations going out of control, something is not right in your algorithm. I recall, from an initial population of 100,000 I lost between 50 - 75k that were not fit to mate.

Play with it some more; you understand how it should work and I am sure you will get it.

Improve this answer
4
  • My doubts are not about the fitness calculation or anything related with the GA's operators. I studied and implemented the GA with all the right steps. The point is, how do you end up the current generation not having more children than the initial population when you get tons of them after the crossover.
    – RubenC
    Jun 12, 2014 at 17:25
  • Because from the initial population, that subset mates and those offspring become a new population. Then, from that population, a subset mates, etc. Each successive generation is smaller because of your selection heuristic and then because each pair only produces one child from crossover which then is mutated. If you have mating pairs producing more than one child, then your search space is only increasing and then decreasing. Now you have something more akin to simulated annealing than a GA.
    – Mushy
    Jun 12, 2014 at 17:27
  • That would happen if my selection heuristic was a fixed number and not a % as I'm using. I select the top 20%. 20% from 500 = 100. After crossover you get ~5000 children. get 20% from that and crossover and you'll get a bigger number of children and so on.. Always Increasing
    – RubenC
    Jun 12, 2014 at 17:39
  • 1
    How are you crossing over from each mating pair? Supposed to take a fit mating pair and cross over just those two to make an offspring. You don't crossover every fit chromosome with every other fit chromosome. That is not GA mating. Then you mutate in only one place of your chromosome randomly to produce the next generation. The search space decreases not increases. This is a provable algorithm that must terminate.
    – Mushy
    Jun 12, 2014 at 17:45
0

Before I answer your question I have to ask you. When you run your GA, did you actually see a gain in your solution? In other words, after each iteration the new generations that you have are actually better than the previous ones?

If you do, then I am shockingly surprised because

  1. As Mushy have pointed out very correctly: your GA is just a sugarcoating of simulated annealing (or Monte Carlo)

  2. As entropy increases because you just mix-and-match, the search space to be explored will keep increasing. And as we are well know, after a few generations, your solutions will degenerate, the only two things that I can see keep that from happening are that

    (a) you have a set of rules on any or the operations you have.. cross-over, selection, mutation, or others if you are creative enough..

    (b) divine intervention, you stick your human hands in and intervene at some or all of the iterations (done through some added heuristic in fitness function, or you can have at iteration 1 do this, 2 do that, ...)

Disclaimer: I am no expert in this area, but even people like me know you have to put heuristic in there somewhere.

Improve this answer
2
  • I already made changes using the operators so I get a good number of new individuals each iteration with good diversity. :)
    – RubenC
    Jun 15, 2014 at 22:27
  • @Rdz. You can have 5000 children. but You must select from the old generation (500) AND the children(5000), the BEST 500, so... You have your problem resolved!. Here you can see any sketchs of different types of evolution. dropbox.com/s/h8c4hy0yobtyipq/ESQUEMAS_EVOLUTIVOS.pdf and different ways of selection sensa.square7.ch/hghgf8.jpg
    – Mika Ike
    Jun 18, 2014 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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