No label defined (Q3978554)

The paper investigates the application of Walsh functions to the analysis of genetic algorithms and introduces Bethke's Walsh-schema transform through the Walsh polynomials. The introduction of a polynomial form presents a common language for discussing the usual composition of mappings that occurs in genetic algorithms when coding are decoded, mapped, and passed as parameters to some objective function. This form provides an intuitive basis for visualizing the interactions of functions and codings using straightforward algebraic methods. The use of polynomials makes proofs and algebraic manipulation more direct and intuitive. The Walsh functions are presented in monomial form and fitness functions are written as a weighted sum of the Walsh functions. The analysis techniques are illustrated by several specific examples, which have demonstrated the usefulness of the methods in determining whether particular coding-function combinations should be easy or hard for a genetic algorithm. A method has been used to design fully deceptive problems. Pascal code implementing the fast Walsh transform is given as an appendix to the paper.