Application of grammatical evolution to stock price prediction
Abstract
Grammatical evolution (GE) is one of evolutionary computation techniques. The aim of GE is to find the function or the executable program or program fragment that will find the optimal solution for the design objective such as the function for representing the set of given data, the robot control algorithm and so on. Candidate solutions are described in bitstring. The mapping process from the genotype (bitstring) to the phenotype (function or program or program fragment) is defined according to the list of production rules of terminal and non-terminal symbols. Candidate solutions are evolved according to the search algorithm based on genetic algorithm (GA). There are three main issues in GE: genotype definition, production rules, and search algorithm. Grammatical evolution with multiple chromosomes (GEMC) is one of the improved algorithms of GE. In GEMC, the convergence property of GE is improved by modifying the genotype definition. The aim of this study is to improve convergence property by changing the search algorithm based on GA with the search algorithm based on stochastic schemata exploiter (SSE) in GE and GEMC. SSE is designed to find the optimal solution of the function, which is the same as GA. The convergence speed of SSE is much higher than that of GA. Moreover, the selection and crossover operators are not necessary for SSE. When GA is replaced with SSE, the improved algorithms of GE and GEMC are named “grammatical evolution by using stochastic schemata exploiter (GE-SSE)” and “grammatical evolution with multiple chromosome by using stochastic schemata exploiter (GEMC-SSE)”, respectively. In this study, GE-SSE is compared with GE in the symbolic regression problem of polynomial function. The results show that the convergence speed of GE-SSE is higher than that of original GE. Next, GE-SSE and GEMC-SSE are compared in stock price prediction problem. The results show that the convergence speed of GEMC-SSE is slightly higher than that of GE-SSE.
Keywords
grammatical evolution (GE), mapping process, stochastic schemata exploiter (SSE), symbolic regression problem, stock price prediction,References
[1] C. Ryan, J.J. Collins, M. O’Neill. Grammatical evolution: Evolving programs for an arbitrary language. In: Proceedings of the 1st European Workshop on Genetic Programming, pp. 83–95, Springer-Verlag, 1998.[2] C. Ryan, M. O’Neill. Crossover in grammatical evolution: A smooth operator? In: Proceedings of the European Conference on Genetic Programming, pp. 149–162, Springer-Verlag, 2000.
[3] M. O’Neill, C. Ryan. Grammatical evolution. IEEE Transactions on Evolutionary Computation, 5(4): 349–358, 2001.
[4] C. Ryan, M. O’Neill. Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Springer-Verlag, 2003.
[5] J.H. Holland. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1st edition, 1975.
[6] D.E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1st edition, 1989.
[7] M.D. Vose. The Simple Genetic Algorithm: Foundations and Theory. The MIT press, 1st edition, 1999.
[8] J.R. Koza [Ed.]. Genetic Programming II. The MIT Press, 1994.
[9] J.R. Koza, F.H. Bennett III, D. Andre, M.A. Keane [Eds.]. Genetic Programming III. Morgan Kaufmann Pub., 1999.
[10] A. Hara, T. Yamaguchi, T. Ichimura, T. Takahama. Multi-chromosomal grammatical evolution. In: Proceedings of 4th International Workshop on Computational Intelligence & Applications, Okayama, Japan, 2008.
[11] N.A. Aizawa. Evolving SSE: A stochastic schemata exploiter. In: Proc. of 1st IEEE Conf. Evol. Comp., pp. 525–529. IEEE, 1994.
[12] T. Maruyama, E. Kita. Estimation and extension of stochastic schemata exploiter. In: Data Mining VI: Data Mining, Text Mining and their Business Applications (Proceedings of Data Mining 2005), pp. 45–54, 2005.
[13] T. Maruyama, E. Kita. Evaluation of extended stochastic schemata exploiter. In: Computer Aided Optimum Design in Engineering X (Proceedings of OPTI2007, USA), pp. 45–54, 2007.
[14] T. Maruyama, E. Kita. Cross-generational elitist selection SSE. In: Proc. of the 7th World Congress of Structural and Multidisciplinary Optimization, 2007. CD-ROM.
[15] T. Maruyama, E. Kita. Convergence analysis of cross-generational elitist selection SSE. In: Proceedings of the 2008 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA2008), 2008.
