<commit_before>%%%%%%%%%%%%%%%%%%%% author.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%%%%%%%%%%%%%%%% Springer %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title*{Using Graph Databases to Explore the Dynamics of Genetic Programming Runs}
% Use \titlerunning{Short Title} for an abbreviated version of
% your contribution title if the original one is too long
\author{<NAME>, <NAME>, and <NAME>}
% Use \authorrunning{Short Title} for an abbreviated version of
% your contribution title if the original one is too long
\institute{<NAME> \at Division of Science and Mathematics, University of Minnesota, Morris, MN USA
\and <NAME> \at Division of Science and Mathematics, University of Minnesota, Morris, MN USA
\and <NAME> \at Computer Science, University of Massachusetts, Amherst, MA USA}

\maketitle

\abstract{
	For both practical reasons and those of habit, most evolutionary computation research is presented in highly summary
	form. These summaries, however, often obscure or completely mask the profusion of specific selections, crossovers, and mutations
	that are ultimately responsible for the aggregate behaviors we're interested in. In this chapter we take a different
	approach and use the Neo4j graph database system to record and analyze the entire genealogical history of 
	a set of genetic programming runs. We then explore a few of these runs in detail, discovering important
	properties of lexicase selection; these may in turn help us better understand the dynamics of lexicase selection, and the
	ways in which it differs from tournament selection. More broadly, we illustrate the value of recording and analyzing this
	level of detail, both as a means of understanding the dynamics of particular runs, and as a way of generating questions
	and ideas for subsequent, broader study.}

\begin{keywords}
	graph database, Neo4j, ancestry, genealogy, lexicase selection, tournament selection
\end{keywords}
\index{graph database}
\index{Neo4j}
\index{ancestry}
\index{genealogy}
\index{lexicase selection}
\index{tournament selection}

\section{Introduction}
\label{sec:introduction}

It is common practice in empirical evolutionary computation (EC) 
research to perform a substantial number of runs, and then 
report a handful of aggregate statistics that summarize and (hopefully) represent 
the complex dynamics of those many runs. Tables present values such 
as mean or median best fitnesses at the end of runs, collapsing the complexities of dozens or 
hundreds of runs into a single number, possibly with a standard deviation or a 
confidence interval to give a sense of the distribution. Plots can often be more informative, 
showing how these numbers change over time during the runs, possibly giving a sense of 
the system dynamics and the range of behaviors. These plots, however, are typically still aggregate representations
that obscure or completely hide important moments that, if explored, might reveal valuable insight into the 
evolutionary dynamics being reported.

