Previous chapters have discussed the DDP models and a series of algorithms designed to 
comment on an optimal combination of settings to these models. Chapter 4 has also discussed external research relevant 
to this thesis.

This chapter presents a series of experiments where we benchmark KEYS and KEYS2 against andard techniques for
solving the DDP requirements satisfaction problem. I will also detail scale-up results that
show KEYS' ability to handle models multiple times larger than those seen in the present day. Lastly, I will show the results of one
attempt to develop a more powerful variant of KEYS2. 

\section{Benchmarking KEYS and KEYS2}\label{sec:bk2}

Each of the algorithms described in Chapter 3 was tested on the five  models of \fig{ddpModels}.
Note that:
\bi
\item
Models one and three are trivially small. They were used them to debug source code, but have been left out the core experiments.
I report my results using models two, four and five since they are large enough to stress test real-time optimization.
\item
Model 4 was discussed in~\cite{me03n} in detail. The largest, model 5 was optimized previously in ~\cite{fea02a}.
At that time (2002), it took 300 seconds to generate solutions using an old, very slow, rule learning method.
\item All five models were assessed by the KEYS algorithm in ~\cite{jalali08}. However, that paper presented no comparison results.
\ei

I have also studied how well KEYS and KEYS2 scale to larger models.
Further, I have instrumented KEYS and KEYS2 to generate decision ordering diagrams.
The results from all of these experiments are  shown below.

\subsection{Attainment and Costs}

All of the comparison algorithms (KEYS, KEYS2, simulated annealing, A*, and MaxFunWalk) were run 1000 times on each model. 
Such a high number of repeats 
was chosen because it yielded enough data points to give a clear
picture of the span of results, and ensured that outlying values would have no effect on the experiment outcomes. 
At the same time, it is a low enough number that I can still generate a complete set of results in a fairly short time
span.  

\begin{figure}[!b]\centering
\begin{center}\scriptsize
\begin{tabular}{c@{}c@{}c@{~}c}
&Model 2&Model 4 &Model 5 \\
& (31 mitigations)& (58 mitigations)&(99 mitigations)\\ \hline
\begin{sideways}~~~~~~~~SA\end{sideways}& \includegraphics[width=4.25cm]{WithLabel/2/SA.pdf} & \includegraphics[width=4cm]{WithLabel/4/SA.pdf} & \includegraphics[width=4cm]{WithLabel/5/SA.pdf} \\\hline 
\begin{sideways}~~MaxFunWalk\end{sideways}& \includegraphics[width=4.25cm]{WithLabel/2/MaxFunWalk.pdf} & \includegraphics[width=4cm]{WithLabel/4/MaxFunWalk.pdf} & \includegraphics[width=4cm]{WithLabel/5/MaxFunWalk.pdf} \\ \hline

\begin{sideways}~~~~~~A*\end{sideways}&  \includegraphics[width=4.25cm]{WithLabel/2/AStar.pdf} & \includegraphics[width=4cm]{WithLabel/4/AStar.pdf} &  \includegraphics[width=4cm]{WithLabel/5/AStar.pdf} \\ \hline

 \begin{sideways}~~~~~~~~KEYS\end{sideways} &  \includegraphics[width=4.25cm]{WithLabel/2/KEYS.pdf} & \includegraphics[width=4cm]{WithLabel/4/KEYS.pdf} & \includegraphics[width=4cm]{WithLabel/5/KEYS.pdf} \\ \hline

\begin{sideways}~~~~~~~KEYS2\end{sideways}& \includegraphics[width=4.25cm]{WithLabel/2/KEYS-L.pdf} & \includegraphics[width=4cm]{WithLabel/4/KEYS-L.pdf} & \includegraphics[width=4cm]{WithLabel/5/KEYS-L.pdf} \\


