Some analyses about the time complexity of evolutionary algorithms. (English) Zbl 1110.68171

Ding, Lixin; Yu, Jinghu

Neural Parallel Sci. Comput. 14, No. 1, 51-68 (2006).

Summary: We consider some problems about the computation time of evolutionary algorithms in this paper. First, some exact analytic expressions of the mean first hitting times of general evolutionary algorithms in finite search spaces are obtained theoretically based on the properties of Markov chain associated with evolutionary algorithms considered. Then, by introducing drift analysis and applying Dynkin’s formula, the general upper and lower bounds of the mean first hitting times of evolutionary algorithms are estimated rigorously under some mild conditions listed in the paper. Those results are general, and the analytic techniques adopted in this paper are widely instructive for analyzing the computation time of evolutionary algorithms in any search space as long as some similar mathematical arts are introduced accordingly.

MSC:

68W40	Analysis of algorithms
68T05	Learning and adaptive systems in artificial intelligence

Keywords:

computation time; drift analysis; Dynkin’s formula