Chinese Journal of Computers   Full Text
Title	A Multi-Gene Evolutionary Algorithm Based on Overlapped Expression
Authors	PENG Jing1),2) TANG Chang-Jie1) YUAN Chang-An1) ZHU Ming-Fang1) QIAO Shao-Jie1)
Address	1)(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871) 2)(School of Computer Science, Sichuan University, Chengdu 610065)
Year	2007
Issue	No.5(775—785)
Abstract &   Background	Abstract Inspired by the overlapped gene expression in the phenomena of biology, this paper proposes a novel evolutionary algorithm, MEOE(Multi-gene Evolutionary algorithm based on Overlapped Expression), and describes the genetic expression structures and relevant algorithm of it. Different from existing works, MEOE suggests a new expression structure of genes with probabilities of overlapped expression for some segments and borrows some idea from artificial immunity algorithm. This paper systematically analyzes MEOE, discusses the features of expression space, capability of expression, and compares MEOE with traditional algorithms. The detailed experiments show that MEOE algorithm is 2.5～9.4 times faster than usual GEP method, and in higher-degree polynomial function finding problem, the success rate of MEOE is 10 times than usual GEP. The experiments results also show that the probability selection function based on density works well in higher-degree polynomial function finding problem. keywords gene expression programming; evolutionary algorithm; overlap gene; expression space background This research belong to the National Science Foundation of China project- "The research on key techniques in knowledge discovery based on Gene Expression programming" (60473071), and is also supported by China Postdoctoral Science Foundation under Grant No.20060400002, Sichuan Youth Science and Technology Foundation under Grant No.07ZQ026-055, National Science Foundation of China (Nos.60503037,60473051), National High-Tech Research and Development Plan of China (No.2006AA01Z230) and the Sichuan Major Science and Technology Project—“The outliner floating population analyses based on knowledge discovery” (No.04SG1640). The projects are mainly focus on research of key techniques based on Gene Expression Programming (GEP). GEP is a new technique in knowledge discovering which borrow idea from the creature evolution rules of gene expression. Comparing the traditional evolution algorithm: GA (Genetic Algorithm) and GP(Genetic Programming) with GEP, presents following key points: (1) GEP combines the advantage of GA and GP, GEP is 100~60000 times faster than GA or GP. (2) GEP has an inborn advantage to weaken the combination explosion. (3) Gene expression programming does not need the hypothesis, but trusts ‘truth is inside the training data’. Inspired by the overlapped expression in biological genetics, this study proposes a novel evolutionary algorithm， MEOE, and describes the genetic expression structures and relevant algorithm of MEOE. This study systematically analyzes MEOE, discusses the features of expression space, capability of expression, and compares MEOE with traditional algorithms. The detailed experiments show that MEOE algorithm is much faster than usual GEP method, and in higher-degree polynomial function finding, the success rate of MEOE is 10 times than usual GEP.