\end{tabular}
\caption{1000 results of running five algorithms on three models (15,000 runs in all).
The y-axis shows
cost and  the x-axis shows attainment. 
The size of each model is measured in number of mitigations. 
Note that better solutions fall
towards the bottom right of each plot; i.e. lower costs and higher attainment.
Also better solutions exhibit less variance, i.e. are clumped tighter together.
\label{fig:finalModelResults}
}
\end{center}
\end{figure}

The results are pictured in ~\fig{finalModelResults}. Attainment
is along the x-axis and cost (in thousands) is along the y-axis.
Note that better solutions fall
towards the bottom right of each plot; that is, the area of lower costs and higher attainment.
Also, better solutions exhibit less variance and, as such, the results
are clumped closely together.

These graphs give a clear picture of the results obtained by the
various algorithms. Two methods are clearly inferior:
\bi
\item Simulated annealing exhibits
the worst variance, lowest attainments, and highest costs.
\item MaxFunWalk is better than SA (less variance, lower costs, higher attainment)
but its variance is still far too high to use in any sort of critical situation.
\ei
As for the other techniques:
\bi
\item
On larger models such as model4 and model5, KEYS and KEYS2 exhibit 
lower variance, lower costs, and higher attainments than A*.
\item On smaller models such as model2,
A* usually produces higher attainments and lower variance than the KEYS algorithms
(this advantage disappears on the larger models). 
However, observe the results near the $(0,0)$ point of model2's A* results: sometimes
A*'s heuristic search failed completely for that model.
\ei

\begin{figure}[!t]
{\scriptsize
\begin{center}
\begin{tabular}{c|c|c|c} 
&Model 2~(31 mitigations)~& Model 4~(58 mitigations)~&Model 5~(99 mitigations)~\\ \hline
SA& 0.577   &1.258        &0.854  \\ \hline
MaxFunWalk& 0.122   &0.429   &0.398         \\ \hline
A*&  0.003  &0.017         &0.048    \\ \hline
KEYS  & 0.011   &0.053         &0.115   \\ \hline
KEYS2 	&0.006  &0.018 		&0.038 \\ 
\end{tabular}
\end{center}
}\caption{
 Runtimes in seconds, averaged over 100 runs, measured using the
``real time'' 
value from the Unix {\tt times} command. 
The size of each model is measured in number of mitigations (and for more details
on model size, see \fig{ddpModels}). 
}
\label{fig:runtimes}
\end{figure}
\subsection{Runtime Analysis}\label{sec:runtimea}
Measured in terms of  attainment and cost, there is little difference between KEYS and KEYS2.
However, as shown by \fig{runtimes}, KEYS2 runs twice to three 
times as fast as its predecessor.
Interestingly, \fig{runtimes} ranks two of the algorithms in a similar order to \fig{finalModelResults}: 
\bi
\item
Simulated annealing is clearly the slowest;
\item MaxFunWalk is somewhat better but not as fast as the other algorithms.
\ei
As to A* versus KEYS or KEYS2:
\bi
\item
A* is faster than KEYS;
\item
and  KEYS2 runs in time comparable to  A*.
\ei
Measured purely in terms of runtimes, there is little to recommend KEYS2 over A*. 
However, A*'s heuristic guesses were sometimes observed to be sub-optimal (recall the above discussion
on the $(0,0)$ results in model2's A* results). Such sub-optimality was never observed for KEYS2.

\subsection{Decision Ordering Algorithms}\label{sec:dodresults}

\begin{figure}
\begin{center}
\noindent
\includegraphics[width=5in]{model2.pdf}

\noindent
{\bf \fig{in5}a:} Internal Decisions on Model 2.

\noindent
~\\
\noindent
\includegraphics[width=5in]{model4.pdf}

\noindent
{\bf \fig{in5}b:} Internal Decisions on Model 4.

\noindent
~\\
\noindent
\includegraphics[width=5in]{model5.pdf}

