On The Computational Complexity Of Evolutionary Algorithms

Evolutionary Algorithms (EAs) are a kind of stochastic optimization algorithms following Darwin's principle of "Survival of the fittest". EAs have received extensive investigations since 1960s, especially in 1980s and 1990s. Years of efforts spent on designing and studying various EAs have established a branch of artificial intelligence, Evolutionary Computation (EC). Generally speaking, EC is usually considered as a branch of computer science which mainly relies on empirical investigations. That is because carrying out rigorous theoretical analysis on the complex stochastic behaviors of EAs is very difficult. To gain more insight into the stochastic behaviors of EAs so as to design efficient algorithms, this thesis focuses on the computational complexity analysis of EAs. Concretely, we study the computational complexity of EAs from broad perspectives:we not only concern the classic EAs (Genetic Algorithms) that are close enough to practical algorithms, but also concern a novel type of EAs that are popular in academia; we not only study EAs on traditional static optimization problems, but also investigate EAs on dynamic optimization problems; we not only concern the theoretical investigation of the algorithms, but also care about the practical implications of theoretical results. The main contributions of this thesis are summarized as follows:(1) We study the computational complexity of population-based classic EAs. As shown in the first chapter, early theoretical time complexity investigations often focused on simplified but impractical EAs. Unlike these studies, we concentrate on population-based EAs that are closer to practical algorithms utilized in real-world applications. To be specific, we propose a novel approach for analyzing the time complexities of population-based EAs, which will be utilized to analyze classic EAs with different population sizes on both unimodal and multimodal optimization problems. In EC field, this is the first time that a approach dedicated to the time complexity analysis of (N+N) classic EAs (where the parent size equals the offspring size) is proposed. It is also the first time that the impact of different population sizes on the performances of EAs is investigated theoretically.(2) We study the computational complexity of a novel type of EAs named Es-timation of Distribution Algorithms (EDAs). Unlike EAs that evolve populations di-rectly, EDAs indirectly evolves populations by employing online-adjustable probabilis-tic models. Over the past two decades, various EDAs have been proposed and studied. However, most investigations were carried out on the basis of empirical observations. Although some scholars have concerned the convergence properties of EDAs, there is no investigation that analyzes successfully the time complexity of population-based EDAs by rigorous mathematical discussions. In this thesis, we propose a general ap-proach to analyzing the time complexity of EDAs. Following this approach, we an-alyze the time complexity of an instance of EDAs, Univariate Marginal Distribution Algorithm (UMDA). In addition to several time complexity results, it is discovered that the relaxation on the probabilistic model of UMDA is effective for promoting the performance of UMDA, and is necessary for avoiding premature convergence of the probabilistic model. Our investigation has made exceptional contributions to the com-putational complexity of EDAs:this is the first time that a general approach is proposed for analyzing the computational complexities of population-based EDAs; this is also the first time that the time complexity of a population-based EDA is analyzed rigorously.(3) We study the impact of time-variable mutation rate schemes on the perfor-mance of a classic EA in the context of dynamic optimization problems. In EC field, many researchers expect that time-variable mutation rate schemes can potentially pro-mote the performance of classic EAs. However, according to our computational com-plexity analysis, on certain dynamic optimization problems, any time-variable mutation rate scheme is not significantly better than fixed mutation rates. According to this result, this thesis suggests that when solving dynamic optimization problems in the absence of prior knowledge, it would be better to give up self-adaptive mutation rate schemes, and follow the well-known Occam's razor by utilizing a fixed mutation rate. In EC field, it is the first time that some general results for any time-variable (e.g., self-adaptive) mutation rate scheme are given and proven rigorously, which substantially increases the understanding of the relationship between time-variable mutation rate scheme and the performance of EA, and the role of mutation in the context of dynamic optimization problems.