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

Yang Yu, Zhi-Hua Zhou

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.

Subjects: 1.9 Genetic Algorithms

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.