Stephanie Forrest

Stephanie Forrest - FGA


Foundations of Genetic Algorithms

This project is in collaboration with Melanie Mitchell. In this work, we have investigated a number of anomalous results (some reported in the literature and some resulting from our own investigations) in which the genetic algorithm fails to perform as theory predicts. In each case, we have found interesting explanations for these failures, which have led us to think more deeply about how the algorithm really works (Forrest and Mitchell, 1991; Mitchell et al., 1992; Forrest and Mitchell 1993a; Forrest and Mitchell 1993b). We have recently described and analyzed an idealized version of the genetic algorithm (the IGA) which contains the features of genetic algorithms that we believe are most important to its success—independent sampling, combining good partial solutions through crossover, and preserving these combinations through selection. Our mathematical analysis provides a lower bound on the time to discover an optimal solution for one class of problems. We performed a similar analysis for hillclimbing, which is a step towards predicting the conditions under which the genetic algorithm will outperform hillclimbing and vice versa (Mitchell et al., 1993a). An important area of future research is to study what parameter settings and versions of the genetic algorithm allow it to conform most closely to the IGA.