To motivate this work, we discuss a model with a  widely-used software engineering predictor for development effort, threats, development time, and defects.We identify certain problems with this model (calibration instability) which makes it inadequate to report point solutions. Hence, this chapter reviews  methods for using AI search over the space of possible solutions.

Note that this thesis explores one such method and other WVU graduate researchers (\cite{menzies09}, \cite{orrego09}, \cite{green09}) are exploring others.  In the following, all references to STAR describe the code developed for this thesis and all references to SEESAW describe an alternate system developed by  Menzies and Williams~\cite{menzies09} that follows the design principles described in this thesis.

\input{tables/models}
\section{Models}\label{sec:models}
In this section we will present the USC software engineering models that were used in this work and which influenced the fitness function used.
\subsection{Effort - COCOMO II}\label{sub:effort}
The COCOMO II model~\cite{boehm00b} is and evolution of the original COCOMO 81 model~\cite{boehm81} which was published by Barry Boehm. Both of these models have the same form referred to in \eq{cogen}, where \textit{$c_{i}$} is the sum of the cost drivers and \textit{A} is domain specific. 

{\begin{equation}\label{eq:cogen}
Effort = A*(c_{i})(Size)^{Exponent}
\end{equation}}

The difference is in what \textit{Size} and \textit{Exponent} represent. In COCOMO 81, \textit{Size} is dependent on deliverable source lines of code (DSI), while for COCOMO II it represents source lines of code (SLOC), function points (FP) and object points. In addition, the \textit{Exponent} in COCOMO 81 is actually a fixed constant that is selected as a function of development mode, which only exists in COCOMO 81, while in COCOMO II it is dependent on scale factors, which were introduced in COCOMO II. This is evident in \eq{coc2}. Other differences, as well as a guide to converting from COCOMO 81 to COCOMO II, are further elaborated on by D.J. Reifer and B. Boehm~\cite{reifer99}. For this thesis, we will be exclusively using COCOMO II.

\input{tables/cocomoii}

The COCOMO effort predictor estimates  development effort in terms of person months where one month is 152
hours (and includes development and management hours). 
In COCOMO, the  {\em scale factors} $SF_i$ of \ref{fig:cparems}
effect effort exponentially (on KSLOC, i.e. Thousand Source Lines of Code)
while {\em effort multipliers} $EM_j$
effect effort linearly:

{\small\begin{equation}\label{eq:coc2}
PM=a*\left(KSLOC^{\left(b+0.01*\sum_{i=1}^{5}SF_i\right)}\right)*\left(\prod_{j=1}^{17}EM_j\right)
\end{equation}}
where KSLOC is estimated
directly or computed from a function point analysis;
 $SF_i$ and $EM_j$ are the {\em scale factors}; and
{\em effort multipliers} respectively of \fig{cparems};
and
$a$ and $b$ are  domain-specific parameters. In our NASA data,
the following ranges were seen for \textit{a} and \textit{b}\begin{equation}\label{eq:ab}
\left( 3.72 \le a \le 9.18 \right) \wedge \left(0.88 \le b \le 1.09\right) 
\end{equation} 
With the effort multipliers, off-nominal ranges (i.e. \{vl=1, l=2, h=4, vh=5, xh=6\}) change the prediction by some amount.
In the special case of the nominal range (i.e. \{n=3\}), the factor it translates to is one; i.e. the nominal
range make no change to the prediction.
Hence, these  ranges  can be modeled as a straight line $y=mx+b$
passing through the point $\{x,y\}$=$\{3,1\}$. Such a line has a y-intercept
of $b=1 - 3m$. Substituting this value of $b$ into $y=mx+b$ yields:
{\small
\begin{equation}\label{eq:lineem}
\begin{array}{l}
\forall x \in \{1..6\}\; EM_i=m_a(x-3) + 1
\end{array}
\end{equation}}
where  $m_a$ denotes the effect of effort multiplier $a$ on {\em effort}.

The effort multipliers form
into two sets:
\begin{enumerate}
\item
The {\em positive effort EM} features, with slopes $m^+_a$, that are proportional to effort. 
These features are:
cplx,
data,
docu,
pvol,
rely,
ruse,
stor, and
time.
\item
The
{\em negative effort EM} features, with slopes $m^-_{a}$,
are inversely proportional to effort.
These features are 
acap,
apex,
ltex,
pcap,
pcon,
plex,
sced ,
site,
tool.
\end{enumerate}
Based on prior work~\cite{boehm00a}, we can describe
the
space of known tunings for COCOMO effort multipliers to be 
{\small\begin{equation}\label{eq:mem}
\left(0.073 \le m^+_a \le 0.21\right) \wedge
\left(-0.178 \le m^-_a \le -0.078\right)
\end{equation}}
Similarly, using experience from 161 projects~\cite{boehm00a},
we can say that the space of known tunings for the COCOMO scale factors 
(prec, flex, resl,team, pmat)
are:
{\small\begin{equation}\label{eq:linesf}
 \forall x \in \{1..6\}\; SF_i=m_b(x - 6) \wedge \left(
-1.56	\le m_b \le -1.014\right)
\end{equation}}
where  $m_b$ denotes the effect of scale factor $b$ on {\em effort}.

Note that the above ranges for the slopes were obtained by finding the average slope for each COCOMO attribute for both effort multipliers and scale factors over the range of values of that attribute.

\subsection{Schedule}\label{sub:schedule}
The COCOMO schedule predictor estimates  development time in terms of elapsed calendar months.
This model is largely based on the COCOMO effort in that it uses
those attributes, there values, and the calibrated coefficients (i.e, $a$ and $b$).
The following are the equations for calculating months:

{\small\begin{equation}\label{eq:mon}
\begin{array}{c}
F=d+0.2*\left(0.01*(\sum_{i=1}^{5}SF_i)\right)\\
TDEV=\left[c*(PM_{NS})^{F}\right]*SCED\%\div100
\end{array}
\end{equation}}
where $PM_{NS}$ is the effort calculated without the inclusion of SCED, 
$SF_i$ are the {\em scale factors} of \ref{fig:cparems},
$c$ and $d$ are  domain-specific parameters that can be calibrated,
and $SCED\%$ is the percentage of schedule relative to the nominal 
schedule. 

\ref{fig:sced} shows the value of this parameter based on 
SCED. $TDEV$ is the development time in months calculated by this model,
and $F$ is referred to as the scaling exponent for schedule.

\input{tables/sced}

\subsection{Defects - COQUALMO}\label{sub:defects}
The COQUALMO model is used to estimate the amount if defects within a software project.
COQUALMO has two core models, used three ways:
\begin{itemize}
\item
 The {\em defect introduction} model is similar to
\ref{eq:coc2}; i.e. settings to \ref{fig:cparems}'s effort multipliers and scale factors
map to predictions about number of defects.
\item
The {\em defect removal} model represents how various tasks (peer review, execution-based
testing, and automated analysis) decrease the introduction of defects.
\item
The above two models are repeated three times 
for
defects introduction \&  removal for
requirements, design, or coding.
\end{itemize}

\input{tables/coqualmoemin}

\input{tables/coqualmosfin}

\input{figures/misc/din}

\input{figures/misc/drf}

\input{figures/misc/addremove}

COQUALMO follows the same convention as COCOMO for the effort multipliers; i.e.
nominal values ($n=3$) add nothing to the predicted number of defects. As the
above, COQUALMO is:
{\small\begin{equation}\label{eq:linedefintro}
\begin{array}{l}
 \forall x \in \{1..6\}\; EM_i=m_c(x-3) + 1
\end{array}
\end{equation}}
where  $m_c$ denotes the effect of $c$ on {\em defect introduction}.

