The Problems with Counting Ancestors in a Simple Genetic Algorithm

摘要

The ease with which the genetic algorithm can generate good solutions to challenging optimization problems has resulted in a tendency for researchers to overlook the easily gathered and largely untapped raw data present in the ancestral relationships that guide a population to convergence. This article introduces the notion of a lineage tree structure and associated ancestor count measure that reveals unexpected regularities when studying instances of a simple genetic algorithm applied to three disparate problems. Consequently, a series of explanatory models was constructed to identify the components of the underlying evolutionary mechanism that may be responsible for the commonalities observed. These components (exponential growth of member parentage and inbreeding caused by the appearance of duplicates and shared ancestries) place constraints on the number of ancestors that a solution may have; an insight that may prove valuable for future analysis of the behavior of the genetic algorithm.