A Comparison of the Fixed and Floating Building Block Representation in the Genetic Algorithm

被引:31
作者
Wu, Annie S. [1 ]
Lindsay, Robert K. [2 ]
机构
[1] Univ Michigan, Artificial Intelligence Lab, Ann Arbor, MI 48109 USA
[2] Univ Michigan, Mental Hlth Res Inst, Ann Arbor, MI 48109 USA
关键词
Genetic algorithm; noncoding segment; intron; building block hypothesis; Royal Road function; symbolic regression;
D O I
10.1162/evco.1996.4.2.169
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This article compares the traditional, fixed problem representation style of a genetic algorithm (GA) with a new floating representation in which the building blocks of a problem are not fixed at specific locations on the individuals of the population. In addition, the effects of noncoding segments on both of these representations is studied. Noncoding segments are a computational model of noncoding deoxyribonucleic acid, and floating building blocks mimic the location independence of genes. The fact that these structures are prevalent in natural genetic systems suggests that they may provide some advantages to the evolutionary process. Our results show that there is a significant difference in how GAS solve a problem in the fixed and floating representations. Genetic algorithms are able to maintain a more diverse population with the floating representation. The combination of noncoding segments and floating building blocks appears to encourage a GA to take advantage of its parallel search and recombination abilities.
引用
收藏
页码:169 / 193
页数:25
相关论文
共 21 条
[1]   EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH [J].
AHO, AV ;
CORASICK, MJ .
COMMUNICATIONS OF THE ACM, 1975, 18 (06) :333-340
[2]  
Bell G. I., 1988, COMPUTERS DNA
[3]   DO GENES-IN-PIECES IMPLY PROTEINS-IN-PIECES [J].
BLAKE, CCF .
NATURE, 1978, 273 (5660) :267-267
[4]  
Curtis H., 1983, BIOLOGY
[5]  
Forrest S., 1993, FDN GENETIC ALGORITH, V2, P109
[6]   GENES-IN-PIECES REVISITED [J].
GILBERT, W .
SCIENCE, 1985, 228 (4701) :823-824
[7]   THE EXON THEORY OF GENES [J].
GILBERT, W .
COLD SPRING HARBOR SYMPOSIA ON QUANTITATIVE BIOLOGY, 1987, 52 :901-905
[8]   WHY GENES IN PIECES [J].
GILBERT, W .
NATURE, 1978, 271 (5645) :501-501
[9]  
GILBERT W, 1991, WIST SYMP S, V4, P155
[10]   CORRELATION OF DNA EXONIC REGIONS WITH PROTEIN STRUCTURAL UNITS IN HEMOGLOBIN [J].
GO, M .
NATURE, 1981, 291 (5810) :90-92