Exploring random permutations effects on the mapping process for grammatical evolution

• Autorzy: Zúñiga Blanca Verónica , Carpio Juan Martín , Sotelo-Figueroa Marco Aurelio , Espinal Andrés , Purata-Sifuentes Omar Jair , Ornelas Manuel , Soria-Alcaraz Jorge Alberto , Rojas Alfonso

Identyfikatory

DOI

10.14313/JAMRIS/1-2020/8

• Języki publikacji: EN

Abstrakty

EN

Grammatical Evolution (GE) is a form of Genetic Programming (GP) based on Context-Free Grammar (CF Grammar). Due to the use of grammars, GE is capable of creating syntactically correct solutions. GE uses a genotype encoding and is necessary to apply a Mapping Process (MP) to obtain the phenotype representation. There exist some well-known MPs in the state-of-art like Breadth-First (BF), Depth-First (DF), among others. These MPs select the codons from the genotype in a sequential manner to do the mapping. The present work proposes a variation in the selection order for genotype’s codons; to achieve that, it is applied a random permutation for the genotype’s codons order-taking in the mapping. The proposal’s results were compared using a statistical test with the results obtained by the traditional BF and DF using the Symbolic Regression Problem (SRP) as a benchmark.

Słowa kluczowe

EN

grammatical evolution; mapping process; symbolic regression

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2020
• Tom: Vol. 14, No. 1
• Strony: 65--72
• Opis fizyczny: Bibliogr. 33 poz., rys.

Twórcy

autor

Zúñiga Blanca Verónica

• Postgraduate Studies and Research Division, León Institute of Technology, León, México

autor

Carpio Juan Martín

• Postgraduate Studies and Research Division, León Institute of Technology, León, México

autor

Sotelo-Figueroa Marco Aurelio

• Organizational Studies Department, DCEA-University of Guanajuato, Guanajuato, México

autor

Espinal Andrés

• Organizational Studies Department, DCEA-University of Guanajuato, Guanajuato, México

autor

Purata-Sifuentes Omar Jair

• Organizational Studies Department, DCEA-University of Guanajuato, Guanajuato, México

autor

Ornelas Manuel

• Postgraduate Studies and Research Division, León Institute of Technology, León, México

autor

Soria-Alcaraz Jorge Alberto

• Organizational Studies Department, DCEA-University of Guanajuato, Guanajuato, México

autor

Rojas Alfonso

• Organizational Studies Department, DCEA-University of Guanajuato, Guanajuato, México

Bibliografia