The effort multipliers and  scale factors form two sets:
\begin{enumerate}
\item The {\em positive defect} features, with slopes $m^+_c$, that are proportional
to the estimated introduced defects. These features are 
flex, data, ruse, cplx, time, stor, and pvol.
\item The {\em negative defect} features, with slopes $m^-_c$, that are inversely proportional
to the estimated introduced defects. These features are 
acap, pcap, pcon, apex, plex, ltex, tool, site, sced, prec, resl, team, pmat, rely, and docu.
\end{enumerate}
\clearpage
\input{figures/misc/rdefects}
The space of tunings for  defect introducing features are:
{\small\begin{equation}\label{eq:coq}
\begin{array}{c}
requirements\left\{
\begin{array}{c}
0 \le m^+_c \le 0.112\\
-0.183 \le m^-_c \le -0.035
\end{array}
\right. \\
~\\
design \left\{
\begin{array}{c}
0 \le m^+_c \le 0.14\\
-0.208 \le m^-_c \le -0.048
\end{array}
\right. \\
~\\
coding \left\{
\begin{array}{c}
0 \le m^+_c \le  0.140\\
-0.19 \le m^-_c \le -0.053
\end{array}
\right.
\end{array}
\end{equation}}

\noindent
The space of tunings for  defect removal features are:
{\small\begin{equation}\label{eq:linedefrem}
\begin{array}{rl}
\forall x \in \{1..6\} &SF_i=m_d(x - 1)\\
requirements: 	& 0.08 	\le m_d \le 0.14 \\
design: 		& 0.1 	\le m_d \le 0.156 \\
coding: 		& 0.11 	\le m_d \le 0.176 \\
\end{array}
\end{equation}}
where  $m_d$ denotes the effect of  $d$ on {\em defect removal}.

\subsection{Threat}\label{sub:threat}

The THREAT model
returns a heuristic estimate of the threat of a
schedule over run in the project. 
This estimation model is dependent upon
the COCOMO effort multipliers

Internally, THREAT contains dozens of tables of the
form of \ref{fig:madeg}. Each such table  adds some ``threat'' value
to the overall project risk when multiplied by
the effort multiplier values of the corresponding COCOMO attributes.
 There are six major categories: schedule, product, personnel, process, platform and reuse.
After the threat for each category is calculated, the sum is
normalized to produce the final threat rating.

\input{tables/madeg}

\ref{fig:madeg} can be represented as
an exponentially decaying function that peaks in one corner of the risk table
at a value of two.
All the tables peak at either a value of two  or four.
Since this model is heuristic in nature, the exact height of the peak is
not certain.
When we perform Monte Carlo simulations over THREAT, we vary the height of
the peak by 
a random factor $0.5 \le x \le 1$ if the peak is four, and $0.5 \le x \le 1.5$ if the peak is two.

\input{figures/misc/threatcalc}

\input{figures/misc/madachy}

\input{figures/default}

\section{Local Calibration(LC)}\label{sec:lc}
This section describes local calibration (LC),
the standard regression procedure used by the COCOMO
community. LC is used in conjunction with local data to calibrate the COCOMO II model, as well as the other COCOMO based models.

LC assumes that a  matrix $D_{i,j}$ 
holds:
\bi
\item
The natural log of the
$LOC$ (lines of code) estimates;
\item
The natural log of  the actual efforts
for each project $j$;
\item
The  natural logarithm of the cost drivers (the scale factors
and effort multipliers) at locations $1\le i \le 15$ (for COCOMO 81)
or $1 \le i \le 22$ (for COCOMO-II).
\ei
With those assumptions, Boehm~\cite{boehm81} shows that
for COCOMO 81,
the following calculation yields estimates
for ``$a$'' and ``$b$'' that minimize the sum of the squares of residual
errors:
{\scriptsize\begin{equation}\label{eq:ab2}
\left.
\begin{array}{rcl}
EAF_i& =& \sum_j^N D_{i,j}\\
a_0  & =& t \\\
a_1  & =& \sum_i^t KLOC_i\\
a_2  & =& \sum_i^t (KLOC_i)^2\\
d_0  & =& \sum_i^t \left(actual_i - EAF_i\right)\\
d_1  & =& \sum_i^t \left((actual_i - EAF_i)*KLOC_i\right)\\
b  & =& (a_0d_1 - a_1d_0)/(a_0a_2 - a_1^2)\\
a_3    & =& (a_2d_0 - a_1d_1)/(a_0a_2 - a_1^2)\\
a    & =& e^{a_3}
\end{array}\right\}
\end{equation}}
In the case of COCOMO 81~\cite{boehm81} these $a,b$ values are used in the following equation to generate
effort estimates. In this equation, $EM_i$ are the effort multipliers from \fig{cparems}:
{\footnotesize\[ effort = a \cdot KSLOC ^ b \cdot \prod^{15}_i EM_i\]}
What is not widely appreciated is the size of
the
variance in the $(a,b)$ values.
The left-hand-side of
\fig{dan}  shows the COCOMO-I $(a,b)$ values learned by   Baker~\cite{baker07}
after, 300 times, extracting 10 projects at random from COCOMO data sets,
then applying \eq{ab} to the remaining data.  
The data sets used in this study contained 93 projects, so LC was applied
to  $\frac{93-10}{93}=89\%$ of the data.
A pre-experimental intuition was that we were using enough of the data to yield stable $(a,b)$ values. As can be clearly seen by the wide
variance on the $(a,b)$ values in \fig{dan},
this was not the case.

\input{figures/misc/dan}

The right-hand-side of
\fig{dan} shows the magnitude of the relative error (or $MRE$)
values 
seen in Baker's study (MRE is a standard measure in the effort estimation field
as follows:
$MRE=\frac{abs(actual - predicted)}{actual}$). 

Some of the MRE errors
are very large (up to nearly 500\%)
suggesting that LC was incomplete or that the variance in the $(a,b)$ calculations  have significant impact on the estimation. In fact, after
thirty 90\% random
samples of that NASA data, Baker found that the a, b ranges were
surprisingly large:
\begin{center}
  $(2.2 \leq a \leq 9.18) \wedge (0.88 \leq b \leq 1.09)$
\end{center}
Note that the right-hand-side \fig{dan}  is not without precedent in the estimation literature:
it is a well-established result that  initial development effort estimates may be incorrect
by a factor of four~\cite{boehm81} or even more~\cite{kemerer87}.

Elsewhere we have been partially successful in
reducing estimation variance
of \fig{dan}
using feature subset selection (FSS)~\cite{chen05,me06d}
or more data collection.
Unfortunately,
FSS reduces but does not eliminate the $a,b$ variance. Also, further
data collection is possible, but only at great organizational expense. This
is due to data not being collected or the business sensitivity associated with the data as well as differences in how
the metrics are defined, collected and archived.  

\section{Search Based Software Engineering}\label{tion:sbse}

The contribution of this thesis falls within the area of search based software engineering~\cite{clark03,harman01}. This is a diverse area of study, and also a young one, that has attempted to deal with many different phases of the software development life cycle. These vary from  software testing to requirements engineering, among others. This thesis, as the title suggests, deals with software process control. Search based software engineering (SBSE) is done by using a combination of a chosen search technique, combined with a fitness function that evaluates the results.

\subsection{Search Algorithms}\label{sub:searchalgo}
There are a variety of meta-heuristic search algorithms that are used in SBSE. Some of these are widely used and considered baseline algorithms, while others are custom made algorithms that rely on domain knowledge to optimize their performance. Crawford and Baker~\cite{crawford94} offer one explanation for the strange success of stochastic search.
For models, such as the ones used in this thesis, 
the solutions are a small part of the total space. A complete search
wastes much time exploring uninformative areas of the problem. A stochastic search, 
on the other hand, does not get stuck in such  uninformative areas.

\subsubsection{Genetic Algorithms}\label{subsub:ga}
Genetic algorithms (GA)~\cite{holland92} are AI search algorithms that attempt to immitate the population based evolutionary model of nature. The algorithm initially starts with a random population of solutions. These solutions, individually referred to as chromosomes, are iteratively seleted, mutated, and recombined based on how well they score with a predefined fitness function. This eventually increases the fitness of the population, after which the algorithm stops when reaching a certain performance milstone in a chromosome, or when it has gone through a certain number of generations. GA has been historically widely used in the field of SBSE, and is very much considered and standard SBSE algorithm.

\subsubsection{Reactive Tabu Search}\label{subsub:tabu}
Tabu search~\cite{glover93tabu} is a local search algorithm that allows the jump to sub-optimal non-improving solutions in order to avoid local optima. Tabu search uses a list, called the \textit{tabu list},  that keeps a record of the recent search history of the algorithm. This is done in order to avoid visiting the same solution repeatedly so that when a sub-optimal jump does occur, a new solution in the search space is being explored. Note that old solutions are not banned forever, but rather they are restricted for a while. This algorithm was developed in 1986 as a response to the development of SA, and like it is based on an analogy of a natural phenomenon.

\subsubsection{Simulated Annealing}\label{subsub:sa}
Simulated Annealing is the AI search algorithm that is used in this work. 
It belongs to the family of Monte Carlo algorithms.
{\em Monte Carlo} algorithms randomly sample the space
of possible controllable model states. 
A  {\em Metropolis} Monte Carlo algorithm~\cite{metropolis53}
creates new states
by  small mutations to some
{\em current} state. 
If a new state is ``better'' (as assessed via an
{\em energy function}),  it becomes the new {\em current}
state used  for future
mutations.  Otherwise, a Boltzmann acceptance
criteria is used to probabilistically   decide to
assess the new state: the worse the new state, the less
likely that it becomes the new current state.
The algorithm is silent on the mutation mechanism. For our experiments,
we freeze $\frac{2}{3}$ of the features and
randomly  select ranges for the rest.

In 1983, Kirkpatrick et al.~\cite{kirkpatrick83} 
proposed a modification that was
inspired
by a procedure used to make the strongest possible glass. Initially,
glass is heated to allow atoms to move freely. The temperature
is then slowly lowered such that the atoms can find the stablest
configuration with lowest energy. 
A {\em simulated annealing} (SA) algorithm adds
a ``temperature'' variable to the Boltzmann accept criteria
such that, at high temperatures, it is more likely that the
algorithm will jump to a  new worse current state.
This allows the algorithm to jump out of local minima while
sampling the space of options, a useful ability. As the temperature cools,
such jumps become less likely and the algorithm reverts
to a simple hill climber.



The acceptance criteria $P$ for a new state is defined using
the current temperature $T$, 
the energy of the current solution ($e$),
and the energy of the new mutation ($en$):

{\small\begin{equation}
P(e,en,T) = e^{(e -en)/T}
\end{equation}}

$T$ is defined to $decrease$ as the simulator loops through $k= 1\ldots kmax$ iterations.
We use
$T = e^{-100*k/kmax}$.

\input{figures/misc/sa}

\input{figures/misc/sajpl}

Two advantages of SA algorithms are their {\em implementation simplicity} and their {\em ability to handle
non-linear models}:
\begin{itemize}
\item {\em Implementation simplicity:}
\ref{fig:sa} illustrates the simplicity of the algorithm. Memory is only required
for one current solution ($s$), one new solution ($sn$) and one best solution ($sb$) that stores
the best solution seen at any time in the simulation.
\item
{\em Non-linear models:}
 Previously~\cite{fea02a,me03i}, SA was applied to non-linear JPL requirements models
where minimizing the cost of project mitigation can decrease the number of requirements
achieved by that project. Hence, decreasing {\em both} the cost and achieved requirements
is a non-linear problem that must trade between minimizing cost and increasing
requirements coverage.
The top-left line  of \fig{sajpl} divides the behavior of the JPL requirements models
before  and after  simulated annealing. 
As shown below the line, 
initial Monte Carlo sampling of the possible mitigation lead to a large range
of costs and benefits. Simulated annealing found a set of mitigation
that lead to the small cloud of solutions above the line. Compared to the initial samples, these
new solutions had decreased cost, increased benefit (number of requirements covered), and decreased variance (shrank
the space of solutions). 
\end{itemize}
Two disadvantages of SA algorithms are their {\em incompleteness} and the {\em
complexity}
of their solutions:
\begin{itemize}
\item 
{\em Incompleteness:} In our domain, we have some evidence that the incomplete nature of the heuristic SA
search is not a major problem.
\ref{fig:saeg} shows a sample run of our SA tool running on our prediction models
for $K=10,000$ simulations. 
As $k$ increases for $1{\ldots}10,000$, it becomes less and less
likely that a better $best$ has been missed. Hence, we run our simulations
for ten times the period it takes for $best$ to stabilize (at $k\approx 1000$). 

\input{figures/misc/saeg}

\item
{\em Solution complexity:}
Simulated annealing offers constraints to all controllable features. 
Often this
is an over-constrained solution since, 
in many domains, a repeated empirical result is a {\em feature subset selection}
effect; i.e. models that constrain M variables perform just as well, or better,
than models that constrain N variables ($M\ll N$)~\cite{kohavi97,hall03}.
For example, Kohavi~\cite{kohavi97}
studied some machine learners to find  that using just 19\% of the available features
{\em increased} prediction accuracy by just 2.14\% (on average).
For another example,
when feature subset selection was applied to the JPL requirements model of \fig{sajpl}, we found that
up to $\frac{2}{3}$-rds of the features can be left unconstrained,
without effecting the conclusions~\cite{fea02a}. 
\end{itemize}

\input{figures/misc/fssr}

\subsubsection{Other Algorithms}\label{subsub:otheralgo}
Harman ~\cite{harman05} discusses several standard search algorithms that are used in the field of SBSE, such as simulated annealing and genetic algorithms. However, SBSE need not be restricted to only these standard algorithms, as there are other custom made AI search algorithms that attempt to perform the same functions as these standard algorithms. We will present two such algorithms here. 
%\paragraph{MaxFunWalk}
%%The design of simulated annealing dates back to the 1950s. In
%%order to benchmark our new search engine (KEYS) against a more recent state-of-the-art
%%algorithm, we implemented the variant of 
%%MaxWalkSat described below.
%
%WalkSat is a local search method designed to address the problem
%of boolean satisfiability~\cite{kautz96}. MaxWalkSat is
%a variant of WalkSat that applies weights to each clause in a
%conjunctive normal form equation~\cite{selman96}. 
%While WalkSat tries to satisfy the entire set of clauses, MaxWalkSat
%tries to maximize the sum of the weights of the satisfied
%clauses. 
%
%In one respect, both algorithms can be viewed
%as a variant of simulated annealing. Whereas simulated annealing always selects
%the next solution randomly, the WalkSat algorithms will {\em sometimes}
%perform random selection while, other times, conduct a local search to find the
%next best setting to one variable.
% 
%MaxWalkSat was adapted to the to the DDP problem~\cite{gay08} as follows.
%The MaxFunWalk algorithm is a variant of MaxWalkSat:
%\bi
%\item
%Like MaxWalkSat, MaxFunWalk makes decisions about settings to variables.
%\item
%Unlike MaxWalkSat, MaxFunWalk  scores those decisions by passing those
%settings to some function. 
%
%
%%In the case of DDP optimization, that function
%%is the scoring function of \eq{score}. 
%\ei
%
%\begin{figure}
%~\hrule~
%{\scriptsize
%\begin{verbatim}
%Procedure MaxFunWalk                
%for TRIES:=1 to MAX-TRIES              
%   SELECTION:=A randomly generate assignment of mitigations         
%   for CHANGED:=1 to MAX-CHANGES           
%       if SCORE satisfies THRESHOLD return      
%       CHOSEN:= a random selection of mitigations from SELECTION   
%       with probability P        
%           flip a random setting in CHOSEN 
%       with probability (P-1)        
%          flip a setting in CHOSEN that maximizes SCORE
%   end for             
%end for                
%return BESTSCORE
%\end{verbatim}
%}
%~\hrule~
%\caption{Pseudocode for MaxFunWalk}
%\label{fig:MWF}
%\end{figure}
%
%%
%The MaxFunWalk procedure is shown in \fig{MWF}. When run, the user supplies an ideal cost and attainment. This setting is normalized, scored, and set as a goal threshold. If the current setting of mitigations satisfies that threshold, the algorithm terminates. 
%
%MaxFunWalk begins by randomly setting every mitigation. From there, it will attempt to make a {\em single} change until the threshold is met or the allowed number of changes runs out (100 by default). 
%A random subset of mitigations is chosen and a random number P between 0 and 1 is generated. The value of P  will decide the form that the change takes:
%\bi
%\item P$\le\alpha$: A stochastic decision is made. A setting is changed completely at random within subset C.
%\item P$>\alpha$: Local search is utilized. Each mitigation in C is tested until one is found that improves the current score.
%\ei
%%
%%The best setting of $\alpha$ is a domain-specific engineering decision. For this study,
%%we used $\alpha=0.3$.
%%
%If the threshold is not met by the time that the allowed number of changes is exhausted, the set of mitigations is completely reset and the algorithm starts over. This measure allows the algorithm to avoid becoming trapped in local maxima. 
%%For the DDP models, we found that the number of retries has little effect on solution quality.
%%
%If the threshold is never met, MaxFunWalk will reset and continue to make changes until the maximum number of allowed resets is exhausted. At that point, it will return the best settings found. 
%%
%%As an additional measure to improve the results found by MaxFunWalk, a heuristic was implemented to limit the number of mitigations that could be set at one time. If too many are set, the algorithm will turn off a few in an effort to bring the cost factor down while minimizing the effect on the attainment. 
%
%\paragraph{A* (ASTAR)}
%
% A* is a best-first path finding algorithm that uses distance from origin ($G$)
%and estimated cost to goal ($H$)
%to find the best path~\cite{hart68}. The algorithm has been proven to be optimal for a given scoring heuristic ~\cite{dechter85}, and has seen widespread use in multiple fields ~\cite{pearl84,norvig03,stout97,hui04}. 
%
%%A* is a natural choice for DDP optimization since the scoring
%%function described above
%%is actually a Euclidean distance measure
%%to the desired goal 
%%of maximum attainment and minimum costs.  
%%Hence, for H,  we can make direct use of \eq{score}.
%
%
%\begin{figure}
%{\scriptsize
%~\hrule~
%\begin{center}
%\begin{verbatim}												
%CURRENT_POSITION:= Starting assignment of mitigations          
%CLOSED[0]:= Add starting position to closed list        
%              
%while END:= FALSE            
%   NEIGHBOR_LIST:=list of neighbors         
%   for each NEIGHBOR in NEIGHBOR_LIST       
%       if NEIGHBOR is not in CLOSED  
%          G:=distance from start 
%          H:=distance to goal  
%          F:=G+H    
%          if F<BEST_F   
%              BEST_NEIGHBOR:=NEIGHBOR
%  end for           
%  CURRENT_POSITION:= BEST_NEIGHBOR           
%  CLOSED[++]:=Add new state to closed list       
%  if STUCK           
%      END:= TRUE       
%end "while "             
%return CURRENT_POSITION       
%\end{verbatim}
%\end{center}
%~\hrule~}
%\caption{Pseudocode for ASTAR}
%\label{fig:ASTAR}
%\end{figure}
%
%%Our implementation of A*, called ASTAR, allows for two possible starting configurations. Like all of the other algorithms used for this experiment, ASTAR can randomly make assignments to each mitigation. This was the setting used for most of our experiments. However, A* is a deterministic algorithm. Given a {\em fixed} starting position and an {\em unchanging} search space, it should always come up with the same final answer. To test this, our ASTAR technique can be set to start from a fixed state where cost and attainment are both equal to 0. 
%
%The ASTAR algorithm keeps a {\em closed} list in order to prevent backtracking. We begin by adding the starting state to the closed list. In each ``round'', a list of neighbors is populated from the series of possible states reached by making a change to a single mitigation. 
%If that neighbor is not on the closed list, two calculations are made: 
%\bi
%\item G = Distance from the start to the current state plus the additional distance between the current state and that neighbor.
%\item H = Distance from that neighbor to the goal (an ideal spot, usually 0 cost and a high attainment determined by the model). 
%For DDP models, we use \eq{score} to compute H.
%\ei
%The {\em best} neighbor is the one with the lowest F=G+H. The algorithm ``travels'' to that neighbor and adds it to the closed list. 
%Part of the optimality of the A* algorithm is that the distance to the goal is underestimated. 
%Thus, the final goal is never actually reached by ASTAR. 
%Our implementation terminates once it stops
%finding better solutions
%for a total of ten rounds. This number was chosen to give ample time for ASTAR to become ``unstuck'' if it hits a corner early on.  


\paragraph{KEYS}
%A*, MaxWalkSat, and simulated annealing are standard search engines. 
Keys is a custom AI serach engine that was developed and compared to other standard algorithms in \cite{gay08}.

The premise of KEYS is that within the space of possible
decisions, there exist a small number of $key$ decisions that
determine all others~\cite{me07d}. 
%As discussed in the related work section, there is much
%evidence that keys can be found in many domains.

If a model contains keys,  then a general search through a large space of
options is superfluous. 
A better (faster, simpler) approach
would be to just explore the keys.
KEYS uses support-based Bayesian sampling to quickly find these important variables. 

%\subparagraph{What are ``keys''?}
%Before explaining the KEYS algorithm,
%we must first explore the general concept of
%``keys''.
%
%Within a model, there are chains of {\em reasons} that link inputs to the desired goals.
%As one might imagine, some of the links in the chain clash with others. 
%Some of those clashes are most upstream; they are not dependent on other clashes. 
%In the following chains of reasoning 
%the clashes are $\{e, \neg e\}$, 
%$\{g, \neg g\}$ 
%\& $\{j,\neg j\}$;
%the most upstream clashes 
%are
%$\{e \neg e\}$, 
%\& $\{g \neg g\}$, 
%\[\begin{array}{r@{}l@{}l}
%&a \longrightarrow b \longrightarrow c \longrightarrow d \longrightarrow e\\
%input_1 \longrightarrow  &f \longrightarrow g \longrightarrow h \longrightarrow i \longrightarrow j & \longrightarrow goal\\
%input_2 \longrightarrow  &k \rightarrow \neg g \longrightarrow l \longrightarrow m \rightarrow \neg j & \longrightarrow goal\\
%&n \longrightarrow o \longrightarrow p \longrightarrow q \longrightarrow
%\neg e
%\end{array}
%\]
%In order to optimize decision making about this model, we must first decide about these {\em upstream clashing reasons}.
%We refer to these decisions as {\em the collars} as they have the most impact on the rest of the model.
%
%Returning to the above reasoning chains,
%any of $\{a, b, ..q\}$ are subject to discussion.
%However, most of this model is completely irrelevant to the task of
%$input_i\vdash~goal$. For example, 
%the $\{e, \neg e\}$ clash is
%unimportant to the decision making process
%as no reason uses $e$ or $\neg e$. 
%In the context of reaching $goal$ from 
%$input_i$, the only important discussions are
%the clashes $\{g,\neg g,j,\neg j\}$.
%Further, since $\{j, \neg
%j\}$ are dependent on $\{g,\neg g\}$, then the core decision
%must be about variable $g$ with two disputed values: true and
%false. 
%
%We call 
%$g$ 
%the {\em collar} since it restricts the entire model.
%The collar may be internal to a model and may not be directly controllable. 
%We refer to the controllable variables that can influence the collar as the   $keys$
%In the previous example, those keys are $input_i$.
%
%Using the keys to set the $collars$ reduces the number of reachable states within the model. 
%Formally, the reachable states reduce to
%the cross-product of all of the ranges of the collars.
%We call this the $clumping$ effect. Only a small fraction of the possible states are actually reachable.
%The effects of clumping can be quite dramatic.
%Without knowledge of these chains and the collar, the above model has $2^{20} > 1,000,000$ possible consistent states.
%However, in the context of 
%$input_i\vdash~goal$,
%those 1,000,000 states clumps to just the following two states: 
%$\{input_1,f,g,h,i,j,goal\}$ or
%$\{input_2,k,\neg g,l,m,\neg j,goal\}$.
%
%\subparagraph{The KEYS Algorithm}

There are two main components to KEYS - a greedy search and the BORE ranking heuristic. This is in some ways similar to part of the STAR Algorithm general structure, which is further explained in \tion{staralgo}.

The greedy
search explores a space of $M$ 
mitigation over the course of 
$M$ ``eras''. 
Initially, the entire set of mitigations is set randomly. 
During each era, one more
mitigation is set to $M_i=X_j$, $X_j \in \{true,false\}$. 
%In the original version of KEYS~\cite{promise08}, the greedy search fixes one variable per era.
%This paper experimented with a newer version, called KEY2, that fixes an increasing number of variables as the search progresses
%(see below for details).

In Keys, each era $e$ generates
a set $<input,score>$ as follows:
\be
\item[1:]
$MaxTries$ times repeat:
\bi
\item
$Selected[1{\ldots}(e-1)]$ are settings from previous eras.
\item
	$Guessed$ are randomly selected values for an unfixed mitigation.  
\item
	$Input = selected \cup guessed$.
\item
%Call {\tt model} to compute $score=ddp(input)$;
Call the fitness function to compute the $score$.
\ei
\item[2:] The $MaxTries$ $score$s are divided into $\beta$\% ``best'' while
the remainder are sent to  ``rest''. 
\item[3:]
The mitigation values in the $input$ sets are then scored using BORE
(described below).
\item[4:]
The top ranked mitigation (the default is one, but the user may fix multiple mitigation at once) are fixed and stored in $selected[e]$.\ee
The search moves to era $e+1$ and repeats steps 1,2,3,4.
This process stops 
when every mitigation has a setting.  
%The exact settings for $MaxTries$ and $\beta$ must be set via engineering judgment.
%After some experimentation, we used $MaxTries=100$ and $\beta=10$.
For full details, see \fig{KEYS}. 
\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
Procedure KEYS            
while FIXED_MITIGATIONS != TOTAL_MITIGATIONS          
   for I:=1 to 100       
      SELECTED[1...(I-1)] = best decisions up to this step
      GUESSED = random settings to the remaining mitigations
      INPUT = SELECTED + GUESSED   
      SCORES= SCORE(INPUT)      
   end for         
   for J:=1 to NUM_MITIGATIONS_TO_SET       
     TOP_MITIGATION = BORE(SCORES)      
     SELECTED[FIXED_MITIGATIONS++] = TOP_MITIGATION      
  end for          
end while		          
return SELECTED \end{verbatim} }
~\hrule~
\caption{Pseudo-code for KEYS}
\label{fig:KEYS}
\end{figure}