{\bf \fig{in5}c:} Internal Decisions on Model 5.
\end{center}
\caption{Median and spread of partial solutions learned by KEYS and KEYS2. X-axis shows the number
of decisions made.  ``Median'' shows the 50th percentile of the measured
value seen in 100 runs at each era. ``Spread'' shows the difference between the 75th  and 50th percentile. }
\label{fig:in5}
\end{figure}

The decision ordering diagrams of \fig{in5} show the effects of the 
decisions made by KEYS and KEYS2.
For both algorithms, at $x=0$, all of
the mitigations in the model are set at random. During each subsequent
era, more mitigations are fixed (KEYS sets one at a time, KEYS2 
freezes an incrementally increasing number).
The lines in each of these
plots show the median and spread seen in the one-hundred calls to the {\tt
model} function during each round. 

Note that the these diagrams are both {\em tame} and {\em well-behaved}, as defined in Chapter 2:
\bi
\item
{\em Tame:} The "spread" values quickly shrink to a small fraction of the median. 
\item
{\em Well-behaved:} The median values move smoothly to a plateau of best performance (high attainment, low costs).
\ei
On termination (at maximum value of $x$), KEYS and KEYS2 
arrive at nearly identical median results (caveat:
for model2, KEYS2 attains slightly more requirements at a slightly higher
cost than KEYS). 
The spread plots  for both algorithms are almost indistinguishable except, again, for model 2. In that model, the KEYS2 spread
is less than KEYS. 
Based on these diagrams, we can observe that KEYS2 achieves approximately the same results as KEYS, but
(as shown in \fig{runtimes} and \fig{scaleupruntimes}) it does so in less time.

A core assumption of this work is the ``keys'' concept - that a small minority of important model variables restrict the remaining majority. 
\fig{in5} offers significant support for this assumption. It can be observed that most of the improvement in costs and attainments 
were achieved after KEYS and KEYS2 
made only a handful of decisions (often ten or fewer).

It is insightful to reflect on the effectiveness of different algorithms at generating these decision ordering diagrams.
KEYS2 is the most direct and fastest method, and by its very design, automatically generates these diagrams. As mentioned above, 
all of the required information can be collected during one execution of KEYS2.
On the other hand,
simulated annealing, A*, and MaxFunWalk would require a post-processor to generate the diagrams:
\bi
\item
Given $D$ possible decisions,
At each era, KEYS and KEYS2 collects statistics on  partial solutions where 
$1,2,3,..|d|$ variables are fixed (where $d$ is the set of decisions)
while the remaining $D-d$ decisions are made at random. 
\item
A*, Simulated Annealing, and MaxFunWalk 
work with full solutions since at each step they offer settings to all 
$d_i\in D$ variables. In the current form, they cannot comment on partial solutions.
Modified forms of these algorithms could theoretically add in extra instrumentation and extra post-processing
to comment 
on partial solutions
using methods like
feature subset selection~\cite{hall03} or a sensitivity
analysis~\cite{saltelli00}. 
\ei

\section{Scale-Up Studies}\label{sec:scaleup}

In order to provide useful blind-spot exploration, our DDP optimization tools must run fast
enough that humans can get feedback before they must move on to other issues. 
Our previous solutions to the DDP optimization problem are too slow. 
Ideally, we wish for requirements optimization to occur in "real-time"; i.e. to offer advice before 
an expert's attention wanders to other issues.  

