Font Size: a A A

Schema Theory And Convergence Theory For Genetic Algorithms

Posted on:2007-12-14Degree:DoctorType:Dissertation
Country:ChinaCandidate:L MingFull Text:PDF
GTID:1118360212959909Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
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.
Keywords/Search Tags:Genetic Algorithm, Schema theory, Global convergence, Convergence rate, Markov chain
PDF Full Text Request
Related items
 1 Research On Improved Genetic Algorithm Of Preventing Premature Convergence 2 The Research Of Fast And Effective Convergence Of Genetic Algorithm 3 Convergence Analysis And Improvement Methods Research Of The Double Chain Quantum Genetic Algorithm 4 The Improvement Of Genetic Algorithms And Its Convergence Analysis And The Applicationins Network Security 5 Convergence And Stability Analysis Of Artificial Bee Colony Algorithm 6 The Convergence Analysis Of Genetic Algorithm Based On Space Mating 7 Convergence Analysis Of Gravitational Search Algorithm Based On Markov Chain 8 A Research On Population Size Impaction On The Performance Of Genetic Algorithm 9 Research On The Premature Convergence And Improved Politics Of Genetic Algorithm 10 The Genetic Algorithm Parameters Adaptive Control And Convergence Research