Unified Approach to (1+1) EA on Discrete Linear Functions

We consider the runtime property of discrete linear functions in (1+1) Evolutionary Algorithms, PO-mutation and Jansen's model, PO-EA. We analyze the process of evolution. This study was motivated by the paper of Jansen treating the runtime property of (1+1) EA on monotonic functions by means of probabilistic theory. As linear functions are special case of monotonic function, we analyze their behavior. We show that the (1+1) EA can obtain an optimum solution at a stable hitting time for discrete liner functions. When the mutation rate is weak, on the order of 1 / l, most monotonic functions behave similarly and can be approximated well by the PO-mutation model.