Research On Linear Genes Encoded Programming Methods And Its Applications

Evolutionary Computation (EC), as an important branch of natural computation, simulates the evolving process of natural biology on the basis of Darwin’s theory of "the Survival of the Fittest". A generic problem solving method, via the abstraction of evolving process and implementation of computer programs, is constructed. This method has not only the characteristics of natural evolution, but also the features of self-organization, self-adaptive, and self-learning. Self-organization, self-adaptive, and self-learning could be called intelligent generally. The intelligent method can solve a large number of complex optimization problems which are difficult to be solved by using traditional methods, and has wide useful applications to task optimization, machine learning, engineering control, hardware design, and economic optimization.Genetic Programming (GP) is an important branch of EC, and a methodology of automatic programming. GP automatically produces programs, which aims to solving a problem with the program evolved automatically by computer. GP, Gene Expression Programming (GEP) and Multi Expression Programming (MEP) all belong to GP methods. GEP and MEP represent the evolution individuals with the chromosome encoded as linear strings of fixed length. For fixed length chromosome, an effective decoding mechanism was inducted to change the genotype to phenotype, and then the phenotype’s barrier is spanned. For chromosome, the fixed, determines the solution space, and the linear strings, makes all the genetic operators are operated in the chromosome’s genotype. Thus, the excellent characteristics of GP and Genetic Algorithm (GA) are included in algorithm of GEP and MEP. In this dissertation, the programming based on linear gene encoded and its several applications are investigated. The main research work and innovations are listed as follows:1. This dissertation studies the developing trend and situation of EC, such as concept knowledge, branchs and characteristics. It presents the application fields of EC and its theory research in various aspects such as GA, Evolutionary Strategy (ES), Evolutionary Programming (EP), GP, GEP, MEP and Swarm Intelligence. An Evolutionary Modeling network is presented to record the operation process and information of GEP algorithm in the most effort. With the analysis methods of Complex network, it can be found that the network of Evolutionary Modeling is a typical Complex Network which has the small-world and scale-free characteristics. Complex Network characteristic, which programming algorithm included and exhibited, is’natural’and’essential’characteristic.2. The concept of gene effective length is presented. With the gene effective length, a method, named as Gene Read & Compute Machine (GRCM) is presented to calculate the fitness of chromosome. The traditional ways of fitness calculation, such as hierarchical tree and heap methods, are modified by GRCM method. The research shows that GRCM is simple to construct but extremely universal. GRCM could be widely used in the programming algorithm whose chromosome encoded based on the linear gene. Four influencing factors, chromosome length, population size, set size and generation, are considered to evaluate the efficiency of GRCM method. The result shows that GRCM method has an excellent performance. Evolutionary Meta Programming (EMP) was presented. EMP includes three meta:Static-Meta,Dynamic-Meta and EDA-Meta. In EMP, the Meta mechanism could enhance the intelligence of algorithm’s chromosome and the efficiency of algorithm.3. A new algorithm-Overlap Reuse Programming (ORP) is introduced which adopts the mechanism of gene reusing. The chromosome of traditional GEP doesn’t have the characteristic of gene reusing. For the same genotype, the Overlap Reuse Chromosome with the overlap reusing technology can get a more complex phenotype compared with traditional GEP chromosome. The gene reusing characteristic of MEP is also analyzed. Combining the common features of GEP, ORP and MEP, the graph analysis method and graph expression method are presented creatively. Graph analysis method and graph expression method is not only effective medium for analyzing algorithm efficiency, but also highly universal. Graph expression is a new expression method which succeeds genotype expression and phenotype expression (Expression Tree). Graph analysis method and graph expression method is the development of common theory about Genetic Programming, and the expansion of EC theory. In graph analysis method, the efficiency of programming algorithms is analyzed and compared by graph expression in four aspects which are solutions in search space, the node distance of graph expression, inherent parallelism of chromosome and evolutionary pressure of node.4. An important challenging problem of EC is unified framework for kinds of algorithms. For common features of GEP, ORP and MEP, a united programming method, United Expression Programming (UEP) is introduced. Linear programming method is formed unified by UEP in three aspects, the methods of chromosome expression, fitness calculation and fitness selection. The research shows that GEP, ORP and MEP are all special cases of UEP.5. Another important challenging problem of EC is composite characteristic in algorithm. Self-organization, self-adaptive and self-learning characteristics are the concrete embodiment of composite characteristic. For some purposes, lots of algorithms, which realizes composite characteristic, are added too much constructing process and controlling factors. So, these algorithms can’t fully reflect the characteristics of self-organization, self-adaptive and self-learning. This dissertation presents a new algorithm creatively: Automatic Operator Generated Evolutionary Algorithm (AOGEA). In AOGEA, one traditional genetic algorithm and UEP are integrated together to solve function optimization problems. Essentially and microscopically, The AOGEA has realized the target of self-organization, self-adaptive and self-learning to a great extend. Compared with Simple Genetic Algorithm (SGA), Particle Swarm Optimization (PSO), Differential Evolution (DE) and Multi Crossover (MC) algorithms, AOGEA gets a higher performance.6. Software Testing is an important part of Software Engineering, and a critical step in the software project implementation. UEP is adopted to generate the test case of class automatically. Experiment preliminary shows that UEP is effective.