KEYS ranks mitigation by combining a novel support-based
Bayesian ranking measure, which is detailed in~\tion{bayrank}.

%BORE ~\cite{clark05} (short for ``best or rest'')
%divides numeric scores seen over $K$ runs and stores the top 10\%  in $best$ and the remaining 90\% scores in the set $rest$
%(the $best$ set is computed by studying the delta
%of each score 
%to the best score seen in any era).
%It then computes the probability that a value is found in $best$
%using
%Bayes theorem.
%The theorem uses
%evidence $E$ and a prior probability $P(H)$ for
%hypothesis $H\in\{best, rest\}$,
%to calculate a  posteriori  probability
%$P(H|E)=P(E|H) P(H)\; /\; P(E)$.
%When applying the theorem, {\em likelihoods}
%are computed from observed
%frequencies. These likelihoods (called "like" below) are then normalized to create
%probabilities. This normalization cancels out $P(E)$ in Bayes theorem.
%footnote{
%Such simple  Bayes classifiers are often called ``n\aive'' since they assume
%independence of each variable. 
%Domingos and Pazzini have shown
%that the independence assumption is a problem in a vanishingly small percent
%of cases~\cite{domingos97optimality}. This explains the repeated
%empirical result that seemingly n{\aive} Bayes classifiers perform as well
%as other more sophisticated schemes; e.g. see Table~1 in~\cite{domingos97optimality}.}.
%
%
%For example, after $K=10,000$ runs are divided into  1,000 {\em best} solutions and 9,000
%{\em rest}, the  value \mbox{$mitigation31=false$} might appear 10 times in the $best$ solutions, but only
%5 times in the $rest$. Hence:\newline
%\begin{minipage}{1.0\linewidth}
%{\scriptsize
%\begin{eqnarray}\nonumber
%E&=& (mitigation31=false)\\\nonumber
%P(best)&=&1000/10000 = 0.1\\\nonumber
%P(rest)&=&9000/10000 = 0.9\\\nonumber
%freq(E|best)&=&10/1000 = 0.01\\\nonumber
%freq(E|rest)&=&5/9000 = 0.00056\\\nonumber
%like(best|E)&=&freq(E|best) \cdot P(best)=0.001\\\nonumber
%like(rest|E)&=&freq(E|rest) \cdot P(rest)= 0.000504\\\label{eq:ten}
%P(best|E)&=& \frac{like(best|E)}{like(best|E) + like(rest|E)}=0.66
%\end{eqnarray}}
%\end{minipage}\newline
%Previously~\cite{clark05},
%we have found that  Bayes theorem
%is a poor ranking heuristic
%since it is easily distracted by low frequency evidence.
%For example, note how
%the probability of $E$ belonging to the best class
%is moderately high even though its support is very low; i.e. $P(best|E)=0.66$ but
%$freq(E|best) = 0.01$. 
%
%To avoid the problem of unreliable low frequency evidence, we augment \eq{ten}
%with a support term.
%Support should $increase$ as the frequency of a value $increases$,  i.e. 
%$like(best|E)$ is a valid support measure.
% Hence, step 3 of our greedy search ranks values  via
%\begin{equation}\label{eq:ps3}\small
%P(best|E) * support(best|E) = \frac{like(best|E)^2}{like(best|E) + like(rest|E)}
%\end{equation}
%
%\subparagraph{KEYS2}
%
%For each era, KEYS samples the DDP models and fixes the top $N=1$ 
%settings.
%The following observation suggested that  $N=1$  is, perhaps, an  overly  conservative search policy.
%
%At least for the DDP models, we have observed that the improvement in costs and attainments generally increase
%for each era of KEYS.
%This lead to the speculation that we could jump further and faster into the solution space by 
%fixing $N\ge 1$ settings  per era.
%Such a {\em jump} policy 
%can be implemented as a
%small change to KEYS:
%\bi
%\item
%Standard KEYS
%assigns the value of one to  {\tt NUM\_MITIGATIONS\_TO\_SET} (see the pseudo-code of \fig{KEYS});
%\item
%Other variants of KEYS assigns larger values.
%\ei
%We experimented with several variants before settling on the following:
%in
%this variant, era $i$ sets $i$ settings. We call this variant ``KEYS2''.
%Note that, in era 1, KEYS2 behaves exactly the same as KEYS
%while
%in (say) era 3, KEYS2 will
%fix the top 3 ranked ranges. 
%Since it sets more variables at each era,
%KEYS2 terminates earlier than KEYS.

