Where genetic drift, crossover and mutation play nice in a free mixing single-population genetic algorithm
Susan Khor · 2008
A variant of the HIFF problem called HIFF-M is compared with HIFF-D - the discrete version of the original HIFF problem. By the SWO statistic, HIFF-M is less epistatic than HIFF-D. Using operator specific FDC measurements, we find that HIFF-M is less crossover-easy and less mutation-hard than HIFF-D. Nevertheless, from our experiments, HIFF-M is still difficult for an unspecialized hill climber and for a mutation-only multi-individual stochastic search algorithm to solve efficiently and reliably. HIFF-M also has a more symmetrical fitness distribution than HIFF-D thus increasing the possibility of useful neutral spaces at higher levels of fitness. Notably, explicit mechanisms to reduce diversity loss made it more difficult for crossover-only GAs to solve HIFF-M than HIFF-D. Over all configurations that we experimented with, the best search performance for HIFF-M was obtained with upGA - a single-population, steady-state GA which uses random parent selection, 1-2 point crossover and no explicit diversity preservation mechanism. This result suggests that HIFF-M has the kind of epistasis to create fitness landscapes where genetic drift, crossover and mutation work well together to balance the exploitative and explorative facets of a GA.