A new approach to estimating the expected first hitting time of evolutionary algorithms

作者:

Highlights:

摘要

Evolutionary algorithms (EA) have been shown to be very effective in solving practical problems, yet many important theoretical issues of them are not clear. The expected first hitting time is one of the most important theoretical issues of evolutionary algorithms, since it implies the average computational time complexity. In this paper, we establish a bridge between the expected first hitting time and another important theoretical issue, i.e., convergence rate. Through this bridge, we propose a new general approach to estimating the expected first hitting time. Using this approach, we analyze EAs with different configurations, including three mutation operators, with/without population, a recombination operator and a time variant mutation operator, on a hard problem. The results show that the proposed approach is helpful for analyzing a broad range of evolutionary algorithms. Moreover, we give an explanation of what makes a problem hard to EAs, and based on the recognition, we prove the hardness of a general problem.

论文关键词:Evolutionary algorithms,Expected first hitting time,Convergence rate,Computational complexity

论文评审过程:Received 12 December 2007, Revised 8 July 2008, Accepted 9 July 2008, Available online 12 July 2008.

论文官网地址:https://doi.org/10.1016/j.artint.2008.07.001