3
$\begingroup$

I'm currently writing my thesis, which uses genetic algorithms at some point. Now I need to define some parameters for the genetic algorithm

I know that, because of the No Free Lunch Theorem there is no optimal parameter configuration for all problems.

However I do need some default parameters, because finding the optimal parameters is out of scope of my paper. Also I don't want to use random values as these parameters.

I would prefer to reuse parameters used in some well trusted sources in the field of genetic algorithms. Then I could rely on these cited sources and reuse these parameters.

I need default values for these parameters:

  • population size
  • mutation rate
  • number of generations

I searched for papers, but am not sure which paper is well-known. I'm looking for papers that are well-known and have these parameters used. A online available pdf is preferable.

$\endgroup$
  • 1
    $\begingroup$ What's the point of reusing these parameters? If your problem is different from the problem you're copying the parameters from, they are no better than random guesses. Why don't you "hand-optimize" the parameters instead by trying a few different values? $\endgroup$ – adrianN Jul 3 '13 at 14:13
  • $\begingroup$ Good default values for 10 parameters would likely be terrible for 10000 parameters. It greatly depends on your data, these are things to play around with. That said, any decent resource should be able to give you some generic starting values / ranges and explain the effects of changing them. I'm sure if you look for "genetic algorithm how to pick population size" (and the same for the others) you'll get some promising results. $\endgroup$ – Dukeling Jul 3 '13 at 14:37
4
$\begingroup$

As you say, there are no universal parameter settings, which means that you won't find a source that cites any such settings. Instead, you find some papers who tune the parameters to their particular problem, and you find many, many others that simply take a "standard" set of parameter settings without much attempt to justify them. In that case, it's not like there's a single authoritative source you can cite -- it's more like bunches of people sort of converge on parameters that seem common to everyone. The best you can really do is to say something like "the parameter values were chosen as being commonly observed in the literature."

Also, it depends not just on the problem, but on the particular structure of your GA. CHC (Eshelman, 1991), for example, is usually used with a population size of 50 (very small by typical standards) and has no conventional mutation operator, but it adds other pieces that make up for it. Genetic programming practitioners often use population sizes in the thousands and use very high mutation rates.

For a "standard GA", if you were to use a population size of 100-200, a mutation rate of 1/L (with L=the length of your encoding, assuming it's discrete), and "enough" generations (more on that in a second), no one would question things too much. However, aside from just citing a random selection of papers, there's not a lot you can point to as justification. Also, some light parameter tuning is almost certainly a better idea if you can afford it at all.

For generation count, the basic rule is to go until you either exhaust the amount of time you have to allot to it or until the algorithm converges, whichever comes first. Of course, these are interdependent. Raising the population size and/or raising the mutation rate will slow convergence, so you still need to tune parameters for the best results.

If you're doing this for research purposes at least, you should also measure the runtime in fitness function evaluations rather than generations. The reason is that if my algorithm finds a solution in N generations, you can almost certainly find a better solution in N generations if you just multiply the population size by 100 or so. You'll get to do about two orders of magnitude more searching than I could do, so the comparison is unfair. Reporting generations used is an automatic red flag in a paper unless the other GA parameters are controlled to a degree that we can be sure that the comparison is apples to apples. Measuring evaluations is much more tightly correlated to wall-clock time than measuring generations, and should essentially always be preferred.

$\endgroup$
  • $\begingroup$ After reading your answer I found de jong books evolutionary computing which has a lot of the parameters you described as commonly observed in literature. Also I didn't think of the problematics with the generation count. A lot of insights. Thank you very much. $\endgroup$ – user8992 Jul 3 '13 at 15:07
1
$\begingroup$

For population size you should see my other answer.

For mutation I found a reference in this paper (page 13):

The rule of thumb is that if the selection pressure used is that associated for instance with the Microbial GA using tournaments of size  the optimal mutation rate is in the region of one mutation per genotype after taking account of any junk or neutral mutations

Finally, the default value for the number of generations is, as deong pointed out, whatever available time you have that will result in a reasonable solution to your problem or until your genotypes converge to an optimum (however this is tricky as they could be converging to one of several local optima).

$\endgroup$
0
$\begingroup$

as indicated by the other answer there are no standard parameters unless you are working with models that have been created by others or attempting to mimic them. however heres another angle on this. you ask specifically about 3 key GA parameters. there are standard indicators obtained from GA evolution of whether your parameters need to be adjusted.

  • population size — if your population is too small, the improvement per iteration in the fitness function will be low (measured as the best candidate solutions or the average of solutions). if you increase the population size and the fitness function increases faster then its a sign its suboptimal. also there is a point where increasing the population size does not improve the rate of increase in the fitness function.

  • mutation rate — if its too low the algorithm will not cover the search space much. if its too high then good candidate solutions will be perturbed and pushed into worse solutions. again basically a rough measure is the rate of improvement in the fitness function.

  • number of generations - the number of generations is related to improvement in the fitness function. a fitness function usually shows major improvement in early generations and then asymptotically approaches an optimum. after enough trend you can determine what the theoretical optimum is from fitting/extrapolating this line, and how much improvement per time is possible.

$\endgroup$
0
$\begingroup$

This question reminds me of a whole area called "meta-optimization". Where the objective is to find suitable parameter settings for a particular evolutionary search algorithm (for a specific problem), and the search is done by another "upper-level evolutionary" process. If your problem does not involve costly function evaluations, then such type of "meta-optimization" could be easily implementable. So far I remember, ECJ already offers such type of implementations.

The settings are inherently dependent on the nature of the problem that you are trying to solve. However, population size could be "somewhat" estimated, see this paper for more details.

$\endgroup$

Your Answer

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