Cited By
View all- Tauritz DWoodward JLi XHandl J(2024)Generative Hyper-heuristicsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648417(1069-1095)Online publication date: 14-Jul-2024
Dynamic primitive granularity control: an exploration of unique design considerations
Pages 1906 - 1914
Abstract
Dynamic primitive granularity control (DPGC) is a promising avenue for improving the performance of genetic programming (GP). However, it remains almost entirely unexplored. Further, it may pose many unique challenges in its design and implementation that traditional GP implementations do not. This paper presents an implementation of DPGC in order to determine what aspects of conventional GP design and implementation require special consideration. There are some common techniques used in GP that have been found here to negatively impact DPGC's ability to improve performance. Parsimony pressure appears to disproportionately penalize low-level primitives, and a mixed-granularity population suffers from heavy biases towards particular granularity levels, seemingly to the detriment of evolution. This paper provides hypotheses as to why these conventional techniques harm DPGC implementations, as well as several potential alternatives for use in the future that may remedy these detrimental effects.
References
[1]
Aaron S. Pope, Daniel R. Tauritz, and Alexander D. Kent. 2016. Evolving random graph generators: A case for increased algorithmic primitive granularity. IEEE Symposium Series on Computational Intelligence (SSCI). IEEE.
[2]
Matthew A. Martin and Daniel R. Tauritz. 2015. Hyper-Heuristics: A Study On Increasing Primitive-Space. In Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO Companion '15). Association for Computing Machinery, New York, NY, USA, 1051--1058.
[3]
Brian W. Goldman and Daniel R. Tauritz. 2011. Meta-evolved empirical evidence of the effectiveness of dynamic parameters. In Proceedings of the 13th annual conference companion on Genetic and evolutionary computation (GECCO '11). Association for Computing Machinery, New York, NY, USA.
[4]
Adam Harter, Aaron S. Pope, Daniel R. Tauritz, and Chris Rawlings. 2019. Empirical evidence of the effectiveness of primitive granularity control for hyper-heuristics. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '19). Association for Computing Machinery, New York, NY, USA, 1478--1486.
[5]
Aaron S. Pope, "The Automated Design of Network Graph Algorithms with Applications in Cybersecurity" Chapter 7, pp. 110--138. PhD diss, Auburn University, 2019
[6]
David J. Montana. "Strongly Typed Genetic Programming," Evolutionary Computation, vol. 3 issue 2, pp 199--230, June 1995.
[7]
K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," in IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182--197, April 2002.
[8]
Walker M (2001) Introduction to genetic programming. Tech Np: University of Montana, Missoula
[9]
John R. Koza, "Genetic Programming II: Automatic Discovery of Reusable Programs.," in Artificial Life, vol. 1, no. 4, pp. 439--441, July 1994.
[10]
Michael O'Neill, Leonardo Vanneschi, Steven Gustafson, and Wolfgang Banzhaf. 2010. Open issues in genetic programming. Genetic Programming and Evolvable Machines 11, 3--4 (September 2010), 339--363.
[11]
L. Spector, Evolving control structures with automatically defined macros. In Working Notes for the AAAI Symposium on Genetic Programming (MIT, Cambridge, MA, USA, 10--12 Nov 1995), ed. by E.V. Siegel, J.R. Koza (AAAI, 1995), pp. 99--105
[12]
J.P. Rosca, Towards automatic discovery of building blocks in genetic programming. In Working Notes for the AAAI Symposium on Genetic Programming (AAAI, 1995), pp. 78--85
[13]
I. Jonyer, A. Himes, Improving modularity in genetic programming using graph-based data mining. In Proceedings of the 19th International Florida Artificial Intelligence Research Society Conference (Melbourne Beach, FL, USA, May 11--13 2006), ed. by G.C.J. Sutcliffe, R.G. Goebel (American Association for Artificial Intelligence, 2006), pp. 556--561
[14]
R. Poli, W. B. Langdon, and N. F. McPhee, A Field Guide to Genetic Programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).
[15]
Aaron S. Pope and Daniel R. Tauritz. 2020. Automated Design of Multi-Level Network Partitioning Heuristics Employing Self-Adaptive Primitive Granularity Control. In Genetic and Evolutionary Computation Conference (GECCO '20), July 8--12, 2020, Cancún, Mexico. ACM, New York, NY, USA, 9 pages.
Index Terms
- Dynamic primitive granularity control: an exploration of unique design considerations
Recommendations
HMXT-GP: an information-theoretic approach to genetic programming that maintains diversity
SAC '11: Proceedings of the 2011 ACM Symposium on Applied ComputingThis paper applies a recent information--theoretic approach to controlling Genetic Algorithms (GAs) called HMXT to tree--based Genetic Programming (GP). HMXT, in a GA domain, requires the setting of selection thresholds in a population and the ...
Evolving choice structures for genetic programming
It is quite difficult but essential for Genetic Programming (GP) to evolve the choice structures. Traditional approaches usually ignore this issue. They define some ''if-structures'' functions according to their problems by combining ''if-else'' ...
Impact of Crossover Bias in Genetic Programming
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary ComputationIn tree-based genetic programming (GP) with sub-tree crossover, the parent contributing the root portion of the tree (the root parent) often contributes more to the semantics of the resulting child than the non-root parent. Previous research ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2020 ACM.
© 2020 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of the United States government. As such, the United States 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: 08 July 2020
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Los Alamos National Laboratory
Conference
GECCO '20
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 172Total Downloads
- Downloads (Last 12 months)57
- Downloads (Last 6 weeks)13
Reflects downloads up to 02 Mar 2025
Other Metrics
Citations
Cited By
View all- Tauritz DWoodward JLi XHandl J(2024)Generative Hyper-heuristicsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648417(1069-1095)Online publication date: 14-Jul-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in