进化算法（EA）理论与应用研究

Evolutionary algorithms (EA) includes four concrete styles such as genetic algorithms (GA), evolution strategies (ES), evolutionary programming (EP), and genetic programming (GP). They are all formulated based the evolution theory and genetics in biology. EA is mainly applied as a robust stochastic heuristic method in solving sophisticated optimization problems or in searching complex spaces, and is empowered with the population based searching and simple genetic operators. It is fitted to the simultaneously searching of multi-parts of the solution space, and also to be implemented on large parallel computer platforms. In the research process of this project, we firstly analyze the schema theory and evolutionary dynamics of genetic agorithms based on binary encoding, and concepts as schemata deceptiveness and GA deception problems are defined exactly. The affection of schema deceptiveness on GA searching behavior is discussed in detail. Then, we present the convergence proof of GA based on real number encoding, which is beneficial to the application of floating GA to practical optimization problems, and further the design of adaptive mutation operators. Meanwhile, this proof and derived conclusions also conform to evolutionary programming and evolution strategies. We also give a new proof for the no free lunch theory, which reveals more explicitly its essence and can provide genuine information to algorithms design and applications of EA to real-world problems.Thirdly, we take the GA as a high-dimension, non-linear, stochastic, discrete and dynamic system, and build up the performance analysis matrix. Different parameterized GAs are tested by calculating probability density function of all individuals. This approach is feasible to aid to find a good algorithm for a given problem. Fourthly, we study the design of genetic strategies with the view of increasing the global searching power of EA. A new non-monotone fitness scaling method in GA is proposed to deal with the schema deceptiveness existed in complex optimization problems. We analyze the behavior of genetic algorithms in solving multimodal function optimization, and formulate the logic of macro-niching method based on multi-populations, and described its mechanism and work flow in detail. We also designed a new approach for calculating niche radius automatically. Fifthly, As to the constrained optimization problems, a new method called direct comparison- proportional method (DCPM) is proposed, which combines tournament selection in GA and the reservation of a fixed percentage of infeasible individuals.Based on the analysis of multi-objective EA, we introduce a new algorithm (ScGA) for solving multi-modal problems which is more effective and accurate. Three new multi-objective algorithms are proposed by using fuzzy preference, sorting and totally weighted sum approaches in selection operations individually. .Finally, EA is applied to optimization problems in knowledge acquisition and data mining. We design concrete styles of GA in concept learning and the construction of Bayes belief network. A new dynamic clustering method based on genetic algorithms is presented for the data analysis in databases. We proposes a supervised training-test method with genetic programming for pattern classification. Compared with conventional methods with regard to deterministic pattern classifiers, this method is applicable to both linear separable problems and linearly non-separable problems. For specific training samples, it can formulate the expression of discriminate function well without any prior knowledge. For the proposed methods and algorithms above, various problems and functions are used to test their feasibility and effectiveness. Experiments are conducted systematically, and results reveal that they are practical, efficient and robust.

本课题的研究主要集中于：进化算法的理论研究以及它在机器学习、模式识别及数据开采等领域中的应用。我们希望通过研究，能够建立一个比较完整和实用的关于进化算法的理论体系，以此来指导分析已有的并且设计新的、高效的、应用于特定问题的遗传操作与算子，生成新的算法，编制成供实际使用的软件包，以解决有重要应用意义和价值的优化、数据开采、模式识别等领域中的实际问题。