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
gbidwell@bbn.com
     and 
Alden H. Wright
Computer Science Dept.
The University of Montana  
Missoula, MT 59812-1008 
wright@cs.umt.edu 

ABSTRACT:
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.