Implicit parallelism in genetic algorithms
type: Item
instance of: scholarly article
title: Implicit parallelism in genetic algorithms
zbMATH Open document ID: 0781.68093
DOI: 10.1016/0004-3702(93)90071-I
author: Alberto Bertoni
author: Marco Dorigo
published in: Artificial Intelligence
publication date: 1993-10-17T00:00:00Z
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.
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 417264
Wikidata QID: Q56972201
MaRDI profile type: Publication
cites work: Q4692508
DBLP publication ID: journals/ai/BertoniD93
description: scientific article; zbMATH DE number 417264