Abstract
Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) is a recent Evolutionary Algorithm (EA) in which the interactions among parts of the solution (i.e., the linkage) are learned and exploited in a novel variation operator. We present GOMGE, the extension of GOMEA to Grammatical Evolution (GE), a popular EA based on an indirect representation which may be applied to any problem whose solutions can be described using a context-free grammar (CFG). GE is a general approach that does not require the user to tune the internals of the EA to fit the problem at hand: there is hence the opportunity for benefiting from the potential of GOMEA to automatically learn and exploit the linkage. We apply the proposed approach to three variants of GE differing in the representation (original GE, SGE, and WHGE) and incorporate in GOMGE two specific improvements aimed at coping with the high degeneracy of those representations. We experimentally assess GOMGE and show that, when coupled with WHGE and SGE, it is clearly beneficial to both effectiveness and efficiency, whereas it delivers mixed results with the original GE.
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
Similar content being viewed by others
References
Thierens, D., Bosman, P.A.: Optimal mixing evolutionary algorithms. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO 2011, pp. 617–624. ACM, New York (2011)
Ryan, C., Collins, J.J., Neill, M.O.: Grammatical evolution: evolving programs for an arbitrary language. In: Banzhaf, W., Poli, R., Schoenauer, M., Fogarty, T.C. (eds.) EuroGP 1998. LNCS, vol. 1391, pp. 83–96. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055930
Bartoli, A., De Lorenzo, A., Medvet, E., Tarlao, F.: Syntactical similarity learning by means of grammatical evolution. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 260–269. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_24
Medvet, E., Bartoli, A., Talamini, J.: Road traffic rules synthesis using grammatical evolution. In: Squillero, G., Sim, K. (eds.) EvoApplications 2017. LNCS, vol. 10200, pp. 173–188. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55792-2_12
Castejón, F., Carmona, E.J.: Automatic design of analog electronic circuits using grammatical evolution. Appl. Soft Comput. 62, 1003–1018 (2018)
Miranda, P.B., Prudêncio, R.B.: Generation of particle swarm optimization algorithms: an experimental study using grammar-guided genetic programming. Appl. Soft Comput. 60, 281–296 (2017)
Medvet, E., Bartoli, A., Talamini, J.: Road traffic rules synthesis using grammatical evolution. In: Squillero, G., Sim, K. (eds.) EvoApplications 2017. LNCS, vol. 10200, pp. 173–188. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55792-2_12
Thorhauer, A.: On the non-uniform redundancy in grammatical evolution. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 292–302. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_27
Thorhauer, A., Rothlauf, F.: On the locality of standard search operators in grammatical evolution. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 465–475. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10762-2_46
Medvet, E., Bartoli, A.: On the automatic design of a representation for grammar-based genetic programming. In: Castelli, M., Sekanina, L., Zhang, M., Cagnoni, S., García-Sánchez, P. (eds.) EuroGP 2018. LNCS, vol. 10781, pp. 101–117. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-77553-1_7
Whigham, P.A., Dick, G., Maclaurin, J.: On the mapping of genotype to phenotype in evolutionary algorithms. Genet. Program. Evol. Mach. 18, 1–9 (2017)
Spector, L.: Introduction to the peer commentary special section on “on the mapping of genotype to phenotype in evolutionary algorithms” by peter a. whigham, grant dick, and james maclaurin. Genet. Program. Evol. Mach. 18(3), 351–352 (2017)
Lourenço, N., Pereira, F.B., Costa, E.: SGE: a structured representation for grammatical evolution. In: Bonnevay, S., Legrand, P., Monmarché, N., Lutton, E., Schoenauer, M. (eds.) EA 2015. LNCS, vol. 9554, pp. 136–148. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-31471-6_11
Medvet, E.: Hierarchical grammatical evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2017, pp. 249–250. ACM, New York (2017)
Virgolin, M., Alderliesten, T., Witteveen, C., Bosman, P.A.N.: Scalable genetic programming by gene-pool optimal mixing and input-space entropy-based building-block learning. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1041–1048. ACM (2017)
Bouter, A., Alderliesten, T., Witteveen, C., Bosman, P.A.: Exploiting linkage information in real-valued optimization with the real-valued gene-pool optimal mixing evolutionary algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 705–712. ACM (2017)
Luong, N.H., La Poutré, H., Bosman, P.A.: Multi-objective gene-pool optimal mixing evolutionary algorithms. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 357–364. ACM (2014)
O’Neill, M., Brabazon, A., Nicolau, M., Garraghy, S.M., Keenan, P.: \(\pi \)grammatical evolution. In: Deb, K. (ed.) GECCO 2004. LNCS, vol. 3103, pp. 617–629. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24855-2_70
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). https://doi.org/10.1007/978-3-540-24650-3_13
Wong, P.-K., Wong, M.-L., Leung, K.-S.: Hierarchical knowledge in self-improving grammar-based genetic programming. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 270–280. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_25
He, P., Johnson, C.G., Wang, H.: Modeling grammatical evolution by automaton. Sci. China Inf. Sci. 54(12), 2544–2553 (2011)
He, P., Deng, Z., Gao, C., Chang, L., Hu, A.: Analyzing grammatical evolution and \(\pi \)Grammatical evolution with grammar model. In: Balas, V.E., Jain, L.C., Zhao, X. (eds.) Information Technology and Intelligent Transportation Systems. AISC, vol. 455, pp. 483–489. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-38771-0_47
Shan, Y., McKay, R.I., Baxter, R., Abbass, H., Essam, D., Nguyen, H.: Grammar model-based program evolution. In: Congress on Evolutionary Computation, CEC2004, Volume 1, pp. 478–485. IEEE (2004)
Shan, Y., McKay, R., Essam, D., Abbass, H.: A survey of probabilistic model building genetic programming. In: Pelikan, M., Sastry, K., CantÚPaz, E. (eds.) Scalable Optimization via Probabilistic Modeling, pp. 121–160. Springer, Heidelberg (2006). https://doi.org/10.1007/978-3-540-34954-9_6
Medvet, E., Daolio, F., Tagliapietra, D.: Evolvability in grammatical evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 977–984. ACM (2017)
Medvet, E., Bartoli, A., Squillero, G.: An effective diversity promotion mechanism in grammatical evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 247–248. ACM (2017)
Thierens, D., Bosman, P.A.N.: Hierarchical problem solving with the linkage tree genetic algorithm. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, pp. 877–884. ACM (2013)
Gronau, I., Moran, S.: Optimal implementations of UPGMA and other common clustering algorithms. Inf. Process. Lett. 104(6), 205–210 (2007)
Uy, N.Q., Hoai, N.X., O’Neill, M., McKay, R.I., Galván-López, E.: Semantically-based crossover in genetic programming: application to real-valued symbolic regression. Genet. Program. Evol. Mach. 12(2), 91–119 (2011)
Vanneschi, L., Castelli, M., Manzoni, L.: The k landscapes: a tunably difficult benchmark for genetic programming. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 1467–1474. ACM (2011)
White, D.R., Mcdermott, J., Castelli, M., Manzoni, L., Goldman, B.W., Kronberger, G., Jaśkowski, W., O’Reilly, U.M., Luke, S.: Better gp benchmarks: community survey results and proposals. Genet. Program. Evol. Mach. 14(1), 3–29 (2013)
Squillero, G., Tonda, A.: Divergence of character and premature convergence: a survey of methodologies for promoting diversity in evolutionary optimization. Inf. Sci. 329, 782–799 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Medvet, E., Bartoli, A., De Lorenzo, A., Tarlao, F. (2018). GOMGE: Gene-Pool Optimal Mixing on Grammatical Evolution. In: Auger, A., Fonseca, C., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds) Parallel Problem Solving from Nature – PPSN XV. PPSN 2018. Lecture Notes in Computer Science(), vol 11101. Springer, Cham. https://doi.org/10.1007/978-3-319-99253-2_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-99253-2_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99252-5
Online ISBN: 978-3-319-99253-2
eBook Packages: Computer ScienceComputer Science (R0)