×

zbMATH — the first resource for mathematics

Some analyses about the time complexity of evolutionary algorithms. (English) Zbl 1110.68171
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
PDF BibTeX XML Cite