Consider
a ``requirements model'' where stakeholders write:
\bi
\item
Their various goals for a project;
\item
All of the possible methods for reaching those goals;
\item
Their view of the possible risks that could compromise
those goals;
\item
What mitigations they believe might reduce those risks.
\ei
A ``solution'' to such  models is an ideal balance between the 
{\em least}
cost set of mitigations that reduce the {\em most} risks, thereby enabling the attainment of the {\em most}
requirements. 
In theory, an algorithm could be used to find the solution
that best satisfies the various goals of the different stakeholders whle ensuring that the project remain within 
the bounds of its budget.
Such tools might even find potential solutions that  were  missed
by these stakeholders.
Finding solutions to these requirements models is a non-linear optimization problem -
a solution must {\em minimize} the sum of the mitigation costs while {\em maximizing} the number of achieved requirements.

According to Mark Harman~\cite{harman07}, understanding the neighborhood of solutions is an open and pressing issue in search-based
software engineering (SBSE).
He argues that  many software engineering problems are over-constrained and, thus, no precise solution over all variables is 
	achievable; therefore, partial solutions based on meta-heuristic search methods are preferred. 

\begin{quote}
		``In some software engineering applications, solution robustness may be as important as solution functionality. For example, it may be 
		better to locate an area of the search space that is rich in fit solutions, rather than identifying an even better solution that is 
		surrounded by a set of far less fit solutions.''
	\end{quote}

	\begin{quote}
		``Hitherto, research on SBSE has tended to focus on the production of the fittest possible results. However, many application areas require 
		solutions in a search space that may be subject to change. This makes robustness a natural second order property to which the research 
		community could and should turn its attention~\cite{harman07}.''
	\end{quote}

The {\em robustness} of solutions is a major problem for such partial heuristic search methods.
There are many heuristic methods that can generate  solutions to non-linear problems (see the {\em Related Work} chapter).
Such methods can be  {\em brittle}~\cite{harman01}. That is, small changes may dramatically alter
the effectiveness of the generated solution. 
Therefore, when offering partial solutions, it is very important to 
	also offer insight into the space of options around the proposed solution. 
Such neighborhood information is very useful for managers with only 
	partial control over their projects, as it can give them confidence that, even if only some of their recommendations are enacted, 
then at least 
	the range of outcomes is well understood. 

A naive approach to understanding the neighborhood  might be
to run a system $N$
times, then report:
\bi
\item
the solutions appearing in more than, for example, $\frac{N}{2}$
cases;
\item
Results with a $\pm95\%$ confidence interval.
\ei
Note that both of these approaches require multiple trials of the chosen analysis method.
Multiple executions are undesirable since, as experience shows~\cite{feather08}, stakeholders often
ask questions across a large
range of ``scenarios'' with hard-wired constraints that cannot be
changed in that scenario. These scenarios might be as simple as what could be achieved assuming a maximum budget
of one billion dollars? Two billion? Five billion?

Scenario analysis can become a time consuming task.
Reflecting over, say, $d=10$ possible decisions over a statistically significant number of repeats ($N=20$)
requires up to $20*2^{10}>20,000$ repeats of the analysis. 
In order to provide useful exploration of this search space - to avoid blind spots, in other words - optimization techniques 
must run fast
enough that humans can get feedback before they must move on to other issues. 
Neilson ~\cite{neilson93} reports 
that "the basic advice regarding response times has been about the same for thirty years; i.e.
\bi
\item One second is about the limit for the user's flow of thought to stay uninterrupted, 
even though the user will notice the delay
\item Ten seconds is the limit for keeping a user's attention focused on the dialogue."
\ei

This thesis reports a set of experiments on the search for robust solutions to a NASA requirements model 
called the Defect Detection and Prevention model.
These experiments address
 two important concerns.
Firstly,
{\em is
demonstrating solution
robustness a time consuming task}? 
Secondly, is it necessary, as Harman suggests, that 
{\em solution quality must be traded off against solution robustness}?
 That is, in the search for the
conclusions that were stable within their local neighborhood, would we
have to reject better solutions because they are not stable across the same neighborhood?

At least for the NASA models used in these experiments, both of the concerns are unfounded.
The KEYS2 algorithm, presented in Chapter 3, terminates in hundredths of a second 
(whereas prior candidate algorithms took minutes to terminate~\cite{fea02a}).
Also, the solutions found by KEYS2 were not only of highest quality of the methods benchmarked, they also exhibited the lowest variance.
Further, KEYS2 generates decision ordering diagrams that can 
be used assess solution robustness in  linear time ({\em decision ordering diagrams}
are a visual representation of the effects of changing a solution). 

In this thesis, I demonstrate that:
\bi
\item Using these diagrams, the region around a solution can be explored in linear time. 
\item A greedy Bayesian-based method called KEYS2 can generate the decision ordering diagrams in $O(N^2)$ time.
\item KEYS2 yields solutions of higher quality that several other methods
(Simulated Annealing, MaxWalkSat, ASTAR).
\item Also, the variance of the solutions found by KEYS2 is less (and hence, better) than those found by the other methods.
\ei

\section{Statement of Thesis}

The KEYS2 algorithm is a robust method for the optimization
of requirements models. 
When assessed in terms of (a) reducing inference times, 
(b) increasing solution quality, and 
(c) decreasing the variance of the generated solution, KEYS2 
outperforms both standard and state-of-the-art search algorithms 
(including simulated annealing, A*, and MaxWalkSat).

\section{Contributions of this Thesis}

This thesis contributes a variety of findings to the literature, 
including:
\bi
\item A new compiled form of the Defect Detection and Prevention model,
a design model used by NASA's Jet Propulsion Lab.
\item Implementations of standard algorithms - Simulated Annealing, A* search, and MaxWalkSat - designed to optimize settings to such models.
\item A novel Bayesian learning mechanism, KEYS, that can generate 
robust requirements decisions in $O(N^2)$ time.
\item An improved version of KEYS that generates model solutions in 
a shorter length of time and with less variance than other standard methods.
\item A visual format - decision ordering diagrams - that models the 
cost and benefit effect of making certain {\em key} decisions.   
\ei

\section{Publications from this Thesis}

\bi
\item Gay, Gregory and Menzies, Tim and Jalali, Omid and Mundy, Gregory and Gilkerson, Beau and Feather, Martin and Kiper, James. Finding robust solutions in requirements models. Automated Software Engineering, 17(1):
87-116, 2010.
\ei

This paper is the first publication of the KEYS2 algorithm. It presents
benchmarking experiments comparing KEYS2 against state-of-the-art
search algorithms. 

\section{Structure of this Document}

The remainder of this thesis is organized as follows:
\bi
\item Chapter 2 presents some background material, including
information on the DDP model format, an objective function for 
scoring model configurations, decision ordering diagrams, and a
generator for building artificial models.
\item Chapter 3 is a literature review of the search-based software engineering field.
\item Chapter 4 describes the KEYS and KEYS2 algorithms, as well as 
a series of standard algorithms that are benchmarked against it.
\item Chapter 5 presents a series of case studies when KEYS is compared
to established algorithms. An experiment demonstrates that KEYS2 scales
well to larger models. A series of experiments are also presented
where attempts are made to improve the speed of KEYS.
\item Chapter 6 concludes this thesis by summarizing the contributions
of this algorithm as well as proposing possible future work.
\ei
