Lower Bounds on the Population Size in Genetic Algorithms and Implicit Parallelism Revisited

• Author(s) / Creator(s)

  • Gao, Yong

• Technical report TR02-20. Determining an appropriate population size is very important in genetic algorithms and is closely related to the principle of implicit parallelism. In this paper, the problem of sizing the population is formulated as that of minimization of sampling errors. Two sampling error criteria are proposed for bounding the population size in genetic algorithms. A theorem on the sampling error of genetic algorithms over a general class of subsets in the individual space is established. Applying the result to the class of schemata, we derive two kinds of lower bounds on the population size and present the principle of implicit parallelism from a new perspective. It is further shown that the lower bound can also result in the monotonic convergence of the correct schema. The lower bounds also depict how the necessary population size is related to the mutation probability and some population statistics. | TRID-ID TR02-20

• Date created

  2002

• Subjects / Keywords

  • Uniform Strong Law of Large Numbers
  • Implicit Parallelism
  • Genetic Algorithms
  • Population Size

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3JS9HF82

• License

  Attribution 3.0 International