Diploidy and Overdominiance in Genetic Algorithms

Diploidy talk for Miniconference on Optimization, UM, 9/12/96

Diploidy and Overdominiance in Genetic Algorithms
As presented by Alden H. Wright

Garrett Bidwell
BBN Systems and Technologies
Cambridge, MA
Alden H. Wright
Computer Science Dept.
The University of Montana  
Missoula, MT 59812-1008 


Genetic algorithms (GAs) are search and optimization procedures based on the mechanics of natural selection. They encode the parameters of a problem in a single-stranded or haploid binary string. However, most haploid organisms in the biological world are simple lifeforms such as bacteria. More complex lifeforms such as plants, animals, and humans rely on a diploid chromosome, which contains homologous chromosome pairs at each locus. When chromosome pairs contain different values (alleles) at the same location, a dominance operator usually resolves the conflict. Overdominance refers to the situation where an individual with different alleles at a location has higher fitness than individuals with the same allele at that location. Biological models show that overdominance can maintain diversity at that location. The primary motivation for incorporating diploidy and dominance into GAs is to increase population diversity and thus avoid premature convergence to a suboptimal solution. In a multimodal fitness landscape, this added diversity may enable a GA to avoid convergence to local optima. In the case of non-stationary function optimization problems, the objective is to use a diploid GA to adapt more readily to changing requirements and thus exhibit improved performance over that of the haploid GA. This talk will discuss application of diploidy to genetic algorithms. Previous empirical work has shown that methods based on artificial diploidy can help to increase population diversity. We discuss a new method of applying diploidy to genetic algorithms that includes overdominance. We show analytically and empirically that a diploid GA is capable of maintaining greater population diversity than the haploid GA, and that it is better able to avoid complete convergence than the haploid GA. In addition, empirical tests are performed to demonstrate the effectiveness of a diploid GA in multimodal and non-stationary environments.