\begin{figure}
\centering
\small
\begin{tabular}{r|l}
Year & Num. Variables\\\hline
2004 & 30 \\
2008 & 100 \\
2010 & 300\\
2013 & 800\\\hline
\end{tabular}
\caption{Growth trends; number of variables in DDP's data dictionary.} 
\label{fig:numVariables}
\end{figure}

\fig{numVariables} shows the growth rate (historically and projected) of the number of variables within a 
DDP model. It is expected that, by 2013, DDP models will be roughly eight times 
larger than they were in 2008 and twice as large as they are today. As shown in ~\fig{runtimes}, KEYS and KEYS2 report results that could be 
considered "real-time." However, it remains unclear whether
they scale to the complex models that we expect to see in the near future?

In order to study how well the scalability of KEYS and KEYS2, an {\em instance generator} was created that:
\bi
\item
Examined the real-world DDP models of \fig{ddpModels}; 
\item
Extracted
statistics related to the different types  of nodes (mitigations or risks or requirements) and the number of
edges between different types of nodes; 
\item 
Used those statistics to build  random models that were 2,4,8, and 16 times
larger than the original models.
\ei
For more on the model generator, see Section \ref{sec:igen}. It is worth noting that, for the purposes
of this scale-up study, I have actually stepped ahead of the expected growth curve. The artificial models generated for
this contain up to 1600 mitigations (twice as large as those that JPL is expected to be designing in 2013, and sixteen times larger than
the largest models studied in this thesis).

\fig{scaleupruntimes} and
\fig{scaleupmodelcalls} 
show the effect of changing the size of the model on the number of times that 
the model is asked to generate a score for both KEYS and KEYS2.

\begin{figure}[!t]
\begin{minipage}{.6\linewidth}
{\scriptsize
\begin{tabular}{c|c|r|r|r|r|}
\multicolumn{3}{c}{~}& \multicolumn{2}{|c|}{Runtime (secs)}&$\frac{\mbox{KEYS}}{\mbox{KEYS2}}$\\\cline{4-5}
model & expansion & model size & KEYS & KEYS2 & \\\hline
2&1&62&0.01&0.01&1.07\\
2&2&124&0.03&0.02&1.23\\
4&1&139&0.04&0.02&2.29\\
5&1&201&0.13&0.04&3.18\\
2&4&248&0.10&0.05&2.09\\
4&2&278&0.17&0.05&3.48\\
5&2&402&0.50&0.12&4.26\\
2&8&496&0.44&0.14&3.21\\
4&4&556&0.73&0.16&4.66\\
5&4&804&1.98&0.38&5.21\\
4&8&1112&2.97&0.52&5.71\\
5&8&1608&8.06&1.35&5.96
\end{tabular}}
\end{minipage}\begin{minipage}{.4\linewidth}
\includegraphics[width=1.75in]{scaleupruntimes.pdf}
\end{minipage}
\caption{Runtimes KEYS vs KEYS2 (medians over 1000 repeats) as models increase in size.
The ``model''
 number in column one corresponds to \fig{ddpModels}. The 
``expansion factor''
of column two shows how much the instance generator expanded the model.
The ``model sizes'' of column three are  the sum of mitigations, requirements, and risks
seen in the expanded model.
}\label{fig:scaleupruntimes}
\end{figure}
\begin{figure}[!t]
\begin{minipage}{.6\linewidth}
{\scriptsize
\begin{tabular}{c|c|r|r|r|r|}
\multicolumn{3}{c}{~}& \multicolumn{2}{|c|}{Calls to {\tt model}}&$\frac{\mbox{KEYS}}{\mbox{KEYS2}}$\\\cline{4-5}
model & expansion & model size & KEYS & KEYS2 & \\\hline
2&1&62&3100&800&3.9\\
2&2&124&6200&1100&5.6\\
4&1&139&5800&1100&5.3\\
5&1&201&9900&1400&7.1\\
2&4&248&12400&1600&7.8\\
4&2&278&11600&1500&7.7\\
5&2&402&19800&2000&9.9\\
2&8&496&24800&2200&11.3\\
4&4&556&23200&2200&10.5\\
5&4&804&39600&2800&14.1\\
4&8&1112&46400&3000&15.5\\
5&8&1608&79200&4000&19.8
\end{tabular}
}
\end{minipage}\begin{minipage}{.4\linewidth}
\includegraphics[width=1.75in]{scaleupcalls.pdf}
\end{minipage}
\caption{Number of model calls made by KEYS vs KEYS2 (medians over 1000 results) as models
increase in size.
This figure uses the same column structure as \fig{scaleupruntimes}.
}\label{fig:scaleupmodelcalls}
\end{figure}
\begin{figure}[!t]
{\footnotesize
\begin{center}
\begin{tabular}{r|r|r|r|r|}
\multicolumn{1}{c}{~}				&\multicolumn{2}{c}{KEYS}	&\multicolumn{2}{c}{KEYS2}\\\cline{2-5}
				&runtimes	&model calls	&runtimes	&model calls\\\hline
exponential 		&0.82	    &0.83		&	0.88&     0.93\\\hline
polynomial (of degree 2)&0.99&	0.99	&		0.99&     0.98\\
\end{tabular}
\end{center}
}
\caption{Coefficients of determination $R^2$ of KEYS/KEYS2 performance figures,
fitted to two different functions: exponential or   polynomial of degree two.
Higher values indicate a better curve fit.
In all cases, the best fit is not exponential.
}\label{fig:fits}
\end{figure}

\fig{fits} shows the results of curve fitting to the plots of
\fig{scaleupruntimes} and
\fig{scaleupmodelcalls}.
The KEYS and KEYS2 performance curves fit a low-order polynomial (of degree two)  with very high coefficients of determination ($R^2\ge 0.98$).
That is to say, the KEYS2 algorithm is of complexity size $O(N^{2})$. 

The evidence in \fig{fits} suggests that one could scale {\em either} KEYS or KEYS2 to larger models without an inordinate increase in
execution time. However, I would still have to recommend KEYS2.
The column marked $\frac{KEYS}{KEYS2}$ in \fig{scaleupmodelcalls}
shows the
ratio of the number of calls made by KEYS vs KEYS2.
As models get larger, the number of calls to the model are an 
order of magnitude greater in KEYS than in
KEYS2. If applied to models with slower runtimes than those current DDP models, then this 
order of magnitude is highly undesirable.

\section{Benchmarking KEYS-R}\label{sec:bkr}

While KEYS2 represents a speed upgrade over the original KEYS, it still has one clear limitation.
By setting multiple mitigations each round, the 
algorithm loses the "support" built by the one-hundred instances generated each round. 
Therefore, while KEYS2 is faster than the original KEYS, its results contain slightly more {\em variance}. Other attempts to
increase the number of mitigations set per round have resulted in variance outside of useful bounds.
When a software profiler was used on KEYS2, one interesting point was revealed. Nearly {\em 70\%} of the runtime was spent in asking the model
for a new $(cost,attainment)$ performance pairing. 
Each round, both KEYS and KEYS2 generate one-hundred random sets of mitigation settings and score them, 
using these scores to find mitigations to fix for subsequent rounds (thus, the model is called one hundred
times each round). 
This instance generation step is the chief bottleneck in the KEYS algorithm. However, one cannot just cut the number of random
configurations generated at each step - a large number of instances is needed to 
provide the {\em support} necessary to accurately rank mitigations. 
If fewer instances are generated, the same issue arises as when too many mitigations
are fixed. There is a larger variance in results, and those results tend to contain higher cost and lower attainment values.
KEYS-R, as explained in Section \ref{sec:keysr}, was developed as an attempt to find a balance between speed
and support. It retains certain high-scoring instances and attempts to reuse them in later rounds.

For two of the models from the original experiment (models 2 and 4), 
as well as several of the artificially-generated models from 
Sections \ref{sec:igen} and  \ref{sec:scaleup}, 
I ran each KEYS, KEYS2, and KEYS-R one-hundred times in order to filter for outliers and obtain stable results. 
For each algorithm and model, the final attainment, cost, and runtimes were recorded. The results are presented in the following subsections. 

\subsection{Attainment and Costs}

\begin{figure}
\small
\begin{tabbing}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\=Original:~\=
\begin{tabular}{|c|r|r|r|} \hline
Model&KEYS&KEYS2&KEYS-R\\ \hline
model2.c& 7325   &7325         &6250           \\ \hline
model4.c& 876500   &921500        &711500          \\ \hline
\end{tabular} \\
\\
\>Artificial:~\>
\begin{tabular}{|c|r|r|r|} \hline
Model&KEYS&KEYS2&KEYS-R\\ \hline
model2-2.c& 0   &140         &140          \\ \hline
model2-4.c& 125   &710         &1055            \\ \hline
model2-8.c& 1080   &3435         &5540          \\ \hline
model2-16.c& 10815   &22030         &35050           \\ \hline
model4-2.c& 1000  &36500        &39500           \\ \hline
model4-4.c& 35500   &146000        &226000          \\ \hline
model4-8.c& 220000   &577000        &670000        \\ \hline
model4-16c& 1422500   &2733000        &5285000            \\ \hline
model5-2.c&13575    &43050        &59500         \\ \hline
model5-4.c&93000    &228000        &325500            \\ \hline
model5-8.c&430050    &796650        &1233575           \\ \hline
\end{tabular}
\end{tabbing}
\caption{Median cost results for each of our algorithms run on each model.}
\label{fig:costs}
\end{figure}

\begin{figure}
\small
\begin{tabbing}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\=Original:~\=
\begin{tabular}{|c|r|r|r|} \hline
Model&KEYS&KEYS2&KEYS-R\\ \hline
model2.c& 0.7   &0.7         &0.7           \\ \hline
model4.c& 3013   &3011        &2858          \\ \hline
\end{tabular}\\
\\
\>Artificial:~\>
\begin{tabular}{|c|r|r|r|} \hline
Model&KEYS&KEYS2&KEYS-R\\ \hline
model2-2.c& 54   &54         &54          \\ \hline
model2-4.c& 112   &112         &112            \\ \hline
model2-8.c& 228   &228         &228          \\ \hline
model2-16.c& 460   &460         &460           \\ \hline
model4-2.c&3835 &3835       &3835           \\ \hline
model4-4.c&8727   &8727        &8727          \\ \hline
model4-8.c&18492   &18492       &18492          \\ \hline
model4-16c&34975   &34975       &34975            \\ \hline
model5-2.c&523    &523       &523         \\ \hline
model5-4.c&845    &845       &845           \\ \hline
model5-8.c&1788    &1788        &1788           \\ \hline
\end{tabular}
\end{tabbing}
\caption{Median attainment results for each of our algorithms run on each model.}
\label{fig:attains}
\end{figure}

As expected, the original KEYS obtains the absolute best balance between cost and attainment, with KEYS2 performing similarly. 
Unfortunately, KEYS-R does not do very well in comparison to KEYS2. KEYS-R returns similar attainments, but much higher cost values.
In certain extreme cases, like artificial model 5-8, it returns a cost
estimate three times higher the value given by the original KEYS. These median results were compared using the Mann-Whitney U tests,
only to reach the same conclusion. KEYS slightly outperforms KEYS2, and both outperform KEYS-R. 

The results that consistently emerged for each model, as output by a Mann-Whitney test were:
\bi
\item Two wins for KEYS;
\item One win and one loss for KEYS2;
\item Two losses for KEYS-R.
\ei

What is occurring here is that KEYS-R, though designed to maintain support, clearly fails to do so. In the best case, it is likely that the
rules governing instance decay were too simple. It is also equally possible that the entire concept of instance retention is flawed - configurations
that scored well at one point just might not be useful later in the search process.

One point of interest is that KEYS-R performed very differently on the original models as opposed to the artificially generated ones. 
The results are not necessarly better, they have just gone in the opposite direction. When executed on the original models, 
KEYS-R returns pairings with lower costs than KEYS or KEYS2 (this is good) but lower attainments as well (this is bad).
The rules governing instance retention were perhaps too loose for the artificially-generated models and too strict on the 
original models. Very few instances are scored as 
"best" (a subset of instances retained within the KEYS-R algorithm).
For example, in one trial involving model 4 from the original set, only three instances were ever stored in the best subset. 
In the artificial version of that model, one-hundred (the limit before decayed instances are replaced) examples are stored. 
This implies that KEYS-R is very dependent on
the actual construction of the model. Things like the 
number of connections between specific risks and mitigations seem 
to drastically affect the results that
appear.

\begin{figure}[!t]
\small
\begin{tabbing}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\=Original:~\=
\begin{tabular}{|c|r|r|r|} \hline
Model&KEYS&KEYS2&KEYS-R\\ \hline
model2.c& 0.00881   &0.00497         &0.00838          \\ \hline
model4.c& 0.04724   &0.01523        &0.03763          \\ \hline
\end{tabular}\\
\\
\>Artificial:~\>
\begin{tabular}{|c|r|r|r|} \hline
Model&KEYS&KEYS2&KEYS-R\\ \hline
model2-1.c& 0.00833   &0.00775        &0.00671           \\ \hline
model2-2.c& 0.02720   &0.02216         &0.0197          \\ \hline
model2-4.c& 0.10398   &0.04964         &0.07067            \\ \hline
model2-8.c& 0.44088   &0.13736         &0.30278          \\ \hline
model2-16.c& 1.76741   &0.48072         &1.29550           \\ \hline
model4-1.c& 0.04375  &0.01911        &0.02502           \\ \hline
model4-2.c& 0.17386  &0.05003        &0.09178           \\ \hline
model4-4.c& 0.73049   &0.15686        &0.39623          \\ \hline
model4-8.c& 2.97024   &0.59174        &1.83779         \\ \hline
model4-16c& 12.60780   &1.88267        &8.8363            \\ \hline
model5-1.c& 0.12882    &0.04055        &0.07276           \\ \hline
model5-2.c& 0.49749    &0.11666        &0.29788         \\ \hline
model5-4.c& 1.97696    &0.37918        &1.34306            \\ \hline
model5-8.c& 8.05896    &1.35119        &5.97226           \\ \hline
\end{tabular}
\end{tabbing}
\caption{Runtime results for each of our algorithms run on each model.}
\label{fig:runtimesR}
\end{figure}


\subsection{Runtime Analysis}

As \fig{runtimesR} shows, KEYS-R falls right between KEYS and KEYS2 in terms of runtime. 
This is crucial, as standard KEYS is too slow to provide realtime results on the largest of 
our artificial models (in one case, taking almost nine seconds).

KEYS2 and KEYS-R outperform the original KEYS on every model. 
However, the fact that is {\em does not} run faster than KEYS2, and that it returns sub-optimal cost and attainment pairings,
leaves little reason to recommend it over the existing solutions to DDP model optimization. 
Unless lingering issues with its instance-retention model were addressed, it is unlikely that KEYS-R could be considered as a replacement for KEYS2.
Future directions for KEYS research will likely involve quick-caching methods (elaborated on in Section \ref{sec:fwork}) rather
than any form of full instance retention.

\section{Summary}

The experiments shown in this chapter have shown that when assessed in terms of
(a) reducing inference times, (b) increasing solution quality, and (c) decreasing the variance of the generated solution,
KEYS2 out-performs other search algorithms including simulated annealing, A*, MaxWalkSat. 

KEYS and KEYS2 are extremely fast algorithms, and I created a series of increasingly large synthetic models to test 
their ability to scale to the complex projects of the future. The second experiment shows that KEYS2 will scale to models up to
sixteen times larger than those currently in existence with no discernible issues. 

Finally, I have compared KEYS and KEYS2 to a new version of KEYS designed to retain certain "good" instances (called KEYS-R). 
Unfortunately, the KEYS-R experiment yielded poor results, with both KEYS and KEYS2 demonstrating higher-quality $(cost,attainment)$ pairings 
(and KEYS2 demonstrating faster
execution times).

The next chapter offers a more detailed analysis of these results, as well as potential plans for future work.