\paragraph{SEESAW}
SEESAW is a novel stochastic stability tool that
(a)~considers a very large set of minor changes using stochastic sampling; and
(b)~carefully selects the right combination of effective minor changes.
\fig{MWF} shows SEESAW's pseudo-code. The code is an adaption 
of Kautz \& Selman's MaxWalkSat local search procedure~\cite{kautz97}. 
The main changes are that  
each solution  is scored via a Monte Carlo  procedure (see {\tt score} in \fig{MWF}) and that
SEESAW seeks to {\em minimize} that score.


%SEESAW
%first combines the ranges for 
%all the COCOMO features
%with the known project constraints of \fig{cases}.
%These constraints 
%range from $Low$ to $High$ values.
%If a case study does not mention a feature, then there
%are no constraints on that feature, and the $combine$ function (line 4)
%returns the entire range of that feature. Otherwise, $combine$
%returns only the values from $Low$ to $High$.
%
%In the case where a feature is $fixed$ to a single
%value, 
%then $Low = High$. Since there is no choice to be made for this
%feature, SEESAW ignores it. The algorithm
% explores only those
% features with a range of $Options$ where
% $Low < High$ (line 5).
%In each iteration of the algorithm, it is possible that one acceptable value
%for a feature $X$ will be discovered. If so, the range for $X$
%is reduced to that single
%value, and the feature is not examined again (line 17).
%
%SEESAW prunes the final  recommendations (line 21).
%This function pop off the $N$
%selections added last that do not significantly change the final score (t-tests, 95\% confidence). This culls
%any final irrelevancies in the selections.
%
%The $score$ function shown at the bottom of
%\fig{MWF} calls COCOMO/COQUALMO models 100 times,
%each time selecting
%random values for each feature $Options$. The median value
%of these 100 simulations is the $score$ for the current project settings. As SEESAW executes,
%the ranges in $Options$ are removed and replaced by single values (lines 16-17),
%thus constraining the space of possible simulations.

