EQUIVALENCE CLASS ANALYSIS OF GENETIC ALGORITHMS
Nicholas J. Radcliffe · 1991
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 non-standard representations and operators have been regarded largely as heuristics, rather than 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. 1 Introduction Intrinsic parallelism 1 ---the phenomenon whereby each n- gene chromosome is an instance of 2 n schemata---has been the key theoretical tool for analysing and understanding genetic algorithms. As conventionally understood, it provides powerful arguments for using binary genes in order to maximise the degree of intrinsic parallelism available. Not all problems, however, find natural expression as binary---or indeed, k-ary---strings. Examples in this class ...