• [1] J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, A Bradford Book, 1992.
• [2] E. A. P. Hemberg, “An Exploration of Grammars in Grammatical Evolution”. PhDthesis, University College Dublin, 2010.
• [3] P. A. Whigham et al., “Grammatically-based Genetic Programming”, Proceedings of the workshop on genetic programming: from theory to real-world applications, vol. 16, 33–41, 1995.
• [4] M. O’Neill and C. Ryan, Grammatical Evolution, Springer US, 2003, DOI: 10.1007/978-1-4615-0447-4.
• [5] D. R. White, J. McDermott, M. Castelli, L. Manzoni, B. W. Goldman, G. Kronberger, W. Jaśkowski, U.-M. O’Reilly and S. Luke, “Better GP benchmarks: community survey results and proposals”, Genetic Programming and Evolvable Machines, vol. 14, no. 1, 2013, 3–29, DOI: 10.1007/s10710-012-9177-2.
• [6] M. O’Neill and C. Ryan, “Grammatical evolution”, IEEE Transactions on Evolutionary Computation, vol. 5, no. 4, 2001, 349–358, DOI: 10.1109/4235.942529.
• [7] C. Ryan, M. O’Neill and J. Collins, “Introduction to 20 Years of Grammatical Evolution”. In: C. Ryan, M. O’Neill and J. Collins (eds.), Handbook of Grammatical Evolution, 2018, 1–21, DOI: 10.1007/978-3-319-78717-6_1.
• [8] M. O’Neill and A. Brabazon, “Grammatical Differential Evolution”. In: H. R. Arabnia (eds.), Proceedings of the 2006 International Conference on Artificial Intelligence, ICAI 2006, Las Vegas, Nevada, USA, June 26-29, 2006, Volume 1, 2006, 231–236.
• [9] D. Fagan and E. Murphy, “Mapping in Grammatical Evolution”. In: C. Ryan, M. O’Neill and J. Collins (eds.), Handbook of Grammatical Evolution, 2018, 79–108, DOI: 10.1007/978-3-319-78717-6_4.
• [10] D. Fagan and M. O’Neill, “Analyzing the Genotype-Phenotype Map in Grammatical Evolution”, PhD thesis, University College Dublin, Oct. 2013.
• [11] M. O’Neill, A. Brabazon, M. Nicolau, S. M. Garraghy and P. Keenan, “πGrammatical Evolution”. In: K. Deb (eds.), Genetic and Evolutionary Computation – GECCO 2004, vol. 3103, 2004, 617–629, DOI: 10.1007/978-3-540-24855-2_70.
• [12] E. Murphy, M. O’Neill, E. Galvan-Lopez and A. Brabazon, “Tree-adjunct grammatical evolution”. In: IEEE Congress on Evolutionary Computation, 2010, 1–8, DOI: 10.1109/CEC.2010.5586497.
• [13] H.-T. Kim and C. W. Ahn, “UMBGE: Univariate Model Based Grammatical Evolution”, Journal f Computational and Theoretical Nanoscience, vol. 13, no. 7, 2016, 4104–4110, DOI: 10.1166/jctn.2016.5257.
• [14] N. Lourenço, F. B. Pereira and E. Costa, “SGE: A Structured Representation for Grammatical Evolution”. In: S. Bonnevay, P. Legrand, N. Monmarché, E. Lutton and M. Schoenauer (eds.), Artificial Evolution, vol. 9554, 2016, 136–148, DOI: 10.1007/978-3-319-31471-6_11.
• [15] D. Fagan, M. O’Neill, E. Galván-López, A. Brabazon and S. McGarraghy, “An Analysis of Genotype-Phenotype Maps in Grammatical Evolution”. In: A. I. Esparcia-Alcázar, A. Ekárt, S. Silva, S. Dignum and A. Ş. Uyar (eds.), Genetic Programming, vol. 6021, 2010, 62–73, DOI: 10.1007/978-3-642-12148-7_6.
• [16] D. Fagan, “Genotype-phenotype Mapping in Dynamic Environments with Grammatical Evolution”. In: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation - GECCO ‘11, 2011, DOI: 10.1145/2001858.2002091.
• [17] J. Hugosson, E. Hemberg, A. Brabazon and M. O’Neill, “Genotype representations in grammatical evolution”, Applied Soft Computing, vol. 10, no. 1, 2010, 36–43,DOI: 10.1016/j.asoc.2009.05.003.
• [18] M. A. Sotelo-Figueroa, H. J. Puga-Soberanes, J. M. Carpio, H. J. Fraire-Huacuja, L. Cruz-Reyes and J. A. Soria-Alcaraz, “Improving the Bin Packing Heuristic through Grammatical Evolution Based on Swarm Intelligence”, Mathematical Problems in Engineering, 2014, 01–12, DOI: 10.1155/2014/545191.
• [19] C. Ryan, M. O’Neill and J. Collins, Handbook of Grammatical Evolution, Springer International Publishing, 2018, DOI: 10.1007/978-3-319-78717-6.
• [20] T. Chareka and N. Pillay, “A study of fitness functions for Data Classification using Grammatical Evolution”. In: 2016 Pattern Recognition Association of South Africa and Robotics and Mechatronics International Conference (PRASARobMech), 2016, 1–4, DOI: 10.1109/RoboMech.2016.7813165.
• [21] O. Quiroz-Ramírez, A. Espinal, M. Ornelas-Rodríguez, A. Rojas-Domínguez, D. Sánchez, H. Puga-Soberanes, M. Carpio, L. E. M. Espinoza and J. Ortíz-López, “Partially-Connected Artificial Neural Networks Developed by Grammatical Evolution for Pattern Recognition Problems”. In: O. Castillo, P. Melin and J. Kacprzyk (eds.), Fuzzy Logic Augmentation of Neural and Optimization Algorithms: Theoretical Aspects and Real Applications, vol. 749, 2018, 99–112, DOI: 10.1007/978-3-319-71008-2_9.
• [22] F. Ahmadizar, K. Soltanian, F. Akhlaghian Tab and I. Tsoulos, “Artificial neural network development by means of a novel combination of grammatical evolution and genetic algorithm”, Engineering Applications of Artificial Intelligence, vol. 39, 2015, 1–13, DOI: 10.1016/j.engappai.2014.11.003.
• [23] X. Li and L. Gao, “An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem”, International Journal of Production Economics, vol. 174, 2016, 93–110, DOI: 10.1016/j.ijpe.2016.01.016.
• [24] M. A. Sotelo-Figueroa, A. Hernández-Aguirre, A. Espinal, J. A. Soria-Alcaraz and J. Ortiz-López, “Symbolic Regression by Means of Grammatical Evolution with Estimation Distribution Algorithms as Search Engine”. In: O. Castillo, P. Melin and J. Kacprzyk (eds.), Fuzzy Logic Augmentation of Neural and Optimization Algorithms: Theoretical Aspects and Real Applications, vol. 749, 2018, 169–177, DOI: 10.1007/978-3-319-71008-2_14.
• [25] F. A. A. Motta, J. M. Freitas, F. R. Souza, H. S. Bernardino, I. L. Oliveira and H. J. C. Barbosa, “A Hybrid Approach of Grammar-based Genetic Programming and Differential Evolution for Symbolic Regression”. In: Proceedings XIII Brazilian Congress on Computational Inteligence, 2018, 1–12, DOI: 10.21528/CBIC2017-110.
• [26] F. A. A. Motta, J. M. de Freitas, F. R. de Souza, H. S. Bernardino, I. L. De Oliveira and H. J. C. Barbosa, “A Hybrid Grammar-Based Genetic Programming for Symbolic Regression Problems”. In: 2018 IEEE Congress on Evolutionary Computation (CEC), 2018, 1–8, DOI: 10.1109/CEC.2018.8477826.
• [27] D. A. Augusto and H. J. C. Barbosa, “Symbolic regression via genetic programming”. In: Proceedings of Sixth Brazilian Symposium on Neural Networks, 2000, 173–178, DOI: 10.1109/SBRN.2000.889734.
• [28] Q. Lu, J. Ren and Z. Wang, “Using Genetic Programming with Prior Formula Knowledge to Solve Symbolic Regression Problem”, Computational Intelligence and Neuroscience, 2016, 1–17, DOI: 10.1155/2016/1021378.
• [29] M. Nicolau and A. Agapitos, “Understanding Grammatical Evolution: Grammar Design”. In: C. Ryan, M. O’Neill and J. Collins (eds.), Handbook of Grammatical Evolution, 2018, 23–53, DOI: 10.1007/978-3-319-78717-6_2.
• [30] T. Nyathi and N. Pillay, “Comparison of a genetic algorithm to grammatical evolution for automated design of genetic programming classification algorithms”, Expert Systems with Applications, vol. 104, 2018, 213–234, DOI: 10.1016/j.eswa.2018.03.030.
• [31] C. R. Darwin, “On the origins of the species by means of natural selection, or the preservation of favoured races in the struggle for life”, H. Milford, Oxford University Press, Cambridge, 1859.
• [32] J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, The MIT Press, 1992, DOI: 10.7551/mitpress/1090.001.0001.
• [33] D. Karaboga, C. Ozturk, N. Karaboga and B. Gorkemli, “Artificial bee colony programming for symbolic regression”, Information Sciences, vol. 209, 2012, 1–15, DOI: 10.1016/j.ins.2012.05.002.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).