SEESAW was designed based on observing the properties of USC software engineering models~\tion{models}. Based on that domain knowledge,
the most interesting ranges in the features was found to be the minimum and maximum values. This observation was due to results produced by STAR (explained in ~\tion{staralgo}) in such papers as~\cite{me07f}.  The reason for this is simple:
All the functions in the above indicated models are  monotonic, causing
the most dramatic effects to occur at the extreme ends of the ranges.
In fact,
SEESAW takes its name from the way the algorithm seesaws between extreme values.
%We have conducted experiments with other approaches that allow
%intermediate values.
%On comparison with the simulated annealing method used
%in a prior publications~\cite{me07f}, it was found that
%seesawing between
%$\{Low,High\}$ values was adequate for our purposes.


%We use this stochastic approach
% since much research from the 1990s showed the benefit of such search methods.

%For example, we have implemented a deterministic version of SEESAW that
%replaces the random selection of {\em one} feature in line 7 with a search
%through {\em all} features for
%the best $\{Low,High\}$ value.  That algorithm ran much slower (runtimes were 12 times greater)
%with nearly identical results to those of the stochastic search.


\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
 1 function run (AllRanges, ProjectConstraints) {
 2   OutScore = -1
 3   P = 0.95
 4   Out = combine(AllRanges, ProjectConstraints)
 5   Options = all Out features with ranges low < high
 6   while Options {
 7     X = any member of Options, picked at random
 8     {Low, High} = low, high ranges of X
 9     LowScore = score(X, Low)
10     HighScore = score(X, High)
11     if LowScore < HighScore
12       then Maybe = Low;  MaybeScore = LowScore
13       else Maybe = High; MaybeScore = HighScore
14     fi
15     if MaybeScore < OutScore or P < rand()
16       then delete all ranges of X except Maybe from Out
17       delete X from Options
18       OutScore = MaybeScore
19     fi
20   }
21  return backSelect(Out)
22 }
23 function score(X, Value) {
24   Temp = copy(Out)  ;; don't mess up the Out global 
25   from Temp, remove all ranges of X except Value 
26   run monte carlo on Temp for 100 simulations
27   return median score from monte carlo simulations
28 }
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for SEESAW.}
\label{fig:MWF}
\end{figure}

