Implicit parallelism in genetic algorithms (Q685342)

This paper is related to Holland's result on implicit parallelism. Roughly speaking, \textit{J. H. Holland} [Classifier Systems and Genetic Algorithms, Artif. Intell. 40, No. 2, 235-282 (1989)] showed a lower bound of the order of \({n^ 3\over c_ 1\sqrt l}\) to the number of schemata usefully processed by the genetic algorithm in a population of \(n=c_ 1\cdot 2^ l\) binary strings, with \(c_ 1\) a small integer. We generalize the result analyzing the case of population of \(n=2^{\beta l}\) binary strings where \(\beta\) is a positive parameter (Holland's result is related to the case \(\beta=1)\). In the main result, for all \(\beta>0\) we state a lower bound on the expected number of processed schemata; moreover, we prove that this bound is tight up to a constant for all \(\beta\geq 1\) and, in this case, we strengthen in probability the previous result.