Abstract
We propose a class of crossover operators for genetic programming that aim at making offspring programs semantically intermediate (medial) with respect to parent programs by modifying short fragments of code (subprograms). The approach is applicable to problems that define fitness as a distance between program output and the desired output. Based on that metric, we define two measures of semantic ‘mediality’, which we employ to design two crossover operators: one aimed at making the semantic of offsprings geometric with respect to the semantic of parents, and the other aimed at making them equidistant to parents’ semantics. The operators act only on randomly selected fragments of parents’ code, which makes them computationally efficient. When compared experimentally with four other crossover operators, both operators lead to success ratio at least as good as for the non-semantic crossovers, and the operator based on equidistance proves superior to all others.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)
McPhee, N.F., Ohs, B., Hutchison, T.: Semantic Building Blocks in Genetic Programming. In: O’Neill, M., Vanneschi, L., Gustafson, S., Esparcia Alcázar, A.I., De Falco, I., Della Cioppa, A., Tarantino, E. (eds.) EuroGP 2008. LNCS, vol. 4971, pp. 134–145. Springer, Heidelberg (2008)
Moraglio, A., Krawiec, K., Johnson, C.: Geometric semantic genetic programming. In: Igel, C., Lehre, P.K., Witt, C. (eds.) The 5th Workshop on Theory of Randomized Search Heuristics, ThRaSH 2011, Copenhagen, Denmark (2011)
Nguyen, Q.U., Nguyen, X.H., O’Neill, M.: Semantic Aware Crossover for Genetic Programming: The Case for Real-Valued Function Regression. In: Vanneschi, L., Gustafson, S., Moraglio, A., De Falco, I., Ebner, M. (eds.) EuroGP 2009. LNCS, vol. 5481, pp. 292–302. Springer, Heidelberg (2009)
Krawiec, K., Lichocki, P.: Approximating geometric crossover in semantic space. In: Raidl, G., Rothlauf, F., Squillero, G., Drechsler, R., Stuetzle, T., Birattari, M., Congdon, C.B., Middendorf, M., Blum, C., Cotta, C., Bosman, P., Grahl, J., Knowles, J., Corne, D., Beyer, H.G., Stanley, K., Miller, J.F., van Hemert, J., Lenaerts, T., Ebner, M., Bacardit, J., O’Neill, M., Di Penta, M., Doerr, B., Jansen, T., Poli, R., Alba, E. (eds.) GECCO 2009: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, Montreal, pp. 987–994. ACM (2009)
Krawiec, K., Wieloch, B.: Analysis of semantic modularity for genetic programming. Foundations of Computing and Decision Sciences 34(4), 265–285 (2009)
Moraglio, A., Poli, R.: Topological Interpretation of Crossover. In: Deb, K., Poli, R., Banzhaf, W., Beyer, H.G., Burke, E., Darwen, P., Dasgupta, D., Floreano, D., Foster, J., Harman, M., Holland, O., Lanzi, P.L., Spector, L., Tettamanzi, A., Thierens, D., Tyrrell, A. (eds.) GECCO 2004, Part I. LNCS, vol. 3102, pp. 1377–1388. Springer, Heidelberg (2004)
Johnson, C.G.: Genetic Programming Crossover: Does It Cross over? In: Vanneschi, L., Gustafson, S., Moraglio, A., De Falco, I., Ebner, M. (eds.) EuroGP 2009. LNCS, vol. 5481, pp. 97–108. Springer, Heidelberg (2009)
Archer, A.F.: A modern treatment of the 15 puzzle. American Mathematical Monthly 106, 793–799 (1999)
The On-line Encyclopedia of Integer Sequences, http://oeis.org
Altenberg, L.: Modularity in evolution: Some low-level questions. In: Rasskin-Gutman, D., Callebaut, W. (eds.) Modularity: Understanding the Development and Evolution of Complex Natural Systems, pp. 99–128. MIT Press, Cambridge (2005)
Watson, R.A.: Compositional Evolution: The impact of Sex, Symbiosis and Modularity on the Gradualist Framework of Evolution, NA. Vienna series in theoretical biology. MIT Press (February 2006)
Krawiec, K.: Semantically embedded genetic programming: automated design of abstract program representations. In: Krasnogor, N., et al. (eds.) GECCO 2011: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, Dublin, Ireland, pp. 1379–1386. ACM (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krawiec, K. (2012). Medial Crossovers for Genetic Programming. In: Moraglio, A., Silva, S., Krawiec, K., Machado, P., Cotta, C. (eds) Genetic Programming. EuroGP 2012. Lecture Notes in Computer Science, vol 7244. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29139-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-29139-5_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29138-8
Online ISBN: 978-3-642-29139-5
eBook Packages: Computer ScienceComputer Science (R0)