A Simple Representation Technique to Improve GA Performance
Steven L. Keast · 2003
This paper proposes a new phenotype-to-genotype encoding representation technique that helps in several areas of Genetic Algorithm (GA) performance. First, it makes it possible to eliminate the problem of illegal gene values from being generated from the crossover operator in most situations. It does this by encoding the traits within the chromosome in such a way as to guarantee no illegal traits can be created. Next, it can increase the variability of offspring, even if the parents are identical, thus increasing the likelihood that the GA will not get stuck on sub-optimal solutions. Finally, it increases the GA’s performance by allowing a more rapid search through the hypothesis space. This is achieved by the prior mentioned genotype encoding technique and the variation in offspring that is seen due this encoding scheme. A new operator called Cloning is introduced that is a key contributor to the performance of the GA. Cloning creates new individuals that have gene values identical to the hypotheses from which they were cloned, but with dramatically different gene representations. This is possible due to the technique used to encode the individual traits. By cloning hypotheses, later crossover operations create offspring that can be very different than their parents, thus increasing the speed in which the hypothesis space is searched. Finally, this paper discusses the test results of the GA and characterizes its performance. Areas covered include investigating the GA’s performance when Tour size, population size and cloning rate are varied.