Gene Expression Programming Core Technology Research

Evolutionary Computation is a. hot point in the research area of Artificial Intelligence, Knowledge Engineering and Data Mining. Genetic Algorithm and Genetic Programming are the most important computation models in Evolutionary computation. Genetic Algorithm uses linear bit string as chromosome code, and solves ordinary problems. Genetic Programming uses tree structure as chromosome code, and want find out the programs for the problems. In 2001, F. Candida proposes a new Evolutionary Computation method named Gene Expression Programming (GEP). GEP is as simple as Genetic Algorithm, and as functional as Genetic Programming. But for most problems, GEP is much fast than Genetic Programming in 2 - 4 magnitudes. While creating new concepts and algorithms, F. Candida left some theoretic issues as open problems. F. Candida also uses many properties without proof. Some conjectures is still list in the first book about GEP written by F. Candida. This paper try to answer these problems based on our research on GEP. The main result and contribution are as follows:(1) Gives rigorous analysis on GEP encoding. This work reveals the relation between K-expression and the expression tree. It points out that they have the same expression power. The dissertation proofs an important theorem about soundness and completeness of GEP gene encoding. It points out that the gene satisfied t = h (X(F) - 1) + 1 can be decoded into a valid function expression tree systematically. This is the basic theory of GEP.(2) Proposes a new fitness function via Complex Correlation Coefficient with strong statistics theoretic background. This work analyzes convergence of GEP using Complex Correlation Coefficient fitness function. It is proved that Symbol Regression based on GEP will convergence by probability to global optimization status. The dissertation also proposes a new constant mining method named Meta constants(MC). The theoretical analysis and experiment results show thatMC method is simple but powerful enough that it can get the predefined precision with only logarithmic cost.(3) Proposes the context-free grammar model for GEP. Proves that the presentation power of GEP and the context-free grammar with one none-terminal are equivalent.(4) According' to the context-free grammar model of GEP, the dissertation point out that Candida's GEP techniques cannot process context-free grammar with multiple none-terminals. The paper proposes the Extended Gene Expression Programming(EGEP) to solve this weakness. It also proposes new concepts about allelic K-expression and multi-segment gene. Proves that the validity of the Extended GEP gene encoding. Proves that GEP is a special case of EGEP.(5) Proposes a new concept named Predicate Association Rule and implements a mining system based on GEP. Proves that the traditional association rule is a special case of Predicate Association Rule. Gives the algorithms about mining Predicate Association Rules. Designs a new fitness function according to the heuristic knowledge. Two groups of experiments show that the application of GEP is successful.(6) Proposes two kinds of time serial prediction methods based on GEP: (a) By Slide Window Method discovers the predication function between history data and future data, (b) By Ordinary Differential Equation Method mines an ordinary differential equation from time serial data, and makes prediction based an initial condition. In order to reduce the affection of the noise, the dissertation proposes Differential by Microscope Interpolation method. This method improves the precision of first order derivative, and improves the reliability of the system. Extensive experiments on real data sets for sun spot prediction show that our new method is effective and powerful.