Abstract
This paper discusses selected aspects of evolutionary search algorithms guided by grammars, such as Grammar Guided Genetic Programming or Grammatical Evolution. The aim of the paper is to demonstrate that, when the efficiency of the search process in such environment is considered, it is not only the language defined by a grammar that is important, but also the form of the grammar plays a key role. In the most common current approach, the person who sets up the search environment provides the grammar as well. However, as demonstrated in the paper, this may lead to a sub-optimal efficiency of the search process. Because an infinite number of grammars of different forms can exist for a given language, manual construction of the grammar which makes the search process most effective is generally not possible. It seems that a desirable solution would be to have the optimal grammar generated automatically for the provided constrains. This paper presents possible solutions allowing for automatic grammar induction, which makes the search process more effective.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
GEVA software, http://ncra.ucd.ie/Site/GEVA.html
Hemberg, E., Ho, L.T.W., O’Neill, M., Claussen, H.: A comparison of grammatical genetic programming grammars for controlling femtocell network coverage. Genetic Programming and Evolvable Machines 14(1), 65–93 (2013), http://dx.doi.org/10.1007/s10710-012-9171-8
Koza, J.: Genetic programming: On the programming of computers by means of natural selection. The MIT Press, Cambridge (1992)
McKay, R.I., Hoai, N.X., Whigham, P.A., Shan, Y., O’Neill, M.: Grammar-based genetic programming: a survey. Genetic Programming and Evolvable Machines 11(3-4), 365–396 (2010), http://dx.doi.org/10.1007/s10710-010-9109-y
Nicolau, M., O’Neill, M., Brabazon, A.: Applying genetic regulatory networks to index trading. In: Coello, C.A.C., Cutello, V., Deb, K., Forrest, S., Nicosia, G., Pavone, M. (eds.) PPSN 2012, Part II. LNCS, vol. 7492, pp. 428–437. Springer, Heidelberg (2012), http://dx.doi.org/10.1007/978-3-642-32964-7_43
Nicolau, M., Saunders, M., O’Neill, M., Osborne, B., Brabazon, A.: Evolving interpolating models of net ecosystem cO2 exchange using grammatical evolution. In: Moraglio, A., Silva, S., Krawiec, K., Machado, P., Cotta, C. (eds.) EuroGP 2012. LNCS, vol. 7244, pp. 134–145. Springer, Heidelberg (2012), http://dx.doi.org/10.1007/978-3-642-29139-5_12
O’Neill, M., Brabazon, A.: mGGA: The meta-grammar genetic algorithm. In: Keijzer, M., Tettamanzi, A., Collet, P., van Hemert, J., Tomassini, M. (eds.) EuroGP 2005. LNCS, vol. 3447, pp. 311–320. Springer, Heidelberg (2005)
O’Neill, M., Brabazon, A.: Evolving a logo design using lindenmayer systems, postscript & grammatical evolution. In: IEEE Congress on Evolutionary Computation, pp. 3788–3794. IEEE (2008), http://dx.doi.org/10.1109/CEC.2008.4631311
O’Neill, M., Ryan, C.: Grammatical evolution. IEEE Trans. Evolutionary Computation 5(4), 349–358 (2001), http://dx.doi.org/10.1109/4235.942529
O’Neill, M., Ryan, C.: Grammatical Evolution: Evolutionary Automatic Programming in a Arbitrary Language, Genetic programming, vol. 4. Kluwer Academic Publishers (2003)
O’Neill, M., Ryan, C.: Grammatical evolution by grammatical evolution: The evolution of grammar and genetic code. In: Keijzer, M., O’Reilly, U.-M., Lucas, S., Costa, E., Soule, T. (eds.) EuroGP 2004. LNCS, vol. 3003, pp. 138–149. Springer, Heidelberg (2004)
Whigham, P.A.: Grammatically-based genetic programming. In: Rosca, J.P. (ed.) Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, Tahoe City, California, USA, pp. 33–41 (July 9, 1995)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Palka, D., Zachara, M. (2015). Automatic Grammar Induction for Grammar Based Genetic Programming. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L., Zurada, J. (eds) Artificial Intelligence and Soft Computing. ICAISC 2015. Lecture Notes in Computer Science(), vol 9119. Springer, Cham. https://doi.org/10.1007/978-3-319-19324-3_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-19324-3_32
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19323-6
Online ISBN: 978-3-319-19324-3
eBook Packages: Computer ScienceComputer Science (R0)