IMPLICIT PARALLELISM IN GENETIC ALGORITHMS

被引:39
作者
BERTONI, A
DORIGO, M
机构
[1] INT COMP SCI INST,1947 CTR ST,SUITE 600,BERKELEY,CA 94704
[2] UNIV MILAN,DIPARTIMENTO SCI INFORMAZ,I-20135 MILAN,ITALY
关键词
D O I
10.1016/0004-3702(93)90071-I
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper is related to Holland's result on implicit parallelism. Roughly speaking, Holland showed a lower bound of the order of n3/c1 square-root l to the number of schemata usefully processed by the genetic algorithm in a population of n = c1 . 2l binary strings, with c1 a small integer. We analyze the case of a population of n = 2betal binary strings where beta is a positive parameter (Holland's result is related to the case beta = 1). In the main result, we state a lower bound on the expected number of processed schemata for all beta > 0; moreover, we prove that this bound is tight up to a constant for all beta greater-than-or-equal-to 1 and, in this case, we strengthen in probability the previous result.
引用
收藏
页码:307 / 314
页数:8
相关论文
共 8 条
  • [1] CLASSIFIER SYSTEMS AND GENETIC ALGORITHMS
    BOOKER, LB
    GOLDBERG, DE
    HOLLAND, JH
    [J]. ARTIFICIAL INTELLIGENCE, 1989, 40 (1-3) : 235 - 282
  • [2] Fitzpatrick J. M., 1988, Machine Learning, V3, P101
  • [3] Goldberg D., 1989, GENETIC ALGORITHMS S
  • [4] GOLDBERG DE, 1985, TCGA N85001 U AL REP
  • [5] GOLDBERG DE, 1989, 3RD P INT C GEN ALG, P70
  • [6] Holland J.H., 1988, EVOLUTION LEARNING C, P111
  • [7] HOLLAND JH, 1975, ADAPTATION NATURAL A
  • [8] HOLLAND JH, 1980, INT J POL ANAL INF S, V4, P217