Evolutionary Computation:Theoreti- Cal Analysis And Learning Algorithms

As the computing technology stepped into its rapid developing period in 1960s, some researchers raised the interest of simulating biologic evolution process in computers, and initially proposed several simulation algorithms. These algorithms together with their later variants are nowadays under the unified term evolutionary algorithms (EAs). EAs are usual-ly used as optimization techniques. They have a simple algorithm structure, can easily in-corporate with domain-dependent heuristics, and have shown extraordinary performance on many real-world problems. Therefore, EAs have been applied in many domains such as sys-tem optimization, industrial design, and data mining. However, since the EAs are originated from simulation biological evolution and involve sophisticated stochastic behaviors, it is hard to perform theoretical analysis, resulting the lack of solid theoretical foundation. Partic-ularly, the performance of EAs as optimization techniques requires theoretical supports. The lack of theoretical foundation injures the further development of EAs, and blocks the appli-cation of EAs in problems where serious algorithms are required. This dissertation focuses on the theoretical analysis of EAs. Moreover, standing on top of the analysis, a new learning algorithm is proposed. The main contributions of the dissertation are summarized as follows.(1) A time complexity analysis approach based on convergence rate is proposed, which is used to derive the lower bounds of several EAs on a hard problem.Most of the previous analysis of EAs used ad hoc approaches to study simple algo-rithms on simple problems. To tackle with this problem, we propose a general approach to allow the analysis of a wide range of EAs on a wide range of problems, which is built on a bridge connecting two theoretical properties of EAs, i.e., the convergence rate and the time complexity. Using this approach, several EAs are analyzed on a hard problem, and nontrivial lower bounds are derived.(2) A time complexity analysis approach based on Markov switching theorems is proposed, which is used to analyze the effect of crossover and population on EAs.Many practical EAs have a sophisticated designed, which causes it hard to perform a fine analysis through existing approaches. To tackle with this problem, we propose the Mar- kov switching approach, which stand on Markov switching theorems derived in this disserta-tion. The proposed approach reduces the analysis of a sophisticated EA to the analysis of a simple EA plus the one-step transition behavior of the sophisticated one. Using this approach, the effect of a crossover on the performance of an EA is analyzed on the OneMax problem for the first time, also, a tight complexity lower bound of a population-based EA on the OneMax problem is obtained for the first time.(3) An approximation performance analysis approach based on isolation functions is proposed, which derives conditions for EAs to obtain good approximation solutions.EAs are commonly used for solving approximate solutions in practice, while the ap-proximation performance is hard to analyze and thus there are only a few results on this topic, In this dissertation, we first propose an EA framework based on isolation functions, in which different isolation function implement the framework as different EAs. Through this frame-work, we derived conditions under which EAs can obtain good approximation solutions. Using this approach, the approximation performance of EAs on the Set Cover problem is studied. The result shows that EAs can achieve the currently best-achievable results. Moreo-ver, the analysis also discloses how EAs can be superior to commonly used greedy algo-rithms.(4) An EvoBoost framework and its multi-core implementation are proposed, which is use to tackle the positive class expansion with single snapshot problem.The family of Boosting algorithms is a kind of the state-of-the-art learning algorithm. However, the embedded greedy optimization of Boosting algorithms makes them hard to utilize the modern multi-core computing architecture. To handle this problem, motivated by our analysis that EAs are superior to greedy algorithms, EvoBoost framework and it mul-ti-core implementation is therefore proposed, which does not keep the advantages of Boost-ing algorithms, but also well utilize the multi-core architecture to accelerating the computa-tion due to the inherited loose coupling structure from EAs. Furthermore, EvoBoost is ap-plied in the problem named positive class expansion with single snapshot, and leads to better performance than usual learning approaches.