Analysis of genetic algorithms from a global random search method perspective with techniques for algorithmic improvement
Charles Peck · 1994
Genetic algorithm behavior is described in terms of the construction and evolution of the sampling distributions over the space of candidate solutions. This novel perspective is motivated by analysis indicating that the schema theory is inadequate for completely and properly explaining genetic algorithm behavior. Based on the proposed theory, it is argued that the similarities of candidate solutions should be exploited directly, rather than encoding candidate solutions and exploiting their similarities. Proportional selection is characterized as a global search operator, and recombination is characterized as the search process that exploits similarities. Numerous novel recombination operators are proposed and found to result in more effective and efficient search than their traditional counterparts on a suite of test functions. Sequential algorithms and many deletion methods are also analyzed. Various forms of elitism are also proposed and characterized. By properly constraining local search breadth, convergence of genetic algorithms to a global optimum can be proved. Many issues associated with applying genetic algorithms to noisy fitness functions are addressed. Based on this analysis, genetic algorithm variants are proposed and shown to exhibit improved performance in the presence of noise. The proposed theory is used in the design of a genetic algorithm-based input selection system for application to a neural network-based function approximator. This system is found to result in improved input lists for the prediction of Space Shuttle Main Engine parameters.