Polynomials, Basis Sets, and Deceptiveness in Genetic Algorithms
Gunar E. Liepins
Oak Ridge National Laboratory, MS 6360 Bldg. 6025, PO Box 2008,
Oak Ridge, TN 37831-6360
Michael D. Vose
The University of Tennessee, Computer Science Department, 107 Ayres Hall,
Knoxville, TN 37996-1301
Abstract
The degree to which the genetic optimization process is transparent is in part determined by the form of the objective function. We develop two forms from first principles: polynomial forms and basis sets. We characterize three function classes that are fully easy for the genetic algorithm in terms of the polynomial representation. We generate functions of varying degrees of deceptiveness in terms of the representation provided by basis sets. We further show the relationship between these representations and the more standard Walsh polynomials.
