Implicit parallelism in genetic algorithms

DOI10.1016/0004-3702(93)90071-IMaRDI QIDQ685342zbMATH OpenDBLPWikidataFDO

Publication date 17 October 1993

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(93)90071-I

Combinatorics on words (68R15) Learning and adaptive systems in artificial intelligence (68T05) Distributed algorithms (68W15)

Review text

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.

Recommendations

Cited in

(12)

This page was built for publication: Implicit parallelism in genetic algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685342)