REDUNDANT CODING OF AN NP-COMPLETE PROBLEM ALLOWS EFFECTIVE GENETIC ALGORITHM SEARCH

In this paper a Genetic Algorithm is used to search for minimal mutation phyletic trees, an NP-complete problem. We depart from the 'classical' G.A. approach to facilitate coding. A clear separation is made between a phenotype and a genotype. The fitness is derived from the phenotype, which represents a tree. The genotype, on which the Genetic Operators are applied, takes the form of a 'dissimilarity-matrix' i.e. a redundant non-(bit)string representation. We show that the 'fitness-landscape' defined by this genotype/phenotype representations allows effective G.A. search.