Abstract
Twelve years have passed since the advent of grammatical evolution (GE) in 1998, but such issues as vast search space, genotypic readability, and the inherent relationship among grammatical concepts, production rules and derivations have remained untouched in almost all existing GE researches. Model-based approach is an attractive method to achieve different objectives of software engineering. In this paper, we make the first attempt to model syntactically usable information of GE using an automaton, coming up with a novel solution called model-based grammatical evolution (MGE) to these problems. In MGE, the search space is reduced dramatically through the use of concepts from building blocks, but the functionality and expressiveness are still the same as that of classical GE. Besides, complex evolutionary process can visually be analyzed in the context of transition diagrams.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
O’Neill M, Ryan C. Grammatical evolution. IEEE Trans Evolut Comput, 2001, 5: 349–358
Ryan C, Collins J J, O’Neill M. Grammatical evolution: Evolving programs for an arbitrary language. In: Banzhaf W, Poli R, Schoenauer M, et al., eds. Proc of the First European Workshop on Genetic Programming (EuroGP98), LNCS, 1998, 1391: 83–96
O’Neill M, Ryan C. Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Norwell, MA: Kluwer Academic Publishers, 2003
Mitchell M. An Introduction to Genetic Algorithms. Cambridge: MIT Press, 1996
Hopcroft J E, Motwani R, Ullman J D. Introduction to Automata Theory, Languages, and Computation. 3rd ed. San Antonio, TX: Pearson Education, Inc. 2008
Aho A V, Lam M S, Sethi R, et al. Compilers: Principles, Techniques, and Tools. 2nd ed. San Antonio, TX: Pearson Education, Inc. 2007
Koza J R. Genetic Programming. Cambridge MA: MIT Press, 1992
Oltean M, Grosan C. A comparison of several linear genetic programming techniques. Complex Syst, 2003, 14: 285–313
Sette S, Boullart L. Genetic programming: principles and applications. Eng Appl Artif Intell, 2001, 14: 727–736
Gavrilis D, Tsoulos I G, Dermatas E. Selecting and constructing features using grammatical evolution. Patt Recog Lett, 2008, 29: 1358–1365
Tsoulos I G, Gavrilis D, Glavas E. Neural network construction and training using grammatical evolution. Neurocomputing, 2008. 72: 269–277
Dempsey I, O’Neill M, Brabazon A. Adaptive trading with grammatical evolution. In: Proc of 2006 IEEE Congress on Evolutionary Computation. Vancouver, BC, Canada, 2006. 2587–2592
Tsoulos I G, Gavrilis D, Dermatas E. GDF: A tool for function estimation through grammatical evolution. Comput Phys Commun, 2006, 174: 555–559
Ferreira C. Gene expression programming: A new adaptive algorithm for solving problems. Complex Syst, 2001, 13: 87–129
Xu K K, Liu Y T, Tang R, et al. A novel method for real parameter optimization based on gene expression programming. Appl Soft Comput, 2009, 9: 725–737
Du X, Ding L X. About the convergence rates of a class of gene expression programming. Sci China Inf Sci, 2010, 53: 715–728
Pierce B C. Types and Programming Languages. Cambridge, MA: The MIT Press, 2002
Boolos G S, Burgess J P, Jeffrey R C. Computability and Logic. 4th ed. Cambridge: Cambridge Univ. Press, 2002
Wong M L, Mun T. Evolving recursive programs by using adaptive grammar based genetic programming. Genetic Program Evolv Mach, 2005, 6: 421–455
Wilson D, Kaur D. Search, neutral evolution, and mapping in evolutionary computing: A case study of grammatical evolution. IEEE Trans Evolut Comput, 2009, 13: 566–590
He P, Kang L S, Fu M. Formality based genetic programming. In: IEEE Congress on Evolutionary Computation. Hong Kong, 2008
He P, Kang L S, Johnson C G, et al. Hoare logic-based genetic programming. Sci China Inf Sci, 2011, 54: 623–637
Harman M, Mansouri S A, Zhang Y Y. Search based software engineering: A comprehensive analysis and review of trends techniques and application. Technical Report, TR-09-03, 2009
Hugosson J, Hemberg E, Brabazon A, et al. Genotype representations in grammatical evolution. Appl Soft Comput, 2010, 10: 36–43
O’Neill M, Brabazon A, Nicolau M, et al. πGrammatical evolution. In: Deb K, Poli R, Banzhaf W, et al. eds. Proc. GECCO, LNCS, 2004, 3103: 617–629
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
He, P., Johnson, C.G. & Wang, H. Modeling grammatical evolution by automaton. Sci. China Inf. Sci. 54, 2544–2553 (2011). https://doi.org/10.1007/s11432-011-4411-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-011-4411-8