1
$\begingroup$

Is there a minimum limit to a pool (population) size when using the genetic algorithm to solve an optimization problem? For example a population of size 2.

$\endgroup$
  • $\begingroup$ In theory you could randomly create a perfect solution on the first try so 1 is enough. That however is a terrible answer. Take a look a schema thoery for bit vectors perhaps. $\endgroup$ – Jake Dec 8 '14 at 17:07
  • $\begingroup$ What do you mean by a minimum limit? I'm having a hard time understanding what you are asking. What precisely are you asking? Why do you think there is a minimum limit to pool size? What do you mean by minimum limit? What have you tried? Where did you go wrong? What research and self-study have you done? We expect you to do a significant amount of research before asking, to show us what you've tried, and to flesh out the question a bit more -- generally, a one- or two-sentence question is usually not enough. $\endgroup$ – D.W. Dec 22 '14 at 2:59
2
$\begingroup$

I had a similar question and emailed Inman Harvey from the University of Sussex (author of Artificial Evolution: A Continuing SAGA and The Microbial Genetic Algorithm). Here is his answer (emphasis mine):

What is an optimum population size? Why?

If, like the natural world, a trillion microbes can evolve in the sea in parallel with no cost to you, then the bigger the better. In practice, on a serial machine, 10 times the pop-size costs you 10 times the time. Experience, with rather little theory, suggests that pop sizes of 30 to 100 minimum get you quite a lot of the advantages that GAs have over hill-climbing (ie pop of 2). So rule of thumb is to start here.

So basically, the bigger the population the better, but realistically you often have to make compromises to reach your goal in a reasonable amount of time. When building a genetic algorithm, you have to guess what the optimal values are for a lot of parameters. There is no good answer. Mostly there is a lot of trial and error.

$\endgroup$
4
$\begingroup$

There is no minimum to population size but it has a few drawbacks when it is too low.

when it is too low your genetic algorithm is almost going to be a deterministic or greedy algorithm and besides that you are going to lose the effect of weak answers. it has been proved that even the weakest answer can move the algorithm to a good answer. The nature of genetic algorithm is randomization and bias to better answers, when the population size is too low non of these are regarded.

When the population size is too low the population is going to lose the diversity so most likely your algorithm will fall in local optimums.

When the population size is too low you will face a few problems in Replacement step. because the population size is too low you will have to reject the unfeasible answers and it is a very bad idea for more illustration, look at this picture:

enter image description here

Let the red color be all of the answers (feasible and unfeasible), the yellow be the space of feasible answers, the green be the space of good answers that are around the optimums and the little blue spot be an unfeasible answer. As you can see an unfeasible answer is very close to the space of good answers so may be a little variation to this unfeasible answer lead to a very good answer, yes? that is why I say when the population size is too low you are going to limit yourself in Replacement step and you will have to remove the unfeasible answers and removing such answers has the bad effect that I just explained.

If the population size is too big your algorithm will be brute force! I recommended you to read the Schema Theory to know how to provide an appropriate population size.

$\endgroup$

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.