A New Approach to Estimating the Expected First Hitting Time of Evolutionary Algorithms

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Machine Learning

The {it expected first hitting time} is an important issue in theoretical analyses of evolutionary algorithms since it implies the average computational time complexity. In this paper, by exploiting the relationship between the convergence rate and the expected first hitting time, a new approach to estimating the expected first hitting time is proposed. This approach is then applied to four evolutionary algorithms which involve operators of mutation, mutation with population, mutation with recombination, and time-variant mutation, respectively. The results show that the proposed approach is helpful for analyzing a broad range of evolutionary algorithms.