SEESAW is a stochastic algorithm:
the selection of the next feature to explore is completely random. SEESAW incrementally grows solutions
from unconstrained (where all features can take any value in $\{Low,High\}$)
to fully constrained (where all features are set to a single value).
This is unlike
simulated annealing or MaxWalkSat, which simultaneously offer settings to all features
at every step of their reasoning.
\fig{run} shows a single run of SEESAW: each dot marks one selection  (lines 16,17,18 of \fig{MWF}).
%In our terminology, selecting  one value from a range  is a {\em decision} on all  
%values in the range.
 For example, if \fig{cases} includes a process maturity of (3,4,5)
and SEESAW selects ``5'', then that is three decisions.
(this is why the 29 dots of
\fig{run} result in 100 decisions).
Note how, as decisions are made, the score is minimized. Score minimization is desirable since
the scores
are calculated 
from  a combination of project predictions that we want to reduce 
(total effort, defects, development time) based on the USC models. 
\begin{figure}
\centering
\includegraphics[width=3in]{misc/default.pdf}
\caption{Single run of SEESAW, score normalized min..max to 0..1}
\label{fig:run}
\end{figure}

%In order to support incremental decision making, SEESAW uses
%a very large $P$ value to control its reasoning.   This
%$P$ value is used to delay ``lose-lose'' decisions until the
%later iterations of the algorithm.  Suppose our search has only constrained (say)
%$pcap=5$ so far.  Our next randomly chosen feature might be  $data$,
%so SEESAW tries $\{Low, High\}$ values of $data=2$ and
%$data=5$.  It is possible that both of these values will result in scores
%that are worse than the current score (using $pcap=5$ alone).
%This means that
%$data$ is not a valuable feature to control,
%and picking either of the $\{Low,High\}$ values would be a ``lose-lose'' decision.
%Using $P=0.95$,
%SEESAW will very likely (95\% of the time) leave $data$ unconstrained
%and pick another, potentially better,  feature to constrain on the next iteration.  The algorithm
%will eventually come back to $data$, but if SEESAW delays making
%that lose-lose decision, it has a better chance of making good
%decisions early.

\paragraph{XOMO and TAR3}

XOMO ~\cite{me05e} is the work that preceded STAR. It was designed as a framework for Monte-Carlo simulations made to run on USC software related models \tion{models}. The search technique that is used by this framework is a data miner called TAR3 (and evolution of TAR2\cite{me03c}). TAR3 can be described as a treatment learner, returning concise rules or ``treatments" that have the largest effect on the output of the fitness function used. Having small rules is useful for software process control since this reduces the managerial interventions on a software project, while at the same time ensuring that such interventions will have high utility for the project. Note that XOMO is the first tool here that integrates multiple models, these being COCOMO, COQUALMO and the threat model. All previously mentioned tools operate on a single model, that being either COCOMO or another project specific model.

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.65]{misc/xomo.png}
\caption{A diagram offering an overview of where and how XOMO is meant to operate. This provided the inspiration to make STAR.}\label{fig:xomomod}
\end{center}
\end{figure}

TAR3 inputs a set of training examples $E$. Each example maps a set of attribute ranges  to some class symbol; i.e.  $\{R_i,R_j,... \rightarrow C\}$ The class symbols $C_1, C_2..$ are stamped with some utility score that ranks the classes; i.e. $\{U_1 < U_2 < .. < U_C\}$. With $E$, these classes occur at frequencies
$F_1\%,F_2\%, ..., F_C\%$.
A ``treatment'' 
$T$ of size $X$ is a conjunction of attribute ranges  $\{R_1 \wedge R_ 2 ... \wedge R_X\}$.
Some subset of $e \subseteq E$ are consistent with the treatment.
In that subset, the classes occur at  frequencies
$f_1\%,f_2\%, ... f_C\%$.
TAR3 seeks the
seek smallest $T$ which most changes the weighted sum of the utilities times frequencies
of the classes. Formally, this is called the $lift$ of a treatment:
\[lift=\frac{\sum_C U_Cf_C}{\sum_C U_CF_C}\]

\input{figures/misc/golfdata}

\input{figures/misc/golft}


For example, consider the log of golf
playing behavior seen in \ref{fig:golfdata}. In that log, we only play
{\em lots} of golf in $\frac{6}{5+3+6}= 43\%$ of cases. To improve
our game, we might search for conditions that increases our
golfing frequency. Two such conditions are shown in the {\tt
WHERE} test of the select statements  in \fig{golft}. In the case
of {\tt outlook= overcast}, we play {\em lots} of golf all the
time. In the case of {\tt humidity $\le$ 90}, we only play {\em
lots} of golf in 20\% of cases.  So one way to play lots of golf
would be to select a vacation location where it was always
overcast. While on holidays, one thing to watch for is the
humidity: if it rises over 90\%, then our frequent golf games are
threatened.


The tests in the {\tt WHERE} clause of the select statements in
\fig{golft} is a treatment. Classes in treatment learning
get a score $U_C$
and the learner uses this to assess the class
frequencies resulting from {\em applying a treatment} (i.e. using
them in a {\tt WHERE} clause). In normal operation, a treatment learner
does {\em
controller learning} that finds a treatment which selects for
better classes and reject worse classes  By reversing the scoring
function, treatment learning can also select for the worse classes
and reject the better classes. This mode is called {\em monitor
learning} since it finds the thing we should most watch for. In
the golf example, {\em outlook = 'overcast'} was the controller
and $humidity \ge 90$ was the monitor.

Formally, treatment learning is a weighted-class minimal
contrast-set association rule learner.  The treatments are associations that occur
with preferred classes. These treatments serve to contrast undesirable situations with
desirable situation where more of the outcomes are favorable. Treatment learning
is different to other contrast set learners like
STUCCO~\cite{bay99} since those other learners don't focus on minimal theories.

