An analysis on genetic algorithms using Markov processes with rewards

Genetic algorithms (GAs) can be regarded as Markov processes. In this paper, we propose a new method to analyze GAs using Markov processes with rewards, which are extensions of Markov processes. The system receives a reward associated with the transition among states in a Markov process with rewards. We can derive the expected value of fitness by regarding differences of fitness between two generations as rewards. We calculate the expected maximum and mean fitness of some basic models. We compare maximum and mean fitness to find the optimum mutation rate based on our results. We also extend our analyses to more general models by computer simulations and by introducing approximation of the mutation rate.