| Genetic algorithms(GAs), as a kind of heuristic search and optimization techniques, have been applied to many domains successfully. However, after "No Free Lunch"(NFL) theorems were proposed, applications of GAs were impacted. Therefore, the study on GA-hardness has been paid more and more attention. In addition, the concept, "fitness landscapes", which came from biology, has been applied to GAs, and became an important tool to describe the characteristics of the fitness space and to analyze the performance of GAs. Under this circumstances, we discussed the principles of fitness landscapes of GAs, and analyzed the GA-hardness based on fitness landscapes. Furthermore, we proposed several methods to measure GA-hardness, or to solve some difficult problems for GAs.The main contents of this dissertation are as follows:1. We reviewed the origin and development of GAs, summarized characteristics of GAs, analyzed the research status about the principles and applications of GAs, and further pointed out some problems, which needed to be solved currently. Meanwhile, we probed into the origin of the notion, "fitness landscapes", and discussed its application status. We also analyzed the background, development, and current situation of the study on GA-hardness.2. We investigated the principles of the fitness landscape and its application to GAs in detail. Firstly, from the viewpoint of graph theory, we analyzed fitness landscapes, and described the random walk correlation function, then we deduced the equation to compute the correlation length. Secondly, we performed the time series analysis for the random walk model on the fitness landscape to discover more information about the fitness landscape, and demonstrated the modeling process based on the NK-landscapes. Thirdly, we proposed the concept of the fitness landscape of schemata, and implemented statistical analysis for fitness landscapes of schemata. Lastly, the dynamic fitness landscape was analyzed in brief.3. We identified some factors which may cause GA-hardness. At the beginning, we discussed the NFL theorems and their significance of the study on GA-hardness. Subsequently, we concluded some important definitions and theorems for GA deceptive problems, and analyzed schema deceptiveness' influence on GA-hardness. Then, we investigated the epistasis of GAs using Walsh-Schema transform, and further evaluated the epistasis order for the continuous function optimization problems. Meanwhile, for the statistical analysis model of epistasis introduced by Davidor, we discussed epistasis variance and epistasis correlation, and further induced two theorems, of which we gave strict mathematic proof. Additionally, several test problems with epistasis for GAs were described. Finally, we studied systematically some other reasons for GA-hardness, such as multi-modal functions, the ruggedness of fitness landscapes, selection of genetic operators, premature problems, control of genetic parameters, etc..4. We probed into some methods to measure GA-hardness. First of all, we compared three approaches: FDC, correlation length, and epistasis measures. Next, we proposed the method of fitness sequence statistics analysis, to directly explore characteristics of fitness landscapes, and to further measure the extent of GA-hardness. We also introduced the fractal theory to study fitness landscapes, and analyzed the complexity of fitness landscapes by computing the correlation dimension based on random walk fitness time series. Because traditional epistasis measure methods can only reflect the extent of interaction between all genes in the chromosome, we used correlation length analysis and epistasis measures on the fitness landscapes of schemata to test the extent of interdependence between some certain gene loci in study. In addition, we formulated measures of GA-hardness for GAs with real-valued encoding, and advanced the method of the first order function approximation. At last, based on the modal of GA dynamics, the performance of genetic operators was analyzed.5. In th...
|
PDF Full Text Request