Subbiah Baskaran, David Noever

Paper #: 92-07-032

The genetic algorithm (GA) represents a powerful class of search and optimization techniques developed in analogy to genetic laws and natural selection. Best solutions are allowed to evolve subject to some fitness criteria, while internally the mechanics are left largely as a black box. For steady-state GAs, efforts directed towards finding general recursion relations have failed, thus obscuring previous comparisons with the other preferred GA based on generational reproduction. For a binary GA using steady-state reproduction, new recursion relations are found in closed form for three trial cases: (1) constant average population fitness; (2) exponentially bounded variation in average fitness; and (3) constant jump size of average fitness between successive generations. In the latter case, the generational GA is found to be a subset of the steady-state for a jump size, $K=1$. In general, the resulting equations provide the relationships of practical interest between estimated run time, problem size, and fitness ratio, along with defining a striking set of new parameters which together give a framework to quantify how the steady-state GA balances its elite selection against the need for diversity and mixing between individual alternatives. Two characteristics of the steady-state analysis are derived as a decay correlation time for the average population fitness (or half-life) and an entropy-like measure of fitness diversity and information exchange within a large population.

PDF