June 3, 3:00, WeH 4601

		Ari Juels (Berkeley) and Shumeet Baluja

		  "Rethinking the Genetic Algorithm"

	We develop a theoretical model  to describe the  action of the
mating phase in  Genetic Algorithms (GAs)  which employ  the crossover
operator.  We prove a characterization of the limiting distribution on
an  infinite population under  repeated crossover steps.  Our  results
lead to a reconception of the GA in the form of a new  algorithm which
we call an Ideal  Genetic Algorithm (IGA).  The IGA is  not  only more
streamlined and more theoretically elegant  than  the GA, but performs
impressively in practice.  We  describe the  performance of this   new
algorithm relative to a standard GA  on a suite of  problems including
the  DeJong  and   Ackley functions  and  several common   NP-complete
problems.