page 1  (23 pages)
2to next section

Using Markov Chains to Analyze GAFOs

Kenneth A. De Jong
Computer Science Department
George Mason University
Fairfax, VA 22030
E-mail: kdejong@gmu.edu

William M. Spears
Diana F. Gordon
Navy Center for Applied Research in Artificial Intelligence
Code 5510
Naval Research Laboratory
Washington, D.C. 20375-5320
E-mail: spears,gordon@aic.nrl.navy.mil

Abstract

Our theoretical understanding of the properties of genetic algorithms
(GAs) being used for function optimization (GAFOs) is not as strong as we would like. Traditional schema analysis provides some first order insights, but doesn't capture the non-linear dynamics of the GA search
process very well. Markov chain theory has been used primarily for
steady state analysis of GAs. In this paper we explore the use of transient Markov chain analysis to model and understand the behavior
of finite population GAFOs observed while in transition to steady
states. This approach appears to provide new insights into the circumstances under which GAFOs will (will not) perform well. Some
preliminary results are presented and an initial evaluation of the merits of this approach is provided.