Complex Systems

Equivalence Class Analysis of Genetic Algorithms Download PDF

Nicholas J. Radcliffe
Department of Physics, University of Edinburgh,
Kings Buildings, Edinburgh, EH9 3JZ, Scotland


The conventional understanding of genetic algorithms depends upon analysis by schemata and the notion of intrinsic parallelism. For this reason, only k-ary string representations have had any formal basis, and nonstandard representations and operators have been regarded largely as heuristics rather than as principled algorithms. This paper extends the analysis to general representations through identification of schemata as equivalence classes induced by implicit equivalence relations over the space of chromosomes.