Abstract
Semantic Backpropagation (SB) was introduced in GP so as to take into account the semantics of a GP tree at all intermediate states of the program execution, i.e., at each node of the tree. The idea is to compute the optimal “should-be” values each subtree should return, whilst assuming that the rest of the tree is unchanged, and to choose a subtree that matches as well as possible these target values. A single tree is evolved by iteratively selecting and replacing a single node with the best subtree from a static library. Replacements are made with the primary aim of reducing the local error, and a secondary aim of reducing the tree size. Previous results for standard Boolean GP benchmarks that have been obtained by the authors with another variant of SB are improved in term of tree size. SB is then applied for the first time to categorical GP benchmarks, and outperforms all known results to date for three variable finite algebras.
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
Notes
- 1.
See also [8] for a survey on recent program synthesis techniques from formal methods and inductive logic programming, to GP.
- 2.
That will also be presented at the Semantic Workshop (SMGP) at GECCO 2015.
- 3.
The same notation will be implicit in the rest of the paper, whatever the nodes A, B and C.
- 4.
The entire code base is freely available at robynffrancon.com/GLTI.html.
References
Ffrancon, R., Schoenauer, M.: Memetic semantic genetic programming. In: Silva, S., Esparcia, A. (eds.) Proceedings of the GECCO. ACM (2015) (To appear)
Hoos, H.H., Stützle, T.: Stochastic Local Search. Morgan Kaufmann, San Francisco (2005)
Koza, J.R., Programming, G.: On the Programming of Computers by Means of Natural Selection, vol. 1. MIT Press, Cambridge (1992)
Krawiec, K., O’Reilly, U.-M., Programming, B.: A broader and more detailed take on semantic GP. In: Arnold, D., et al. (ed.) Proceedings of the GECCO, pp. 935–942. ACM Press (2014)
Krawiec, K., Pawlak, T.: Approximating geometric crossover by semantic backpropagation. In: Blum, C., Alba, E. (eds.) Proceedings of the 15th GECCO, pp. 941–948. ACM (2013)
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)
Pawlak, T., Wieloch, B., Krawiec, K.: Semantic backpropagation for designing search operators in geneticprogramming. IEEE Trans. Evol. Comput. PP(99), 1 (2014)
Schmid, U., Kitzelmann, E., Plasmeijer, R. (eds.): AAIP 2009. LNCS, vol. 5812, p. 74. Springer, Heidelberg (2010)
Spector, L., Clark, D.M., Lindsay, I., Barr, B., Klein, J.: Genetic programming for finite algebras. In: Ryan, C., Keijzer, M. (eds.) Proceedings of the 10th GECCO, pp. 1291–1298. ACM (2008)
Vanneschi, L., Castelli, M., Silva, S.: A survey of semantic methods in GP. Genet. Program. Evolvable Mach. 15(2), 195–214 (2014)
Wieloch, B., Krawiec, K., Backwards, R.P.: Instruction inversion for effective search in semantic spaces. In: Blum, C., Alba, E. (eds.) Proceedings of the 15th GECCO, pp. 1013–1020. ACM (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Ffrancon, R., Schoenauer, M. (2016). Greedy Semantic Local Search for Small Solutions. In: Bonnevay, S., Legrand, P., Monmarché, N., Lutton, E., Schoenauer, M. (eds) Artificial Evolution. EA 2015. Lecture Notes in Computer Science(), vol 9554. Springer, Cham. https://doi.org/10.1007/978-3-319-31471-6_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-31471-6_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-31470-9
Online ISBN: 978-3-319-31471-6
eBook Packages: Computer ScienceComputer Science (R0)