Conceptually, a treatment learner explores all possible subsets of the attribute
ranges looking for good treatments. Such a search is impractical
in practice so the art of treatment learning is quickly pruning unpromising attribute
ranges. This study uses the
TAR3 treatment learner~\cite{ying02} that uses  stochastic search
to find its treatments. 

Sometimes, one round of TAR3 is not enough.
{\em Iterative TAR3} runs by conducting multiple Monte Carlo
simulations over the ranges of any uncertain variables. For example,
there are 28 variables in XOMO, which uses the USC models:
\bi
\item
Ksloc;
\item
5 scale factors;
\item
17 effort multipliers;
\item
2 calibration parameters (``{\tt a,b}'');
\item
3 defect removal activities (automated analysis, peer reviews,
execution testing and  tools).  
\ei 
In the case studies that follow, only a partial description of some of these variables are available.
Hence, learning is a process of sampling from the known constraints, finding the best
treatment, then revising the constraints.
 After, say,
1000 Monte Carlo runs, 
BORE(\tion{bayrank}), short for ``best or rest'', classifies the outputs as (say) either the
333 $best$ or 667 $rest$.  The treatment learner studies the
results and notes which input ranges select for $best$.
The ranges found by the learner then become restraints for 
future
simulations. %The whole cycle looks like this:

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.55]{misc/xomocontrol.png}
\caption{The reductions that XOMO was able to produce in the model estimates.}\label{fig:xomocont}
\end{center}
\end{figure}

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.65]{misc/xomostability.png}
\caption{The occurance of attributes in the TAR3 recommendations over 10 runs of XOMO.}\label{fig:xomostab}
\end{center}
\end{figure}

Using XOMO and TAR3, we were able to able to produce stable conclusions within the space of options provided to us in a project, as well as achieve control over the estimates of the models. \fig{xomostab} demonstrates one instance of such stability, and shows that some attributes were chosen regularly for the specific project used. \fig{xomocont}, on the other hand, shows that at the same time XOMO was able to offer control over the estimates of a project, reducing the mean and the standard deviation of those estimates. Further discussing these results is outside the scope of this thesis.

\subsection{Applications of SBSE}\label{sub:appofsbse}
SBSE is being studied for use in tackling many software engineering issues, some of which will be mentioned here and briefly described. This section is presented in the form of a brief literature survey, and aims to present the reader with the diversity of the field of SBSE. 

\subsubsection{Project Planning and Cost Estimation}\label{subsub:projectplan}

In~\cite{aguilar01}, software project simulators, such as the likes of STELLA, VENSIM, ITHINK and POSERSIM, are used to generate a search space of possible decisions along with the outcome of using such decisions. This search space is passed to an evolutionary algorithm similar in concept to a genetic algorithm. By evaluating decisions using a fitness function based on how well the rule classifies project examples, this algorithm is able to generate a hierarchy of decision rules. They are able to demonstrate how applying these rules improves the management of the software project. Note that the model used for this system is project specific rather than an industry standard software engineering model.

In~\cite{antoniol04}, a scheme is developed for project management and allocating work loads to teams. The goal of this scheme is to determine the optimal flow of ``work packages" (WP) and at the same time determine the optimal team organization given a predetermined staff allocation. This being an NP-Hard task, the authors elect to use search based techniques, genetic algorithms (GA) specifically. Note that each of those issues has a dedicated GA for solving it, and that the fitness function is based on queuing theory~\cite{gross85}. Their system alternates back and forth between the two problems till equilibrium is achieved, after which the final output of development time is compared to a supplied deadline. If the deadline isn't met, rethinking staffing is recommended. In addition to this, simulation for different project scenarios (involving reworking and/or abandoning parts of the project) is also undertaken. The estimation model is not specified. An empirical study was conducted on a massive Y2K maintenance intervention conducted on a large financial software system from a European financial organization. Using this study they were able to demonstrate the ability of their scheme of being able to find an optimal or near-optimal solution, and hence reduce development time. A followup study was conducted~\cite{antoniol06} where hill climbing and simulated annealing were also used, and the results from all three algorithms were compared. GA was found to more efficient in finding the best solution; however, is was also found that the simpler methods (hill climbing, simulated annealing) also eventually caught up to GA given additional iterations.

In~\cite{kirsopp03}, case-based reasoning is used for predicting project effort. The method used for this, ``Angel", 
%is described as being close to k-nearest neighbor, and 
was used on the ``Finnish" data set. This data set is comprised of 407 cases, each described by 90 features. It should be noted that these features aren't COCOMO features, rather they are specific to that particular dataset. It should also be noted that the COCOMO model, and standard models in general, are criticized as being too specific to the data set that they are derived from. In this study, feature subset selection is used in order to determine the most significant features to use in predicting the effort. In order to do that, three search based methods were used: Random Search (RS), Hill Climbing (HC), and Forward Sequential Selection (FSS). While they all reduce the error rates compared to using all the features, HC and FSS produced the best results, with FSS edging out HC due to its quicker performance and more stable results.

\subsubsection{Software testing}\label{subsub:swtest}

In~\cite{baresel04}, the authors are using evolutionary testing that's based on genetic algorithms to generate test data for software projects. The main point of the paper is exploring a testability transformation~\cite{harman04(2)} algorithm that allows the evolutionary testing system used to handle code with loop-assigned flags. The system used was the Daimler Chrysler Evolutionary Testing System~\cite{wegener01} running on top of the Matlab Genetic and Evolutionary toolbox~\cite{pohlheim}. The empirical studies were conducted on several code bases, one of which was a the code for a car navigation system.

In~\cite{briand05}, a genetic algorithm based system is utilized in order to determine test cases where a given real-time system is apt to failure, effectively stress testing such systems. Failure here is defined as not being able to complete a time critical task within the time limits set for that task to be completed. The testing system prototype is called the Real-Time Test Tool (RTTT), and is based on using GAlib, a C++ genetic algorithm framework, and a POSIX compliant scheduler that emulates single processor execution. RTTT was used in a case study on a generic avionics platform that was a joint effort between the software engineering institute , the Naval weapons center and IBM's federal sector division. In this scenario and others, RTTT was found to be able to automatically generate test cases that were able to stress real-time systems. Note that a single GA execution run under this system took a mean time of 46.5 minutes.

In~\cite{li07}, regression testing and test case prioritization are the tasks being tackled. Test case prioritization is conducted due to the lack of enough resources to run all the regression test cases available for a project, and in order to improve the effectiveness of the regression tests being used. The main purpose of the paper is to compare several algorithms in there ability to generate prioritized test cases. The algorithms compared were greedy, additional-greedy, 2-optimal, hill climbing, and genetic algorithms. The first three are greedy algorithms that might settle for a local minimum solution. Three fitness functions were utilized and involved a percent measure of coverage of certain code aspects. After conducting empirical studies on code bases of varying sizes and with varying availability of test suites, it was found that plain greedy search performed the worst, while all the other algorithms performed very closely to each other.

\subsubsection{Automated maintenance}\label{subsub:automain}

The authors of~\cite{mitchell06} use a tool called ``Bunch'' in order to generate abstract high level representations of software. It does so by clustering module dependency graphs (MDG) using a search algorithm that is integrated within Bunch to examine a small subset of all possible clustering outcomes. The algorithm used within Bunch is hill climbing, with the option of using simulated annealing to avoid getting stuck in local optima. Note that the MDG's are produced by other language specific tools, making Bunch language independent. However, due to the nature of the algorithms used, the clustering results aren't always identical, and it isn't always clear why MDG's are clustered the way they are, sometimes requiring user intervention to clear things up a bit. Case studies are demonstrated on the dot graphing tool, the korn shell and a proprietary AT\&T file system, showing how it is possible using the tool to generate a high level abstraction of the software. This is ultimately meant to facilitate software maintenance on software engineers by giving them an overview of the software that is simpler to understand.

