Greedy Semantic Local Search for Small Solutions
Pages 1293 - 1300
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 replacing one of its nodes with the best subtree from a static library according to this local fitness, with tree size as a secondary criterion. 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.
References
[1]
Robyn Ffrancon and Marc Schoenauer. Memetic semantic genetic programming. In S. Silva and A. Esparcia, editors, Proc. GECCO. ACM, 2015. To appear.
[2]
Holger H. Hoos and Thomas Stützle. Stochastic Local Search. Morgan Kaufmann, 2005.
[3]
John R Koza. Genetic Programming: on the Programming of Computers by means of Natural Selection, volume 1. MIT press, 1992.
[4]
K. Krawiec and U.-M. O'Reilly. Behavioral Programming: A Broader and More Detailed Take on Semantic GP. In Dirk Arnold et al., editor, Proc. GECCO, pages 935--942. ACM Press, 2014.
[5]
K. Krawiec and T. Pawlak. Approximating Geometric Crossover by Semantic Backpropagation. In Ch. Blum and E. Alba, editors, Proc. 15th GECCO, pages 941--948. ACM, 2013.
[6]
N. F. McPhee, B. Ohs, and T. Hutchison. Semantic Building Blocks in Genetic Programming. In M. O'Neill et al., editor, Proc. 11th EuroGP, volume 4971 of LNCS, pages 134--145. Springer Verlag, 2008.
[7]
A. Moraglio, K. Krawiec, and C. G. Johnson. Geometric Semantic Genetic Programming. In Coello, Carlos A. Coello et al., editor, Parallel Problem Solving from Nature - PPSN XII, volume 7491 of LNCS, pages 21--31. Springer Verlag, 2012.
[8]
T. Pawlak, B. Wieloch, and K. Krawiec. Semantic Backpropagation for Designing Search Operators in Genetic Programming. Evolutionary Computation, IEEE Transactions on, PP(99):1--1, 2014.
[9]
Ute Schmid, Emanuel Kitzelmann, and Rinus Plasmeijer, editors. Inductive Programming: A Survey of Program Synthesis Techniques, volume 5812 of Lecture Notes in Computer Science. Springer Verlag, 2010.
[10]
Lee Spector, David M Clark, Ian Lindsay, Bradford Barr, and Jon Klein. Genetic Programming for Finite Algebras. In C. Ryan and M. Keijzer, editors, Proc. 10th GECCO, pages 1291--1298. ACM, 2008.
[11]
L. Vanneschi, M. Castelli, and S. Silva. A Survey of Semantic Methods in GP. Genetic Programming and Evolvable Machines, 15(2):195--214, 2014.
[12]
B. Wieloch and K. Krawiec. Running Programs Backwards: Instruction Inversion for Effective Search in Semantic Spaces. In Ch. Blum and E. Alba, editors, Proc. 15th GECCO, pages 1013--1020. ACM, 2013.
Index Terms
- Greedy Semantic Local Search for Small Solutions
Recommendations
Memetic Semantic Genetic Programming
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary ComputationSemantic 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 ...
Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming
In this paper, a greedy heuristic and two local search algorithms, 1-opt local search and k-opt local search, are proposed for the unconstrained binary quadratic programming problem (BQP). These heuristics are well suited for the incorporation into meta-...
Greedy Semantic Local Search for Small Solutions
Revised Selected Papers of the 12th International Conference on Artificial Evolution - Volume 9554Semantic 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2015
1568 pages
Copyright © 2015 ACM.
Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 July 2015
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
GECCO '15
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 43Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in