Schema Theory And Convergence Theory For Genetic Algorithms

In the past, the research on genetic algorithms has mainly been focused on designing new algorithms, improving existing algorithms and applying the existing algorithms to real world problems. However, the theoretical results on schema theory and convergence theory, two important theoretical issues on genetic algorithms, are relatively few. In this dissertation, these two important problems were studied. The main contributions in this dissertation are as follows:1. The schema theory for one-point crossover is proposed. For one-point crossover, only the survival action to schema is mainly discussed in the existing schema theory. There are few works tackling the construction action to schema. Furthermore, there exist some limitations in these research results on schema construction theory. For example, the effects of the schema survival and the schema construction by crossover can not be distinguished. In order to analyze the effects of the survival and construction of crossover, respectively, a ternary representation for schema is proposed in this dissertation, through which the effects of the survival and construction of a schema can be easily distinguished. As a result, not only the effects of the schema survival and the schema construction by crossover can be analyzed separately, but also the effect of their united action can be analyzed.2. The schema theory for uniform crossover is presented. Uniform crossover is one of the most popular crossovers. In this dissertation, the effects of the schema survival and the schema construction of uniform crossover are analyzed based on ternary representation. Subsequently, the united action of schema survival and construction of uniform crossover is discussed too. Moreover, the results of the schema survival and schema construction between one-point crossover and uniform crossover are compared, respectively.3. The aforementioned research results on one-point crossover and uniform crossover are generalized to any crossover operator, and the corresponding schema theory for arbitrary crossover is presented.4. A model for a class of genetic algorithms is proposed. This model includes manygenetic algorithms besides the canonical genetic algorithms. By using Markov chain model, the global convergence of this class of genetic algorithms is proved. Moreover, the convergence rate of this class of genetic algorithms is estimated, and the estimation method is more applicable and different from the existing methods.5. The convergence rate of another class of genetic algorithms without the elitist scheme is discussed. One special minorization condition of Markov chain is used to estimate its convergence rate, which extends the existing results.