Hierarchical Crossover in Genetic Algorithms

Abstract

This paper identifies the limitations of conventional crossover in genetic algorithms when operating on two chromosomes of differing lengths. To address these problems, the concept of a Semantic Hierarchy (i.e. tree of meaning) of a genotype within a genetic algorithm is introduced. With this in mind, a new form of crossover operator known as Hierarchical Crossover is presented, capable of performing crossover with genotypes of different sizes, while still being functionally equivalent to standard, single-point (uniform) crossover. Various aspects and advantages of this method are discussed. Finally, an example of some results produced by an implementation is shown. Key words: hierarchical crossover, semantic hierarchy, variable-length chromosome, genetic algorithm, evolutionary design. 1. Introduction The genetic algorithm (GA) is a highly efficient and robust search algorithm based on evolution in nature (Holland, 1975). Today, GAs are widely used to evolve good solutions to hundre...