Convergence in Probability on a Big Class of Time-Variant Evolutionary Algorithms

Abstract

Motivated by the growing popularity of time-variant evolutionary algorithms (EAs) in solving practical problems, this paper uses spectral analyses to study convergence in probability for a general class of time-variant EAs which can be asymptotically described by reducible Markov chains with multiple aperiodic recurrent classes, covering many existing concrete case studies as specific instantiations. We provide a universal yet easily checkable characteristic for time-variant EAs satisfying global convergence, by introducing the asymptotical elitism and asymptotical monotonicity. To illustrate the effectiveness of our result, we consider four specific EAs with distinct asymptotical behavior, and recover, under even mild conditions, the state-of-the-art result as simple applications of our general theorem. Besides, simulation experiments further verify these results.