Representational redundancy in evolutionary algorithms

In a regular genetic algorithm (GA), the accumulation of fit building blocks stops when the population converges. Premature convergence is caused by insufficient building-block accumulation throughout the evolution run, and the final population members may not contain the best overall combination of building blocks. It is common practice to remove duplicate-population genotypes in a steady-state GA. This allows the process of building block accumulation to continue for a greater period of time compared with a regular GA and typically results in better final-population solutions. These duplicate genotypes that appear during evolution represent only one possible avenue of diversity loss. The paper describes the allied problem of representational redundancy in the genetic encoding. Representational redundancy can lead to a form of cloaked duplicates-where a population at generation g may contain a subset P of different genotypes that each encode the one problem point p. If such isomorphic genotypes are identified (set P), and the cardinality of set P is kept to 1 (at most) at all times, then the problem seen by the GA is significantly reduced. Results on a 30 town TSP problem instance provide a comparison of various isomorphic and duplicate-removal combinations