A Markov Chain Analysis of Genetic Algorithms with a State Dependent Fitness Function
Herbert Dawid
Department of Operations Research and Systems Theory,
Vienna University of Technology,
Argentinierstr. 8/119, A-1040 Vienna, Austria
Abstract
We analyze the behavior of a Simple Genetic Algorithm (GA) in systems where the fitness of a string is determined by a function depending on the state of the whole population. The GA is modeled by a Markov chain and we conclude that for small mutation probabilities the limit distribution will put almost all the weight to the homogeneous states. We derive conditions under which a homogeneous state will be stable for the dynamics representing the expected behavior of the GA. Interpreting the state dependent fitness function as an economic system we prove that any strict economic equilibrium will be asymptotically stable with respect to the expected behavior of the GA.