Automated refactoring of code is explored in~\cite{okeeffe06}. This refactoring is aimed at simplifying software maintenance by increasing flexibility, reusability and understandability according to the Object-Oriented Design Quality Assessment (QMOOD)~\cite{bansiya02}. A system called {\em CODe-Imp} was developed which uses the Java program model (JPM) to assess legal refactoring that is to be applied to the abstract syntax tree (AST) of java 1.4 based programs. Possible types of refactoring include moving fields and methods between the classes according to the hierarchy, and modifying the class hierarchy by inserting or removing intermediate classes. There were three search methods used by this system: First-Ascent Hill Climbing (HC1), Steepest-Ascent Hill climbing (HC2), and Simulated Annealing (SA). In empirical testing, it was found that all three search methods generated quality improvements, with slightly different results. HC1 was the least computationally intensive, HC2had the most consistent results between runs, and SA producing the greatest improvement in some cases. In addition, use of the reusability fitness function produced unsatisfactory results.

\subsubsection{Other Applications}\label{subsub:otherapp}
Several other applications of SBSE exist, amog those are the following:
\bi
\item
\textbf{Requirements Engineering: }The Multi-objective next release problem (MONRP) is tackled for the first time in~\cite{zhang07}. This is an extension from the next release problem~\cite{bagnall01}, where instead of having a single release requirement or several requirements that are considered independent, there are multiple requirements that might conflict with each other. This is an NP-hard problem with a set of possible solutions that are along a Pareto front. This front needs to be defined so that a decision maker is able to pick an acceptable approximate Pareto optimal solution. The search algorithms used in this study were Random Search, used as the baseline sanity check, and three other algorithms based on genetic algorithms (GA). These were Single-Objective GA, Pareto GA, and Non-dominated Sorting GA II (NSGA-II)~\cite{deb02}. In the empirical study, all the GA's performed better than Random Search, and within the smaller problem instances showed little difference between there results. However, in the larger problem instances that have more requirements, NSGA-II outperformed the others in being able to trace the Pareto front, and further widened the gap between it and Random Search, while Single-Objective GA was better able to find the extreme ranges of the Pareto front. So, it was demonstrated that solving MONRP is feasible. 
\item
\textbf{Compiler Optimization: }Cohen et al.~\cite{cohen06} attempts to improve garbage collection for multi-threaded applications by clustering threads and creating sub-heaps for each cluster of threads, while maintaining a shared heap among all the thread clusters. The premise is that this will aid in parallelizing garbage collection, while at the same time allowing this method to scale better than providing a heap for every individual thread for very highly threaded programs. The clustering system used is based on hill climbing, and uses thread dependency graphs to cluster the threads together. The empirical study was conducted on a peer-to-peer file sharing distributed application based on the .Net platform. By clustering the threads, the size of the shared heap was reduced by up to 30\%, thus contributing to  parallelizing garbage collection and increasing its efficiency.
\item
\textbf{Quality Assessment: }In~\cite{bouktif06(2)}, an approach is proposed to enhance predictive accuracy of software quality by reusing expertise from a several experts, and combining them to form an expert with the optimal predictive accuracy. This approach is modeled as an optimization problem in a large solution space, making it suitable for meta-heuristic search algorithms such as simulated annealing (SA) and genetic algorithms (GA). Both of those algorithms are used in the studies conducted in this paper, with empirical studies conducted on the JAVA API classes. Note that the specific aspect of software quality that is explored is object oriented software stability, where the quality metrics used to define this are dependent on the attributes of the software code base. The experts are modeled as Bayes Classifiers. Each expert is broken up into ``expertise chunks'' by limiting the input space. These chunks are then combined and modified to increase the final predictive accuracy. The search algorithm is responsible for choosing the chunks, where the fitness function used is the predictive accuracy. The resulting combined expert was shown to be better than any individual expert in terms of predictive accuracy. This showed that even bad experts have good expertise to contribute, where a correlation was shown between the accuracy and the amount of experts used to form the final expert. It was also shown through this study that SA performed comparably to GA, while being slightly quicker.
\ei



\section{Moving on}\label{sec:moveon}

The reader may wonder why we use a stochastic
methods to explore project options. Would not
a simpler method suffice? For example, in the case of linear
models that have been precisely tuned using local data, it is a
simple matter to check if a combination of internal changes improve the project estimates. Many of the relationships
inside the COCOMO model, as well as its sister models, are linear. For such models, ``what-
if'' queries require just a {\em simple linear extrapolation} to assess the relative effectiveness of some combination of internal changes. 

Unfortunately, not all tunings are precise. Sometimes,
even after tuning, the gradient of the relationships may not
be known with certainty. One example is the COCOMO effort model predictions being affected linearly and exponentially by two features a, b. We showed above in \tion{lc} the Baker result~\cite{baker07} that shows that even with tuning data, variance of the parameters, and the MRE of the resulting estimates, can be very large.


%Elsewhere we have been partially successful in reducing
%the range of \eq{coc2} with feature subset selection
%(FSS)~\cite{chen05,me06d} or more data collection. FSS reduces but does
%not eliminate the a, b variance. Also, further data collection
%is possible, but only at great organizational expense. This
%is due to data not being collected or the business sensitivity associated with the data as well as differences in how
%the metrics are deﬁned, collected and archived. 
%For example, after two years we were only able to add 7 records to
%a NASA-wide software cost metrics repository [?]. Having
%failed to generate precise tunings, we developed STAR
%to discover what stable conclusions we could ﬁnd within the
%space of possible tunings.

Another drawback with simplistic linear extrapolation is
that, when optimizing for effort and time and defects and threats, there
may be contradictory effects. For example, \fig{xomoouts} shown below shows several results, produced by XOMO in~\subsub{otheralgo}, where the change in effort doesn't transfer to the same amount of change in defects. Hence, optimizing our models is not a simple
matter of moving fixed distances over some linear effect;
there are also some trade-offs to be considered.

\begin{figure}
\begin{center}{\em
{\footnotesize
\begin{tabular}{c@{~}c@{~}cc@{~}c@{~}c@{~}c@{~}|c@{~}|c@{~}|c@{~}}
\multicolumn{7}{c}{26 inputs}&\multicolumn{3}{|c}{3 outputs}\\\hline
&& && & &  &&schedule&\\
rely&  plex& ksloc&\dots&pcap& time&aa&effort&risk&defects\\\hline

5&1&118.80&\dots&5&3&5&2083&69&0.50\\
5&1&105.51&\dots&1&3&5&4441&326&0.86\\
5&4&89.26&\dots&3&5&3&1242&63&0.96\\
5&2&89.66&\dots&1&4&5&2118&133&2.30\\
5&1&105.45&\dots&2&4&5&6362&170&2.66\\
5&3&118.43&\dots&2&6&2&7813&112&4.85\\
5&4&110.84&\dots&4&4&4&4449&112&6.81\\ 
\ldots
\end{tabular}}
}\end{center}
\caption[XOMO output from \cite{me05e}]{XOMO output from \cite{me05e}. Looking at the first and third lines of results, notice how even though changing project parameters manages to reduce the effort, defects almost doubles.}\label{fig:xomoouts}
\end{figure}

\fig{xomoouts} demonstrates how managing the estimates in one of the models does not necessarily translate to the estimates of all the other models. One instance that demonstrates this is comparing the last and the second row of \fig{xomoouts}, where plex is reduced from \textit{high}(4) to \textit{very low}(1). In this instance defects is vastly reduced, threat increases drastically, and effort maintains its levels. Stochastic, AI search, algorithms are able to solve for such non-linear problems and escape from local minima/maxima, while also finding solutions faster than complete search, and for larger problems~\cite{motwani95}.

Since we failed to generate precise tunings that yield exact estimates, and given the need to consider combinations of effects, we considered a change  in our research goals. In our attempt to find stable conclusions within the space of options provided to us, we created XOMO and were able to achieve that as presented briefly in \subsub{otheralgo}. However, XOMO proved to be too slow, taking as much as 30 minutes to rank features \cite{me07g}. In addition, it was very hard to maintain and customize the tool, and we were unable to explore the internal variance of the model tunings using XOMO. This drove us to attempt to embrace this variance within the models and use it to our advantage~\cite{me07g, me07f} by developing and using another faster, more maintainable and more customizable tool that uses an AI search algorithm to attempt to find stable conclusions. We called this tool STAR.
