The Walsh Transform and the Theory of the Simple Genetic Algorithm

The Walsh Transform and the Theory of the Simple Genetic Algorithm

Michael D. Vose    
Computer Science Dept.    
The University of Tennessee    
Knoxville, TN 37996-1301    
vose@cs.utk.edu    

Alden H. Wright
Computer Science Dept. 
The University of Montana 
Missoula, MT 59812-1008 
wright@cs.umt.edu

ABSTRACT

This paper surveys a number of recent developments concerning the
Simple Genetic Algorithm, its formalism, and the application of the
Walsh transform to the theory of the Simple Genetic Algorithm.

Introduction

The Walsh transform has a history of applications to signal processing
and pattern recognition.  Genetic algorithms are also being
successfully applied to problems in these areas.  This paper is about
both the Walsh transform and genetic algorithms, though not as they
pertain to applications, but as how they relate to each other.  Our
subject is the mathematical formalization of the Simple Genetic
Algorithm and how the Walsh transform appertains to its theoretical
development.

We begin with a general description of a heuristic search method, {\em
Random Heuristic Search}, of which the Simple Genetic Algorithm (SGA)
is a special case. We then specialize random heuristic search to
obtain the SGA.  Next the Walsh transform is introduced and we present
a series of results which explore its relevance to theoretical aspects
of the SGA.

This paper surveys topics, many of which which have appeared in
electronic bulletin boards, technical reports, conference
presentations, books, or journal articles.  They have not, however,
been integrated into a coherent account before.  Several results will
be sketched, by leaving technicalities to the reader, and others will
be summarized.  Complete details will eventually be available in book
form (together with additional material) in ``The Simple Genetic
Algorithm: foundations and theory'' to published by MIT press next
year.