An alternative would be to collect, store, and analyze at least some of the rich panoply of 
evolutionary and genealogical events that make up the low-level details of these runs. 
Databases provide a natural tool for 
storing and accessing large data sets, but traditional relational
databases are poorly suited for many of the queries that are important for genealogical analysis.
In this chapter, we illustrate the use of graph databases as an alternative storage and analysis tool for
evolutionary computation runs. We have previously demonstrated that graph databases
can be an effective tool for analyzing complex genetic programming (GP) dynamics \citep{donatuccianalysis}, which led directly
to a proposed change to standard sub-tree crossover in tree-based GP \citep{mcphee:GECCO15}.
Here we will use the open source Neo4j graph database tool\footnote{\url{http://neo4j.com/}} 
to explore data from a
collection of PushGP runs \citep{Helmuth:2015:GPTP} on several problems drawn from a benchmark collection of introductory 
programming problems \citep{Helmuth:2015:GECCO}.

Note that this is \emph{not} going to be a presentation of ``traditional hypothesis-driven 
research''. It will be based on an \emph{assumption}, namely that something interesting happens in
these runs, and that we can learn useful things by exploring them in more detail, but the presentation
will be fairly discursive, reflecting our back-and-forth experience of wrestling with the data. Our
initial queries start from fairly obvious questions (e.g., ``Why did we succeed here?''), but from
there we engage in a dialog with data, letting the answers to early questions shape and guide our 
subsequent exploration. We are not presenting a tidy, sterile summary of our adventures, but
the messier (but we think more informative in this context) journal of what Pickering might call
our ``mangle of practice'' \citep{smith2008mangle, pickering:AJS:1993}.

Here we explore the impact of lexicase \citep{Spector:2012:GECCOcompA} and tournament selection 
on the dynamics of runs whose aim is to solve a basic software synthesis problem. 
In the process we are able to discover surprising and likely important properties of
lexicase that suggest areas of additional exploration and indicate reasons
for the substantially better performance seen when using lexicase on a variety of software synthesis 
problems \citep{Helmuth:2015:GECCO}.

We're not the first people to recognize the potential value of exploring lineages and ancestry graphs. 
The HeuristicLab team has been
working for several years on a set of tools to analyze at least small genealogical run histories 
\citep{Burlacu:2013:GECCOcomp:new, Burlacu:CIEES:2015}; hopefully these exciting features will be in 
an upcoming release. \citep{Burlacu:2013:GECCOcomp:new} also has an excellent survey of a variety of work
that uses genealogical information in EC work; none of this, however, appears to save and analyze full 
genealogical histories, but instead tends to use local ancestry information for purposes such as diversity
promotion. Recent work \citep{kuber2014ancestral} applies network theory to ancestry graphs, looking
for things like cliques as a way of better understanding EC dynamics; that work is similar in spirit to this
chapter, but differs in the kinds of graphs that are built and the tools used to analyze them.

Because we're going to focus on the use of graph databases, there will
on occasion be avenues of exploration that we won't pursue because they would properly involve
different tools. This exploration, for example, raises important questions about the relationships between
parent and child genomes. These could be addressed using, e.g.,
difference-merge tools from software engineering, or sequence alignment tools from genomics;
see, e.g., \citep{Burlacu:2013:GECCOcomp:new}
for an excellent example of this kind of analysis. We will, however, consider that
beyond the scope of this chapter. A key value of our graph database results will be in providing focus
for our use of those other tools, identifying key moments
and individuals in the course of a run that deserve additional attention. There are thousands
of potential genome comparisons to make in a single run, for example, but our graph databases analysis helps identify
some of the critical individuals, crossovers, and mutations in the run, allowing us to concentrate on the
steps that are likely to have mattered most.

We'll provide expanded motivation for this work in Section~\ref{sec:motivation}, and background on relevant tools
and concepts in Section~\ref{sec:background}. In Section~\ref{sec:lexicaseRun} we explore in some detail a successful
lexicase selection run, identifying several properties of lexicase selection that distinguish it from
other, more traditional selection methods. We then explore a successful tournament selection run in
Section~\ref{sec:tournamentRun}, comparing those results to the earlier lexicase results. 
In Section~\ref{sec:cumulativeResults} we step back a little and look at the results of expanding some of our queries
across hundreds of runs, and then wrap up with some conclusions in Section~\ref{sec:whatDidWeLearn}.

\section{Motivation}
\label{sec:motivation}

\index{ancestry}
\index{genealogy}

Consider the job of a paleontologist, who regularly reconstructs not just individuals but also
species and entire phylogenetic trees on the basis of a handful of teeth and bones, or even just
impressions left in prehistoric mud. They rarely have DNA, so any evolutionary relationship is
inherently speculative, subject to constant debate and revision. Even with detailed DNA sequences,
the construction of phylogenetic trees for existing species is non-trivial.

In evolutionary computation, however, we have access to \emph{everything}, at least in principle. 
We could gather every
selection, every mutation, and every crossover as they play out in our systems.
Yet we typically throw almost all that data away, reporting just aggregate statistics and summary
plots, completely failing to take advantage of our privileged position, a position most 
paleontologists would presumably eye with considerable envy. Not only does this seem an inherent
waste, these aggregations typically obscure critical moments in the dynamics of runs which might
speak volumes if explored.

While this sort of aggregate reporting is often valuable, allowing for important comparative
analysis, it typically fails to provide
any sense of the \emph{why}. Yes, Treatment A led to better aggregate performance than 
Treatment B -- but what happened in the runs that led to that result? Any end result
is ultimately the intricate combination of thousands or millions of of selections, recombinations,
and mutations, and if Treatment A is in some sense ``better'' than Treatment B, it must ultimately
be because it affected all those genealogical and genetic events in some significant way, biasing them
in a way that improved performance.

Unfortunately, published research rarely includes information that might shed light on 
these \emph{why} events. We rarely see evolved programs, for example, or any kind of post-run analysis
of those programs, and there is almost never any data or discussion of the genealogical history that
might help us understand how a successful program actually came to be. 
Sometimes these events and details aren't included
for reasons of space and time; evolved programs, for example, are often extremely large and complex,
and a meaningful presentation and discussion of such a program could easily take up more space than
authors have available.
We suspect, however, that another reason this sort of \emph{why} analysis often isn't 
reported is because it isn't done, in no small part because it's hard. As EC researchers we're in the
``privileged'' position of being able to collect anything and everything that happens in a run, 
but that's a potentially huge amount of data, and leaves us with two substantial problems: 
How to \emph{store} the data, and how to \emph{analyze} the data
after it's stored. 
Decreasing data storage costs have done much to mitigate the first problem, but one still needs good
tools to process and explore what could quickly run into terabytes of data.

Assuming one has access to the necessary storage, 
databases are the obvious tool for the collection of the data. Most common database tools,
however,
don't lend themselves to the kinds of analysis that we need in evolutionary computation work. 
Most relational and document-based databases, for example, require complex and expensive 
recursive joins to trace significant hereditary lines.
In exploring the dynamics of an EC run, it may be necessary to
make connections across dozens or even hundreds of generations, which simply isn't plausible with a
relational database \citep{Robinson:GraphDB:Book}. 
While we use Neo4j as our graph database in this work, there are 
numerous other 
graph databases that could potentially be effective tools \citep{wiki:GraphDB}. We make no claims
to have exhaustively explored the range of possible database tools for this sort of work.

\section{A little background on tools and problems}
\label{sec:background}

This section provides some background on some of the key subjects of this work: The Neo4j graph 
database and its query language Cypher; the PushGP system; lexicase selection; and the 
replace-space-with-newline test problem.

\subsection{Neo4j and Cypher}
\label{subsec:Neo4j}

\index{graph database}
\index{Neo4j}

Graph databases \citep{Robinson:GraphDB:Book} are a relatively new database tool, where data is stored 
as a collection of nodes and relationships in a graph, with a specialized query language that makes 
it easy to ask questions about complex relationships.
In our work, nodes typically represent individuals, and \texttt{:PARENT\_OF} relationships 
capture the central genealogical connections. We store important data such as the total error as
properties of individual nodes, and genetic operators as properties on 
\texttt{:PARENT\_OF} edges.

The Neo4j query language, Cypher, allows this patterns in this data to be readily extracted.
A detailed description of Cypher is beyond the scope of this chapter, but Cypher's central feature is
the ability to describe sub-graph patterns. The Neo4j engine can then search
for subgraphs matching these patterns. Cypher also provides the ability to 
filter results based on properties in a manner quite similar to more traditional SQL queries.

\subsection{PushGP}

PushGP \citep{spector:2002:GPEM, 1068292:new} is a stack-based genetic programming system. The details
of PushGP aren't crucial for this analysis, but it is useful to know a few things:
\begin{itemize}
	\item PushGP uses a linear genome, which is then converted into a program.
	\item PushGP supports a variety of \emph{typed} stacks, with corresponding typed instructions.
	The \texttt{integer-add} instruction takes the top two items from the \texttt{integer}
	stack, adds them, and pushes the result back onto the \texttt{integer} stack.
	\item There is an \texttt{exec} stack which can hold blocks of instructions. This is what allows
	PushGP programs to loop or recurse, as pushing a block of instructions onto the \texttt{exec}<commit_msg>Removed a spurious word.<commit_after>%%%%%%%%%%%%%%%%%%%% author.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%%%%%%%%%%%%%%%% Springer %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title*{Using Graph Databases to Explore the Dynamics of Genetic Programming Runs}
% Use \titlerunning{Short Title} for an abbreviated version of
% your contribution title if the original one is too long
\author{<NAME>, <NAME>, and <NAME>}
% Use \authorrunning{Short Title} for an abbreviated version of
% your contribution title if the original one is too long
\institute{<NAME> \at Division of Science and Mathematics, University of Minnesota, Morris, MN USA
\and <NAME> \at Division of Science and Mathematics, University of Minnesota, Morris, MN USA
\and <NAME> \at Computer Science, University of Massachusetts, Amherst, MA USA}

\maketitle

\abstract{
	For both practical reasons and those of habit, most evolutionary computation research is presented in highly summary
	form. These summaries, however, often obscure or completely mask the profusion of specific selections, crossovers, and mutations
	that are ultimately responsible for the aggregate behaviors we're interested in. In this chapter we take a different
	approach and use the Neo4j graph database system to record and analyze the entire genealogical history of 
	a set of genetic programming runs. We then explore a few of these runs in detail, discovering important
	properties of lexicase selection; these may in turn help us better understand the dynamics of lexicase selection, and the
	ways in which it differs from tournament selection. More broadly, we illustrate the value of recording and analyzing this
	level of detail, both as a means of understanding the dynamics of particular runs, and as a way of generating questions
	and ideas for subsequent, broader study.}

\begin{keywords}
	graph database, Neo4j, ancestry, genealogy, lexicase selection, tournament selection
\end{keywords}
\index{graph database}
\index{Neo4j}
\index{ancestry}
\index{genealogy}
\index{lexicase selection}
\index{tournament selection}

\section{Introduction}
\label{sec:introduction}

It is common practice in empirical evolutionary computation (EC) 
research to perform a substantial number of runs, and then 
report a handful of aggregate statistics that summarize and (hopefully) represent 
the complex dynamics of those many runs. Tables present values such 
as mean or median best fitnesses at the end of runs, collapsing the complexities of dozens or 
hundreds of runs into a single number, possibly with a standard deviation or a 
confidence interval to give a sense of the distribution. Plots can often be more informative, 
showing how these numbers change over time during the runs, possibly giving a sense of 
the system dynamics and the range of behaviors. These plots, however, are typically still aggregate representations
that obscure or completely hide important moments that, if explored, might reveal valuable insight into the 
evolutionary dynamics being reported.

An alternative would be to collect, store, and analyze at least some of the rich panoply of 
evolutionary and genealogical events that make up the low-level details of these runs. 
Databases provide a natural tool for 
storing and accessing large data sets, but traditional relational
databases are poorly suited for many of the queries that are important for genealogical analysis.
In this chapter, we illustrate the use of graph databases as an alternative storage and analysis tool for
evolutionary computation runs. We have previously demonstrated that graph databases
can be an effective tool for analyzing complex genetic programming (GP) dynamics \citep{donatuccianalysis}, which led directly
to a proposed change to standard sub-tree crossover in tree-based GP \citep{mcphee:GECCO15}.
Here we will use the open source Neo4j graph database tool\footnote{\url{http://neo4j.com/}} 
to explore data from a
collection of PushGP runs \citep{Helmuth:2015:GPTP} on several problems drawn from a benchmark collection of introductory 
programming problems \citep{Helmuth:2015:GECCO}.

Note that this is \emph{not} going to be a presentation of ``traditional hypothesis-driven 
research''. It will be based on an \emph{assumption}, namely that something interesting happens in
these runs, and that we can learn useful things by exploring them in more detail, but the presentation
will be fairly discursive, reflecting our back-and-forth experience of wrestling with the data. Our
initial queries start from fairly obvious questions (e.g., ``Why did we succeed here?''), but from
there we engage in a dialog with data, letting the answers to early questions shape and guide our 
subsequent exploration. We are not presenting a tidy, sterile summary of our adventures, but
the messier (but we think more informative in this context) journal of what Pickering might call
our ``mangle of practice'' \citep{smith2008mangle, pickering:AJS:1993}.

Here we explore the impact of lexicase \citep{Spector:2012:GECCOcompA} and tournament selection 
on the dynamics of runs whose aim is to solve a basic software synthesis problem. 
In the process we are able to discover surprising and likely important properties of
lexicase that suggest areas of additional exploration and indicate reasons
for the substantially better performance seen when using lexicase on a variety of software synthesis 
problems \citep{Helmuth:2015:GECCO}.

We're not the first people to recognize the potential value of exploring lineages and ancestry graphs. 
The HeuristicLab team has been
working for several years on a set of tools to analyze at least small genealogical run histories 
\citep{Burlacu:2013:GECCOcomp:new, Burlacu:CIEES:2015}; hopefully these exciting features will be in 
an upcoming release. \citep{Burlacu:2013:GECCOcomp:new} also has an excellent survey of a variety of work
that uses genealogical information in EC work; none of this, however, appears to save and analyze full 
genealogical histories, but instead tends to use local ancestry information for purposes such as diversity
promotion. Recent work \citep{kuber2014ancestral} applies network theory to ancestry graphs, looking
for things like cliques as a way of better understanding EC dynamics; that work is similar in spirit to this
chapter, but differs in the kinds of graphs that are built and the tools used to analyze them.

Because we're going to focus on the use of graph databases, there will
on occasion be avenues of exploration that we won't pursue because they would properly involve
different tools. This exploration, for example, raises important questions about the relationships between
parent and child genomes. These could be addressed using, e.g.,
difference-merge tools from software engineering, or sequence alignment tools from genomics;
see, e.g., \citep{Burlacu:2013:GECCOcomp:new}
for an excellent example of this kind of analysis. We will, however, consider that
beyond the scope of this chapter. A key value of our graph database results will be in providing focus
for our use of those other tools, identifying key moments
and individuals in the course of a run that deserve additional attention. There are thousands
of potential genome comparisons to make in a single run, for example, but our graph databases analysis helps identify
some of the critical individuals, crossovers, and mutations in the run, allowing us to concentrate on the
steps that are likely to have mattered most.

We'll provide expanded motivation for this work in Section~\ref{sec:motivation}, and background on relevant tools
and concepts in Section~\ref{sec:background}. In Section~\ref{sec:lexicaseRun} we explore in some detail a successful
lexicase selection run, identifying several properties of lexicase selection that distinguish it from
other, more traditional selection methods. We then explore a successful tournament selection run in
Section~\ref{sec:tournamentRun}, comparing those results to the earlier lexicase results. 
In Section~\ref{sec:cumulativeResults} we step back a little and look at the results of expanding some of our queries
across hundreds of runs, and then wrap up with some conclusions in Section~\ref{sec:whatDidWeLearn}.

\section{Motivation}
\label{sec:motivation}

\index{ancestry}
\index{genealogy}

Consider the job of a paleontologist, who regularly reconstructs not just individuals but also
species and entire phylogenetic trees on the basis of a handful of teeth and bones, or even just
impressions left in prehistoric mud. They rarely have DNA, so any evolutionary relationship is
inherently speculative, subject to constant debate and revision. Even with detailed DNA sequences,
the construction of phylogenetic trees for existing species is non-trivial.

In evolutionary computation, however, we have access to \emph{everything}, at least in principle. 
We could gather every
selection, every mutation, and every crossover as they play out in our systems.
Yet we typically throw almost all that data away, reporting just aggregate statistics and summary
plots, completely failing to take advantage of our privileged position, a position most 
paleontologists would presumably eye with considerable envy. Not only does this seem an inherent
waste, these aggregations typically obscure critical moments in the dynamics of runs which might
speak volumes if explored.

While this sort of aggregate reporting is often valuable, allowing for important comparative
analysis, it typically fails to provide
any sense of the \emph{why}. Yes, Treatment A led to better aggregate performance than 
Treatment B -- but what happened in the runs that led to that result? Any end result
is ultimately the intricate combination of thousands or millions of of selections, recombinations,
and mutations, and if Treatment A is in some sense ``better'' than Treatment B, it must ultimately
be because it affected all those genealogical and genetic events in some significant way, biasing them
in a way that improved performance.

Unfortunately, published research rarely includes information that might shed light on 
these \emph{why} events. We rarely see evolved programs, for example, or any kind of post-run analysis
of those programs, and there is almost never any data or discussion of the genealogical history that
might help us understand how a successful program actually came to be. 
Sometimes these events and details aren't included
for reasons of space and time; evolved programs, for example, are often extremely large and complex,
and a meaningful presentation and discussion of such a program could easily take up more space than
authors have available.
We suspect, however, that another reason this sort of \emph{why} analysis often isn't 
reported is because it isn't done, in no small part because it's hard. As EC researchers we're in the
``privileged'' position of being able to collect anything and everything that happens in a run, 
but that's a potentially huge amount of data, and leaves us with two substantial problems: 
How to \emph{store} the data, and how to \emph{analyze} the data
after it's stored. 
Decreasing data storage costs have done much to mitigate the first problem, but one still needs good
tools to process and explore what could quickly run into terabytes of data.

Assuming one has access to the necessary storage, 
databases are the obvious tool for the collection of the data. Most common database tools,
however,
don't lend themselves to the kinds of analysis that we need in evolutionary computation work. 
Most relational and document-based databases, for example, require complex and expensive 
recursive joins to trace significant hereditary lines.
In exploring the dynamics of an EC run, it may be necessary to
make connections across dozens or even hundreds of generations, which simply isn't plausible with a
relational database \citep{Robinson:GraphDB:Book}. 
While we use Neo4j as our graph database in this work, there are 
numerous other 
graph databases that could potentially be effective tools \citep{wiki:GraphDB}. We make no claims
to have exhaustively explored the range of possible database tools for this sort of work.

\section{A little background on tools and problems}
\label{sec:background}

This section provides some background on some of the key subjects of this work: The Neo4j graph 
database and its query language Cypher; the PushGP system; lexicase selection; and the 
replace-space-with-newline test problem.

\subsection{Neo4j and Cypher}
\label{subsec:Neo4j}

\index{graph database}
\index{Neo4j}

Graph databases \citep{Robinson:GraphDB:Book} are a relatively new database tool, where data is stored 
as a collection of nodes and relationships in a graph, with a specialized query language that makes 
it easy to ask questions about complex relationships.
In our work, nodes typically represent individuals, and \texttt{:PARENT\_OF} relationships 
capture the central genealogical connections. We store important data such as the total error as
properties of individual nodes, and genetic operators as properties on 
\texttt{:PARENT\_OF} edges.

The Neo4j query language, Cypher, allows patterns in this data to be readily extracted.
A detailed description of Cypher is beyond the scope of this chapter, but Cypher's central feature is
the ability to describe sub-graph patterns. The Neo4j engine can then search
for subgraphs matching these patterns. Cypher also provides the ability to 
filter results based on properties in a manner quite similar to more traditional SQL queries.

\subsection{PushGP}

PushGP \citep{spector:2002:GPEM, 1068292:new} is a stack-based genetic programming system. The details
of PushGP aren't crucial for this analysis, but it is useful to know a few things:
\begin{itemize}
	\item PushGP uses a linear genome, which is then converted into a program.
	\item PushGP supports a variety of \emph{typed} stacks, with corresponding typed instructions.
	The \texttt{integer-add} instruction takes the top two items from the \texttt{integer}
	stack, adds them, and pushes the result back onto the \texttt{integer} stack.
	\item There is an \texttt{exec} stack which can hold blocks of instructions. This is what allows
	PushGP programs to loop or recurse, as pushing a block of instructions onto the \texttt{exec}
{'fraction_non_alphanumeric': 0.04763735495596253, 'fraction_numerical': 0.00482315112540193, 'mean_word_length': 5.140128755364807, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4618011', 'n_tokens_mistral': 7081, 'n_tokens_neox': 6554, 'n_words': 4111}