Markov chain analysis of evolutionary algorithms for monotonic functions

The theoretical investigation of evolutionary algorithms (EAs) has increased our knowledge of the computational mechanism of algorithms. In this paper, we report the convergence properties of an algorithm that is a variant of (1+1) EA, partially ordered evolutionary algorithm (PO-EA), which was initially designed for representing the evolutionary behaviors of all linear functions. Recently, PO-EA has been expected to give a model for deriving an upper bound on the expected hitting time of EA for monotonic functions. A monotonic function is a pseudo-boolean function whose value increases by flipping positive number of zeros to one. This study makes use of Markov chain model to analyze the movement of PO-EA. We divide PO-EA into two parts, PO-mutation and ZeroMax models, and study their mutation rate dependences of the expected hitting times.