LAUSR

Evolutionary algorithms (EAs) are randomized optimization search techniques, and the theoretical study of the first hitting time is very important in the practical applications of EA. We investigate the first hitting time of Leading Ones (LO) problem theoretically on Random Local Search (RLS) algorithm and (1 + 1)EA by absorbing Markov chain. This paper reports the calculation method of the first hitting time on LO problem with (1 + 1)EA and RLS. We found that the results only depend on the length of string, and the hitting times can be given approximately by the quadratic function. In the numerical experiments, we showed the agreement between the results of the practical calculation and the theoretical results. Our results give the good example to predict the running time of the practical EA calculations by Markov chain method.