@article{Helmuth:2021:ALifeJournal,
author = {Thomas Helmuth and Lee Spector},
title = {Problem-solving benefits of down-sampled lexicase selection},
journal = {Artificial Life},
year = {2021},
note = {In press},
doi-url = {},
url = {},
pdf = {https://arxiv.org/pdf/2106.06085.pdf}
}
@article{Helmuth:2020:GPEM,
author = {Thomas Helmuth and Edward Pantridge and Lee Spector},
title = {On the importance of specialists for lexicase selection},
journal = {Genetic Programming and Evolvable Machines},
publisher = {Springer},
year = {2020},
volume = {21},
number = {3},
pages = {349--373},
month = sep,
note = {Special Issue: Highlights of Genetic Programming 2019
Events},
keywords = {genetic algorithms, genetic programming, Lexicase
selection, Specialists, Parent selection, Program
synthesis},
issn = {1389-2576},
doi = {doi:10.1007/s10710-020-09377-2},
size = {25 pages},
abstract = {Lexicase parent selection filters the population by
considering one random training case at a time,
eliminating any individual with an error for the
current case that is worse than the best error of any
individual in the selection pool, until a single
individual remains. This process often stops before
considering all training cases, meaning that it will
ignore the error values on any cases that were not yet
considered. Lexicase selection can therefore select
specialist individuals that have high errors on some
training cases, if they have low errors on others and
those errors come near the start of the random list of
cases used for the parent selection event in question.
We hypothesize here that selecting such specialists,
which may have high total error, plays an important
role in lexicase selection observed performance
advantages over error-aggregating parent selection
methods such as tournament selection, which select
specialists less frequently. We conduct experiments
examining},
doi-url = {http://dx.doi.org/10.1007/s10710-020-09377-2},
url = {https://link.springer.com/article/10.1007%2Fs10710-020-09377-2},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2020-GPEM-lexicase-specialists.pdf}
}
@article{LaCava:2019:ecj,
author = {William {La Cava} and Thomas Helmuth and Lee Spector
and Jason H. Moore},
title = {A probabilistic and multi-objective analysis of
lexicase selection and epsilon-lexicase selection},
journal = {Evolutionary Computation},
year = {2019},
url = {https://www.mitpressjournals.org/doi/pdf/10.1162/evco_a_00224},
pdf = {https://arxiv.org/pdf/1709.05394.pdf},
keywords = {genetic algorithms, genetic programming},
issn = {1063-6560},
doi = {doi:10.1162/evco_a_00224},
size = {28 pages},
abstract = {Lexicase selection is a parent selection method that
considers training cases individually, rather than in
aggregate, when performing parent selection. Whereas
previous work has demonstrated the ability of lexicase
selection to solve difficult problems in program
synthesis and symbolic regression, the central goal of
this paper is to develop the theoretical underpinnings
that explain its performance. To this end, we derive an
analytical formula that gives the expected
probabilities of selection under lexicase selection,
given a population and its behaviour. In addition, we
expand upon the relation of lexicase selection to
many-objective optimization methods to describe the
behavior of lexicase selection, which is to select
individuals on the boundaries of Pareto fronts in
high-dimensional space. We show analytically why
lexicase selection performs more poorly for certain
sizes of population and training cases, and show why it
has been shown to perform more poorly in continuous
error spaces. To address this last concern, we propose
new variants of epsilon-lexicase selection, a method
that modifies the pass condition in lexicase selection
to allow near-elite individuals to pass cases, thereby
improving selection performance with continuous errors.
We show that epsilon-lexicase outperforms several
diversity-maintenance strategies on a number of
real-world and synthetic regression problems.},
doi-url = {http://dx.doi.org/10.1162/evco_a_00224}
}
@article{Helmuth:2015:ieeeTEC,
author = {Thomas Helmuth and Lee Spector and James Matheson},
title = {Solving Uncompromising Problems with Lexicase
Selection},
journal = {IEEE Transactions on Evolutionary Computation},
year = {2015},
volume = {19},
number = {5},
pages = {630--643},
month = oct,
keywords = {genetic algorithms, genetic programming, parent
selection, lexicase selection, tournament selection,
PushGP},
issn = {1089-778X},
url = {http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6920034},
doi = {doi:10.1109/TEVC.2014.2362729},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/lexicase-IEEETEC-2014.pdf},
size = {14 pages},
abstract = {We describe a broad class of problems, called
uncompromising problems, characterised by the
requirement that solutions must perform optimally on
each of many test cases. Many of the problems that have
long motivated genetic programming research, including
the automation of many traditional programming tasks,
are uncompromising. We describe and analyse the
recently proposed lexicase parent selection algorition
and show that it can facilitate the solution of
uncompromising problems by genetic programming. Unlike
most traditional parent selection techniques, lexicase
selection does not base selection on a fitness value
that is aggregated over all test cases; rather, it
considers test cases one at a time in random order. We
present results comparing lexicase selection to more
traditional parent selection methods, including
standard tournament selection and implicit fitness
sharing, on four uncompromising problems: finding terms
in finite algebras, designing digital multipliers,
counting words in files, and performing symbolic
regression of the factorial function. We provide
evidence that lexicase selection maintains higher
levels of population diversity than other selection
methods, which may partially explain its utility as a
parent selection algorithm in the context of
uncompromising problems.},
notes = {also known as \cite{6920034}},
doi-url = {http://dx.doi.org/10.1109/TEVC.2014.2362729}
}
@inproceedings{Helmuth:2021:GECCO:PSB2,
author = {Thomas Helmuth and Peter Kelly},
title = {{PSB2}: The Second Program Synthesis Benchmark Suite},
booktitle = {2021 Genetic and Evolutionary Computation Conference},
series = {GECCO '21},
year = {2021},
isbn13 = {978-1-4503-8350-9},
address = {Lille, France},
size = {10 pages},
doi = {10.1145/3449639.3459285},
publisher = {ACM},
publisher_address = {New York, NY, USA},
month = {10-14} # jul,
doi-url = {https://doi.org/10.1145/3449639.3459285},
url = {https://dl.acm.org/doi/10.1145/3449639.3459285},
pdf = {https://arxiv.org/pdf/2106.06086.pdf},
associated = {https://cs.hamilton.edu/~thelmuth/PSB2/PSB2.html},
note = {\textbf{Nominated, Best Paper Award, Genetic Programming Track}}
}
@inproceedings{Helmuth:2020:ALife:downsampledlexicase,
author = {Helmuth, Thomas and Spector, Lee},
title = {Explaining and Exploiting the Advantages of Down-sampled Lexicase Selection},
booktitle = {Artificial Life Conference Proceedings},
publisher = {MIT Press},
pages = {341-349},
month = {13-18 } # jul,
year = {2020},
doi = {10.1162/isal_a_00334},
url = {https://direct.mit.edu/isal/proceedings/isal2020/32/341/98485},
pdf = {https://direct.mit.edu/isal/proceedings-pdf/isal2020/32/341/1908528/isal_a_00334.pdf},
video = {https://youtu.be/IR14htbTatg},
abstract = { In genetic programming, parent selection is ordinarily based on aggregate measures of performance across an entire training set. Lexicase selection, by contrast, selects on the basis of performance on random sequences of test cases; this has been shown to enhance problem-solving power in many circumstances. Lexicase selection can also be seen as better reflecting biological evolution, by modeling sequences of challenges that organisms face over their lifetimes. Recent work has demonstrated that the advantages of lexicase selection can be amplified by down-sampling, meaning that only a random subsample of the training cases is used each generation, which can also be seen as modeling environmental change over time. Here we provide the most extensive benchmarking of down-sampled lexicase selection to date, showing that its benefits hold up to increased scrutiny. The reasons that down-sampling helps, however, are not yet fully understood. Hypotheses include that down-sampling allows for more generations to be processed with the same budget of program evaluations; that the variation of training data across generations acts as a changing environment, encouraging adaptation; or that it reduces overfitting, leading to more general solutions. We systematically evaluate these hypotheses, finding evidence against all three, and instead draw the conclusion that down-sampled lexicase selection's main benefit stems from the fact that it allows GP to examine more individuals within the same computational budget, even though each individual is examined less completely. }
}
@inproceedings{Helmuth:2020:ALife:source,
author = {Helmuth, Thomas and Pantridge, Edward and Woolson, Grace and Spector, Lee},
title = {Genetic Source Sensitivity and Transfer Learning in Genetic Programming},
booktitle = {Artificial Life Conference Proceedings},
publisher = {MIT Press},
pages = {303-311},
month = {13-18 } # jul,
year = {2020},
doi = {10.1162/isal_a_00326},
url = {https://direct.mit.edu/isal/proceedings/isal2020/32/303/98422},
pdf = {https://direct.mit.edu/isal/proceedings-pdf/isal2020/32/303/1908486/isal_a_00326.pdf},
video = {https://youtu.be/w1ogl2oNVgc},
abstract = { Genetic programming uses biologically-inspired processes of variation and selection to synthesize computer programs that solve problems. Here we investigate the sensitivity of genetic programming to changes in the probability that particular instructions and constants will be chosen for inclusion in randomly generated programs or for introduction by mutation. We find, contrary to conventional wisdom within the field, that genetic programming can be highly sensitive to changes in this source of new genetic material. Additionally, we find that genetic sources can be tuned to significantly improve adaptation across sets of related problems. We study the evolution of solutions to software synthesis problems using untuned genetic sources and sources that have been tuned on the basis of problem statements, human intuition, or prevalence in prior solution programs. We find significant differences in performance across these approaches, and use these lessons to develop a method for tuning genetic sources on the basis of evolved solutions to related problems. This “transfer learning” approach tunes genetic sources nearly as well as humans do, but by means of a fully automated process that can be applied to previously unsolved problems. }
}
@inproceedings{Helmuth:2019:GECCO,
author = {Thomas Helmuth and Edward Pantridge and Lee Spector},
title = {Lexicase selection of specialists},
booktitle = {GECCO '19: Proceedings of the Genetic and Evolutionary
Computation Conference},
year = {2019},
noeditor = {Manuel Lopez-Ibanez and Thomas Stuetzle and Anne Auger
and Petr Posik and Leslie {Peprez Caceres} and Andrew
M. Sutton and Nadarajen Veerapen and Christine Solnon
and Andries Engelbrecht and Stephane Doncieux and
Sebastian Risi and Penousal Machado and Vanessa Volz
and Christian Blum and Francisco Chicano and Bing Xue
and Jean-Baptiste Mouret and Arnaud Liefooghe and
Jonathan Fieldsend and Jose Antonio Lozano and Dirk
Arnold and Gabriela Ochoa and Tian-Li Yu and Holger
Hoos and Yaochu Jin and Ting Hu and Miguel Nicolau and
Robin Purshouse and Thomas Baeck and Justyna Petke and
Giuliano Antoniol and Johannes Lengler and Per Kristian
Lehre},
isbn13 = {978-1-4503-6111-8},
pages = {1030--1038},
address = {Prague, Czech Republic},
doi = {doi:10.1145/3321707.3321875},
publisher = {ACM},
publisher_address = {New York, NY, USA},
month = {13-17 } # jul,
organisation = {SIGEVO},
keywords = {genetic algorithms, genetic programming},
notes = {Also known as \cite{3321875} GECCO-2019 A
Recombination of the 28th International Conference on
Genetic Algorithms (ICGA) and the 24th Annual Genetic
Programming Conference (GP)},
doi-url = {http://dx.doi.org/10.1145/3321707.3321875},
url = {https://dl.acm.org/citation.cfm?doid=3321707.3321875},
pdf = {https://arxiv.org/pdf/1905.09372.pdf},
note = {\textbf{Winner of Best Paper Award, Genetic Programming Track} (38\% acceptance rate out of 39 submissions in track, 3 best paper nominations)}
}
@inproceedings{Jundt:2019:GECCO,
author = {Lia Jundt and Thomas Helmuth},
title = {Comparing and combining lexicase selection and novelty
search},
booktitle = {GECCO '19: Proceedings of the Genetic and Evolutionary
Computation Conference},
year = {2019},
noeditor = {Manuel Lopez-Ibanez and Thomas Stuetzle and Anne Auger
and Petr Posik and Leslie {Peprez Caceres} and Andrew
M. Sutton and Nadarajen Veerapen and Christine Solnon
and Andries Engelbrecht and Stephane Doncieux and
Sebastian Risi and Penousal Machado and Vanessa Volz
and Christian Blum and Francisco Chicano and Bing Xue
and Jean-Baptiste Mouret and Arnaud Liefooghe and
Jonathan Fieldsend and Jose Antonio Lozano and Dirk
Arnold and Gabriela Ochoa and Tian-Li Yu and Holger
Hoos and Yaochu Jin and Ting Hu and Miguel Nicolau and
Robin Purshouse and Thomas Baeck and Justyna Petke and
Giuliano Antoniol and Johannes Lengler and Per Kristian
Lehre},
isbn13 = {978-1-4503-6111-8},
pages = {1047--1055},
address = {Prague, Czech Republic},
doi = {doi:10.1145/3321707.3321787},
publisher = {ACM},
publisher_address = {New York, NY, USA},
month = {13-17 } # jul,
organisation = {SIGEVO},
keywords = {genetic algorithms, genetic programming},
notes = {Also known as \cite{3321787} GECCO-2019 A
Recombination of the 28th International Conference on
Genetic Algorithms (ICGA) and the 24th Annual Genetic
Programming Conference (GP)},
doi-url = {http://dx.doi.org/10.1145/3321707.3321787},
url = {https://dl.acm.org/citation.cfm?doid=3321707.3321787},
pdf = {https://arxiv.org/pdf/1905.09374.pdf}
}
@inproceedings{Helmuth:2018:GECCO,
author = {Thomas Helmuth and Nicholas Freitag McPhee and Lee
Spector},
title = {Program synthesis using uniform mutation by addition
and deletion},
booktitle = {GECCO '18: Proceedings of the Genetic and Evolutionary
Computation Conference},
year = {2018},
noeditor = {Hernan Aguirre and Keiki Takadama and Hisashi Handa
and Arnaud Liefooghe and Tomohiro Yoshikawa and Andrew
M. Sutton and Satoshi Ono and Francisco Chicano and
Shinichi Shirakawa and Zdenek Vasicek and Roderich
Gross and Andries Engelbrecht and Emma Hart and
Sebastian Risi and Ekart Aniko and Julian Togelius and
S{\'e}bastien Verel and Christian Blum and Will Browne
and Yusuke Nojima and Tea Tusar and Qingfu Zhang and
Nikolaus Hansen and Jose Antonio Lozano and Dirk
Thierens and Tian-Li Yu and J{\"u}rgen Branke and
Yaochu Jin and Sara Silva and Hitoshi Iba and Anna I
Esparcia-Alcazar and Thomas Bartz-Beielstein and
Federica Sarro and Giuliano Antoniol and Anne Auger and
Per Kristian Lehre},
isbn13 = {978-1-4503-5618-3},
pages = {1127--1134},
address = {Kyoto, Japan},
url = {http://doi.acm.org/10.1145/3205455.3205603},
doi = {doi:10.1145/3205455.3205603},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2018-GECCO-UMAD.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
month = {15-19 } # jul,
organisation = {SIGEVO},
keywords = {genetic algorithms, genetic programming},
notes = {Also known as \cite{3205603} GECCO-2018 A
Recombination of the 27th International Conference on
Genetic Algorithms (ICGA-2018) and the 23rd Annual
Genetic Programming Conference (GP-2018)},
doi-url = {http://dx.doi.org/10.1145/3205455.3205603},
note = {\textbf{Winner of Best Paper Award, Genetic Programming Track} (37\% acceptance rate out of 30 submissions in track, 3 best paper nominations)}
}
@inproceedings{Helmuth:2017:GECCO,
author = {Thomas Helmuth and Nicholas Freitag McPhee and Edward
Pantridge and Lee Spector},
title = {Improving Generalization of Evolved Programs Through
Automatic Simplification},
booktitle = {Proceedings of the Genetic and Evolutionary
Computation Conference},
series = {GECCO '17},
year = {2017},
isbn13 = {978-1-4503-4920-8},
address = {Berlin, Germany},
pages = {937--944},
size = {8 pages},
url = {http://doi.acm.org/10.1145/3071178.3071330},
doi = {doi:10.1145/3071178.3071330},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2017-GECCO-simplification-for-generalization.pdf},
acmid = {3071330},
publisher = {ACM},
publisher_address = {New York, NY, USA},
keywords = {genetic programming, automatic
simplification, generalization, overfitting, Push},
month = {15-19 } # jul,
notes = {Also known as \cite{Helmuth:2017:IGE:3071178.3071330}
GECCO-2017 A Recombination of the 26th International
Conference on Genetic Algorithms (ICGA-2017) and the
22nd Annual Genetic Programming Conference (GP-2017)},
doi-url = {http://dx.doi.org/10.1145/3071178.3071330},
note = {\textbf{Nominated, Best Paper Award, Genetic Programming Track} (36\% acceptance rate out of 47 submissions in track, 3 best paper nominations)}
}
@inproceedings{Helmuth:2016:GECCO,
author = {Thomas Helmuth and Nicholas Freitag McPhee and Lee
Spector},
title = {The Impact of Hyperselection on Lexicase Selection},
booktitle = {GECCO '16: Proceedings of the 2016 conference on Genetic and
Evolutionary Computation Conference},
year = {2016},
editor = {Tobias Friedrich},
pages = {717--724},
keywords = {genetic algorithms, genetic programming},
month = {20-24 } # jul,
organisation = {SIGEVO},
address = {Denver, USA},
publisher = {ACM},
publisher_address = {New York, NY, USA},
isbn13 = {978-1-4503-4206-3},
doi = {doi:10.1145/2908812.2908851},
url = {http://doi.acm.org/10.1145/2908812.2908851},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2016-GECCO-hyperselection.pdf},
abstract = {Lexicase selection is a parent selection method that
has been shown to improve the problem solving power of
genetic programming over a range of problems. Previous
work has shown that it can also produce hyperselection
events, in which a single individual is selected many
more times than other individuals. Here we investigate
the role that hyperselection plays in the
problem-solving performance of lexicase selection. We
run genetic programming on a set of program synthesis
benchmark problems using lexicase and tournament
selection, confirming that hyperselection occurs
significantly more often and more drastically with
lexicase selection, which also performs significantly
better. We then show results from an experiment
indicating that hyperselection is not integral to the
problem-solving performance or diversity maintenance
observed when using lexicase selection. We conclude
that the power of lexicase selection stems from the
collection of individuals that it selects, not from the
unusual frequencies with which it sometimes selects
them.},
notes = {Washington and Lee University, University of Minnesota
Morris, Hampshire College GECCO-2016 A Recombination of
the 25th International Conference on Genetic Algorithms
(ICGA-2016) and the 21st Annual Genetic Programming
Conference (GP-2016)},
doi-url = {http://dx.doi.org/10.1145/2908812.2908851},
note = {\textbf{Nominated, Best Paper Award, Genetic Programming Track} (39\% acceptance rate out of 31 submissions in track, 3 best paper nominations)}
}
@inproceedings{Helmuth:2015:GECCO,
author = {Thomas Helmuth and Lee Spector},
title = {General Program Synthesis Benchmark Suite},
booktitle = {GECCO '15: Proceedings of the 2015 conference on Genetic and
Evolutionary Computation Conference},
year = {2015},
noeditor = {Sara Silva and Anna I Esparcia-Alcazar and Manuel
Lopez-Ibanez and Sanaz Mostaghim and Jon Timmis and
Christine Zarges and Luis Correia and Terence Soule and
Mario Giacobini and Ryan Urbanowicz and Youhei Akimoto
and Tobias Glasmachers and Francisco {Fernandez de
Vega} and Amy Hoover and Pedro Larranaga and Marta Soto
and Carlos Cotta and Francisco B. Pereira and Julia
Handl and Jan Koutnik and Antonio Gaspar-Cunha and
Heike Trautmann and Jean-Baptiste Mouret and Sebastian
Risi and Ernesto Costa and Oliver Schuetze and
Krzysztof Krawiec and Alberto Moraglio and Julian F.
Miller and Pawel Widera and Stefano Cagnoni and JJ
Merelo and Emma Hart and Leonardo Trujillo and Marouane
Kessentini and Gabriela Ochoa and Francisco Chicano and
Carola Doerr},
isbn13 = {978-1-4503-3472-3},
pages = {1039--1046},
keywords = {genetic algorithms, genetic programming},
month = {11-15 } # jul,
organisation = {SIGEVO},
address = {Madrid, Spain},
url = {http://doi.acm.org/10.1145/2739480.2754769},
doi = {doi:10.1145/2739480.2754769},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2015-GECCO-benchmark-suite.pdf},
associated = {http://thelmuth.github.io/GECCO_2015_Benchmarks_Materials/},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {Recent interest in the development and use of
non-trivial benchmark problems for genetic programming
research has highlighted the scarcity of general
program synthesis (also called traditional programming)
benchmark problems. We present a suite of 29 general
program synthesis benchmark problems systematically
selected from sources of introductory computer science
programming problems. This suite is suitable for
experiments with any program synthesis system driven by
input/output examples. We present results from
illustrative experiments using our reference
implementation of the problems in the PushGP genetic
programming system. The results show that the problems
in the suite vary in difficulty and can be useful for
assessing the capabilities of a program synthesis
system.},
notes = {Also known as \cite{2754769} GECCO-2015 A joint
meeting of the twenty fourth international conference
on genetic algorithms (ICGA-2015) and the twentith
annual genetic programming conference (GP-2015)},
doi-url = {http://dx.doi.org/10.1145/2739480.2754769}
}
@inproceedings{LaCava:2015:GECCO,
author = {William {La Cava} and Thomas Helmuth and Lee Spector
and Kourosh Danai},
title = {Genetic Programming with Epigenetic Local Search},
booktitle = {GECCO '15: Proceedings of the 2015 conference on Genetic and
Evolutionary Computation Conference},
year = {2015},
noeditor = {Sara Silva and Anna I Esparcia-Alcazar and Manuel
Lopez-Ibanez and Sanaz Mostaghim and Jon Timmis and
Christine Zarges and Luis Correia and Terence Soule and
Mario Giacobini and Ryan Urbanowicz and Youhei Akimoto
and Tobias Glasmachers and Francisco {Fernandez de
Vega} and Amy Hoover and Pedro Larranaga and Marta Soto
and Carlos Cotta and Francisco B. Pereira and Julia
Handl and Jan Koutnik and Antonio Gaspar-Cunha and
Heike Trautmann and Jean-Baptiste Mouret and Sebastian
Risi and Ernesto Costa and Oliver Schuetze and
Krzysztof Krawiec and Alberto Moraglio and Julian F.
Miller and Pawel Widera and Stefano Cagnoni and JJ
Merelo and Emma Hart and Leonardo Trujillo and Marouane
Kessentini and Gabriela Ochoa and Francisco Chicano and
Carola Doerr},
isbn13 = {978-1-4503-3472-3},
pages = {1055--1062},
keywords = {genetic algorithms, genetic programming},
month = {11-15 } # jul,
organisation = {SIGEVO},
address = {Madrid, Spain},
url = {http://doi.acm.org/10.1145/2739480.2754763},
doi = {doi:10.1145/2739480.2754763},
pdf = {http://hampshire.edu/lspector/pubs/Epigenetics_2015_GECCO_final.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {We focus on improving genetic programming through
local search of the space of program structures using
an inheritable epigenetic layer that specifies active
and inactive genes. We explore several genetic
programming implementations that represent the
different properties that epigenetics can provide, such
as passive structure, phenotypic plasticity, and
inheritable gene regulation. We apply these
implementations to several symbolic regression and
program synthesis problems. For the symbolic regression
problems, the results indicate that epigenetic local
search consistently improves genetic programming by
producing smaller solution programs with better
fitness. Furthermore, we find that incorporating
epigenetic modification as a mutation step in program
synthesis problems can improve the ability of genetic
programming to find exact solutions. By analyzing
population homology we show that the epigenetic
implementations maintain diversity in silenced portions
of programs which may provide protection from premature
convergence.},
notes = {Also known as \cite{2754763} GECCO-2015 A joint
meeting of the twenty fourth international conference
on genetic algorithms (ICGA-2015) and the twentith
annual genetic programming conference (GP-2015)},
doi-url = {http://dx.doi.org/10.1145/2739480.2754763},
note = {\textbf{Nominated, Best Paper Award, Genetic Programming Track} (44\% acceptance rate out of 45 submissions in track, 3 best paper nominations)}
}
@inproceedings{Helmuth:2014:GECCO,
author = {Thomas Helmuth and Lee Spector},
title = {Word count as a traditional programming benchmark
problem for genetic programming},
booktitle = {GECCO '14: Proceedings of the 2014 conference on
Genetic and evolutionary computation},
year = {2014},
noeditor = {Christian Igel and Dirk V. Arnold and Christian Gagne
and Elena Popovici and Anne Auger and Jaume Bacardit
and Dimo Brockhoff and Stefano Cagnoni and Kalyanmoy
Deb and Benjamin Doerr and James Foster and Tobias
Glasmachers and Emma Hart and Malcolm I. Heywood and
Hitoshi Iba and Christian Jacob and Thomas Jansen and
Yaochu Jin and Marouane Kessentini and Joshua D.
Knowles and William B. Langdon and Pedro Larranaga and
Sean Luke and Gabriel Luque and John A. W. McCall and
Marco A. {Montes de Oca} and Alison Motsinger-Reif and
Yew Soon Ong and Michael Palmer and Konstantinos E.
Parsopoulos and Guenther Raidl and Sebastian Risi and
Guenther Ruhe and Tom Schaul and Thomas Schmickl and
Bernhard Sendhoff and Kenneth O. Stanley and Thomas
Stuetzle and Dirk Thierens and Julian Togelius and
Carsten Witt and Christine Zarges},
isbn13 = {978-1-4503-2662-9},
pages = {919--926},
keywords = {genetic algorithms, genetic programming},
month = {12-16 } # jul,
organisation = {SIGEVO},
address = {Vancouver, BC, Canada},
url = {http://doi.acm.org/10.1145/2576768.2598230},
doi = {doi:10.1145/2576768.2598230},
pdf = {https://github.com/thelmuth/GECCO_2014_WC_Materials/raw/master/wc.pdf},
associated = {http://thelmuth.github.io/GECCO_2014_WC_Materials/},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {The Unix utility program wc, which stands for word
count, takes any number of files and prints the number
of newlines, words, and characters in each of the
files. We show that genetic programming can find
programs that replicate the core functionality of the
wc utility, and propose this problem as a traditional
programming benchmark for genetic programming systems.
This wc problem features key elements of programming
tasks that often confront human programmers, including
requirements for multiple data types, a large
instruction set, control flow, and multiple outputs.
Furthermore, it mimics the behavior of a real-world
utility program, showing that genetic programming can
automatically synthesize programs with general utility.
We suggest statistical procedures that should be used
to compare performances of different systems on
traditional programming problems such as the wc
problem, and present the results of a short experiment
using the problem. Finally, we give a short analysis of
evolved solution programs, showing how they make use of
traditional programming concepts.},
notes = {Also known as \cite{2598230} GECCO-2014 A joint
meeting of the twenty third international conference on
genetic algorithms (ICGA-2014) and the nineteenth
annual genetic programming conference (GP-2014)},
doi-url = {http://dx.doi.org/10.1145/2576768.2598230}
}
@inproceedings{Spector:2012:GECCO,
author = {Lee Spector and Kyle Harrington and Thomas Helmuth},
title = {Tag-based modularity in tree-based genetic
programming},
booktitle = {GECCO '12: Proceedings of the fourteenth international
conference on Genetic and evolutionary computation
conference},
year = {2012},
noeditor = {Terry Soule and Anne Auger and Jason Moore and David
Pelta and Christine Solnon and Mike Preuss and Alan
Dorin and Yew-Soon Ong and Christian Blum and Dario
Landa Silva and Frank Neumann and Tina Yu and Aniko
Ekart and Will Browne and Tim Kovacs and Man-Leung Wong
and Clara Pizzuti and Jon Rowe and Tobias Friedrich and
Giovanni Squillero and Nicolas Bredeche and Stephen
Smith and Alison Motsinger-Reif and Jose Lozano and
Martin Pelikan and Silja Meyer-Nienberg and Christian
Igel and Greg Hornby and Rene Doursat and Steve
Gustafson and Gustavo Olague and Shin Yoo and John
Clark and Gabriela Ochoa and Gisele Pappa and Fernando
Lobo and Daniel Tauritz and Jurgen Branke and Kalyanmoy
Deb},
isbn13 = {978-1-4503-1177-9},
pages = {815--822},
keywords = {genetic algorithms, genetic programming},
month = {7-11 } # jul,
organisation = {SIGEVO},
address = {Philadelphia, Pennsylvania, USA},
url = {http://dl.acm.org/citation.cfm?doid=2330163.2330276},
doi = {doi:10.1145/2330163.2330276},
pdf = {http://hampshire.edu/lspector/pubs/p815.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {Several techniques have been developed for allowing
genetic programming systems to produce programs that
make use of subroutines, macros, and other modular
program structures. A recently proposed technique,
based on the tagging and tag-based retrieval of blocks
of code, has been shown to have novel and desirable
features, but this was demonstrated only within the
context of the PushGP genetic programming system.
Following a suggestion in the GECCO-2011 publication on
this technique we show here how tag-based modules can
be incorporated into a more standard tree-based genetic
programming system. We describe the technique in detail
along with some possible extensions, outline arguments
for its simplicity and potential power, and present
results obtained using the technique on problems for
which other modularization techniques have been shown
to be useful. The results are mixed; substantial
benefits are seen on the lawnmower problem but not on
the Boolean even-4-parity problem. We discuss the
observed results and directions for future research.},
notes = {Also known as \cite{2330276} GECCO-2012 A joint
meeting of the twenty first international conference on
genetic algorithms (ICGA-2012) and the seventeenth
annual genetic programming conference (GP-2012)},
doi-url = {http://dx.doi.org/10.1145/2330163.2330276}
}
@inproceedings{Spector:2011:GECCO,
author = {Lee Spector and Brian Martin and Kyle Harrington and
Thomas Helmuth},
title = {Tag-based modules in genetic programming},
booktitle = {GECCO '11: Proceedings of the 13th annual conference
on Genetic and evolutionary computation},
year = {2011},
isbn13 = {978-1-4503-0557-0},
pages = {1419--1426},
keywords = {genetic algorithms, genetic programming, pushGP,
lawnmower},
month = {12-16 } # jul,
organisation = {SIGEVO},
address = {Dublin, Ireland},
url = {http://dl.acm.org/citation.cfm?doid=2001576.2001767},
doi = {doi:10.1145/2001576.2001767},
pdf = {http://hampshire.edu/lspector/pubs/spector-tags-gecco-2011-with-citation.pdf},
associated = {http://hampshire.edu/lspector/tags-gecco-2011/},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {In this paper we present a new technique for evolving
modular programs with genetic programming. The
technique is based on the use of tags that evolving
programs may use to label and later to refer to code
fragments. Tags may refer inexactly, permitting the
labelling and use of code fragments to co-evolve in an
incremental way. The technique can be implemented as a
minor modification to an existing, general purpose
genetic programming system, and it does not require
pre-specification of the module architecture of evolved
programs. We demonstrate that tag-based modules readily
evolve and that this allows problem solving effort to
scale well with problem size. We also show that the
tag-based module technique is effective even in
complex, non-uniform problem environments for which
previous techniques perform poorly. We demonstrate the
technique in the context of the stack-based genetic
programming system PushGP, but we also briefly discuss
ways in which it may be used with other kinds of
genetic programming systems.},
notes = {Section 7: tags in other forms of GP Tag data to be
tried. Also known as \cite{2001767} GECCO-2011 A joint
meeting of the twentieth international conference on
genetic algorithms (ICGA-2011) and the sixteenth annual
genetic programming conference (GP-2011)},
doi-url = {http://dx.doi.org/10.1145/2001576.2001767}
}
@inproceedings{Ahmad:2018:GECCO,
author = {Hammad Ahmad and Thomas Helmuth},
title = {A comparison of semantic-based initialization methods
for genetic programming},
booktitle = {GECCO '18: Proceedings of the Genetic and Evolutionary
Computation Conference Companion},
year = {2018},
noeditor = {Carlos Cotta and Tapabrata Ray and Hisao Ishibuchi and
Shigeru Obayashi and Bogdan Filipic and Thomas
Bartz-Beielstein and Grant Dick and Masaharu Munetomo
and Silvino {Fernandez Alzueta} and Thomas Stuetzle and
Pablo Valledor Pellicer and Manuel Lopez-Ibanez and
Daniel R. Tauritz and Pietro S. Oliveto and Thomas
Weise and Borys Wrobel and Ales Zamuda and Anne Auger
and Julien Bect and Dimo Brockhoff and Nikolaus Hansen
and Rodolphe {Le Riche} and Victor Picheny and Bilel
Derbel and Ke Li and Hui Li and Xiaodong Li and Saul
Zapotecas and Qingfu Zhang and Stephane Doncieux and
Richard Duro and Joshua Auerbach and Harold {de Vladar}
and Antonio J. Fernandez-Leiva and JJ Merelo and Pedro
A. Castillo-Valdivieso and David Camacho-Fernandez and
Francisco {Chavez de la O} and Ozgur Akman and Khulood
Alyahya and Juergen Branke and Kevin Doherty and
Jonathan Fieldsend and Giuseppe Carlo Marano and Nikos
D. Lagaros and Koichi Nakayama and Chika Oshima and
Stefan Wagner and Michael Affenzeller and Boris Naujoks
and Vanessa Volz and Tea Tusar and Pascal Kerschke and
Riyad Alshammari and Tokunbo Makanju and Brad Alexander
and Saemundur O. Haraldsson and Markus Wagner and John
R. Woodward and Shin Yoo and John McCall and Nayat
Sanchez-Pi and Luis Marti and Danilo Vasconcellos and
Masaya Nakata and Anthony Stein and Nadarajen Veerapen
and Arnaud Liefooghe and Sebastien Verel and Gabriela
Ochoa and Stephen L. Smith and Stefano Cagnoni and
Robert M. Patton and William {La Cava} and Randal Olson
and Patryk Orzechowski and Ryan Urbanowicz and Ivanoe
{De Falco} and Antonio {Della Cioppa} and Ernesto
Tarantino and Umberto Scafuri and P. G. M. Baltus and
Giovanni Iacca and Ahmed Hallawa and Anil Yaman and
Alma Rahat and Handing Wang and Yaochu Jin and David
Walker and Richard Everson and Akira Oyama and Koji
Shimoyama and Hemant Kumar and Kazuhisa Chiba and
Pramudita Satria Palar},
isbn13 = {978-1-4503-5764-7},
pages = {1878--1881},
address = {Kyoto, Japan},
doi = {doi:10.1145/3205651.3208218},
url = {http://doi.acm.org/10.1145/3205651.3208218},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2018-GECCO-workshop-semantic-initialization.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
month = {15-19 } # jul,
organisation = {SIGEVO},
keywords = {genetic algorithms, genetic programming},
abstract = {During the initialization step, a genetic programming
(GP) system traditionally creates a population of
completely random programs to populate the initial
population. These programs almost always perform poorly
in terms of their total error---some might not even
output the correct data type. In this paper, we present
new methods for initialization that attempt to generate
programs that are somewhat relevant to the problem
being solved and/or increase the initial diversity
(both error and behavioural diversity) of the
population prior to the GP run. By seeding the
population---and thereby eliminating worthless programs
and increasing the initial diversity of the
population---we hope to improve the performance of the
GP system. Here, we present two novel techniques for
initialization (Lexicase Seeding and Pareto Seeding)
and compare them to a previous method (Enforced Diverse
Populations) and traditional, non-seeded
initialization. Surprisingly, we found that none of the
initialization m},
notes = {Also known as \cite{3208218} GECCO-2018 A
Recombination of the 27th International Conference on
Genetic Algorithms (ICGA-2018) and the 23rd Annual
Genetic Programming Conference (GP-2018)},
doi-url = {http://dx.doi.org/10.1145/3205651.3208218}
}
@inproceedings{Pantridge:2018:GECCO,
author = {Edward Pantridge and Thomas Helmuth and Nicholas
Freitag McPhee and Lee Spector},
title = {Specialization and elitism in lexicase and tournament
selection},
booktitle = {GECCO '18: Proceedings of the Genetic and Evolutionary
Computation Conference Companion},
year = {2018},
noeditor = {Carlos Cotta and Tapabrata Ray and Hisao Ishibuchi and
Shigeru Obayashi and Bogdan Filipic and Thomas
Bartz-Beielstein and Grant Dick and Masaharu Munetomo
and Silvino {Fernandez Alzueta} and Thomas Stuetzle and
Pablo Valledor Pellicer and Manuel Lopez-Ibanez and
Daniel R. Tauritz and Pietro S. Oliveto and Thomas
Weise and Borys Wrobel and Ales Zamuda and Anne Auger
and Julien Bect and Dimo Brockhoff and Nikolaus Hansen
and Rodolphe {Le Riche} and Victor Picheny and Bilel
Derbel and Ke Li and Hui Li and Xiaodong Li and
Sa{\'u}l Zapotecas and Qingfu Zhang and St{\'e}phane
Doncieux and Richard Duro and Joshua Auerbach and
Harold {de Vladar} and Antonio J. Fernandez-Leiva and
JJ Merelo and Pedro A. Castillo-Valdivieso and David
Camacho-Fernandez and Francisco {Chavez de la O} and
Ozgur Akman and Khulood Alyahya and Juergen Branke and
Kevin Doherty and Jonathan Fieldsend and Giuseppe Carlo
Marano and Nikos D. Lagaros and Koichi Nakayama and
Chika Oshima and Stefan Wagner and Michael Affenzeller
and Boris Naujoks and Vanessa Volz and Tea Tusar and
Pascal Kerschke and Riyad Alshammari and Tokunbo
Makanju and Brad Alexander and Saemundur O. Haraldsson
and Markus Wagner and John R. Woodward and Shin Yoo and
John McCall and Nayat Sanchez-Pi and Luis Mart{\'i} and
Danilo Vasconcellos and Masaya Nakata and Anthony Stein
and Nadarajen Veerapen and Arnaud Liefooghe and
S{\'e}bastien Verel and Gabriela Ochoa and Stephen L.
Smith and Stefano Cagnoni and Robert M. Patton and
William {La Cava} and Randal Olson and Patryk
Orzechowski and Ryan Urbanowicz and Ivanoe {De Falco}
and Antonio {Della Cioppa} and Ernesto Tarantino and
Umberto Scafuri and P. G. M. Baltus and Giovanni Iacca
and Ahmed Hallawa and Anil Yaman and Alma Rahat and
Handing Wang and Yaochu Jin and David Walker and
Richard Everson and Akira Oyama and Koji Shimoyama and
Hemant Kumar and Kazuhisa Chiba and Pramudita Satria
Palar},
isbn13 = {978-1-4503-5764-7},
pages = {1914--1917},
address = {Kyoto, Japan},
url = {http://doi.acm.org/10.1145/3205651.3208220},
doi = {doi:10.1145/3205651.3208220},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2018-GECCO-workshop-lexicase-specialization.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
month = {15-19 } # jul,
organisation = {SIGEVO},
notes = {Also known as \cite{3208220} GECCO-2018 A
Recombination of the 27th International Conference on
Genetic Algorithms (ICGA-2018) and the 23rd Annual
Genetic Programming Conference (GP-2018)},
doi-url = {http://dx.doi.org/10.1145/3205651.3208220}
}
@inproceedings{Pantridge:2017:GECCOa,
author = {Edward Pantridge and Thomas Helmuth and Nicholas
Freitag McPhee and Lee Spector},
title = {On the Difficulty of Benchmarking Inductive Program
Synthesis Methods},
booktitle = {Proceedings of the Genetic and Evolutionary
Computation Conference Companion},
series = {GECCO '17},
year = {2017},
isbn13 = {978-1-4503-4939-0},
address = {Berlin, Germany},
pages = {1589--1596},
size = {8 pages},
url = {http://doi.acm.org/10.1145/3067695.3082533},
doi = {doi:10.1145/3067695.3082533},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2017-GECCO-workshop-benchmarking-program-synthesis.pdf},
acmid = {3082533},
publisher = {ACM},
publisher_address = {New York, NY, USA},
keywords = {genetic algorithms, genetic programming, benchmarking,
inductive program synthesis, machine learning},
month = {15-19 } # jul,
abstract = {A variety of inductive program synthesis (IPS)
techniques have recently been developed, emerging from
different areas of computer science. However, these
techniques have not been adequately compared on general
program synthesis problems. In this paper we compare
several methods on problems requiring solution programs
to handle various data types, control structures, and
numbers of outputs. The problem set also spans levels
of abstraction; some would ordinarily be approached
using machine code or assembly language, while others
would ordinarily be approached using high-level
languages. The presented comparisons are focused on the
possibility of success; that is, on whether the system
can produce a program that passes all tests, for all
training and unseen testing inputs. The compared
systems are Flash Fill, MagicHaskeller, TerpreT, and
two forms of genetic programming. The two genetic
programming methods chosen were PushGP and Grammar
Guided Genetic Programming. The results suggest that
PushGP and, to an extent, TerpreT and Grammar Guided
Genetic Programming are more capable of finding
solutions than the others, albeit at a higher
computational cost. A more salient observation is the
difficulty of comparing these methods due to
drastically different intended applications, despite
the common goal of program synthesis.},
notes = {Also known as
\cite{Pantridge:2017:DBI:3067695.3082533} GECCO-2017 A
Recombination of the 26th International Conference on
Genetic Algorithms (ICGA-2017) and the 22nd Annual
Genetic Programming Conference (GP-2017)},
doi-url = {http://dx.doi.org/10.1145/3067695.3082533}
}
@inproceedings{Helmuth:2016:GECCOcomp,
author = {Thomas Helmuth and Nicholas Freitag McPhee and Lee
Spector},
title = {Effects of Lexicase and Tournament Selection on
Diversity Recovery and Maintenance},
booktitle = {GECCO '16 Companion: Proceedings of the Companion
Publication of the 2016 Annual Conference on Genetic
and Evolutionary Computation},
year = {2016},
noeditor = {Tobias Friedrich and Frank Neumann and Andrew M.
Sutton and Martin Middendorf and Xiaodong Li and Emma
Hart and Mengjie Zhang and Youhei Akimoto and Peter A.
N. Bosman and Terry Soule and Risto Miikkulainen and
Daniele Loiacono and Julian Togelius and Manuel
Lopez-Ibanez and Holger Hoos and Julia Handl and
Faustino Gomez and Carlos M. Fonseca and Heike
Trautmann and Alberto Moraglio and William F. Punch and
Krzysztof Krawiec and Zdenek Vasicek and Thomas Jansen
and Jim Smith and Simone Ludwig and JJ Merelo and Boris
Naujoks and Enrique Alba and Gabriela Ochoa and Simon
Poulding and Dirk Sudholt and Timo Koetzing},
isbn13 = {978-1-4503-4323-7},
pages = {983--990},
address = {Denver, Colorado, USA},
month = {20-24 } # jul,
keywords = {genetic algorithms, genetic programming},
organisation = {SIGEVO},
doi = {doi:10.1145/2908961.2931657},
url = {http://doi.acm.org/10.1145/2908961.2931657},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2016-GECCO-workshop-diversity-maintenance.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {In genetic programming systems, parent selection
algorithms select the programs from which offspring
will be produced by random variation and recombination.
While most parent selection algorithms select programs
on the basis of aggregate performance on multiple test
cases, the lexicase selection algorithm considers each
test case individually, in random order, for each
parent selection event. Prior work has shown that
lexicase selection can produce both more diverse
populations and more solutions when applied to several
hard problems. Here we examine the effects of lexicase
selection, compared to those of the more traditional
tournament selection algorithm, on population error
diversity using two program synthesis problems. We
conduct experiments in which the same initial
population is used to start multiple runs, each using a
different random number seed. The initial populations
are extracted from genetic programming runs, and fall
into three categories: high diversity populations, low
diversity populations, and populations that occur after
diversity crashes. The reported data shows that
lexicase selection can maintain high error diversity
and also that it can re-diversify less-diverse
populations, while tournament selection consistently
produces lower diversity.},
notes = {Distributed at GECCO-2016.},
doi-url = {http://dx.doi.org/10.1145/2908961.2931657}
}
@inproceedings{Spector:2016:GECCOcomp,
author = {Lee Spector and Nicholas Freitag McPhee and Thomas
Helmuth and Maggie M. Casale and Julian Oks},
title = {Evolution Evolves with Autoconstruction},
booktitle = {GECCO '16 Companion: Proceedings of the Companion
Publication of the 2016 Annual Conference on Genetic
and Evolutionary Computation},
year = {2016},
noeditor = {Tobias Friedrich and Frank Neumann and Andrew M.
Sutton and Martin Middendorf and Xiaodong Li and Emma
Hart and Mengjie Zhang and Youhei Akimoto and Peter A.
N. Bosman and Terry Soule and Risto Miikkulainen and
Daniele Loiacono and Julian Togelius and Manuel
Lopez-Ibanez and Holger Hoos and Julia Handl and
Faustino Gomez and Carlos M. Fonseca and Heike
Trautmann and Alberto Moraglio and William F. Punch and
Krzysztof Krawiec and Zdenek Vasicek and Thomas Jansen
and Jim Smith and Simone Ludwig and JJ Merelo and Boris
Naujoks and Enrique Alba and Gabriela Ochoa and Simon
Poulding and Dirk Sudholt and Timo Koetzing},
isbn13 = {978-1-4503-4323-7},
pages = {1349--1356},
address = {Denver, Colorado, USA},
month = {20-24 } # jul,
keywords = {genetic algorithms, genetic programming},
organisation = {SIGEVO},
doi = {doi:10.1145/2908961.2931727},
url = {http://doi.acm.org/10.1145/2908961.2931727},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2016-GECCO-workshop-autoconstruction.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {In autoconstructive evolutionary algorithms,
individuals implement not only candidate solutions to
specified computational problems, but also their own
methods for variation of offspring. This makes it
possible for the variation methods to themselves
evolve, which could, in principle, produce a system
with an enhanced capacity for adaptation and superior
problem solving power. Prior work on autoconsruction
has explored a range of system designs and their
evolutionary dynamics, but it has not solved hard
problems. Here we describe a new approach that can
indeed solve at least some hard problems. We present
the key components of this approach, including the use
of linear genomes for hierarchically structured
programs, a diversity-maintaining parent selection
algorithm, and the enforcement of diversification
constraints on offspring. We describe a software
synthesis benchmark problem that our new approach can
solve, and we present visualizations of data from
single successful runs of autoconstructive vs.
non-autoconstructive systems on this problem. While
anecdotal, the data suggests that variation methods,
and therefore significant aspects of the evolutionary
process, evolve over the course of the autoconstructive
runs.},
notes = {Distributed at GECCO-2016.},
doi-url = {http://dx.doi.org/10.1145/2908961.2931727}
}
@inproceedings{McPhee:2016:GECCOcomp,
author = {Nicholas Freitag McPhee and Maggie M. Casale and
Mitchell Finzel and Thomas Helmuth and Lee Spector},
title = {Visualizing Genetic Programming Ancestries},
booktitle = {GECCO '16 Companion: Proceedings of the Companion
Publication of the 2016 Annual Conference on Genetic
and Evolutionary Computation},
year = {2016},
isbn13 = {978-1-4503-4323-7},
pages = {1419--1426},
keywords = {genetic algorithms, genetic programming, pushGP, liner
genetic programming, Clojush, lexicase selection},
month = {20-24 } # jul,
organisation = {SIGEVO},
address = {Denver, Colorado, USA},
doi = {doi:10.1145/2908961.2931741},
url = {http://doi.acm.org/10.1145/2908961.2931741},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2016-GECCO-workshop-visualizing-ancestries.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
size = {8 pages},
abstract = {Previous work has demonstrated the utility of graph
databases as a tool for collecting, analysing, and
visualizing ancestry in evolutionary computation runs.
That work focused on sections of individual runs,
whereas this paper illustrates the application of these
ideas on the entirety of large runs (up to three
hundred thousand individuals) and combinations of
multiple runs. Here we use these tools to generate
graphs showing all the ancestors of successful
individuals from a variety of stack-based genetic
programming runs on software synthesis problems. These
graphs highlight important moments in the evolutionary
process. They also allow us to compare the dynamics for
successful and unsuccessful runs. As well as displaying
these full ancestry graphs, we use a variety of
standard techniques such as size, colour, pattern,
labelling, and opacity to visualize other important
information such as fitness, which genetic operators
were used, and the distance between parent and child
genomes. While this generates an extremely rich
visualization, the amount of data can also be somewhat
overwhelming, so we also explore techniques for
filtering these graphs that allow us to better
understand the key dynamics.},
notes = {Titan graph database. Tinkerpop query tools. Graphviz
dot. Mutation and crossover. Hyperselection events.
Replace space with newline benchmark. p1420 'uses
restricted Boltzmann machines (RBMs) to compress the
200 error values into 24-bit RGB color values' p1423
'presence of an individual could have had..impact..even
if..never contributed genetic material' p1423
'unfilter' p1426 future dynamic tools. My pdf reader
barfs Slides
https://www.slideshare.net/NicMcPhee/visualizing-genetic-programming-ancestries
Cites \cite{series/sci/BurlacuAWKK15}},
doi-url = {http://dx.doi.org/10.1145/2908961.2931741}
}
@inproceedings{Liskowski:2015:GECCOcomp,
author = {Pawel Liskowski and Krzysztof Krawiec and Thomas
Helmuth and Lee Spector},
title = {Comparison of Semantic-aware Selection Methods in
Genetic Programming},
booktitle = {GECCO 2015 Semantic Methods in Genetic Programming
(SMGP'15) Workshop},
year = {2015},
noeditor = {Colin Johnson and Krzysztof Krawiec and Alberto
Moraglio and Michael O'Neill},
isbn13 = {978-1-4503-3488-4},
keywords = {genetic algorithms, genetic programming, Semantic
Methods in (SMGP'15) Workshop},
pages = {1301--1307},
month = {11-15 } # jul,
organisation = {SIGEVO},
address = {Madrid, Spain},
url = {http://doi.acm.org/10.1145/2739482.2768505},
doi = {doi:10.1145/2739482.2768505},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2015-GECCO-semantic-aware-selection.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {This study investigates the performance of several
semantic-aware selection methods for genetic
programming (GP). In particular, we consider methods
that do not rely on complete GP semantics (i.e., a
tuple of outputs produced by a program for fitness
cases (tests)), but on binary outcome vectors that only
state whether a given test has been passed by a program
or not. This allows us to relate to test-based problems
commonly considered in the domain of coevolutionary
algorithms and, in prospect, to address a wider range
of practical problems, in particular the problems where
desired program output is unknown (e.g., evolving GP
controllers). The selection methods considered in the
paper include implicit fitness sharing (ifs), discovery
of derived objectives (doc), lexicase selection (lex),
as well as a hybrid of the latter two. These
techniques, together with a few variants, are
experimentally compared to each other and to
conventional GP on a battery of discrete benchmark
problems. The outcomes indicate superior performance of
lex and ifs, with some variants of doc showing certain
potential.},
notes = {Also known as \cite{2768505} Distributed at
GECCO-2015.},
doi-url = {http://dx.doi.org/10.1145/2739482.2768505}
}
@inproceedings{Helmuth:2013:GECCOcomp,
author = {Thomas Helmuth and Lee Spector},
title = {Evolving a digital multiplier with the {PushGP} genetic
programming system},
booktitle = {GECCO '13 Companion: Proceeding of the fifteenth
annual conference companion on Genetic and evolutionary
computation conference companion},
year = {2013},
noeditor = {Christian Blum and Enrique Alba and Thomas
Bartz-Beielstein and Daniele Loiacono and Francisco
Luna and Joern Mehnen and Gabriela Ochoa and Mike
Preuss and Emilia Tantar and Leonardo Vanneschi and
Kent McClymont and Ed Keedwell and Emma Hart and Kevin
Sim and Steven Gustafson and Ekaterina Vladislavleva
and Anne Auger and Bernd Bischl and Dimo Brockhoff and
Nikolaus Hansen and Olaf Mersmann and Petr Posik and
Heike Trautmann and Muhammad Iqbal and Kamran Shafi and
Ryan Urbanowicz and Stefan Wagner and Michael
Affenzeller and David Walker and Richard Everson and
Jonathan Fieldsend and Forrest Stonedahl and William
Rand and Stephen L. Smith and Stefano Cagnoni and
Robert M. Patton and Gisele L. Pappa and John Woodward
and Jerry Swan and Krzysztof Krawiec and
Alexandru-Adrian Tantar and Peter A. N. Bosman and
Miguel Vega-Rodriguez and Jose M. Chaves-Gonzalez and
David L. Gonzalez-Alvarez and Sergio Santander-Jimenez
and Lee Spector and Maarten Keijzer and Kenneth
Holladay and Tea Tusar and Boris Naujoks},
isbn13 = {978-1-4503-1964-5},
keywords = {genetic algorithms, genetic programming},
pages = {1627--1634},
month = {6-10 } # jul,
organisation = {SIGEVO},
address = {Amsterdam, The Netherlands},
url = {http://dl.acm.org/citation.cfm?doid=2464576.2466814},
doi = {doi:10.1145/2464576.2466814},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/digital-multiplier-GECCO-2013.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {A recent article on benchmark problems for genetic
programming suggested that researchers focus attention
on the digital multiplier problem, also known as the
multiple output multiplier problem, in part because it
is scalable and in part because the requirement of
multiple outputs presents challenges for some forms of
genetic programming [20]. Here we demonstrate the
application of stack-based genetic programming to the
digital multiplier problem using the PushGP genetic
programming system, which evolves programs expressed in
the stack-based Push programming language. We
demonstrate the use of output instructions and argue
that they provide a natural mechanism for producing
multiple outputs in a stack-based genetic programming
context. We also show how two recent developments in
PushGP dramatically improve the performance of the
system on the digital multiplier problem. These
developments are the ULTRA genetic operator, which
produces offspring via Uniform Linear Transformation
with Repair and Alternation [12], and lexicase
selection, which selects parents according to
performance on cases considered sequentially in random
order [11]. Our results using these techniques show not
only their utility, but also the utility of the digital
multiplier problem as a benchmark problem for genetic
programming research. The results also demonstrate the
exibility of stack-based genetic programming for
solving problems with multiple outputs and for serving
as a platform for experimentation with new genetic
programming techniques.},
notes = {Also known as \cite{2466814} Distributed at
GECCO-2013.},
doi-url = {http://dx.doi.org/10.1145/2464576.2466814}
}
@inproceedings{Helmuth:2011:GECCOcomp,
author = {Thomas Helmuth and Lee Spector and Brian Martin},
title = {Size-based tournaments for node selection},
booktitle = {GECCO 2011 Graduate students workshop},
year = {2011},
noeditor = {Miguel Nicolau},
isbn13 = {978-1-4503-0690-4},
keywords = {genetic algorithms, genetic programming},
pages = {799--802},
month = {12-16 } # jul,
organisation = {SIGEVO},
address = {Dublin, Ireland},
url = {http://dl.acm.org/citation.cfm?doid=2001858.2002095},
doi = {doi:10.1145/2001858.2002095},
pdf = {http://hampshire.edu/lspector/pubs/node-selection-gecco2011-cited.pdf},
erratum = {http://cs.hamilton.edu/~thelmuth/node-selection-gecco-2011.html},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {In genetic programming, the reproductive operators of
crossover and mutation both require the selection of
nodes from the reproducing individuals. Both unbiased
random selection and Koza 90/10 mechanisms remain
popular, despite their arbitrary natures and a lack of
evidence for their effectiveness. It is generally
considered problematic to select from all nodes with a
uniform distribution, since this causes terminal nodes
to be selected most of the time. This can limit the
complexity of program fragments that can be exchanged
in crossover, and it may also lead to code bloat when
leaf nodes are replaced with larger new subtrees during
mutation. We present a new node selection method that
selects nodes based on a tournament, from which the
largest participating subtree is selected. We show this
method of size-based tournaments improves performance
on three standard test problems with no increases in
code bloat as compared to unbiased and Koza 90/10
selection methods.},
notes = {Also known as \cite{2002095} Distributed on CD-ROM at
GECCO-2011. ACM Order Number 910112.},
doi-url = {http://dx.doi.org/10.1145/2001858.2002095}
}
@inproceedings{Spector:2019:GPTP,
author = {Edward Pantridge and Thomas Helmuth and Lee Spector},
title = {Comparison of Linear Genome Representations For
Software Synthesis},
booktitle = {Genetic Programming Theory and Practice XVII},
year = {2019},
editor = {Wolfgang Banzhaf and Erik Goodman and Leigh Sheneman
and Leonardo Trujillo and Bill Worzel},
pages = {255--274},
address = {East Lansing, MI, USA},
month = {16-19 } # may,
publisher = {Springer},
keywords = {genetic algorithms, genetic programming},
isbn13 = {978-3-030-39957-3},
url = {https://link.springer.com/chapter/10.1007/978-3-030-39958-0_13},
doi = {doi:10.1007/978-3-030-39958-0_13},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2019-GPTP-linear-genomes-representations.pdf},
abstract = {In many genetic programming systems, the program
variation and execution processes operate on different
program representations. The representations on which
variation operates are referred to as genomes.
Unconstrained linear genome representations can provide
a variety of advantages, including reduced complexity
of program generation, variation, simplification and
serialization operations. The Plush genome
representation, which uses epigenetic markers on linear
genomes to express nonlinear structures, has supported
the production of state-of-the-art results in program
synthesis with the PushGP genetic programming system.
Here we present a new, simpler, non-epigenetic
alternative to Plush, called Plushy, that appears to
maintain all of the advantages of Plush while providing
additional benefits. These results illustrate the
virtues of unconstrained linear genome representations
more generally, and may be transferable to genetic
programming systems that target different languages for
evolved programs.},
notes = {Part of \cite{Banzhaf:2019:GPTP}, published after the
workshop},
doi-url = {http://dx.doi.org/10.1007/978-3-030-39958-0_13}
}
@inproceedings{Troise:2017:GPTP,
author = {Sarah Anne Troise and Thomas Helmuth},
title = {Lexicase Selection with Weighted Shuffle},
booktitle = {Genetic Programming Theory and Practice XV},
editor = {Wolfgang Banzhaf and Randal S. Olson and William
Tozier and Rick Riolo},
year = {2017},
series = {Genetic and Evolutionary Computation},
pages = {89--104},
address = {University of Michigan in Ann Arbor, USA},
month = may # { 18--20},
organisation = {the Center for the Study of Complex Systems},
publisher = {Springer},
keywords = {genetic algorithms, genetic programming},
isbn13 = {978-3-319-90511-2},
url = {https://link.springer.com/chapter/10.1007/978-3-319-90512-9_6},
doi = {doi:10.1007/978-3-319-90512-9_6},
abstract = {Semantic-aware methods in genetic programming take
into account information about programs performances
across a set of test cases. Lexicase parent selection,
a semantic-aware selection, randomly shuffles the list
of test cases and places more emphasis on those test
cases that randomly appear earlier in the ordering than
those that appear later in the ordering. In this work,
we explore methods for weighting this shuffling of test
cases to give some test cases more influence over
selection than others. We design and test a variety of
weighted shuffle algorithms and methods for weighting
test cases. In experiments on two program synthesis
benchmark problems, we find that none of these methods
significantly outperform regular lexicase selection. We
analyse these results by examining how each method
affects population diversity, and find that those
methods that perform much worse also have significantly
lower diversity.},
notes = {GPTP 2017, Part of \cite{Banzhaf:2017:GPTP} published
after the workshop in 2018},
doi-url = {http://dx.doi.org/10.1007/978-3-319-90512-9_6},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2017-GPTP-weighted-lexicase.pdf}
}
@inproceedings{Spector:2017:GPTP,
author = {Lee Spector and William {La Cava} and Saul Shanabrook
and Thomas Helmuth and Edward Pantridge},
title = {Relaxations of Lexicase Parent Selection},
booktitle = {Genetic Programming Theory and Practice XV},
editor = {Wolfgang Banzhaf and Randal S. Olson and William
Tozier and Rick Riolo},
year = {2017},
series = {Genetic and Evolutionary Computation},
pages = {105--120},
address = {University of Michigan in Ann Arbor, USA},
month = may # { 18--20},
organisation = {the Center for the Study of Complex Systems},
publisher = {Springer},
keywords = {genetic algorithms, genetic programming},
isbn13 = {978-3-319-90511-2},
url = {https://link.springer.com/chapter/10.1007/978-3-319-90512-9_7},
doi = {doi:10.1007/978-3-319-90512-9_7},
abstract = {In a genetic programming system, the parent selection
algorithm determines which programs in the evolving
population will be used as the material out of which
new programs will be constructed. The lexicase parent
selection algorithm chooses a parent by considering all
test cases, individually, one at a time, in a random
order, to reduce the pool of possible parent programs.
Lexicase selection is ordinarily strict, in that a
program can only be selected if it has the best error
in the entire population on the first test case
considered, and the best error relative to all other
programs that remain in the pool each time it is
reduced. This strictness may exclude high-quality
candidates from consideration for parenthood, and hence
from exploration by the evolutionary process. In this
chapter we describe and present results of four
variants of lexicase selection that relax these strict
constraints: epsilon lexicase selection, random
threshold lexicase selection, MADCAP epsilon lexicase
selection, and truncated lexicase selection. We present
the results of experiments with genetic programming
systems using these and other parent selection
algorithms on symbolic regression and software
synthesis problems. We also briefly discuss the
relations between lexicase selection and work on
many-objective optimization, and the implications of
these considerations for future work on parent
selection in genetic programming.},
notes = {GPTP 2017, Part of \cite{Banzhaf:2017:GPTP} published
after the workshop in 2018},
doi-url = {http://dx.doi.org/10.1007/978-3-319-90512-9_7},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2017-GPTP-relaxed-lexicase.pdf}
}
@inproceedings{Helmuth:2016:GPTP,
author = {Thomas Helmuth and Lee Spector and Nicholas Freitag
McPhee and Saul Shanabrook},
title = {Linear Genomes for Structured Programs},
booktitle = {Genetic Programming Theory and Practice XIV},
year = {2016},
editor = {Rick Riolo and Bill Worzel and Brian Goldman and Bill
Tozier},
pages = {85--100},
address = {Ann Arbor, USA},
month = {19-21 } # may,
publisher = {Springer},
keywords = {genetic algorithms, genetic programming, Uniform
variation, linear genomes, Push, Plush},
isbn13 = {978-3-319-97087-5},
url = {http://cs.hamilton.edu/~thelmuth/Pubs/2016-GPTP-plush.pdf},
url = {https://www.springer.com/us/book/9783319970875},
doi = {doi:10.1007/978-3-319-97088-2_6},
size = {15 pages},
abstract = {In most genetic programming systems, candidate
solution programs themselves serve as the genetic
material upon which variation operators act. However,
because of the hierarchical structure of computer
programs, and the syntactic constraints that they must
obey, it is difficult to implement variation operators
that affect different parts of programs with uniform
probability. This can have detrimental effects on
evolutionary search. In prior work, structured programs
were linearised prior to variation in order to
facilitate uniformity, but this necessitated syntactic
repair after variation, which reintroduced
non-uniformities. In this chapter we describe a new
approach that uses linear genomes, from which
structured programs are expressed only for the purpose
of fitness testing. We present the new approach in
detail and show how it facilitates both uniform
variation and the evolution of programs with meaningful
structure.},
notes = {Part of \cite{Tozier:2016:GPTP} published after the
workshop},
doi-url = {http://dx.doi.org/10.1007/978-3-319-97088-2_6},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2016-GPTP-plush.pdf}
}
@inproceedings{McPhee:2016:GPTP,
author = {Nicholas Freitag McPhee and Mitchell D. Finzel and
Maggie M. Casale and Thomas Helmuth and Lee Spector},
title = {A detailed analysis of a {PushGP} run},
booktitle = {Genetic Programming Theory and Practice XIV},
year = {2016},
editor = {Rick Riolo and Bill Worzel and Brian Goldman and Bill
Tozier},
pages = {65--83},
address = {Ann Arbor, USA},
month = {19-21 } # may,
publisher = {Springer},
keywords = {genetic algorithms, genetic programming, PushGP,
ancestry graph, lineage, inheritance},
isbn13 = {978-3-319-97087-5},
url = {https://www.springer.com/us/book/9783319970875},
doi = {doi:10.1007/978-3-319-97088-2_5},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2016-GPTP-full-run-analysis.pdf},
abstract = {In evolutionary computation runs there is a great deal
of data that could be saved and analysed. This data is
often put aside, however, in favour of focusing on the
final outcomes, typically captured and presented in the
form of summary statistics and performance plots. Here
we examine a genetic programming run in detail and
trace back from the solution to determine how it was
derived. To visualize this genetic programming run, the
ancestry graph is extracted, running from the
solution(s) in the final generation up to their
ancestors in the initial random population. The key
instructions in the solution are also identified, and a
genetic ancestry graph is constructed, a subgraph of
the ancestry graph containing only those individuals
contributed genetic information (or instructions) to
the solution. This visualization and our ability to
trace these key instructions throughout the run allowed
us to identify general inheritance patterns and key
evolutionary moments in this run.},
notes = {Part of \cite{Tozier:2016:GPTP} published after the
workshop},
doi-url = {http://dx.doi.org/10.1007/978-3-319-97088-2_5}
}
@inproceedings{Helmuth:2015:GPTP,
author = {Thomas Helmuth and Nicholas Freitag McPhee and Lee
Spector},
title = {Lexicase Selection For Program Synthesis: {A}
Diversity Analysis},
booktitle = {Genetic Programming Theory and Practice XIII},
year = {2015},
noeditor = {Rick Riolo and William P. Worzel and M. Kotanchek and
A. Kordon},
series = {Genetic and Evolutionary Computation},
address = {Ann Arbor, USA},
month = may,
publisher = {Springer},
keywords = {genetic algorithms, genetic programming, Lexicase
selection, diversity, tournament selection, implicit
fitness sharing},
isbn13 = {978-3-319-34223-8},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2015-GPTP-lexicase-diversity-analysis.pdf},
url = {http://www.springer.com/us/book/9783319342214},
size = {16 pages},
abstract = {Lexicase selection is a selection method for
evolutionary computation in which individuals are
selected by filtering the population according to
performance on test cases, considered in random order.
When used as the parent selection method in genetic
programming, lexicase selection has been shown to
provide significant improvements in problem-solving
power. In this chapter we investigate the reasons for
the success of lexicase selection, focusing on measures
of population diversity. We present data from eight
program synthesis problems and compare lexicase
selection to tournament selection and selection based
on implicit fitness sharing. We conclude that lexicase
selection does indeed produce more diverse populations,
which helps to explain the utility of lexicase
selection for program synthesis.},
notes = {Replace Space With Newline, Syllables, String Lengths
Backwards, Negative To Zero, Double Letters, Scrabble
Score, Checksum, Count Odds.
http://cscs.umich.edu/gptp-workshops/ Part of
\cite{Riolo:2015:GPTP} Published after the workshop in
2016}
}
@inproceedings{McPhee:2015:GPTP,
author = {Nicholas Freitag McPhee and David Donatucci and Thomas
Helmuth},
title = {Using Graph Databases to Explore Genetic Programming
Run Dynamics},
booktitle = {Genetic Programming Theory and Practice XIII},
year = {2015},
noeditor = {Rick Riolo and William P. Worzel and M. Kotanchek and
A. Kordon},
series = {Genetic and Evolutionary Computation},
address = {Ann Arbor, USA},
month = may,
publisher = {Springer},
keywords = {genetic algorithms, genetic programming},
isbn13 = {978-3-319-34223-8},
url = {http://www.springer.com/us/book/9783319342214},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2015-GPTP-graph-database.pdf},
notes = {http://cscs.umich.edu/gptp-workshops/ Part of
\cite{Riolo:2015:GPTP} Published after the workshop in
2016}
}
@inproceedings{Kannappan:2014:GPTP,
author = {Karthik Kannappan and Lee Spector and Moshe Sipper and
Thomas Helmuth and William La Cava and Jake Wisdom and
Omri Bernstein},
title = {Analyzing a Decade of Human-Competitive (``{HUMIE}'')
Winners: What Can We Learn?},
booktitle = {Genetic Programming Theory and Practice XII},
year = {2014},
noeditor = {Rick Riolo and William P. Worzel and Mark Kotanchek},
series = {Genetic and Evolutionary Computation},
pages = {149--166},
address = {Ann Arbor, USA},
month = {8-10 } # may,
publisher = {Springer},
keywords = {genetic algorithms, genetic programming, HUMIES,
Evolutionary Computation, Human Competitive},
isbn13 = {978-3-319-16029-0},
url = {http://link.springer.com/chapter/10.1007%2F978-3-319-16030-6_9},
doi = {doi:10.1007/978-3-319-16030-6_9},
pdf = {http://faculty.hampshire.edu/lspector/pubs/Anaylzing_the_Humies.pdf},
size = {16 pages},
abstract = {Techniques in evolutionary computation (EC) have
improved significantly over the years, leading to a
substantial increase in the complexity of problems that
can be solved by EC-based approaches. The HUMIES awards
at the Genetic and Evolutionary Computation Conference
are designed to recognise work that has not just solved
some problem via techniques from evolutionary
computation, but has produced a solution that is
demonstrably human-competitive. In this chapter, we
take a look across the winners of the past 10 years of
the HUMIES awards, and analyse them to determine
whether there are specific approaches that consistently
show up in the HUMIE winners. We believe that this
analysis may lead to interesting insights regarding
prospects and strategies for producing further human
competitive results.},
notes = {http://cscs.umich.edu/gptp-workshops/ Part of
\cite{Riolo:2014:GPTP} published after the workshop in
2015},
doi-url = {http://dx.doi.org/10.1007/978-3-319-16030-6_9}
}
@incollection{Spector:2013:GPTP,
author = {Lee Spector and Thomas Helmuth},
title = {Uniform Linear Transformation with Repair and
Alternation in Genetic Programming},
booktitle = {Genetic Programming Theory and Practice XI},
year = {2013},
series = {Genetic and Evolutionary Computation},
noeditor = {Rick Riolo and Jason H. Moore and Mark Kotanchek},
publisher = {Springer},
chapter = {8},
pages = {137--153},
address = {Ann Arbor, USA},
month = {9-11 } # may,
keywords = {genetic algorithms, genetic programming, Uniform
mutation, Uniform crossover, ULTRA, Push, PushGP, Drug
bioavailability problem, Pagie-1 problem, Factorial
regression, Boolean multiplexer problem},
isbn13 = {978-1-4939-0374-0},
url = {http://link.springer.com/chapter/10.1007%2F978-1-4939-0375-7_8},
doi = {doi:10.1007/978-1-4939-0375-7_8},
pdf = {http://faculty.hampshire.edu/lspector/pubs/spector-gptp-2013-preprint-erratum.pdf},
abstract = {Several genetic programming researchers have argued
for the utility of genetic operators that act
uniformly. By act uniformly we mean two specific
things: that the probability of an inherited program
component being modified during inheritance is
independent of the size and shape of the parent
programs beyond the component in question; and that
pairs of parents are combined in ways that allow
arbitrary combinations of components from each parent
to appear in the child. Uniform operators described in
previous work have had limited utility, however,
because of a mismatch between the relevant notions of
uniformity and the hierarchical structure and variable
sizes of many genetic programming representations. In
this chapter we describe a new genetic operator, ULTRA,
which incorporates aspects of both mutation and
crossover and acts approximately uniformly across
programs of variable sizes and structures. ULTRA treats
hierarchical programs as linear sequences and includes
a repair step to ensure that syntax constraints are
satisfied after variation. We show that on the drug
bioavailability and Pagie-1 benchmark problems ULTRA
produces significant improvements both in
problem-solving power and in program size relative to
standard operators. Experiments with factorial
regression and with the Boolean 6-multiplexer problem
demonstrate that ULTRA can manipulate programs that
make use of hierarchical structure, but also that it is
not always beneficial. The demonstrations evolve
programs in the Push programming language, which makes
repair particularly simple, but versions of the
technique should be applicable in other genetic
programming systems as well.},
notes = {http://cscs.umich.edu/gptp-workshops/ Part of
\cite{Riolo:2013:GPTP} published after the workshop in
2013},
doi-url = {http://dx.doi.org/10.1007/978-1-4939-0375-7_8}
}
@incollection{Helmuth:2012:GPTP,
author = {Thomas Helmuth and Lee Spector},
title = {Evolving {SQL} Queries from Examples with
Developmental Genetic Programming},
booktitle = {Genetic Programming Theory and Practice X},
year = {2012},
series = {Genetic and Evolutionary Computation},
noeditor = {Rick Riolo and Ekaterina Vladislavleva and Marylyn D.
Ritchie and Jason H. Moore},
publisher = {Springer},
chapter = {1},
pages = {1--14},
address = {Ann Arbor, USA},
month = {12-14 } # may,
keywords = {genetic algorithms, genetic programming, Data mining,
Classification, SQL, Push, PushGP},
isbn13 = {978-1-4614-6845-5},
url = {http://link.springer.com/chapter/10.1007%2F978-1-4614-6846-2_1},
doi = {doi:10.1007/978-1-4614-6846-2_1},
pdf = {http://hampshire.edu/lspector/pubs/gptp-2012-preprint.pdf},
abstract = {Large databases are becoming ever more ubiquitous, as
are the opportunities for discovering useful knowledge
within them. Evolutionary computation methods such as
genetic programming have previously been applied to
several aspects of the problem of discovering knowledge
in databases. The more specific task of producing
human-comprehensible SQL queries has several potential
applications but has thus far been explored only to a
limited extent. In this chapter we show how
developmental genetic programming can automatically
generate SQL queries from sets of positive and negative
examples. We show that a developmental genetic
programming system can produce queries that are
reasonably accurate while excelling in human
comprehensibility relative to the well-known C5.0
decision tree generation system.},
notes = {part of \cite{Riolo:2012:GPTP} published after the
workshop in 2013},
doi-url = {http://dx.doi.org/10.1007/978-1-4614-6846-2_1}
}
@incollection{Spector:2011:GPTP,
author = {Lee Spector and Kyle Harrington and Brian Martin and
Thomas Helmuth},
title = {What's in an Evolved Name? The Evolution of Modularity
via Tag-Based Reference},
booktitle = {Genetic Programming Theory and Practice IX},
year = {2011},
noeditor = {Rick Riolo and Ekaterina Vladislavleva and Jason H.
Moore},
series = {Genetic and Evolutionary Computation},
address = {Ann Arbor, USA},
month = {12-14 } # may,
publisher = {Springer},
chapter = {1},
pages = {1--16},
keywords = {genetic algorithms, genetic programming, modularity,
names, tags, stack-based genetic programming, Push
programming language, PushGP},
isbn13 = {978-1-4614-1769-9},
url = {http://link.springer.com/chapter/10.1007%2F978-1-4614-1770-5_1},
pdf = {http://hampshire.edu/lspector/pubs/spector-gptp11-preprint.pdf},
doi = {doi:10.1007/978-1-4614-1770-5_1},
size = {18 pages},
abstract = {Programming languages provide a variety of mechanisms
to associate names with values, and these mechanisms
play a central role in programming practice. For
example, they allow multiple references to the same
storage location or function in different parts of a
complex program. By contrast, the representations used
in current genetic programming systems provide few if
any naming mechanisms, and it is therefore generally
not possible for evolved programs to use names in
sophisticated ways. we describe a new approach to names
in genetic programming that is based on John Holland's
concept of tags. We demonstrate the use of tag-based
names, we describe some of the ways in which they may
help to extend the power and reach of genetic
programming systems and we look at the ways that
tag-based names are actually used in an evolved program
that solves a robot navigation problem.},
notes = {section 1. 'Grammars of most programming languages
fail to be fully context free because name definitions
and uses must match...' Push in C++, Java, JavaScript,
Python, Common Lips, Clojure, Scheme, Erlang and R.
Tags both for values (variables) and code (functions).
untag. scoping rules? dirt-sensing robot 15 modules
(table 1-1). See also \cite{Spector:2011:GECCO}. Part
of \cite{Riolo:2011:GPTP}},
affiliation = {Cognitive Science, Hampshire College, Amherst, MA
01002, USA},
doi-url = {http://dx.doi.org/10.1007/978-1-4614-1770-5_1}
}
@inproceedings{Helmuth:2020:GECCOcomp,
author = {Thomas Helmuth and Amr Abdelhady},
title = {Benchmarking Parent Selection for Program Synthesis by
Genetic Programming},
year = {2020},
noeditor = {Richard Allmendinger and Hugo Terashima Marin and
Efren Mezura Montes and Thomas Bartz-Beielstein and
Bogdan Filipic and Ke Tang and David Howard and Emma
Hart and Gusz Eiben and Tome Eftimov and William {La
Cava} and Boris Naujoks and Pietro Oliveto and Vanessa
Volz and Thomas Weise and Bilel Derbel and Ke Li and
Xiaodong Li and Saul Zapotecas and Qingfu Zhang and Rui
Wang and Ran Cheng and Guohua Wu and Miqing Li and
Hisao Ishibuchi and Jonathan Fieldsend and Ozgur Akman
and Khulood Alyahya and Juergen Branke and John R.
Woodward and Daniel R. Tauritz and Marco Baioletti and
Josu Ceberio Uribe and John McCall and Alfredo Milani
and Stefan Wagner and Michael Affenzeller and Bradley
Alexander and Alexander (Sandy) Brownlee and Saemundur
O. Haraldsson and Markus Wagner and Nayat Sanchez-Pi
and Luis Marti and Silvino {Fernandez Alzueta} and
Pablo {Valledor Pellicer} and Thomas Stuetzle and
Matthew Johns and Nick Ross and Ed Keedwell and Herman
Mahmoud and David Walker and Anthony Stein and Masaya
Nakata and David Paetzel and Neil Vaughan and Stephen
Smith and Stefano Cagnoni and Robert M. Patton and
Ivanoe {De Falco} and Antonio {Della Cioppa} and
Umberto Scafuri and Ernesto Tarantino and Akira Oyama
and Koji Shimoyama and Hemant Kumar Singh and Kazuhisa
Chiba and Pramudita Satria Palar and Alma Rahat and
Richard Everson and Handing Wang and Yaochu Jin and
Erik Hemberg and Riyad Alshammari and Tokunbo Makanju
and Fuijimino-shi and Ivan Zelinka and Swagatam Das and
Ponnuthurai Nagaratnam and Roman Senkerik},
isbn13 = {9781450371278},
publisher = {ACM},
publisher_address = {New York, NY, USA},
url = {https://doi.org/10.1145/3377929.3389987},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2020-GECCO-poster-benchmarking-parent-selection.pdf},
doi = {doi:10.1145/3377929.3389987},
booktitle = {Proceedings of the 2020 Genetic and Evolutionary
Computation Conference Companion},
pages = {237--238},
size = {2 pages},
keywords = {genetic algorithms, genetic programming, parent
selection, benchmark, program synthesis},
series = {GECCO '20},
month = jul # { 8-12},
organisation = {SIGEVO},
notes = {Also known as \cite{10.1145/3377929.3389987}
GECCO-2020 A Recombination of the 29th International
Conference on Genetic Algorithms (ICGA) and the 25th
Annual Genetic Programming Conference (GP)},
doi-url = {http://dx.doi.org/10.1145/3377929.3389987}
}
@inproceedings{Helmuth:2020:GECCOcompa,
author = {Thomas Helmuth and Lee Spector and Edward Pantridge},
title = {Counterexample-Driven Genetic Programming without
Formal Specifications},
year = {2020},
noeditor = {Richard Allmendinger and Hugo Terashima Marin and
Efren Mezura Montes and Thomas Bartz-Beielstein and
Bogdan Filipic and Ke Tang and David Howard and Emma
Hart and Gusz Eiben and Tome Eftimov and William {La
Cava} and Boris Naujoks and Pietro Oliveto and Vanessa
Volz and Thomas Weise and Bilel Derbel and Ke Li and
Xiaodong Li and Saul Zapotecas and Qingfu Zhang and Rui
Wang and Ran Cheng and Guohua Wu and Miqing Li and
Hisao Ishibuchi and Jonathan Fieldsend and Ozgur Akman
and Khulood Alyahya and Juergen Branke and John R.
Woodward and Daniel R. Tauritz and Marco Baioletti and
Josu Ceberio Uribe and John McCall and Alfredo Milani
and Stefan Wagner and Michael Affenzeller and Bradley
Alexander and Alexander (Sandy) Brownlee and Saemundur
O. Haraldsson and Markus Wagner and Nayat Sanchez-Pi
and Luis Marti and Silvino {Fernandez Alzueta} and
Pablo {Valledor Pellicer} and Thomas Stuetzle and
Matthew Johns and Nick Ross and Ed Keedwell and Herman
Mahmoud and David Walker and Anthony Stein and Masaya
Nakata and David Paetzel and Neil Vaughan and Stephen
Smith and Stefano Cagnoni and Robert M. Patton and
Ivanoe {De Falco} and Antonio {Della Cioppa} and
Umberto Scafuri and Ernesto Tarantino and Akira Oyama
and Koji Shimoyama and Hemant Kumar Singh and Kazuhisa
Chiba and Pramudita Satria Palar and Alma Rahat and
Richard Everson and Handing Wang and Yaochu Jin and
Erik Hemberg and Riyad Alshammari and Tokunbo Makanju
and Fuijimino-shi and Ivan Zelinka and Swagatam Das and
Ponnuthurai Nagaratnam and Roman Senkerik},
isbn13 = {9781450371278},
publisher = {ACM},
publisher_address = {New York, NY, USA},
url = {https://doi.org/10.1145/3377929.3389983},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2020-GECCO-poster-counterexample-gp.pdf},
doi = {doi:10.1145/3377929.3389983},
booktitle = {Proceedings of the 2020 Genetic and Evolutionary
Computation Conference Companion},
pages = {239--240},
size = {2 pages},
keywords = {genetic algorithms, genetic programming,
counterexamples, program synthesis},
series = {GECCO '20},
month = jul # { 8-12},
organisation = {SIGEVO},
notes = {Also known as \cite{10.1145/3377929.3389983}
GECCO-2020 A Recombination of the 29th International
Conference on Genetic Algorithms (ICGA) and the 25th
Annual Genetic Programming Conference (GP)},
doi-url = {http://dx.doi.org/10.1145/3377929.3389983}
}
@inproceedings{Helmuth:2020:GECCOcompb,
author = {Thomas Helmuth and Edward Pantridge and Grace Woolson
and Lee Spector},
title = {Transfer Learning of Genetic Programming Instruction
Sets},
year = {2020},
noeditor = {Richard Allmendinger and Hugo Terashima Marin and
Efren Mezura Montes and Thomas Bartz-Beielstein and
Bogdan Filipic and Ke Tang and David Howard and Emma
Hart and Gusz Eiben and Tome Eftimov and William {La
Cava} and Boris Naujoks and Pietro Oliveto and Vanessa
Volz and Thomas Weise and Bilel Derbel and Ke Li and
Xiaodong Li and Saul Zapotecas and Qingfu Zhang and Rui
Wang and Ran Cheng and Guohua Wu and Miqing Li and
Hisao Ishibuchi and Jonathan Fieldsend and Ozgur Akman
and Khulood Alyahya and Juergen Branke and John R.
Woodward and Daniel R. Tauritz and Marco Baioletti and
Josu Ceberio Uribe and John McCall and Alfredo Milani
and Stefan Wagner and Michael Affenzeller and Bradley
Alexander and Alexander (Sandy) Brownlee and Saemundur
O. Haraldsson and Markus Wagner and Nayat Sanchez-Pi
and Luis Marti and Silvino {Fernandez Alzueta} and
Pablo {Valledor Pellicer} and Thomas Stuetzle and
Matthew Johns and Nick Ross and Ed Keedwell and Herman
Mahmoud and David Walker and Anthony Stein and Masaya
Nakata and David Paetzel and Neil Vaughan and Stephen
Smith and Stefano Cagnoni and Robert M. Patton and
Ivanoe {De Falco} and Antonio {Della Cioppa} and
Umberto Scafuri and Ernesto Tarantino and Akira Oyama
and Koji Shimoyama and Hemant Kumar Singh and Kazuhisa
Chiba and Pramudita Satria Palar and Alma Rahat and
Richard Everson and Handing Wang and Yaochu Jin and
Erik Hemberg and Riyad Alshammari and Tokunbo Makanju
and Fuijimino-shi and Ivan Zelinka and Swagatam Das and
Ponnuthurai Nagaratnam and Roman Senkerik},
isbn13 = {9781450371278},
publisher = {ACM},
publisher_address = {New York, NY, USA},
url = {https://doi.org/10.1145/3377929.3389988},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2020-GECCO-poster-transfer-learning-instruction-sets.pdf},
doi = {doi:10.1145/3377929.3389988},
booktitle = {Proceedings of the 2020 Genetic and Evolutionary
Computation Conference Companion},
pages = {241--242},
size = {2 pages},
keywords = {genetic algorithms, genetic programming, transfer
learning, instruction set, PushGP},
series = {GECCO '20},
month = jul # { 8-12},
organisation = {SIGEVO},
notes = {Also known as \cite{10.1145/3377929.3389988}
GECCO-2020 A Recombination of the 29th International
Conference on Genetic Algorithms (ICGA) and the 25th
Annual Genetic Programming Conference (GP)},
doi-url = {http://dx.doi.org/10.1145/3377929.3389988}
}
@inproceedings{McPhee:2017:GECCOa,
author = {Nicholas Freitag McPhee and Thomas Helmuth and Lee
Spector},
title = {Using Algorithm Configuration Tools to Optimize
Genetic Programming Parameters: A Case Study},
booktitle = {Proceedings of the Genetic and Evolutionary
Computation Conference Companion},
series = {GECCO '17},
year = {2017},
isbn13 = {978-1-4503-4939-0},
address = {Berlin, Germany},
pages = {243--244},
size = {2 pages},
url = {http://doi.acm.org/10.1145/3067695.3076097},
doi = {doi:10.1145/3067695.3076097},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2017-GECCO-poster-SMAC-and-PushGP.pdf},
acmid = {3076097},
publisher = {ACM},
publisher_address = {New York, NY, USA},
keywords = {genetic algorithms, genetic programming, SMAC,
parameter optimization, pushGP, software synthesis},
month = {15-19 } # jul,
abstract = {We use Sequential Model-based Algorithm Configuration
(SMAC) to optimize a group of parameters for PushGP, a
stack-based genetic programming system, for several
software synthesis problems. Applying SMAC to one
particular problem leads to marked improvements in the
success rate and the speed with which a solution was
found for that problem. Applying these {"}tuned{"}
parameters to four additional problems, however, only
improved performance on one, and substantially reduced
performance on another. This suggests that SMAC is
overfitting, tuning the parameters in ways that are
highly problem specific, and raises doubts about the
value of using these {"}tuned{"} parameters on
previously unsolved problems. Efforts to use SMAC to
optimize PushGP parameters on other problems have been
less successful due to a combination of long PushGP run
times and low success rates, which make it hard for
SMAC to acquire enough information in a reasonable
amount of time.},
notes = {Also known as \cite{McPhee:2017:UAC:3067695.3076097}
GECCO-2017 A Recombination of the 26th International
Conference on Genetic Algorithms (ICGA-2017) and the
22nd Annual Genetic Programming Conference (GP-2017)},
doi-url = {http://dx.doi.org/10.1145/3067695.3076097}
}
@inproceedings{McPhee:2017:GECCO,
author = {Nicholas Freitag McPhee and Maggie M. Casale and
Mitchell Finzel and Thomas Helmuth and Lee Spector},
title = {Visualizing Genetic Programming Ancestries Using Graph
Databases},
booktitle = {Proceedings of the Genetic and Evolutionary
Computation Conference Companion},
series = {GECCO '17},
year = {2017},
isbn13 = {978-1-4503-4939-0},
address = {Berlin, Germany},
pages = {245--246},
size = {2 pages},
url = {http://doi.acm.org/10.1145/3067695.3075617},
doi = {doi:10.1145/3067695.3075617},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/2017-GECCO-poster-ancestries.pdf},
acmid = {3075617},
publisher = {ACM},
publisher_address = {New York, NY, USA},
keywords = {genetic algorithms, genetic programming, ancestry,
graph database, visualization},
month = {15-19 } # jul,
notes = {Also known as \cite{McPhee:2017:VGP:3067695.3075617}
GECCO-2017 A Recombination of the 26th International
Conference on Genetic Algorithms (ICGA-2017) and the
22nd Annual Genetic Programming Conference (GP-2017)},
doi-url = {http://dx.doi.org/10.1145/3067695.3075617}
}
@inproceedings{Spector:2014:GECCOcomp,
author = {Lee Spector and Thomas Helmuth},
title = {Effective simplification of evolved push programs
using a simple, stochastic hill-climber},
booktitle = {GECCO Comp '14: Proceedings of the 2014 conference
companion on Genetic and evolutionary computation
companion},
year = {2014},
noeditor = {Christian Igel and Dirk V. Arnold and Christian Gagne
and Elena Popovici and Anne Auger and Jaume Bacardit
and Dimo Brockhoff and Stefano Cagnoni and Kalyanmoy
Deb and Benjamin Doerr and James Foster and Tobias
Glasmachers and Emma Hart and Malcolm I. Heywood and
Hitoshi Iba and Christian Jacob and Thomas Jansen and
Yaochu Jin and Marouane Kessentini and Joshua D.
Knowles and William B. Langdon and Pedro Larranaga and
Sean Luke and Gabriel Luque and John A. W. McCall and
Marco A. {Montes de Oca} and Alison Motsinger-Reif and
Yew Soon Ong and Michael Palmer and Konstantinos E.
Parsopoulos and Guenther Raidl and Sebastian Risi and
Guenther Ruhe and Tom Schaul and Thomas Schmickl and
Bernhard Sendhoff and Kenneth O. Stanley and Thomas
Stuetzle and Dirk Thierens and Julian Togelius and
Carsten Witt and Christine Zarges},
isbn13 = {978-1-4503-2881-4},
keywords = {genetic algorithms, genetic programming: Poster},
pages = {147--148},
month = {12-16 } # jul,
organisation = {SIGEVO},
address = {Vancouver, BC, Canada},
url = {http://doi.acm.org/10.1145/2598394.2598414},
doi = {doi:10.1145/2598394.2598414},
pdf = {http://cs.hamilton.edu/~thelmuth/Pubs/simplification-GECCO-2014.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {Genetic programming systems often produce programs
that include unnecessary code. This is undesirable for
several reasons, including the burdens that
overly-large programs put on end-users for program
interpretation and maintenance. The problem is
exacerbated by recently developed techniques, such as
genetic programming with geometric semantic crossover,
that tend to produce enormous programs. Methods for
automatically simplifying evolved programs are
therefore of interest, but automatic simplification is
non-trivial in the context of traditional program
representations with unconstrained function sets. Here
we show how evolved programs expressed in the
stack-based Push programming language can be
automatically and reliably simplified using a simple,
stochastic hill-climber. We demonstrate and
quantitatively characterise this simplification process
on programs evolved to solve four non-trivial genetic
programming problems with qualitatively different
function sets.},
notes = {Also known as \cite{2598414} Distributed at
GECCO-2014.},
doi-url = {http://dx.doi.org/10.1145/2598394.2598414}
}
@inproceedings{Helmuth:2012:GECCOcomp,
author = {Thomas Helmuth and Lee Spector},
title = {Empirical investigation of size-based tournaments for
node selection in genetic programming},
booktitle = {GECCO Companion '12: Proceedings of the fourteenth
international conference on Genetic and evolutionary
computation conference companion},
year = {2012},
noeditor = {Terry Soule and Anne Auger and Jason Moore and David
Pelta and Christine Solnon and Mike Preuss and Alan
Dorin and Yew-Soon Ong and Christian Blum and Dario
Landa Silva and Frank Neumann and Tina Yu and Aniko
Ekart and Will Browne and Tim Kovacs and Man-Leung Wong
and Clara Pizzuti and Jon Rowe and Tobias Friedrich and
Giovanni Squillero and Nicolas Bredeche and Stephen
Smith and Alison Motsinger-Reif and Jose Lozano and
Martin Pelikan and Silja Meyer-Nienberg and Christian
Igel and Greg Hornby and Rene Doursat and Steve
Gustafson and Gustavo Olague and Shin Yoo and John
Clark and Gabriela Ochoa and Gisele Pappa and Fernando
Lobo and Daniel Tauritz and Jurgen Branke and Kalyanmoy
Deb},
isbn13 = {978-1-4503-1178-6},
keywords = {genetic algorithms, Genetic programming: Poster},
pages = {1485--1486},
month = {7-11 } # jul,
organisation = {SIGEVO},
address = {Philadelphia, Pennsylvania, USA},
url = {http://dl.acm.org/citation.cfm?doid=2330784.2331004},
doi = {doi:10.1145/2330784.2331004},
pdf = {http://hampshire.edu/lspector/pubs/p1485.pdf},
publisher = {ACM},
publisher_address = {New York, NY, USA},
abstract = {In genetic programming systems, genetic operators must
select nodes upon which to act; the method by which
they select nodes influences problem solving
performance and possibly also code growth. A recently
proposed node selection method using size-based
tournaments has been shown to have potential, but
variations of the method have not been studied
systematically. Here we extend the ideas of size-based
tournaments and test how they can improve
problem-solving performance. We consider allowing
tournament size to depend on whether we are selecting
nodes within donors for crossover, recipients for
crossover, or targets of mutation. We also consider
tournaments that bias selection toward smaller trees
rather than larger trees. We find that differentiating
between donors and recipients is probably not
worthwhile and that size 2 tournaments perform
near-optimally.},
notes = {Also known as \cite{2331004} Distributed at
GECCO-2012. ACM Order Number 910122.},
doi-url = {http://dx.doi.org/10.1145/2330784.2331004}
}
@inproceedings{Spector:2011:FSE:2001858.2001932,
author = {Spector, Lee and Helmuth, Thomas and Harrington, Kyle},
title = {Fecundity and Selectivity in Evolutionary Computation},
booktitle = {Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation},
series = {GECCO '11},
year = {2011},
isbn = {978-1-4503-0690-4},
location = {Dublin, Ireland},
pages = {129--130},
numpages = {2},
url = {http://doi.acm.org/10.1145/2001858.2001932},
doi = {10.1145/2001858.2001932},
pdf = {http://hampshire.edu/lspector/pubs/decimation-gecco2011-cited.pdf},
acmid = {2001932},
month = {12-16 } # jul,
organisation = {SIGEVO},
address = {Dublin, Ireland},
publisher = {ACM},
publisher_address = {New York, NY, USA},
keywords = {deb's deceptive problem, decimation, fecundity, selection, truncation}
}
@inproceedings{Helmuth:2021:GECCOtutorial:lexicase,
author = {Thomas Helmuth and Bill La Cava},
title = {Lexicase Selection},
year = {2021},
publisher = {ACM},
publisher_address = {New York, NY, USA},
url = {},
pdf = {},
doi = {},
booktitle = {Proceedings of the 2021 Genetic and Evolutionary
Computation Conference Companion},
series = {GECCO '21},
month = jul # { 10-14},
organisation = {SIGEVO}
}
@phdthesis{Helmuth:thesis,
author = {Thomas Helmuth},
title = {General Program Synthesis from Examples Using Genetic
Programming with Parent Selection Based on Random
Lexicographic Orderings of Test Cases},
school = {College of Information and Computer Sciences,
University of Massachusetts Amherst},
year = {2015},
address = {USA},
month = sep,
keywords = {genetic algorithms, genetic programming, lexicase},
url = {https://web.cs.umass.edu/publication/details.php?id=2398},
pdf = {https://web.cs.umass.edu/publication/docs/2015/UM-CS-PhD-2015-005.pdf},
size = {159 pages},
abstract = {Software developers routinely create tests before
writing code, to ensure that their programs fulfill
their requirements. Instead of having human programmers
write the code to meet these tests, automatic program
synthesis systems can create programs to meet
specifications without human intervention, only
requiring examples of desired behavior. In the
long-term, we envision using genetic programming to
synthesize large pieces of software. This dissertation
takes steps toward this goal by investigating the
ability of genetic programming to solve introductory
computer science programming problems. We present a
suite of 29 benchmark problems intended to test general
program synthesis systems, which we systematically
selected from sources of introductory computer science
programming problems. This suite is suitable for
experiments with any program synthesis system driven by
input/output examples. Unlike existing benchmarks that
concentrate on constrained problem domains such as list
manipulation, symbolic regression, or Boolean
functions, this suite contains general programming
problems that require a range of programming
constructs, such as multiple data types and data
structures, control flow statements, and I/O. The
problems encompass a range of difficulties and
requirements as necessary to thoroughly assess the
capabilities of a program synthesis system. Besides
describing the specifications for each problem, we make
recommendations for experimental protocols and
statistical methods to use with the problems. This
dissertation's second contribution is an investigation
of behaviour-based parent selection in genetic
programming, concentrating on a new method called
lexicase selection. Most parent selection techniques
aggregate errors from test cases to compute a single
scalar fitness value; lexicase selection instead treats
test cases separately, never comparing error values of
different test cases. This property allows it to select
parents that specialise on some test cases even if they
perform poorly on others. We compare lexicase selection
to other parent selection techniques on our benchmark
suite, showing better performance for lexicase
selection. After observing that lexicase selection
increases exploration of the search space while also
increasing exploitation of promising programs, we
conduct a range of experiments to identify which
characteristics of lexicase selection influence its
utility.},
notes = {UM-CS-Phd-2015-005 Supervised by Lee Spector GP
discussion list 27 Sep 2015:
https://groups.yahoo.com/neo/groups/genetic_programming/conversations/messages/6785}
}
@techreport{Helmuth:2015006:UM,
author = {Thomas Helmuth and Lee Spector},
title = {Detailed Problem Descriptions for General Program Synthesis Benchmark Suite},
institution = {Computer Science, University of Massachusetts, Amherst},
year = {2015},
type = {Technical Report},
number = {UM-CS-2015-006},
month = {June},
keywords = {program synthesis, genetic programming, benchmarks},
url = {https://web.cs.umass.edu/publication/details.php?id=2387},
pdf = {https://web.cs.umass.edu/publication/docs/2015/UM-CS-2015-006.pdf},
size = {17 pages},
abstract = {Recent interest in the development and use of non-trivial benchmark problems for genetic programming research has highlighted the scarcity of general program synthesis (also called ``traditional programming'') benchmark problems. We present a suite of $29$ general program synthesis benchmark problems systematically selected from sources of introductory computer science programming problems. This suite is suitable for experiments with any program synthesis system driven by input/output examples. We present results from illustrative experiments using our reference implementation of the problems in the PushGP genetic programming system. This technical report provides sufficient detail of the problems and our reference implementation for researchers to implement and attempt to solve these problems in other synthesis systems. The results show that the problems in the suite vary in difficulty and can be useful for assessing the capabilities of a program synthesis system.}
}
This file was generated by bibtex2html 1.96.